TopCoderOpen 2011 Marathon Roun2 - プログラミングとか

今回は頑張りが足りなかったです。最終順位はおそらく５０位ぐらいですが、実は通過の１００位以内も結構危なかった。
以下、参加したときのメモ。特に纏めてはいないのでぐちゃぐちゃです。CodeChefのJune Long Contestにも参加してたので、それも混じってます。

２０１１・６・１

19:37
とりあえずCodeChefのCLONEを解いてる。これは楽に解けそう。
２１：０７
やっとCLONEを通した。最後に%modをするのを忘れて何回かWAを食らった。一番乗りでちょっと嬉しい。
１１：５２
CTEAMSを送信。pythonでかくよりCで書いたほうが楽だったかも。しかもRAをくらってる。
２２：０４
訳が分からないが、最初のN=input()でRuntimeErrorを食らってるらしい。謎だ。
２２：１６
N=int(raw_input())にしたら通った。いくらなんでも謎過ぎる。

疲れたのでちょっと休憩。

２０１１・６・２

１：０４
Maximal Score Pathをサブミット。無事一発で通過。これで三問。

２：１７
marathon matchの問題。第一印象。幾何か・・・。
sizeの定義が書いてない気がする・・・。面積のことでいいのだろうか。
面積だとしたら、あまり辺数の多い多角形を作っても仕方ない。とりあえずは正三角形を作るべき？
得点が相対性なのがちょっと不満。そこそこ奥が深そうなので一位続出はないと信じたい。テストケースの数を増やすかもしれないし。

２：２２
どうやって正三角形を探索しよう？頂点数５０００は結構厳しい。

２：２３
test Case Generationが結構ややこしそう。実際の図をみてもかなり特徴的な分布という感じがする。

２：２７
半径１とすると三角形より四角形のほうが有利っぽい。
三角形　ルート３/2=0.4380 正方形1/2=0.50...

２：５１
正方形の探索は、誤差を気にしなければOrder(P^2)で終わりそう。

３：００
眠くなってきたので、適当に何か実装、送信して、とりあえず寝よう。

４：０１
区間分割して、正方形を作るのが妥当な作戦？

１１：２０
起床。得点の予想つかないけど、とりあえず組んでみるか。今回の問題はむずい・・・。１００位以内も実は少し怖い。

２０１１・６・３

２：１８
SRMに参加してた。そろそろ、今日寝るまでに、何か送信しておかないとずるずる行ってまずい気がする。

３：１５
javaのsubprocessとして実行すると、デバッグしにくいので、ファイルに書き出すことに。

４：０９
choosePolygonsを呼び出しただけでsegmentaton faultを引き起こす謎のバグが発生。原因が分からなくてどうしようもない。

４：２８
原因が分かった気がする。どうやら全然関係なさそうな部分に原因があるらしい。

１０：４４
起きた。

１１：０９
バグをなんとか修正して、やっと正のスコアが取れた。かなり出遅れてる感があるが大丈夫かな・・・。

１１：１３
１６点ってどういうことだろう？いやな予感がする。

１１：２０
問題文よく見たら書いてた。・・・・。やばい。sizeは面積のことじゃなかった。頂点数の二乗らしい。これは非常にまずい。

１１：２１
かなり無駄に時間を過ごしてしまった。というか戦略を１から考え直すはめになった。

１１：２５
ふ、二日間ロスっただけだ。まだ、何とかなる。しかし、この得点の決め方だと、同点続出の可能性が確かにあるなあ。面積の方がよかった気がする。

１１：２６
やっぱり、すぐにプロトタイプを作らないと危険だということが分かった。恐ろしい・・・。

１１：３４
しかし、逆にちょっと考えやすい問題になったのは確かだ。基本的にでかい多角形から順に作っていけばいいだけの気がするし。

１１：４９
図形は小さくてもいいんだよなあ。それが一番重大な事実かもしれない。

１５：４２
Test Case Generationをちゃんと読んだ。螺旋状に点が配置されるのかと思ったらそんなことは全然無かった。
意図的に正多角形を作りやすくしてる感じ。

１５：４４
点が多い場合は中心位置を推理するのがまず重要になりそうだ。
中心の個数は最大５〜２０個。

１５：４６
点の個数が５０−４９９　と、５００−５０００で、色々パターンがあるので、場合わけをするべきかも。とりあえずは点の個数が多い場合の対策をするべき。

１５：５３
明確に円っぽい物が見えるときもあるけど、必ずしもそうではないなあ。

６/4

００：３４
ニコニコみて時間つぶしてた。何やってんだ・・・。

２２：０７
pygameで極座標表示をしてみたり。
相当だらだら過ごしてるから、このままのペースでいくとまずい。

