Hatena::Grouptopcoder

yehara のTopCoder日記

 | 

2009-11-05

SRM 452 Div1

23:57 |  SRM 452 Div1 - yehara のTopCoder日記 を含むブックマーク はてなブックマーク -  SRM 452 Div1 - yehara のTopCoder日記

Level 1 (250)

長方形のグリッド上にどの石同士のユークリッド距離も2にならないように石を配置するとして、最大何個の石をおけるか。

端からとにかく greedy に置けるところに置いていくんじゃなんかまずいのか、と思いつつとりあえずそのままのコードを書いてみるとテストケースは通った。短辺と長辺どちらから埋めるかで結果かわるかもと思って念のためどちらも試すコードにした(つもりがよく見たらそうなってなかった。return Math.max(r1, r1) って。一度死んだほうがいい)。

といった馬鹿なコードを submit してしまったが、落ち着いて考えてみると結局市松模様になるので、どちらからやっても同じ。多くの人が瞬殺してるし、これ以上の引っかけはないでしょと思って恥ずかしいコードをそのまま放置。7 分くらいで 235.52 点。

Level 2 (500)

ワイルドカードの含まれた文字列から、I,O,I が等間隔に含まれる文字列が何通り作られるか求める問題。

DP ぽいなと思いつつ良い方針を思いつかないので、とりあえず再帰でチャレンジ。すでに IOI が確定している場合は即終了。一つおけば IOI になる場所を優先的に埋めるといったことをしてみた。

これでテストケースは通ったんだが、やはりというか最大ケースでは全然時間が足りない。いくつか改良を加えてみたが無理。タイムアップ。

Level 3 (1000)

みてない。結果的に誰も解けなかったようだ。

まとめ

部屋ではだれも 500 を submit してないし 250 は簡単だったのであまりチャレンジフェーズもやれることないでしょと思っていたら、別の部屋ではわりと高位の人も 250 を落とされている。なんか罠があるのかと不安になったが、無事 System Test 通過。なんだったんだろう。

まったく達成感はないが、とりあえず黄色に復活 1421->1540。naoya_t さんとは仲良くなれそうだ。

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