360.1

二回目なのに、余りの頭の悪さに絶望した...。

250

NxMの盤面に数字が書かれている。どの行・どの列からも二つ以上数字を選ばないように選んだとき、総和が等しくなるか否かを答えよ、という問題。

DPすれば良い。選択しない行があるとめんどくさいので、行の方が少なくなるように転置する。

実際には、選ばなくて良い行がある場合には、ある行と他の行が完全一致しなくてはならない、というような制約がいくつかあるだけなので、それを確認するだけでできるらしい。

500

スタートからゴールまで移動することを考える。いくつ妨害すれば移動できなくなるか答えよ、という問題。

ゴールに隣接していない限り、隣接4マスを封鎖すればゴールできなくなるので、高々3マスを全パターン試すだけ。マス数が100なので100^3のオーダーがくるが、ここで100C3通り試すようにしておけば通るという程度の定数倍の違いがあった...。

最大流で普通に通す方法もあるらしいし、そっちの方が確実っぽい...。