AtCoder Beginner Contest 359
2完 AB
perf 370
やる気がなくなって途中で撤退したappbird.icon
1. C問題が結構特殊な感じで場合わけに圧倒された
2. 研究の締切が迫っており、その作業をずっとしていたため脳内リソースがなくなっていた
3. 寝不足 かつ 昼寝をしていない
教訓:脳内リソースを8割使い果たして意識が若干ぼんやりしている時にABC Ratedに挑むべきでない
同じ色の服を着た人は二人しかいないことが保証されているので、$ iを全探索 スタート点を通り、傾き$ 1の直線に沿わせるように移動するラインは最小コストで移動できる(...と仮定する)
本当は傾き$ -1についても考える必要があるが、スタート点に関する$ x, y軸方向線対象性を使えば考えなくて良い。 (ということを考えついていたのだが、なぜか$ x軸方向には対称性がないなと思っていた)
タイルのズレ部分を考えるのがめんどくさくなっていたappbird.icon
そのため、$ (T_x, T_y)から$ lに、$ x, y軸に平行な方向に移動させて、
対称性を使えば、
$ 2^{1000}通りをやるのはダメだなあ...と思ってた
$ K \leq 10なので、それぞれの部分文字列ごとにその通り(高々$ 2^{10}通り)を計算できたら良さそうだな、と考えていた
BitDPはわからんなあ....。appbird.icon