paizaオンラインハッカソン(POH)・Liteで動的計画法を復習する

By | Date : 2016/01/12 ( Last Update : 2016/02/19 ) | 57 views

カテゴリ : C# プログラミング タグ: , , ,

ニアです。

私は1月30日にpaiza主催の「【ITエンジニアを目指す2017卒学生対象!!】 paizaでpizzaを食べながらもぐもぐ就活勉強会。」に参加します。

今回はそのイベントの事前課題「パイザオンラインハッカソン・Lite 」を解いて、動的計画法の復習をしました。

使用した言語はC#です。

 

 

1. 事前課題(POH Lite)の概要

標準入力からプロジェクトに必要な人員数と下請け会社の人員数・発注費用を読み込み、必要な人員数を満たす最も発注費用が安い組み合わせの時の合計金額を出力します。

 

2. 動的計画法の「ど」の字をまだ知らなかった当時の私が解いたプログラム

実はこの問題は2回チャレンジしています。最初にチャレンジした頃は動的計画法を知りませんでした。

下請け会社が最大50社ということで、64ビット整数型を利用して1から2のm乗までの整数をビットの列として表現します。各下請け会社の人員数と発注費用を格納する配列を作り、先ほどの64ビット整数の各ビットを調べて、1である位置をインデックスとして利用し、人員数と発注費用の合計金額を求めます。

POH-Lite3

また、内側のfor文の繰り返し条件に、

 

このプログラムを実行したところ、7つテストケースの内、テストケース5までが通りました。しかし、テストケース6でタイムオーバーしました。

テストケース1:success 0.03秒
テストケース2:success 0.03秒
テストケース3:success 0.03秒
テストケース4:success 0.04秒
テストケース5:success 0.05秒
テストケース6:invalid (タイムオーバー)
テストケース7:invalid (スキップ)

Score : 71 / 100  Rank : A

http://paiza.jp/poh/kirishima/result/c042e1d9

下請け会社が最大の50社の時、bmaxの値は2の50乗すなわち1000兆以上ものパターンを調査していることになります。

 

3. 動的計画法で解いてみよう

そこで、人員数と発注費用の合計を格納するリストを作成し、新たに追加する要素と今まで格納されている各要素との人員数と発注費用の合計を求めて、それぞれリストに追加します。

下請け会社が3社(A社、B社、C社)の時、

  1. A社の人員数と発注費用をリストに追加します。
  2. B社の人員数と発注費用をリストに追加します。
  3. A社とB社の人員数及び発注費用の合計を求めて、リストに追加します。
  4. C社の人員数と発注費用をリストに追加します。
  5. A社とC社、B社とC社の人員数及び発注費用の合計を求めて、それぞれリストに追加します。
  6. A社とB社とC社の人員数及び発注費用の合計を求めて、リストに追加します。

手順6において、A社とB社の人員数及び発注費用の合計はリストに追加済みなので、それを利用して求めていきます。

POH-Lite4

このように、既知の計算結果を利用して求めていきます。

また、求める値は最も安い発注費用なので、同じ人員数の時には発注費用を安い方に更新していくことで、リストの要素数を節約し、計算回数を減らすことができます。

 

2.1. C#でコーディング

それでは、C#でコードを書いてみましょう。.NET FrameworkのDictionaryクラスを利用して、人員数をキーに求めた発注費用の合計を追加します。

 

foreach文でリスト列挙する場合、あらかじめそのリストの複製を作り、それを列挙していきます。

 

Dictionaryクラスのインデクサーで値をセットする時、指定したキーがリストになければ、新たなキーと値のペアとして追加されます。

 

人員数と発注費用のリストができたら、LINQのWhereメソッドでプロジェクトに必要な人数を満たす要素を抽出し、Minメソッドで発注費用の合計の最小値を求めます。

 

完成したプログラムを下に示します。

 

2.2. 条件文のショートサーキット評価でコードがスリムに

ところで、if文の条件文が以下のような構成にしているのは、条件OR演算子「||」より前の条件式がtrueの時に「||」以降の条件式の評価がスキップされる仕組み(ショートサーキット評価)を利用しているからです。

 

Dictionaryクラスのインデクサーで値を取得する時、指定したキーがリストに存在しない場合、例外(KeyNotFoundException)がスローされます。そこで条件OR演算子を使用して、

