読者です 読者をやめる 読者になる 読者になる

kazurof weblog

技術ネタのメモを並べます

POH lite 天才火消しエンジニア霧島をやってみた。

Java

https://paiza.jp/poh/kirishima をやってみました。

自分の理解のため、解法の説明をしながらコードを晒します。

アルゴリズム概要

簡単に言えば、ナップサック問題の変形を動的計画法で解くアルゴリズムです。

処理を進めるにあたり、下請け会社の組み合わせで取りうる合計人数とその場合の合計コストを算出します。 その情報を costByNumOfMember なる配列(ソース10行目)に保存します。 配列添字が合計人数です。値がコストです。

そして、それぞれの下請け会社毎にこの配列の情報を更新します。 つまり、ある下請け会社についてこれを使ったほうが安くなるような組み合わせ(=合計人数)があるならば その下請け会社で更新します。

すべての下請け会社をチェックした後、必要な人数以上の範囲でコストの最小値を求めます。 それが本問の回答です。

プログラム

gist4865fa5ab62c8aae09af

プログラムの解説

30行目から38行目は入力データの読み込みです。 同時に全ての会社を選択した場合の人数も足し上げて保存しています。

40行目から43行目は costByNumOfMember の生成と初期化です。 合計人数は1始まりなので、この配列もそのように使うべく長さを +1 しています。 添字0番目は使っていません。

45行目は、会社のリストでループを回します。 この内部は会社ごとの処理です。

46行目のループは、costByNumOfMemberについて特定した会社を考慮する時の処理です。 配列costByNumOfMemberのそれぞれの要素(=取りうる人数とコスト)について、 特定した会社(変数名 company)を含めた組み合わせのほうがコストが安い場合これを更新します。

ループについて、開始は「全ての会社を選択した場合の人数」です。 終了は「特定した会社の人数」です。大きい方から小さい方へ処理している理由は後述します。 ループ変数は i です。

このループ内部では、costByNumOfMember[i] を特定した会社の情報で更新できるならしたいです。 どうやってやりましょうか?どんな条件で?どんな値で?

実は、costByNumOfMember[i]を更新してよいかの判定には、 costByNumOfMember[i - company.members]を検査することが必要になります。

もしも、costByNumOfMember[i - company.members]に何らかの値が設定されていたら、 そのような下請け会社の組み合わせが存在することになります。 この値にcompanyを加味して新たな組み合わせを検討してみましょう。

0 < costByNumOfMember[i - company.members] であるならば、以前のループの処理で 組み合わせとコストが確定していた事になります。 この値と company.cost の和は costByNumOfMember[i]の候補になります。

未設定ならば新規に値を設定するべきです、 未設定でなくても現在のcostByNumOfMember[i]よりも少ないならばやはり更新するべきです。 新たな組み合わせがあり得てしかも安いということですから。 この処理は、updateCostByNumOfMemberメソッドに切り出してあります。

ループを大きい方から小さい方へ処理している理由は、costByNumOfMember[i - company.members] の値をもって costByNumOfMember[i]を更新しているからです。若い方の値から古い方を更新しています。 もしループを小さい方へ大きい方へ回したら、同じ company で以前処理した costByNumOfMember[i - company.members]の 値をもって、costByNumOfMember[i]を更新することになります。companyを2重に評価することになります。

また、内部のループでの処理に加え、companyだけを選択した場合についても 考慮する必要があります。同様に updateCostByNumOfMemberを実行する。(53行目の処理)

56行目からの処理は requiedNumOfMember 以上の範囲で一番安いコストを検索する処理です。 端から走査するだけですね。

取得した結果を表示して終わりです。

実行結果

http://paiza.jp/poh/kirishima/result/2bbd184057c0ee7da43c9d0f4384eb9c

100 点はとれてますが実行時間は 0.11 秒から0.18 秒の範囲です。 当然ながら最速のコードよりは大きく離れていますね。 

その他雑駁な話

言い訳

このコードはしえるさんのコードをコピペして、自分がわかりやすいように 直して(でもアルゴリズムの本質は変えていない)記事にしているものです。 http://qiita.com/cielavenir/items/d07e62d1dc61c2915003

他人の褌で相撲を取っているようなもので、申し訳ありません。 しえるさん。もしこの記事に問題ありましたらどうぞお知らせください。 削除する準備はいつでも出来ています。

感想など

競技プログラミングということを考えたら、しえるさんが書いたような方向になるべきでしょうね。

実行速度が全てに優先する。余計なことはしない。それが標準APIであったとしても。 使いまわせる変数は使いまわす。読みやすさ、アルゴリズムのわかりやすさは目指さない。

ですので競技プログラミングの目指すところはいわゆるシステム開発とは異なるものであるなと。

ただ、アルゴリズムがわからないのではコードに責任が持てないので、 勉強よろしく書き直しながらやってみました。下請け会社の組み合わせについての情報は全く捨てるというのが ちょっと新鮮でした。学部の頃やっていたような気もするのですが、思い出しながらということで。

さらなる修正について。

costByNumOfMember は今のところ int[] ですが、 これをクラスにする方向もあって良いかなと思いました。今回のプログラムはcostByNumOfMemberに対する処理が そこかしこに散在しています。mainメソッドの一部として置くよりもオブジェクト指向プログラミング的には そのほうが適切かもしれません。もっとプログラムが大規模になって処理の散在具合が大きくなったら 実施すべきかと思います。

変数名の長さ加減でいかにもおっさんが書きそうなJavaコードっぽさが演出されたかもしれません。 今のデザインでは横幅制限が厳しいので次回できれば改善したいと思います。