Hatena::Grouptopcoder

yehara のTopCoder日記

 | 

2011-03-09

SRM 499 Div1

14:37 | SRM 499 Div1 - yehara のTopCoder日記 を含むブックマーク はてなブックマーク - SRM 499 Div1 - yehara のTopCoder日記

o o x 219.16 + 293.49 + 0 + 0 = 512.65 (126位)

Level 1 (250)

同じ数字を言ううさぎはできる限り同じ色とみなす。同じ色の数字を言えるのは、最大その数字+1匹という点だけに注意すれば OK かな。これで計算する和が入力の個数を下回ることはなさそう。テストケースが親切なので、落としている人は少なかったみたい。みんな速いなあ・・・

Level 2 (550)

RETURN を入力する回数は固定なので SPACE/DELETE を入力する回数だけ考えれば良いはず。いろいろなサンプルを考えていくと、DELETE を使うケースは、同じ手数の DELETE を使わない手順に置き換えられる気がしてきた。たとえばサンプルにある [3,2,3] は

  • [3,3,3] にしてから 2 行目で DELETE する手順
  • [2,2,2] にしてから 1,3 行目で SPACE を入力する手順

は同じ手数。

あと、上下に連続する SP は必ず 1 回の SPACE 入力で対応できるはず。

ということで全ての桁で連続する SP のブロックが何ブロックあるのか(何本の縦線で SP だけを塗りつぶせるか)を数えれば良いのではないかという仮説を立て、実装する。するとテストケースが全部通った。しばらく反例を考えるが思いつかないので提出。

550 がこんなに簡単なはずないなーと思い、提出後も必死に反例を考え続けたが思いつかない。なんと通ってしまった。個人的には儲かったが、こんなちゃんと証明できないやり方しかできない自分もレベルが低いと思うし、問題も 550 にするのは不適切なんじゃないかなーと思ってしまう。

Level 3 (1000)

あきらめて、Level 2 を考え続けてた。

まとめ

チャレンジフェーズもずっと Level 2 を考え続けてた。全体で見ると Level 2 が撃墜されまくっていたので、自分のも絶対だめだろうなと思ってたがまさかの通過。結構Rating 上がった。1766 -> 1841

トラックバック - http://topcoder.g.hatena.ne.jp/yehara/20110309
 |