Quiz
https://codeforces.com/contest/1162/problem/C
Submission
https://codeforces.com/contest/1162/submission/53758184
考察
- 値 i がguess値と同じ時、1度だけ(i-1, i+1に)「分裂」できるとする
- すでに分裂済みで、またguess値と当たった時「捕まる」とする
- サンプル1で考えてみる
- 必要に迫られるまで分裂はしないとする
- 分裂するときは隣の値(iならi-1, i+1)に分裂する(i=1, i=Nのみ例外)
- 分裂することなく最後まで行けたなら最後に3分裂するとする(i=1, i=Nのときのみ2分裂)
解法
- 各値 i=1〜Nを始点とする
- 初めてguess値とぶつかる時に分裂して避ける
- それ以降で分裂後の値(i-1, i+1)が捕まらなければ最後まで行ける
- これは、
- 各値(1〜N)が最初に出るindex ・・・A
- 各値が最後に出るindex ・・・B
- をそれぞれ配列で持っていれば解ける
- 各値が分裂して避けなければいけないタイミングは、Aで分かる
- 分裂した値がそれ以降で捕まってしまうかの判定は、Bで分かる
計算量
- 配列A, Bを事前計算で持っておくことで、各値 i (1〜N)それぞれが最後までたどり着けるか、その時何分岐しているかがO(1)で分かる
- 各値(1〜N)について求めるので、合計の計算量はO(N)
