TopCoder Open 2014 Round2 参戦ログ１
問題文
http://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=15982&pm=13189
順位表
http://community.topcoder.com/longcontest/?module=ViewStandings&rd=15982
ほぼ体調不良で寝込んでたので、殆ど価値がない情報です＞＜
ログ
１日目(5/22)
1:01
始まると思ったら2時からだった。開始１か月前からずっこけてる。大丈夫か。
1:55
起きた。今度こそ頑張ろう。
2:06
ようわからんけど長方形をN個敷き詰めて、領域面積と価値の２乗でスコアを計算するらしい。この辺りはソースコード読んだ方が早い気がするし、ぱぱっと入力だけ書いてぱぱっとビジュアライザ―動かしてみる。
2:19
0点のコード書いて大体分かった。holeってのを作って、holeの面積*(holeの個数^2)がスコアになるわけだ。
んで、holeってなんだ。穴じゃねえのか。穴でいいんだよな・・・？
2:24
穴でよさそうだ。 長方形を障害物として、２点が曲線で繋げたら同じ領域とする。その領域が有限ならholeと見做す。うん、これは穴だ。
とりあえず問題解釈はさくっと終わって良かった。
で、３人が満点なんだけどこれなんだ。全員0点じゃねえのか。
2:26
とりあえず問題設定の意味は解る。１つのAreaを最大化しようとするのに使う個数がNとすると、面積は１辺がNに比例する正方形とか円とかになるから、AreaはO(N^2)だ。んで、holeの個数CntはO(N)で、こっちに２乗がかかっているのでちょうど良い。
これを元に、最適な形、というのを考えると、
- 一つの大きなholeを、大きな長方形を半分使って作成する。
- 残りの半分で、内側か外側かにCntを稼ぎまくるための小さいholeを作ってあげる
とりあえずこれが第一感。誰でも思いつく第一感。スタートライン。これの実装、だいぶむずいけどね。
2:35
考えたいことは色々ある。
- 与えられた長方形群から、最大のholeを作成するアルゴリズム
- 与えられた長方形群から、最多数のholeを作成するアルゴリズム
- 無限に長い２辺があったとして、最多数のholeを作成するアルゴリズム
- そもそもどうやって面積を計算するか
うん、まぁ色々と大変そうである。
とりあえず１つ目をそんなに上手じゃなくて良いので実装したい。
2:39
外側にくっつけるより、内側にくっつけた方がCntは稼ぎやすそうだなあ・・・・
四隅に凄く作りやすい。どう作るのが良いか考えてから作らないと死ぬぞこれ。
2:49
最大である自信は持ててないんだけど、
- 半分より大きい長方形は、斜辺を構成するように斜めに繋ぐ
- 小さい長方形は、４隅の部分でブロック状にholeの数を増やす
って感じにするのが良いような気がした。ここから先は起きてから。
10:09
おきた。やるか。
10:10
とりあえずランキングを眺める。開始から８時間ってことは、「自分が考えてることは絶対に実装仕切られていない」という前提を持って良い。
ただ、1位2位は結構うまく実装してるんじゃないかなーと思っている。どうなんだろうな。
10:15
とりあえず組んでみるのは、
- 大きいの半分くらいで、最大面積に近いAreaを作る
- 残り半分で小さいAreaをたくさん作る
なのは確定で、小さいAreaの作り方がどうするのが良いか解らないので、色々と作ってみるのがいいかな。
多分そこを焼きなましにするんだろうなーと思ってるけど、今のところ明確な具体案はない。
10:19
四隅に作ろうと思ってたけど、１つの隅だけでやった方が簡単かな。たくさんholeを作る方法がむずいけど。ブロック数Nに対してN/2は最低でも作りたいなぁ。そこがスタートラインで、そこからいかにNに近づけられるかの勝負じゃないかなぁ、と今のところ見てる。
10:34
yowaさんが2位と3倍の100万点で1位。やっぱりみんなそこまで凄いのは組んでない気がする。何を組んでるのか想像できないのがちょっとみょーんとするけれども。
10:44
悩ましいなぁ。
右下に圧倒的に長い棒が２本あると仮定しちゃうと凄く楽なんだけど、これを仮定するほど大小比に差がない。
1-1000でランダム分布するんだから、x+yの平均は1000くらい。大きい方の平均の計算は地味に面倒なのだけど、まぁ1400はない。逆に言えば、小さい方の平均は600を越える。
四隅に1000+1000のブロックを使っていたとしても、圧倒的どころか、３つか４つ分くらいにしかならない、というのが今回の個人的な悩みどころ。
10:57
積み重ね方は、多分階段状にするのが一番なんだろうなぁ、と思っている。端っこがダメになるけど端っこ除けば1個につき1個生成出来て良い感じっぽい。
11:09
階段状にしちゃダメやん。「飛び出た形」をいくつ作れるかが大切で、「１つ置いて２つ飛び出る形を作る」が出来る、階段状以外の置き方を考慮しないのは愚の骨頂に見える。
しかしどう配置するのがいいんだ・・・。
11:21
大前提。
- ブロックの数Nで作成可能なholeの数はN-3個である。
- 生成可能なAreaの最大値は、*1/4)^2以下である。
とりあえずこれが大前提。これら2つのバランスを取る。
- holeの数はN/2弱を目指す。
- Areaの最大値は、*2/8)^2程度を目指す。
とりあえずこんなもん。
Areaの最大値自体は、ほんとは、サイズの差があるので、多分/7くらいまでは近づけられる、はず。逆にholeの数がむずい。
11:25
「ｋ封鎖空間」という単語を定義する。上下左右でブロックにふさがれている箇所がｋ個ある空間をｋ封鎖空間とする。
階段状に最大Areaを作った時、斜辺は２封鎖空間である。これを３封鎖空間にし、３封鎖空間を４封鎖空間、つまりholeにすることが、今回の基本戦術。
この時守るべきルールとして、
- ３封鎖空間が出来たら、それは必ずholeにするので、真っ先にholeにして良い。
- ３封鎖空間を埋める際に、最大２つの３閉鎖空間を作り出すことが可能である。これを出来るだけ多く生成するような置き方を考える。
- ２封鎖空間はなくなることはあり得ないので、３封鎖空間がない時のみ、２閉鎖空間から３閉鎖空間を作る。
- その際、可能であれば２つの３閉鎖空間を同時に作る。
さて。こういう探索を考えた時、どうするか。直感的にはビームサーチ。だがビームサーチって言われてもあんまりぴんとこない。もうちょっと考察したいなぁ。
11:31
難しいのは、「封鎖空間の管理の実装」なんだけど、どうやるんだろ。
11:35
良い実装が浮かばないなぁ。一応無理じゃないんだけど。遅い。遅いのは良くない。
遅い実装というのは、隣接した辺（頂点で隣接した場合は両辺）に対して、隣接した場所の１だけ隣から、反対側がどこに存在するかを全探索でチェックする、みたいな実装。それが存在すれば３閉鎖空間になってるし、存在しなければ２閉鎖にしかならない。
３閉鎖空間になっていれば、再帰的にそこを埋めるようにまた呼び出す。
11:42
とりあえず上記の遅い実装を使って、貪欲＋再帰で適当に組んでみるかぁ。それでも一応10秒は絶対かからないし。
目標は18時。結構かかると思う。これ書いて1位じゃなかったら泣く。
11:53
これyowaさんもう良いコード組んでるんじゃないかな。
eldidouさんがN個でhole作るとしてN/2な実装、それに対してyowaさんがNに近づける実装をしてると、今の点数差はある程度納得できる。
11:56
これ実装していいのかなぁ。「スタートライン」は見えてるけれども、上位争いがどこで発生するのかまだ
13:06
適当にぐるぐる大きいArea作る実装をしてみたんだけど、でっかいAreaできないぞこれ。
とりあえず、外側を構築する長方形を４の倍数の個数にして、４つのグループに振り分けて、ソートしながら上手く中心に帰ってくるまでランダムシャッフル、みたいな手抜き手法でやってみてる。
13:13
とりあえず大きいの作ってみた。
なんか思った通りにソート出来てないな・・・あれー。
- 外周には大きな長方形を使う
- 使う順番はx/yでソートする
を組んだつもりだったのだけど。
13:19
出来たけど逆だこれ。
13:22
出来た出来た。
滑らかにしたほうが面積が大きいのかはよくわからないのでとりあえず省略（多分でかい）
seed1(N=407)で、最初のが1310302249、次のが1875965326、最後のが2838871648
桁がでかくて解りにくい・・・ｗ
とりあえずこのフェースは35億くらいが目標になるのかな。そしてCntが200くらいになればとりあえずの目標達成。
13:45
最初は適当な実装で良い。
- 適当な頂点を選び、そこから１（内部的には２倍しているので２）ずらした位置に適当なブロックを配置する
- そこでできた３閉鎖空間を埋めるために必要な辺を考えて、そこを埋めてあげる。
- 再帰的に３閉鎖空間が出来てたらわーいわーいって次のに移る
- 100連続なんもhole作れなかったらおわり。
とりあえずこんなんで。
15:33
とりあえずくっつけるだけ まだCntは1
17:12
パッと見期待通りに動いているのに、holeが1でなんでーなんでーってなってる。
19:29
とりあえず提出 seed1がこんな感じ
Holes count (Cnt) = 112
Holes area (Area) = 2838836663
Score = 35610367100672
Example scores:
0) 3.5610367100672E13
1) 2.206763335E13
2) 2.85838359030939E14
3) 2.33826471534256E14
4) 2.307734804148E12
5) 8.63183841033E11
6) 1.349605465555293E15
7) 9.556940551E12
8) 2.0003379344267E13
9) 2.0284493966625E14
Cntをあと1.5倍くらいにしないといけなくって、それが出来るかどうかの勝負。
（ってことで、2.25倍以上離されてたらびびる。）
→74万点でした。ひとまず安心。
21:51
順番並び替えて適当に３回くらいランダムで試してみる実装に
6) Score: 1.865413695212544E15 Run Time: 9141 ms
あっぶねえ・・・ｗ
Example scores:
0) 5.4068792139144E13
1) 3.3413827945464E13
2) 4.40057527985344E14
3) 3.53964670770996E14
4) 3.265221423366E12
5) 1.22184952736E12
6) 1.865413695212544E15
7) 1.2333083921451E13
8) 2.9091055368024E13
9) 2.81519558432908E14
実行速度がもうちょい欲しいなー。思ったより遅いなー。
とりあえずこれで提出して997112点でトップに。
22:36
「これもう絶対にアカン」って感じの奴を適当に弾こう。それで高速化しよう。
具体的には、「ミニブロック置いたら重なってた」とかは一瞬で弾ける。
22:59
くっつけるところをひとかたまりにしてみた。だいぶ伸びる。（スコアで言うと２割くらい）
0) 6.7468219724444E13
1) 3.8601486478368E13
2) 4.9107609481875E14
3) 4.36304831222772E14
4) 3.967078188416E12
5) 1.277173410363E12
6) -1.0
7) 1.73104892708E13
8) 3.5516253625821E13
9) 3.29143897719652E14
TLEしたので高速化必須に。ぐぬぬ。まぁ手は確かに抜いてるけど、間に合って欲しいところだなぁ・・・・。
23:19
高速化した。
0) 6.4918411660681E13
1) 4.1590272821284E13
2) 5.07703004470062E14
3) 4.13642370140019E14
4) 3.854065280625E12
5) 1.230232739008E12
6) -1.0
7) 1.5741370825425E13
8) 3.60650142866E13
9) 3.212414675536E14
あれー。
2日目(5/23)
0:09
ノリだけで入れてたrandomshuffleがボトルネックでした。死にたい。
0:27
提出。１位。結構スコアが目まぐるしく変わっている。まぁ２位と10万点弱差ついてるので、とりあえずある程度優位には立っていると言って良い。
0:57
今のseed6、こんな感じ。
内側に入っちゃうの修正した方がいいのかどうかはちょっと解らないので保留。多分このままのがいいと思うんだよね。
1:23
前半の最大エリア部分はそれなりに動いてると仮定して。
エリア数増加率は、今のところ１手あたり0.75-0.80程度。ぶっちゃけ結構良い。
これはどう頑張っても1に満たないと思うので、神が提出しても50万点を切ることはなさげ。ここからは増加率増やしても点数が増えにくいから難しいね。
ちなみに、小さいケース（seed1くらい）では、時間いっぱいまで回せば0.85くらいまで伸びることは解っている’
1:32
角から内側ににょきにょきさせようと思ったんだけど、
なぜか外側に出る。なんでや。どう内側に持って行こうとしても上手くいかないのでボツに。うーん。良さげに見えるんだけどなぁ。長いのが処理しきれないのかなぁ。
2:42
開始24時間なので、時間おおよそフルに使って提出
提出タイミングの都合で24時間終了時点の1位を取り損ねたのだけど、とりあえず無事に1位。この調子で行きたい・・・んだけど、この後どうすんだ、という感じでもある。一応Example
Example scores:
0) 8.6308438290732E13
1) 5.3957031135696E13
2) 6.225515479656E14
3) 4.91334116282352E14
4) 5.5102400712E12
5) 2.046094540992E12
6) 2.58542176657092E15
7) 2.3147694252906E13
8) 4.803614604E13
9) 3.90393266263956E14
3:00
うーん。こういう、やるべきことが解りやすくて、どれだけそれを突き詰められるか、みたいな問題はちょっと苦手な印象だ。また時間に追われている、という事実もさらに良くない。
3:05
角に置くのが失敗したのは多分何かしらミスったからだと思うんだけど、何をミスったんだろうなぁ。よくわからん。
例えばこういうの。内側に入るだけで相当隣接点増えそうだよね。
3:08
今後どう改良していくかなんだけど、とりあえず高速化。高速化しないと話にならない。
んで、Cntを増やしたいんだから、make3をもっと正確に行わないといけない。置いてみてたくさん連鎖したらやったー、じゃなくって、条件付けをちゃんと行って、この条件なら１個出来る、この条件なら２個出来る、この条件なら０個出来る、みたいなのをちゃんと作ってあげないといけない、ように見える。ちゃうのかなぁ。
これをちゃんとして、２個出来る条件のものを素早く拾ってくることで、今までより良い感じになる・・・はず！
あと大きいのは小さいのより基本強いっぽいので、同条件だったら小さいのを採用する、というのも地味に大切な感じがする。
・・・・地味なヒューリスティック連発、５日目くらいだと自分の強みだなーって感じられるんだけど、初日からやってるとなんか違う気がする。
3:11
予想としては、やっぱりビームサーチかなぁ。
今はN=1000のケースでは幅1で間に合わないくらいなんだけど、これって前回のマラソンと殆ど同じ状況で、頑張って高速化すれば幅10くらいにはなるはず。
この幅を増やす方法は、
- 「隣接している点」の探し方をもう少し工夫する。「長方形に隣接している長方形」のデータを上手い事活用してどうにかする
- 長方形をサイズごとに適当に持っておいて、「これくらいのサイズが欲しいなー」ってのを取り出せるようにする
- C++を使う！！！！！！ やだ！！！！！！！
しかしなんつーか、ビーム幅が50くらいにはなってくれないと、ビームサーチが有効に働いてることを前提としたプログラム、って感じで組めないから、ほんとどうにかしないとね・・・。
今やってる処理は、
- とりあえずおっきいArea作る。
- 2閉鎖空間を3閉鎖空間にするための、閉鎖空間選び。O(N)回。O(N)個の領域からランダムにtake回選ぶ。（この時選んだ長方形を、初期長方形と呼ぶ。）takeは1000000/N^3。
- 2.で選んだ初期長方形の4つの頂点から、ある方向に2ずらした４パターンの始点を考え、そこから4通りの長方形の置き方を考える。（合計64通り）
- 3.で選んだ長方形の置き方に対し、ミニ長方形を置いて、有効な置き方となっているか検証する。ミニ長方形で1つでも3閉鎖空間が出来ていれば採用する。
- 4でOKだった場所に対して、置いてない長方形を順番に全探索する。（といいつつ、4つくらい置くのを試したら諦める。置いてみたけどだめだった、を無限に繰り返すとO(N)だけどあんまりないはず）
- 5で3閉鎖空間が出来る置き方であれば、再帰的に調べていき、最終的にいくつのholeが作れるかを調べる。置き方は貪欲に見つけた順番から。たまにshuffle書けないと長方形が偏って死ぬ。
- 5の結果で最大値を更新する
- 最大の結果を現在の状態に反映させて繰り返し。
みたいな感じ。
takeは無視して、1が1回。2がO(N)回。3がO(N)回。4がO(N * 64)回。5が、微妙なんだけど、4と同じとしてO(N*64)回。5の中での処理が、「見つけた３閉鎖空間に対して色々置いてみる処理」がO(N)だし、結構かかる。「反対側にあるかチェックする」処理もO(N)ってるのかもなぁ。
6:20
起床。ちょっと円形に近づけてみた。
きめのこまかいのだともうちょっときれいに丸い
こっちの方が面積は大きいみたいで5%ほどうｐ。わーい。
やり方は、４パターンに分けていたところを、８パターンに。４パターンの時と違って、上からスタートだと死ぬので、斜め左上からスタートしてる。ちょっと飛び出てる部分があるのがつじつま合わせ。
しかし、角っぽい部分がなくなったから、「角に寄せる」って出来なくなったな。良いのか悪いのか。
細長いところがあれば、こんな感じに交互に空白地帯を作る、みたいなことも出来るし、両端に支えられている影響は大きいので、角の利用はかなりよさげかなーと思っていたのだけれども。むむ。
6:32
しかしまぁ、いかにも発展途上です、って感じの図だ。好き放題伸びてる感じがする。
これをきちっと端っこに上手く配置して、地の利を生かすような方向性を持たせてあげれば、もうちょい伸びるんだろうなぁ。
6:36
Example scores:
0) 9.17826904925E13
1) 5.7970199143115E13
2) 6.63908360584E14
3) 5.45455195074513E14
4) 5.97899652725E12
5) 2.006356957386E12
6) 1.546821251095104E15
7) 2.4406073881303E13
8) 5.0413484411189E13
9) 4.38062637625E14
seed7が間に合ってないねえ・・・。しかしそれ以外は１割近く伸びている。
seed7なんで間に合わないんだろ。特に遅くなる要素はないはずなんだけどなぁ。
6:49
属しているx軸y軸のグループ、みたいなのをリストで管理しているのだけれども、これの幅を1000から1600に増やしてみると、気持ち早くなったような気がする。
Example scores:
0) 9.234430338E13
1) 5.8028398709022E13
2) 6.63707655016E14
3) 5.37190660060225E14
4) 5.85378540884E12
5) 2.006356957386E12
6) 2.823225844976253E15
7) 2.3971088304828E13
8) 5.2462640646848E13
9) 4.31555136419776E14
とりあえずseed7は間に合ってるんだけど、他は早くなったり遅くなったりまちまちで、なんか不思議な感じだ・・・。
まぁしかしとりあえず安心なスコアに。
削られてるのは間に合ってない分だろうなぁ。
7:04
これ、今ランダムで上手い事そこそこの成果出してるけど、最終的には、最低でもアベレージ２０連鎖とかそれくらいにならないとダメじゃん？
そうなると結構今やってること微妙な気がするんだけどそんなことないのかなぁ。意外と今の回答そこそこよかったりするのかなぁ。
16:24
再開。
抜かれてるのは予想通りだけど、思ったより大差やなぁ・・・。
16:45
色々考えたけど、今見落としてる要素無茶苦茶多いから、そこをちょっと弄るだけで無茶苦茶伸びそう。
例えばこんな感じで赤いのを置いたとしよう。今、赤い線を伸ばして、それを左に移動することで、ふさぐべき場所を求めてるわけだ。
これを再帰的に処理するとこうなる。青い部分が見つかる。適当にやると、赤い部分を置いて青い部分を潰してしまうし、現状この青い部分は発見出来てすらいない
青、緑と置いたとして、緑の線で示されている部分は、「この線を塞げば確実にArea分割が出来る」線になっている。これを使うと美味しい。（何でも置けてボーナスタイムっぽいから以下bonusとかボーナスとか呼ぶ）
とりあえずこれを実装しよう。青を置いた瞬間、緑の置き方が２通り発生しているのも見落とさずに。
これを実装したら、「出来たholeにぴったり嵌るものを探して、嵌ったら中を埋めていく」とかも実装する。これは実装出来た後に後述。
これやりだすと、「ぴったり嵌めるだめにどれだけずらすか」とかやらんといけないので大変なことになるけれども。ずらす余地があるのは２閉鎖空間から３閉鎖空間を作るところだけだから大丈夫かな・・・。計算量的にも実装的にも組める自信あんまないな・・・。
まぁ、何にせよ、スコア伸びる余地が多いのは嬉しいね。
18:08
2つ3閉鎖空間が候補に挙がってて、1つ目が違った時に、2つ目のチェックに行かないバグがあることが発覚。ひっでえ・・・。
18:33
とりあえずボーナスタイム状態（２方向無条件置ける！）を無視して組んでみた感じ、殆ど変化なし。ここからボーナス入れるとどうなるかはちょっと読めない。
3日目(5/24)
1:25
色々あってようやく再開。まだボーナスタイム組んでない。
1:26
じぶん「なんか誰でも考え付きそうだし誰でも組めるものしか組んでなくてつまんないー」
脳内おにゃのこ（以下女の子）「誰でもって何色くらいを想定してるの？」
じぶん「黄色上位」
女の子「誰でもじゃないね」
じぶん「ほんとだ」
女の子「ね」
じぶん「わーい」
13:46
風邪でした。なるほどなー。だから組む気が起こらないのか。なるほどなー。
7日目(5/28)
0:27
い、色々とあって何も出来ず。ぐぬぬ。
つーかこんだけ休んでても14位なのか。15位以下の人は反省しなさい！
しかし１位の人の記録なんだこれ。ちょっと高過ぎる。2位の人と比べて絶望的なまでに高い気がするんだが。
４位まではまぁ取らないといけない点数だよなーって感じするんだけど、１位～３位くらい今の方針だとちょっと見える気しないね。色々考えないとダメそうだ。
まぁしかし、あれだ。いいハンデだ。そういうことにしとく。レーティング的に格上なのはACRushだけじゃないか。
0:28
とりあえずあれだ。１位２位の人点取れ過ぎだし、なんかおかしい。
基本的に５日目くらいまでは舐めてかかっても良いんだよ。そう簡単に自分が負けるはずがない。大差があるとしたら基本的な部分だ。
つーことは多分、最大サイズ取れてねえなこれ。
(x+y)でソートしてたけど、x^2+y^2でソートするか。
0:36
うん。4%くらい増えたね。とりあえずここに修正の余地あり、ということであれば、１位の記録もまぁ解る範囲だな。よし。今日中に90万乗っけるよー！
0:50
バグってる可能性も考えよう。観察観察。
んー・・・。わからん！けどなんかちょっと怪しい気がする！
なんか、３つのブロックがなんとなく接してる感じになってる場所が存在するのが気に食わない。だいぶ気に食わない。すっごく気に食わない。
1:31
開始ブロックの指定をちょっと弄って、一回開始ブロックとして使ったブロックはもう使わない方針にしてみた。1%上昇。思ったより伸びるね。
1:39
bonus実装するほどまだ元気じゃないので細かい調整。半分ずつに分けるのが良い、と書いているけれども、これは真っ赤なウソで、辺の長さの変化が線形でない。ブロックを使えば使うほど効率が落ちる。ので、最初の方の高効率のところだけ使えばよさそう、な気がする。たぶん。
となると、今8要素に分けるのをN/16個にしてるところをN/17個にすれば良いのでは・・・！ということでちょっと実験。実行速度的に悪くなるかもしれない。
結果は0.6%上昇。まぁ誤差範囲かなぁ・・・。
1:43
んー・・・・・・・・。なんかセンスがない気がする。なんか探索方法がまずい気がする。正直今の方法で追いつける気があんまりしていない。
いや、真面目に実装すれば４位くらいにはなれると思う。ただそこまでなんだよね。なんかないかな。なんかないかな。
正直bonus実装してもスコア3%伸びないと思っているので、なんか決定打が欲しい。
1:46
あかん。ねむい。あかん。本調子にならんと無理やこれ。明日や。
2:13
起きた。crossmeって関数が、「自分とクロスしてるのがあるか探すよ！」って関数なんだけど、O(N)掛かってた。だいぶ減らした。これはぶん殴りたいミス。とりあえず5%の上昇。
これでいまのところ83万点くらいかなー。まだ１割ちょいしか増えてない。さっさと90万点には到達しなければ。
2:42
もうちょい試行回数を増やしてみる。2%増加。
これで2%増えるならちょろい感じするんだけどなー。現実は多分そんなに甘くない。
12:27
さて頑張る。今日中に90万点。
Example scores:
0) 1.039962215516E14
1) 6.15681207489E13
2) 7.818928054592E14
3) 6.5156344254662E14
4) 6.412604883048E12
5) 2.408267951856E12
6) 3.373899480773766E15
7) 2.557698122025E13
8) 5.7576387316643E13
9) 5.16040987434561E14
12:47
一桁復帰、と。
どうすっかな。良いっちゃ良いんだけど、悪いっちゃ悪い、みたいな微妙なスコアや。
でもまだ後半部分のrateが0.86とかその程度しか出てないんだよね。0.93くらいにすりゃ追いつきそうだし、そんな大変じゃない。0.97とかが必須になると絶望感凄いけど。
12:57
実行時間十分余裕があるので試行回数を2倍にしてみる。2%くらい増えた。強いな。
14:00から営業でそろそろ出ないといけないので、小細工ばっかりしている
13:00
今までで最高値を出した始点を何度も繰り返してみるような実装にしてみる。1%良くなった。ほー。ということで出発。
18:02
とりあえず自動提出の結果をチェック
８位。なるほど。87万点。あと１２万点かぁ、ちょっときついなぁ。
内側より外側のが強そうなので、外側実装つけて１万点増えるかどうかで（多分増えない）、それを直したら後は根本的な部分直さないとかぁ。ちょっとむずそう。
９５万点はすぐなんだけど、９９万点は遠いなぁ、って印象。
まぁbonus実装して、様子見るかぁ。
18:41
なんか2ずらしてるところを20ずらしてみると解０になってしまう。これバグっぽい気がするのでちょっと検証してから。とりあえずごはん。
8日目(5/29)
0:14
ごはんたべたら眠くなってねちゃった・・・ｗ
0:20
ずらす場所間違えてただけだった。これなら気にする必要なさげ。
ずらす値、どうやって決めるのがいいかなぁ。上から幾つか取ってくるだけ、と言えばそれまでなんだけど。
できるだけ細長い奴を穴埋めに使っていく、みたいなのを基調にすれば、早々おかしなことにはならないと思うけど。
0:23
状況が変わっている
・・・・・・・んー。colunさん強くね？アホみたいに強くね？
これちょっと追いつける目途立たないんだけど。マジか。どうしよ。
根本的に組み方変えるのを検討したほうがいいかもなぁ。
とりあえずbonus部分さっさと組みたいんだけど、体調的にどうもコーディングが全然進まない。ぐぬぬ。
bonus部分組んで、四角の中埋め組んで、初期ずらしを入れるだけで90万点はいくと思うんだけどなぁ・・・。
そこから６万点・・・伸びねえよなぁ。んー。
colunさん上位なのを見ると定型なんか良いのあるのかなーって疑ってるんだけど、手で試した感じあんまり良いのないんだよねえ・・・。クロスワードの時の力技みたいなのもあるし、あの人読みにくい。ぐぬぬ。
ただまぁ定型に上手く落とし込めるのであれば、そっちのほうが処理量減らせるし筋が良い。出来れば小さいサイズの定型をくっつける形がいいんだけど、colunさんだし大き目の定型も考慮に入れて。とりあえずrandomベースでダメだったら要検討、って感じ。実装する元気がほしいー。初日に1500行くらい書いてから何も書けてないー。
5:40
起床。
・・・なんだろう。コード全然書いてない。モチベが全然出てこない、というか、なんというか。
体調悪いのもあるんだろうし、そのせいだと思って横になってたんだけど、これ普通にモチベがないだけなんじゃないだろうか。それでボロ負けたらもうこれ引退やな。
6:53
あかん。ログつけてると何も出来ていないのが明確になるのがアカン。そしてもう超眠い。
14:51
起床。ふええ。
マジかー。現時点の100万点が通過ラインなさそうな勢いじゃないか。絶対届かねえぞそれ。どうすんだこれ。ぐぬぬ。
18:00
１位が見えないからもやっとしてるのかな。そうなのかな。
とりあえず深さ優先探索で組み切るだろ？その後に、状態を適当に保持して、「現在の状態」「３閉鎖空間に出来ている辺」「存在してる四角の閉鎖空間」あたりを適当に持ってビームサーチっぽく持ってく。それだけである程度良い解が作れるはず。
18:02
いやなんだろうなぁ・・・。ビームサーチは正直センスないと思ってるんだけど、それを何でかって言われるとよくわかんない。
なんつーか、「ビームサーチにするほど選択肢ねえだろうが」って言う話で、その選択肢をどうやって絞るかに悩んでる、って言う感じかなぁ。
であればさ、色々調べる前に「変化が起こるのはこのサイズ以上のだよ」ってのを全部計算して、「二つの辺のサイズが条件を満たすものの中で、一番小さい/大きいもの」を取り出すデータ構造みたいなの用意してあげるといいんじゃね？
・・・・用意できなくね？それむずくね？どーやんの？
いやもうちょっと話を単純にしよう。大体のサイズでバケット作ってソートしちゃって、それを上から順番にとってくりゃいいんだ。別にそんな難しいことを求められてるわけじゃない。
・・・・んー。ビームサーチ？んー。 ビームサーチが疑えちゃう問題はRound1でもRound2でもそうなんだけど嫌いだ。
18:05
さすがに全ターンに対して色々やるのは効率悪すぎね？どうせ３閉鎖空間って全部使うでしょ？とかそういうことを考えると、ビームサーチってやっぱり効率悪い気がするんだよなー。けど３閉鎖空間の使う順序って大切だからなぁ。いやでも使う順序が大切っていうなら、使う順序をビームサーチするときに一意に定まるようにすりゃ何の問題もないわけで。
んー。
なんで嫌なんだろうな。ビームサーチ嫌いなのかな自分。
18:06
とりあえず速度はもっと出せるし、ビームサーチの線は捨てないでおこう。ビームサーチじゃなくても、「次にどの３閉鎖空間を埋めて四角を作っていくか」っていうのを外から眺める視点は必要なので、今みたいな深さ優先探索でごりごり、っていう形にはもうならない、と思う。たぶん。たぶんね。どちらかというと幅優先探索っぽくなるのかなぁ、とか、そんな風に考えてる。
18:07
使うブロックのチョイスもだけど、これ貪欲でばしっと決められないかなぁ。２閉鎖空間のチョイスが結構な量あるから、やっぱりビームサーチとかやってる余裕あんまりなくって、そこをばしっと一意に決めてあげるのが一番優しい気がするんだけどなぁ。
あとはあれだって、「思ったサイズの四角を作る」っていうのが大切で、多分今は「全く考慮しない」になってるのを、「初手だけ考慮して、初手１つだけ四角を埋められるようにする」に改良する必要があって、そこから「初手は確実、そこから運よく埋められる四角が出現したら喜々として埋める」になって、最終的に「２つ以上上手い事作れるような組み合わせを模索する」に変わっていくと思うんだけど、なんか結果を見てる感じ、そこまで四角で埋められるほどの小さいブロックって存在しないのかなぁ、うーん、みたいな気持ちにもなっている。むずかしい。
18:09
一意に決める、って言ったけど、「ランダムで適当に１回だけ決める」が弱いことがある程度解っていて、「ランダムで色々試してみる」が結構強いことも解っているので、ここら辺どうするのが正着なのか正直よくわからんね。適切なのがパッと見つけられるならよし。そうでないならまずい。
18:12
日本語書いてたらちょっと頭回ってきた気がする。読めるものにはなってないと思うけど、正直「他の日本勢のためにログ残しておこう！！！」とか思えるほど余裕のある順位ではない、というかこのままだとボロ負けや。
18:13
ということで組むぞー！！！
18:40
100行くらい書き進めたところでごはん。30分で100行とか素人かよ。
19:32
ワタリガニだった。食べるのに超時間かかった。予想外のロスである。しかし無茶苦茶美味しかった。
ワタリガニ嫌いーって言う人いるけどね、冷凍のワタリガニとかだったら、ちょっと考え直した方が良い。生きてるワタリガニをさっと調理して食べたら超上手い。卵とか超上手いし味噌もおいしい。身も独特の味で超美味しい。食べたことない人は超損してる。人生損してる。
「回転寿司のうにを食べて、うにをまずいと判断する」に近しい行為だと思うね。
19:34
こんなことをコンテスト中に考えててもRedCoderにはなれます。
前半はガチで具合悪かったし、マラソンの事全く考えられなかったので、「早く良くならないかなー」って横になりながらログホライズン読んでたし、まぁそんなものでしょう。
19:48
アカン気がする。1/8しか実装してないけどそもそもチャンスがすっごい少ない感じが。
20:18
0.3%しか伸びなかった。適当にseed1-10見た感じ発見率結構あるなーと思っていたのだけれども、試行回数増やしてたからそりゃたくさん発見するの当たり前だなーということに組み切ってから気づいた。酷い。
んー。「今まで置けなかった場所に置ける」を増やすのは強力だと思うんだけど、そういう手で全然増えないのはもやっとするなぁ。
20:21
気を取り直して。
すでに存在するAreaを分割することで上手い事やる系の回答を考えよう。
20:55
bonusの連鎖機能抜けてた。でもあんまり連鎖してるように見えない。1%くらい伸びてたのでちょっとだけ安心。
21:01
やっぱなんかおかしい気がする。今、後半に回してる分の88%くらいは作れてるわけじゃん。点数83万点じゃん。適当に概算すると96.6%くらいないと１位に届かないんだよ。96%って。1/25だから、平均24連鎖くらいしないといけないわけですよ。ちょっとそれは無理な気しかしないわけですよ。
なんか根本的な見落としがあるとしか思えないなぁ・・・・。殆ど理論値出されちゃうとちょっとなぁ・・・。
21:05
見落としてる可能性のあるものの列挙
- Area全体のサイズを大きく出来る
- 大きなAreaを作りながらなおかつAreaの数も増やす方法がある
- 何か定型で超連鎖を起こせる方法を見落としている
- 定型じゃなくても、致命的な置きミスが存在し、それを行っている
んー。
21:12
右下にちょっとカバー出来てないとこあるけど、そんな悪くないやろこれ・・・。
大きいのが上手く使えずあと回しになってる、って印象は確かに受けなくもないけれども。
あと、置けてないパターンいくつかあるんだけど、全然決定打にならないんだよねえ・・・。
ちなみにこれは後半のArea作成率0.862だそうな。
21:25
ちょっと適当に考えていた。n個の長方形使ってareaたくさんつくるなら、(√n-1)^2個は作れるべきだよね。100個なら81個、みたいな。400個なら361個、みたいな。
根拠はなんか、上手い事ずらして配置出来るのがそんなもんかな？みたいな適当なものだけど。サイズ差考えて、１辺は外側のアレで補強出来る事考えるともっといけるとは思うけど。
21:35
折り返し付き階段、というのをちょっと考察している。
これは誰でも浮かぶ定型。けどこれが組めると思う人は多分少ないと思う。こんな細長いの都合よくたくさんあったら苦労しない。これはとりあえずロス１
とりあえずこんな感じで、ちっちゃい四角をたくさんつかって階段を作る。ロス３
なんかこんな感じで。上の図から無駄置き０。階段作ってたんだけど、オレンジの部分で折り返してる。毎回折り返さないといけなかった部分を、事前に階段をたくさん置いとくことで、普通に起きやすいブロックを増やした感じ。
・・・しかしまぁ、これだけ端っこに余ってると仮定しても、無駄置き３使ってるから、別に今と比べて特別いいかって言われると、凄い良いわけではないんだよなぁ・・・・。しかも、こんなちっちゃいブロック置きまくれるなら、別にこういう条件じゃなくても置きまくれそうだし・・・。
22:13
なんとかすればどうにかなる気がしてるんだけど、ほんとにどうにかなるかなぁ、って半信半疑な感じ。
今と同様にブロックを置いとくんだけど、ここの緑部分の空白を、さっきのＴ字戦法で埋めていくような。こんな方式取ってあげると、中くらいのブロックから小さいブロックまで消費出来て、楽だったりするのかな？とか考えてる。
これは初日か２日目かに既に考えていたことなんだけど、「今まで考慮してなかった場所に確実に置ける」ってのはだいぶ伸びる・・・はずなんだよね。
しかもbonusと違って初手に必ず発生する、というのもポイント。
・・・・なんだけど、なんかそれで足りる気が全然しないし、その方向で伸ばしていっていいのかなぁ、と悩んでる。
ちなみに、途中で発生する四角にも、偶然サイズが合うようなものがあればガンガンぶち込んでいいんだけど、１辺一致してないと無理なのが条件だいぶ厳しいんだよね。だから、調節の効く初手以外はあんまり意味がない。もちろん入れられれば超らっきーなんだけどねー。それで出来るパターンってサイズも大きくないし期待しない方が良いねー。
四角の埋め方はこんな感じ。左、上を必要分だけ空ける、みたいな考え方。一番最後が縦幅ぴったりになってないとロス１。四角の出来るサイズはどう頑張っても1000*1000、まぁ現実的に実現可能なサイズでも500*500とかなので、まぁ大した数は出来ない。としたときに、ロス１で取りに行くメリット小さいよね。
22:33
今の方針で良くするとしたら、こういう小手先じゃなくって、「根本的な置き方の変更」もしくは「置き方を色々探索するような実装に変更」しないといけない感じはする。
でもなんかそこのネタが出てこないんだよねえ・・・。評価関数でぼーん、とかじゃないし。なんか上手い事出来ない、というか。うーん。
22:50
このパターンでbonusなってるの見落としてたので実装。1%くらい増えた。
23:03
データ構造を考え中。
「目的のサイズの残っている長方形からランダムに取り出せる」「目的のサイズの残っている長方形から、一番小さいものを取り出せる」「目的のサイズの残っている長方形から一番大きいものを取り出せる」みたいな実装をどうやってするべきなのかなぁ、と悩んでいる。うーん。うーん。
これが出来るのが最低限だよねー。探索を上手い事したいなら。
本当に凄く簡単に言ってしまえば、「大きければ大きい程何かが起こりやすい」のは間違いないわけで、で、小さい方が色々と細かいパターン使えるわけで・・・。あれ、大きい順に取り出せばよくね？（初手は例外になるだろうけど。）
23:19
さすがに上位の人たちおかしい気しかしないので、最大面積疑ってるんだけど、やっぱりあれ最大だよなぁ・・・・。
23:25
提出してみたけど上と離れ過ぎ。アホか。こんなん無理やろ・・・。
いやなんつーか、有力な点数稼ぐ手段はあるんだけど、それじゃ１位に届かないのでどうしたら良いのかわからん、って感じ。
どんだけ都合良く見積もっても今６位の黄色の人の点数が目標くらいになってしまう。なんだこれ。しかもそこだって届く気が正直全然しない。ぐぬぬ・・・。
23:55
5つくらい試して全部置けなかったら諦める、みたいなのを実装したら5倍くらい早くなったので、3倍くらい試行回数増やしてみる。
13日目(6/3)
5:07
また熱が出て寝込んでいた。もうちょっとだけ休む。もうちょっとだけ。
9:03
起き上がってコードを２，３行書いてみたけど、まだだめ。お話にならない。もうちょっと寝る。
思考ログってなんだっけ・・・。体調報告みたいになっている・・・。
11:13
無理っぽいので撤退します。
やりたかったこと
- 穴を埋めるパターンの実装
- 最初に大きな円を作るのをやめて、全部を使ってholeを最大に
- 時間全部使ってちゃんと探索
- 探索する時に使うブロックをきちんと選ぶ
とかまぁそんなん。これ絶対hole全部作らないといけない流れだろうし、長く触れて色々遊ばずに上位取るとか絶対無理なので、ちょっとどうしようもない。
