Atcoder Grand Contest 08

参加した。

A問題 Simple Calculator

xに対して+1or符号反転を最小で何回やればyになるかという問題。

とりあえず愚直に場合分けすりゃ余裕っしょ！→x,yの符号と大小がややこしくてどっか間違えてWA。

人間にとってわかりやすい解き方を考える。

y-x,y+x+1,-y-x+1,-y+x+2のうち非負で最小のものを取ればいい。AC

B問題 Contiguous Repainting

与えられた数列に対して自由にk個連続する箇所を黒か白で上塗りして、最終的に黒く塗られているところの和の最大値を求める問題。

ある程度自由に色塗ることはできそうということはわかった。dpっぽさがあったのでdpを考えてみる。

mマス目までの時の最大値がわかっている時にm+1マス目を黒か白で塗る過程があるかでdpやろうとした。サンプルは通ったけど残念ながらWA。つらみ。

C問題 Tetromino Tiling

与えられたテトリミノで2*2nの長方形を作った時のnの最大値を求める問題。

最初任意の長方形かと思ってこんなん無理でしょと思っていたがよく読むと2*2nだった。テトリスをやったことある人ならなんとなく分かると思いますが、2*nの長方形になる時は、Oミノ、Iミノ、Lミノ、Jミノの4種類の組み合わせしかない。

Oミノはそのまま置けばいい。他のものはとりあえず2つ組み合わせれば2*4の長方形ができる。IミノLミノJミノ1枚ずつで2*6の長方形ができるので、それにだけ注意する。

AC

D問題以降は知りません。D問題はワンチャンあったのかもしれないけど、まあ結果論。

169位 パフォーマンス 1989 新レート1868(+16)

2000は遠いなぁ。