TopCoder Member SRM494 Div1

けっこうひさしぶりのするめ

250

黒と白でグリッドを塗りたい。塗るのには正方形のブラシを使う。白のところに塗ってはいけない。どれだけ大きな正方形を使えるか？

やるだけ。グリッドは正方形じゃないので落ちた

500

ある直線上で、木の高さはある範囲の整数値をランダムにとる。「良い木の列」とは隣り合う木の高さが、大きくなったり小さくなったりを交互に繰り返しているものと定義する。ある「良い木の列」に対して、隣り合う木の高さの差の絶対値の和を「美しさ」と定める。直線上の木を何本か取り去って、最も「美しさ」が高くなるような「良い木の列」にする。このとき、「美しさ」の期待値を求めよ。

「良い木の列」とか延々書いてあるけど別に「良い木の列」にしなくても「美しさ」は構わず計算できるから差の絶対値の和の期待値を求めればいい。
これはDPを使う手もあるが、「隣り合う項の差の絶対値」をすべての場所に対して計算すればいいみたい

1000

マスに対して、「そのマスと、ナイトの動きでいけるマスの色を反転する」操作を考える。
長方形のグリッドがあって、最初はすべて白に塗られている。いくつかのマスに操作をして、全部黒にしたい。同じマスに対して２回以上操作してはいけない。操作の方法は何通りあるか（操作の順番だけが異なるものは同一視する）。

わからない。mod2の連立合同式を解くという解法も考えたがNMが22500ぐらいになるので無理とわかってあきらめた。

結果

250でおとされる。問題文よく読まない症候群
500は通った。

xox 349.72 最下位未満（126位）
Rating: 2292 -> 2304 なぜかちょっとあがった