Hatena::Grouptopcoder

TopCoder煮ブログ

本家ブログはこっち → http://d.hatena.ne.jp/nitoyon/

2009-12-23

SRM456 DIV1

| 13:06 | SRM456 DIV1 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM456 DIV1 - TopCoder煮ブログ

今年最後の2週間ぶり。

13941474 (214.04pt, 191位/565人)

○-- (challenge: 1 success, 1 fail)

成績・ソース (要ログイン)

SilverDistance (Easy)

将棋の銀が目的地に到達するまで何回動かなきゃいけないかを計算する問題。日本人有利! 盤面は高々200万×200万。

引き算などを駆使して直接計算できそうだったが、計算ミスが怖かったので距離を狭める方向に移動していくループを書いて直接求めた。ただし、目的地の真上にいるような場合では回り込まないと到達できないので、下方向への移動を優先するようにした。

challenge phase では場合分けをミスってる人がいたので1人倒した。いろんな答えをみたが、人によって方針が違っていて面白い。id:chokudai 先生がこの問題、全体1位になっていて、脅威の2行コードだった。美しい。

CutSticks (Medium)

n個の棒をC回切って、K番目に長い棒の最大長を求める問題。全く方針が分からず、試行錯誤したが諦め。一番長いやつを半分にしていけばいいかと思ったが、そうじゃないケースもあって混乱して投げ出した。

challenge で半分に割ってるコードを見つけて「半分だけとは限らない。アホか」と戦いを挑んだが、アホなのは自分だった。2分探索のコードだった。2分探索で解くらしい。

FunctionalEquation (Hard)

1人しか解けてなかった。