AHC001方針メモ

初手、ルールを把握した後

希望の場所1マスだけを与えるプログラムをとりあえず書く(未提出なので点数は知らない)。入出力回りとビジュアライザの仕様を把握

とりあえず最初に思いついたもの

最初に希望の1マスを与えておき、そこから上下左右に範囲を伸ばす。希望する範囲で伸ばせるだけ伸ばす。O(N²)。左に伸ばせるかどうかを最初に判定するので当然だけど、ほとんどの範囲が横長になった。 41,143,612,083点 https://atcoder.jp/contests/ahc001/submissions/20686741

横長対策

範囲が横長になるのはあんまり良くなさそうだと思ったので、解消する。範囲を広げる際に一気に伸ばすのではなく1マスずつ伸ばしていくようにした。多分O(N²)にsqrt(10000)ぐらいの定数倍がつく。実行時間の増大と引き換えに45,268,726,139点(+4,125,114,056) https://atcoder.jp/contests/ahc001/submissions/20736626

他の広告枠が邪魔

ビジュアライザの出力を見ていて、他の企業の広告枠が邪魔になっていてあまり点数を伸ばせていない企業があることに気づいた。ある企業の広告枠を右に移動させてその隙間にもう少し面積を与えるみたいなことをすると点数が伸びそう。片側が広告枠でふさがれているとき反対側に1マスずつ移動させる方針でとりあえず実装。実装が面倒でした46,716,099,783点(+1,447,373,644) https://atcoder.jp/contests/ahc001/submissions/20740459

操作順序は関係あるか?

今までは適当に生成した可変長配列を舐めていろいろやっていたが、この操作順序が点数の伸びを阻害している可能性に気づいた。とりあえずループ毎にshuffleするようにした。配列の並び替えを想定したコードだったのでシャッフルを書くだけでした46,778,126,853点(+62,027,070(誤差かな?)) https://atcoder.jp/contests/ahc001/submissions/20740685

シャッフル分節約できないかな

この時点で次の手は思いついていたけど、タイミング的にお風呂とか食事の片手間にできる軽いテストをやっている。

適当にシャッフルする方針にしたときに実行時間が1秒ぐらい伸びた(1,400ms->2,400ms程)ので、これを削減できないかと思った。固定の並び順でできるだけいい点を出すには、rが小さいものを優先すればいい気がする。範囲を広げる処理はrが小さい順、既にある広告枠を避ける処理はrが大きい順と小さい順を両方試す。それぞれ46,735,106,956点 https://atcoder.jp/contests/ahc001/submissions/20741114 と46,716,569,615点 https://atcoder.jp/contests/ahc001/submissions/20741219 だったので、広告枠を避ける処理はrが大きい順にやるのがよさそう? どちらにしてもshuffleするほうがいい点数が出てるのでTLEしたときに採用する。

シャッフル節約の2

固定の並び順でなくても一定の規則にしたがって並び替えればshuffleと同等かそれ以上の効率が出ないかなと思い立つ。ある時点でs/rが小さいものの面積を大きくするほうが全体の点数からして効率がいいので、shuffleの代わりにこのソートを書く。 46,721,508,825点 https://atcoder.jp/contests/ahc001/submissions/20741491 だったので採用は無し。

シャッフル節約の3

面積を大きくしたときの効果が大きいものを優先するのが良さそうなので点数計算の式を微分した値が大きい順に処理をしてみる。やはりあんまり効果はない46,719,560,602点 https://atcoder.jp/contests/ahc001/submissions/20741974

一度広げた範囲を小さくする

一度広げた広告枠が他の広告枠の広がりを阻害している場合がある。ので、隣接している広告枠であって、自分が小さくなることで減少する点数を相手が大きくなることにより得られる点数が上回る場合に自分を小さくしてもいい。という方針で実装。50位を切って小躍りしてた47,973,416,260点(+1,195,289,407) https://atcoder.jp/contests/ahc001/submissions/20743449

このへんで無限ループになる処理パスが存在するようになったらしいので時間により処理を打ち切るようにした。ジャッジに最低4分ちょっとかかるようになりましたね?

横にずらせばまだ大きくできるやつがあるのでは

範囲を小さくするときに、他の枠に触っている辺を1マス引くことで小さくしている。これをほかの枠に触っている辺と垂直方向の辺を引くことでも小さくするようにする。 48,314,228,405点( +340,812,145) https://atcoder.jp/contests/ahc001/submissions/20761270

面積を縮小したタイミングで処理を終了したら損かも?

処理を時間で打ち切っているので、面積を縮小したタイミングで終了するという損が発生する可能性があると思った。最後100msは面積を縮小する処理を行わないようにした。乱数のブレ程度の点数低下が発生したのであんまり大きな影響はないかもだけどこのままいく。 48,263,482,621点 https://atcoder.jp/contests/ahc001/submissions/20762796

垂直方向に引く処理を変えてみる

ほかの枠に触っている辺と垂直方向の辺を引く処理で、引く/引かないの二値だったのをにぶたんしてどこまで引くかという処理にしてみた。点数が下がったので非採用 47,278,131,191点 https://atcoder.jp/contests/ahc001/submissions/20764167

面積を広げる処理専用の時間を伸ばす

最後100msは面積を広げる処理のみを行っていたのを、最後1500msまで伸ばした。ほとんど変わらない 48,261,114,447点 https://atcoder.jp/contests/ahc001/submissions/20764507

水平に引く処理をもうちょっと賢くする

今までは全枠のペアに対して判定をしていたのを、おなじ枠に接している複数の枠を同時に考慮してやるようにした。若干点数が下がった48,256,842,441点 https://atcoder.jp/contests/ahc001/submissions/20766227

いろいろ試したところ、これはこの時点だと処理が重い割に改善効率が良くないので全体的にあんまり良くはないらしいことがわかった。

正方形に近づける

枠が細長い長方形になった場合他の枠を阻害することが多いと思ったので、縦横比が極端な場合にそれを補正して正方形に近づけるような処理を追加した。

最初に一度広げる

現状の改善策が、他の枠に触れているという条件で動くものが多いので、横長対策のときのコードで一度限界まで広げるのを第一段階として実施した後処理を開始するようにした。これにした場合に水平に引く処理を賢くしたものが結構いい働きをしてくれるようになった。

採用しなかった方針

試してないから知らんけど多分そんなに良くない方針

希望に答える企業とそうでない企業を取捨選択する

ある企業には適当な1マスのみを枠として与え(0ポイント)、それ以外の企業に100%の枠を与えるみたいなこと。

[x,y]=meshgrid(0:1e-3:1)
mesh(x,y,1-(1-min(x,y)./max(x,y)).^2)

これをプロットすると上のほうはなだらかになってるので、ある企業は100%、ある企業は0%という取捨選択をするよりもすべての企業に80%応える方が高得点になると思って不採用点数の計算式が2乗じゃなくてルートだったらアリかも。