AGC003 A, B 考察

agc003 A - Wanna go back home

移動量は調節できるので東西・南北のそれぞれで 1 以上のペアまたは 0 のペアをつくれるなら家に戻れる。逆に言うと東西・南北のいずれかで 1 以上と 0 のペアになってしまうと家に戻れない。

解説 AC 。問題文を読み間違えていた。「同じカードが複数のペアに使われないように」を「同じ整数が複数のペアに使われないように」だと勘違いしていた。

誤った解答の「同じ整数が複数のペアに使われないように」で考えると各ペアを使ったか使っていないかを調べて使っていれば次の要素ではペアとして使えない。そういう DP で解けたと思う (たぶん) 。

正しい解答は同じカードを複数回使わなければ良いので先頭から貪欲にペアをつくっていくだけ。途中 A_i が 0 のところでペアをつくれなかったカードが残ってしまう。それ以外はすべてペアになる。

仕事中に体を伸ばしたら首をひねってしまったらしい。寝違えたみたいになっている。

あとはなんだか寒気がする。