Hatena::Grouptopcoder

TopCoderの学習のお時間 RSSフィード

戦績(topcoder.com) / 戦績(competitiveprogramming.info) / 過去記事 / 日記

 | 

2009-03-04

[][]TCO09 Marathon Round1 02:41 はてなブックマーク - TCO09 Marathon Round1 - TopCoderの学習のお時間


問題

http://www.topcoder.com/longcontest/?module=ViewProblemStatement&rd=13766&pm=10322

等高線図が与えられて地形を復元するという課題。


履歴

日付使った時間やったこと
2/27(金)0.5h問題を読んだ
2/28(土)4h環境を構築して超単純なアルゴリズムでとりあえず提出。
各エリアで適当に1点測って、1つのエリア内は全部その代表値で埋めるという方法
3/01(日)12h各等高線上で1点測って、それぞれの等高線が一番下から何ステップ目かを推定する。
等高線間のエリア内の値は、近接する等高線との距離を使って内挿して決定
3/02(月)2hアドホック最適化
変なデータの場合はどうなろうが無視していたのをある程度救うようにした、とか
3/03(火)4hアドホックにいろいろ改善
3/04(水)4hアドホックにとにかくいろいろ改良

結果

スコア 35.61 (最良を100とした相対評価)

暫定順位 20/420


感想

なかなか良い結果でした。過去最高順位になれそう。

きっと、シードされてる強い人がいなかったり、Round1ということで通過しさえすればOKというスタンスの人が多かったりした、という要因あってのことでしょうが、嬉しいものです。


等高線同士がくっついているなどの綺麗ではないデータを扱わされるので、泥臭いプログラムをがりがり書くことになってしんどかったです。ひたすら場当たり的に最適化していったせいでコードがひどいことに…。

入力データが綺麗なものではないため、テストケース次第でかなり結果が異なりそうです。最後の最後に入れたちょっとした変更で、テストケースによってスコアが10倍になったり1/10になったりして焦りました。

 |