２２：０８
辺数を増やしたとき、実はradiiDiffってあんまり関係ない気がする。凸性と、sidesDiffの条件からradiiDiffは自然に大丈夫になるんじゃないかと。

２２：０９
実験してみないと分からないけど。

６/6

００：４１
中心決める方法はあんまりうまく行かなさそうなきがするなあ。

１４：２０
正多角形の位置の頂点で、一番近い点を選択するという、普通の方法を実装することにする。何故かこれを思いつくのに時間がかかった。

６/８

4:30
あと一時間以内に方針を決めて、さらに１時間以内にsubmitしよう。

４：５０
やりかた候補
完全にランダムに中心と半径を決める。
二点決めて、その中心と距離で半径を決める。
３点選んで中心と半径を決める。

６/10

謎の雑務が終わったので、今から本気出して頑張る。とりあえず駄目コードで一回submitしている状態。
１８．０３点で１４６位。clock()関数があまりよく機能していないことに気付いて衝撃を受けている。これはまずいだろ。

6/11

1:21
起きたので開始。

１：５３
clock()関数で１秒で打ち切ったら、実行時間が３〜５秒ほど。なにこれ・・・。

２：２１
clock()関数の代わりにgettimesofdayを使ったら、うまく行った。何か変な気がするけど、これで戦える。

２：４８
timerをちゃんとセットして送信したら、28.03点。１２６位。

６：０５
exampleの結果をメモ
112.0
928.0
8352.0
13040.0
864.0
8576.0
736.0
512.0
3968.0
208.0

これは二点選んで、それを対点とする正方形を探索し続ける作戦。

６：２１
時間が<5のときは辺数６
＞５のときは辺数４で
テスト

116.0
940.0
10992.0
17872.0
916.0
9828.0
696.0
496.0
5292.0
200.0

逆にSCOREが落ちているケースもある。（３つのケース）。これは意外。

１５：２３
全く同じコードでテストしてみたら、結果が不安定。これはちょっとやる気をなくす。

6/12

０：２９
正三角形も真面目にサーチしたら、それだけで割りとましな点数になりそう。

163.0
1424.0
11754.0
18614.0
1225.0
11049.0
1118.0
762.0
5626.0
288.0

全て上昇した。

送信してみる。今は順位126->134らしい。

００：３４
三回目のsubmit。57.66点ゲット。134->70位。100位以内に入ったのがなんとなく安心材料。まだまだ油断できないけど。

００：３９
これ以上、先に進める場合は、実行時間によって最善の選択肢が変化する可能性があるので、最適化を先に行っておくほうがいいかもしれない。

1:57
正多角形を作ろうとする試みを何回行っているかメモするようにした。
グローバル変数をinfoを作った。あまりグローバル変数を使いたくないが仕方ない。

２：３０
何気なく結果を見てたけど、どう考えても処理に時間がかかりすぎている。例えば最初の５秒で、7480のバケットしか
調べられていない。多分bucketのサイズが大きくなりすぎている。（ひとつのバケットに点が入りすぎている）のが原因と思われる。
２：５０
変数がよほど大きくならない限りは、最も近い点を調べる作戦に大きな問題があるとは思われない。

３：１６
ボロノイ図的なものをつくるのがいいかな。

３：２９
時間を増やしても、SCOREの上昇は多少に留まる。もう点数は限界が近いかな。

１２：３１
起きた。なんかぼろぼろだ。

１９：００
一応profileをとったらsq()に時間がかかってるので、やっぱりbucket大きすぎ説は正しい。

１９：０１
二度寝してしまったので、

２１：２２
ボロノイ図作ってみたけど、まだ速度が甘いかな。

２１：２３
と思って、何も変更せずにもう一度送信してみたら、探索量が増えてる。謎。さっきたまたま遅かっただけか・・・。

２３：３４
探索量があまりに不安定だし、example testでも似たような感じだから、なにかおかしなことが起きてそうだ。調べたほうがいい。
177.0
1294.0
11077.0
17272.0
1117.0
10746.0
1064.0
675.0
5225.0
288.0

6/13

ボロノイ的なことをしたら、余計に得点が下がってしまったが、これは多分、近距離候補の１０点をを全て使い切ってしまっているため。対策はどうしよう・・・。

０：３８
きれいなやり方ではないけど、残りのpointの数が減ったら、全探索に切り替えるという手もある。

３：４４
次の手はどう打つべきか・・・。ボロノイを利用する作戦はあまりうまく行ってないようにみてる。色々なサイズのbucketを用意するのがいい気がする。

５：３８
一時間以内に次の作戦を決める。

６：２７
bucket法を拡張するのが妥当という結論に落ち着いた。

６：２８
点の数が多い場合は思った以上に煮詰まっているんじゃないかという気がしてきた。

