コンテストへのリンク
No.969 じゃんけん
Xが0, 4, 10のときに、あいこの可能性がある。
No.970 数列変換マシン
・とりあえず立式してみる
のが重要か。
立式したら、とりあえず、$b_1+b_2+...+b_n$を考えてみる。それを使って$a_1+a_2+...+a_n$を表せる。
No.971 いたずらっ子
南か東にしか行けない、というのを読み落とさないのが大切。
また、あるマスのいたずらっ子には一度しか妨害されないので、再度そのマスに行くためには、前と同じルートを通れば妨害されずにそこまで行ける。
なので、マス(i, j)までの最短時間は(i-1, j)または(i, j-1)までの最短時間から計算できる。
No.972 選び方のスコア
・とりあえずソート
した上で、
・中央値→二分探索
を考えるのは自然。問題は、どういう判定問題にすべきか。
ソートされた数列、$a_1, a_2, ... ., a_n$の中央値が$a_i$で、残りが$2*k$個のとき、それらは一番大きい方からk個と、$a_{i-1}$から大きい順にk個とれば良いと分かる。
ここで、kを一つ増やすことを考えると、取るべき数値は左右どちらもk個目に取った値より小さい。つまり、求めたいスコアへの寄与は単調減少だと分かるので、二分探索が使える。
なお、取る個数が偶数個なときが最善じゃないことは、（公式解説の通り）一つ小さい個数へ帰着させることで分かる。
中央値の位置で全探索することを思いつけば、取る個数で二分探索する発想は浮かぶと思うけど、何で探索すべきか思いつくのは結構難しい気がする。
私は最初、左右からの累積和とかを考えてたけど、もっと落ち着いて、どういう風な値を選ぶのが最善か考えるべきだった。
No.973 余興
こういうゲーム系は、
・真似っこなどの最適戦略
がなければ、
・ゲームDP
を考えるのが良さそう。（Grundy数を考えると分かりやすいこともあるか）
今回は、制約を見ると区間i～jが残ったときに勝てるか？ をDP[i][j]として区間DPができそう。ただ、更新にO(N)かかってしまい全体でO($N^3$)になりそうで困りコンテスト中は解けなかった。
その後、公式解説や、けんちょんさんの記事、kmjpさんの記事では累積和を使えば良いと書いてあって、その方針を考えたんだけど、それでも私には分からなかった。
結局、次のようにして解いた。
DPを区間の小さい方から更新していく。その際、
・i～jの区間を使ったとき負け（DP[i][j]=0）だったら、そこへ遷移できる区間i~kやk~jでは勝ち
なことを利用して、DP[i][j]=0となる場所が現れたときに、勝ちとなる区間を更新した。
あるiを固定したとき、DP[i][k]=1を引き起こすDP[i][j]=0は一ヶ所だけなので、DP[i][j]=1を更新する更新回数は、左右からの高々二回。なので、この更新回数はO($N^2$)で収まる。
だから、累積和など使わなくてもO($N^2$)で収まったと思う。
最後の更新部分に累積和が使えると思うんだけど、正直よく分かっていない。この解法の方が自然じゃないかなぁ。
No.974 最後の日までに
一応、今やったら自力ACできた。
現時点での（お金, 好感度）を持ってDPし、「お金も好感度も低い状態」を枝狩りしたらACできた。
解説の半分全列挙はなるほど、という感じ。
でも、いくつか提出を見た感じ、枝狩りで通してしまっている人が結構いそうだった。
ただ多分、この枝狩りでは本質的な計算量は減ってない気がする。Hack caseが作れる気がするんだけど、どうなんだろう。
追記：test caseが追加され、MLEになっていました。半分全列挙しないと通らなくなったのかな。
追記：test caseが追加され、MLEになっていました。半分全列挙しないと通らなくなったのかな。