ABC 401-500/ABC412C - Giant Domino - 競技プログラミング用 知識集積所

---

問題

ABC412C

必要知識

B以下レベルの内容は省略

• 貪欲法（アルゴリズム系）（未作成）

考え方

例えば

8
4 11 3 13 6 25 7 20

の場合を考える。

4の次には3か6か7を置けるが、貪欲法（未作成）により、7と決めつけてよい。
なぜなら、次に3や6が置いてある場合は、

• さらに後ろに7がある場合、4と7の間にあるドミノを全て削除する
• さらに後ろに7がない場合、3や6を7に変更する

という方法によって、2番目に7がある同等以上の例を作れるからである。

4、7の次は11、3、6、13が置けるが、同様に13と決めつけてよい。

4、7、13の次はなんでも置けるが、最終的に20を置きたいのでそれを置いてゴール。
（うっかり勢いで25を置かないように注意）

つまり、アルゴリズムとして

• 今の末尾より大きくて2倍以下のものが存在しなければ不可能判定
• ゴールの1枚を置けるなら、それを置く
• ゴールの1枚を置けないなら、置ける範囲でなるべく大きいドミノを置く

を繰り返せばいい。
これは、最初にソートをして小さい順にドミノを確認していくことで実装できる。
最初に絶対に使わないやつ（最初のより小さい、最後のより大きい）を除去しておくと、ゴールの1枚を置けるかの判定を省略できるので楽になる。

解答例

解答例

注意点

最初が最後より小さいとは限らない

ここの大小関係が不自然な場合にちゃんと2と答えられるようにしておく必要がある。

別解

二分探索でも解ける

ただし、イテレータの扱いが必要なのと、罠が1つあるので少し難度が上がるか。
（全てのドミノが同じ大きさだったような場合に、うっかり「自分と同じサイズのしか置けないから不可能」にならないように）
解答例