７：３７
何か適当に改良してexample testしてみた。
177.0
1452.0
13136.0
21312.0
1272.0
12207.0
1108.0
821.0
6169.0
299.0

ローカルよりいい点数が出やすいようだ。これはちょっとやりにくい・・・。

７：３９
submitしてみるか・・・。現在５４．２９点で８３位。これは４回目のsubmit。

7:43
結果は65.64点で５４位だった。土日を乗り切ったから多分、もう１００以内からは多分落ちない。
前日ラッシュの可能性も無いわけではないけど。

８：１１
しまった。よく考えたら -O2オプションつけるの忘れてた。そりゃローカルの挙動がおかしくなって当然だ。あほだ・・・。

９：４６
頂点数が多い場合は遅かれ早かれ、最適化ゲーになる可能性が高い。とりあえず、まずは頂点数<500の対策を先にやっておこう。

１７：２９
まず、最後の三角形の選択の改良をどうにかしないと。

6/14

22:22
もう残り時間が少ない。結局だらするだけで時間が過ぎ去ってしまっているので、今からは本気でやる。
今は７０位なので非常に危ない。

まず、方針はひとつに絞ってやるべき。あんまりだらだらやってると、予選落ちもありうる。
現在は正多角形を、選んだら、それで固定してその点は使わないアルゴリズムになっている。
長所は、使われていない点による正多角形のみを、検索しているので効率がよい。
短所は、一般に解は最適とは限らない。
この短所を克服すれば多少の点数アップが望めると思われる。
というより、これをいかに行うかが高得点化の鍵だと思われる。
そのためには正多角形をリストアップしてから、どの多角形を使うか決める方法がいい。
ただし、この戦略のせいで、長所が死んでしまうと、逆に点数が落ちかねないからそれは気をつける必要がある。
もうひとつ、今までは、時間が来たら探索を終了していた。
正多角形をリストアップしてから、どれを使うかきめる方法をとったとき、
正多角形をきめるステップの実行時間を正しく評価できていないと、タイムオーバーの危険があったりで、
有効に計算時間を使うのが難しい。正多角形を見つけるたびに動的に使う多角形リストを変化させれば、単に時間いっぱい計算すればいいことになって、有効に時間を使える。どっちの作戦がいいかは分からない。
安全なのは後者なので、後者の作戦でいくべきだろうか？残りの時間は少ないので。
後者の作戦で行くとして、どのようにアルゴリズムを設計するべきだろう？
まず、辺数の大きいほうから決定することに大きな問題はない気がする。大きな辺数の多角形を犠牲にして逆に点数を稼げるパターンも無いわけではないけど、割合としては少ないだろう。より上位を目指すならそうするべきだが、とりあえず後回し。
で、動的に多角形リストを更新ってどうやってやるんだ？

２２：４９
ちょっと紙に書いて考える。いつもこのまま考えてる間に堕落するパターンなので、２３：１０までに切り上げて、状況を整理する。２３：００
前回のR２と同じようにラグランジュ緩和法をつかうのはひとつの手だ。多分前回よりうまく行きやすい状況だとは思う。
でも、正直なんでうまくいってるのか自分でもあまり理解していない方法なので、あまり使いたくはない。というのがある。

２３：０３
しかし、これはどうみても重みつきset packing problemだよなあ。納得はいかないけど、ラグランジュ緩和法をつかうのは仕方ない気がしてきた。

２３：０９
packing problemとして定式化する方法を詰めてみる。一つ目の問題点は、使われていない点による正多角形の検索を放棄していること。

２３：１１
現在の正多角形のリストアップ方法は、
１：ランダムに二点を選ぶ
２：その二点を対点とする正多角形を検索する。
３：そのさい頂点は、理想の位置に最も近い点で、まだ使われていない点を検索する。
という方法をとっている。

２３：１８
最悪、前のアルゴリズムを繰り返しまくる作戦でもそこまで大きな問題はない気がする。

２３：２３
とりあえず、ラグランジュ緩和的なことをすることで、方針は決定した。よく考えればこれは非常にいい方法だという気がしてくる。

２３：２５
まだ一時間ほどしか考えてないが疲れた。とりあえず後一時間ほどは双対的な方法のやり方を自分なりに整理する。

6/15

５：３９
単体法を今から実装する。

単体法は放棄しました。

２２：３８
メモをとる余裕もないぐらいあせりまくってます。順位は１１０位。やばい。
example testの結果。

179.0
1559.0
13339.0
21514.0
1333.0
12434.0
1158.0
830.0
6400.0
328.0

一応全て点数が上がったから何とかなるかな。何とかなってほしい。

２２：４１
最適化に取り組む。

２３：５３
送信した。71.23点。５０位。

example 15のresult
179.0
1575.0
14283.0
24640.0
1262.0
12240.0
1169.0
853.0
7120.0
328.0