競技プログラミング用 知識集積所
ABC412C - Giant Domino
最終更新:
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
例えば
8 4 11 3 13 6 25 7 20
の場合を考える。
4の次には3か6か7を置けるが、貪欲法(未作成)により、7と決めつけてよい。
なぜなら、次に3や6が置いてある場合は、
なぜなら、次に3や6が置いてある場合は、
- さらに後ろに7がある場合、4と7の間にあるドミノを全て削除する
- さらに後ろに7がない場合、3や6を7に変更する
という方法によって、2番目に7がある同等以上の例を作れるからである。
4、7の次は11、3、6、13が置けるが、同様に13と決めつけてよい。
4、7、13の次はなんでも置けるが、最終的に20を置きたいのでそれを置いてゴール。
(うっかり勢いで25を置かないように注意)
(うっかり勢いで25を置かないように注意)
つまり、アルゴリズムとして
- 今の末尾より大きくて2倍以下のものが存在しなければ不可能判定
- ゴールの1枚を置けるなら、それを置く
- ゴールの1枚を置けないなら、置ける範囲でなるべく大きいドミノを置く
を繰り返せばいい。
これは、最初にソートをして小さい順にドミノを確認していくことで実装できる。
最初に絶対に使わないやつ(最初のより小さい、最後のより大きい)を除去しておくと、ゴールの1枚を置けるかの判定を省略できるので楽になる。
これは、最初にソートをして小さい順にドミノを確認していくことで実装できる。
最初に絶対に使わないやつ(最初のより小さい、最後のより大きい)を除去しておくと、ゴールの1枚を置けるかの判定を省略できるので楽になる。
解答例
注意点
最初が最後より小さいとは限らない
ここの大小関係が不自然な場合にちゃんと2と答えられるようにしておく必要がある。
別解
二分探索でも解ける
ただし、イテレータの扱いが必要なのと、罠が1つあるので少し難度が上がるか。
(全てのドミノが同じ大きさだったような場合に、うっかり「自分と同じサイズのしか置けないから不可能」にならないように)
解答例
(全てのドミノが同じ大きさだったような場合に、うっかり「自分と同じサイズのしか置けないから不可能」にならないように)
解答例