「!compMemCost.ContainsKey( mem1 )」、「compMemCost[mem1] > cost1」の順

に並べ、指定したキーがリストに存在しない時(「!compMemCost.ContainsKey( mem1 )」の結果がtrue)は、「compMemCost[mem1] > cost1」の評価をスキップするようにします。

こうすることで、リストに存在しないキーを指定して値を取得してしまうというエラーを回避することができます。

POH-Lite5

このプログラムを実行したところ、7つテストケースの内、すべて通りました。

テストケース1:success 0.04秒
テストケース2:success 0.04秒
テストケース3:success 0.04秒
テストケース4:success 0.04秒
テストケース5:success 0.04秒
テストケース6:success 0.12秒
テストケース7:success 0.38秒

Score : 100 / 100  Rank : S

http://paiza.jp/poh/kirishima/result/ce2729d7

 

2.3. さらに効率のよいコードにする

プロジェクトに必要な人員数を満たす最安の発注費用の合計をLINQで求める代わりに、変数1つに「下請け会社をすべて利用する時の発注費用の合計」で初期化して、安い値にどんどん更新していく方法でやってみましょう。

まず、各社の下請け会社の人員数と発注費用を格納する構造体を作成し、

 

標準入力からの読み込みます。そのついでに下請け会社をすべて利用する時の発注費用の合計を求めます。

 

あとはPOH3-Lite2.csと同じように、Dictionaryクラスで下請け会社を組み合わせた時のプロジェクトの人数と発注費用のリストを作るのですが、

現在の要素の人員数(memCost.Mem)と既知の人員数(item.Key)の和(mem1)が、プロジェクトに必要な人員数を満たしているかどうかで条件分岐を行います。

  • 満たしている時、今まで求めた発注費用の合計の最小値より小さい時、その最小値を更新
  • 満たしていない時、 men1に対する発注費用の合計が未登録 or 登録済みの発注費用の合計より、現在の要素の発注費用(memCost.Cost)と既知の人員数に対する発注費用の合計(item.Value)の和(cost1)が小さい時、mem1とcost1を新たなペアとしてリストに追加 or mem1に対する値を更新

なぜなら、memCost.Costがすでにプロジェクトに必要な人員数を満たしている場合、既知の人員数と組合せる必要がなく、またmem1がプロジェクトに必要な人員数を満たしている場合、以降の要素の人員数と組合せる必要がないからです。

POH-Lite6

こうすることで、リストの要素数をさらに節約することができます。

 

このプログラムを実行したところ、7つテストケースの内、すべて通りました。POH3-Lite2.csより、テストケース6で0.04秒、テストケース7で0.02秒速くなりました。

テストケース1:success 0.04秒
テストケース2:success 0.04秒
テストケース3:success 0.04秒
テストケース4:success 0.04秒
テストケース5:success 0.04秒
テストケース6:success 0.08秒
テストケース7:success 0.36秒

Score : 100 / 100  Rank : S

http://paiza.jp/poh/kirishima/result/82813e9e

 

 

4. パターンの数はいくつあるの?

今回のストーリーに登場する火村氏が書いたコードを見てみましょう。

https://paiza.jp/poh/kirishima の「火村氏のヒント」より

な、何だこの超大盛りスパゲッティコード・・・(汗)

 

下請け会社がm社ある時のパターンの数は、以下の画像の式に示すように、組み合わせ「mC1」から「mCm」までの総和(※2のm乗-1と等価)です。

POH-Lite

 

 

つまり、下請け会社の数が50社ある時は、1,125,899,906,842,623(約1126兆)パターンもあります。

これを火村氏が書いたコードのように、1社から50社までのパターンを構成すると、パターンの総数は2,251,799,813,685,196(約2252兆)通りとなります!これではソースコードがカオスなことになってしまいますね。

POH-Lite2

 

 

それでは、See you next!

 

◆ 関連サイト

 

この記事をシェアする
Chronoir.netのRSSフィードを購読する

About : ニア(Nia)

紅茶とコーヒーが好きな湘南生まれのプログラマー/ITエンジニアです。主にC#/C++/PHPを使ってプログラミングをしています。趣味は写真撮影と音ゲーです。時々イラストを描いています。プログラミングを勉強している方々と仲良くなりたいです! 興味を持っている分野:UWP/Xamarin/Android Wear/WPF/Windows/Visual Studio/WordPress/KUSANAGI/nginx

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

*