Hatena::Grouptopcoder

tanakhの日記 このページをアンテナに追加 RSSフィード

 | 

2009-12-23

SRM456

14:42 | SRM456 - tanakhの日記 を含むブックマーク はてなブックマーク - SRM456 - tanakhの日記 SRM456 - tanakhの日記 のブックマークコメント

http://www.topcoder.com/stat?c=coder_room_stats&cr=22627322&rd=13909&rm=303110

年内red無理だった…

250 220.21 AC

将棋の銀の駒があるマスからあるマスへ移動する最短距離を求めよ。

数が大きいので探索は無理ぽいので適当に考える。まず斜めに移動して、それから縦か横に移動するようなのを3つ場合分けして書いた。

450 187.57 AC

棒がいくつかある。最大C回棒を分割する操作して、大きいほうからK番目の棒の長さを最大化せよ。

450なので、簡単なのかなあと思いきや、全然わからない。適当に均等に分割するのかなあと考える。ドント方式に見えるが、数が大きすぎて無理。とりあえずじっくり考えたところ、長いほうからi本を、ちょうどK本に分割するのを考えればいいことがわかった。それぞれの棒を何本に分割すれば良いかは、棒の長さの比で計算すればいい。きっちりと整数には分割できないので、少なめにして、余った分割数を、ドント方式的につじつまを合わせる。ごりごり実装して、全然計算が合わなくて、絶対もっと簡単な方法あるだろうなあと思いつつ何とか答えが合ったので、自信がないがサブミット。

1050 Opened

開いては見たが、時間がほとんどなくて読むだけ無駄かと思ったのでやっぱり閉じる。

Challenge Phase

特にはまりどころがわからず、何もできず。誰も誰も落とせず。

450自分以外全員解を二分探索で求めていて涙目。

感想

250も450も自信がなかったのでどきどき。とりあえずは通ってよかった。二分探索なんで気づかなかったのだろうか。次からはまず二分探索を疑うことにする。値の範囲が大きいときの二分探索は絶好のチャレンジポイントだということがわかった。これも覚えておく。

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