ABC 401-500/ABC453C - Sneaking Glances - 競技プログラミング用 知識集積所

---

問題

ABC453C

必要知識

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

• bit全探索※

別解の場合

• 動的計画法

考え方

C問題は「愚直にやるとTLE」という問題が多い。
しかし今回はNが最大でも20であり、愚直にやっても2^20通りそれぞれ20ステップのシミュレーションで、約2100万回の計算で終わる。
むしろ、変に貪欲法※などを使うとWAになる。

問題は、愚直にやるコード自体が少し難しい点。
2択がたくさんあることから、通常はbit全探索※を用いることになる。

あとは通常通りのbit全探索※。
0を左へのジャンプ、1を右へのジャンプとして、N回のジャンプ2^N通りを全部シミュレーションして、通り過ぎ回数最大のものを探せばよい。

小数を扱うのはいろいろ発生するリスクがあるため、座標全部から0.5を引き、「0と-1の間を通った回数は？」という問題にすると実装しやすい。

解答例

解答例

注意点

long long型を用いる

ジャンプを同じ方向に繰り返し行うと、int型をはみ出た座標に行くことがある。
現在位置をもつ変数にはlong long型を用いること。

別解

動的計画法っぽく解く

bit全探索※部分を、代わりに動的計画法っぽくすることもできる。
i回目のジャンプの後、「どこにいて、通り過ぎ何回」のありえる可能性を全てDPの継承情報として保管する。
これをジャンプの回数だけ更新処理していけば、全ジャンプパターンの行先と回数を求められる。
その中から回数の最大値を探せばよい。
解答例