[AOJ] No. 0529 Darts

Darts

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0529

愚直な解法は思いつきますが、TLEとなるため工夫が必要な問題です。

考え方

解き方が分からなかったので、解説記事を探すことにしました。下の記事が分かりやすかったです。

http://imulan.hatenablog.jp/entry/2015/03/02/035241

方針としては、半分全列挙と二分探索を行います。

点数の配列に \( 0 \) を追加したものを \( P \) とします。2回ダーツを投げて得られる点数のリスト \( L \) の要素は、

\[ P_i + P_j \]

となります。この点数のリストは全体の点数の組み合わせに対して、半分全列挙していると言えます。3、4回目については、総得点が \( M \) を超えないようにリストを二分探索します。つまり、\( M – L_i\) 以下の最大の \( L_j \) を二分探索によって得ます。

ソースコード

感想

半分全列挙という考え方を始めてしりました。最初この問題を解こうとしたとき、二回目までの点数の配列を作って、とかを考えたんですが、そのあとは思いつきませんでした。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする