競技プログラミング用 知識集積所

ABC412C - Giant Domino

最終更新:

sport_programming

- view
管理者のみ編集可


問題


必要知識

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つあるので少し難度が上がるか。
(全てのドミノが同じ大きさだったような場合に、うっかり「自分と同じサイズのしか置けないから不可能」にならないように)
解答例
ウィキ募集バナー