[AOJ] No. 0529 Darts

2019年5月18日

問題

方針

半分全列挙

ダーツは最大で \( 4 \) 本投げることができますが、そのすべての得点パターンを列挙することは厳しいと思います。なので、\( 2 \) 本投げた時に得られる \( M \) 以下の得点のパターンをすべて列挙します。得られた得点の配列を \( v \) とします。

次に、\( v \) を昇順に整列させます。全ての \( v \) の要素番号 \( i \) について、\( M – v[i] \) 以下の \( v \) の要素を二分探索します。二分探索によって得られた値を \( k \) とすると、最大値の候補は \( v[i] + k \) となります。

コード

提出したコード

二分探索