https://agc023.contest.atcoder.jp/
A
map
B
(i,j)と同じでなければならないのは(j+B-A,i+A-B)です。よってB-Aの値だけが重要なのでO(N^3)です。
C
あーなるほどなぁ。
自分の中で全ての問題は貪欲orDPに落とせるって考えていたのが間違えでした。
なのでDPしようしようとずっと漸化式立ててたんですがうまく行かず。
これはいわゆる数学ゲーですね。ちょっと見方を変えると実は式がうまく立てられるパターンのやつです。
必要条件十分条件で攻めるのも数学ゲーの一種だと思っても良さそうです。数学ゲーのポイントはやはり「見方」ですね。
今回の問題は終了するまでの回数Kでまとめられたかが肝となりました。
僕はコンテスト中、ずっとDPしようDPしようと思っていたので、回数Kでまとめるなんて解法としてありえないと思ってしまいました。
全ての問題は貪欲orDPor数学ゲーであると思うのが良さそうですね。
