AtCoder Heuristic Contest 014 参加記
参加中に書いていた日記です。殆どコピペなので長いです。解説記事は追って書こうと思います。
内容を整理した解説記事はこちらです↓
penguin46.hatenablog.com
9/17（土）
- ルールを確認した。
- 頂点を増やしてスコアが下がることはない。
- 同じ頂点を追加しても長方形は一つに決めらないから他の3点も出力するのか。
- 操作の順序が影響する。
- 最終的にはビームサーチか、AHC013みたいな焼きなましになる？
- まあとりあえず貪欲だよな。
- AHC013みたいな焼きなましが出来る？
- 大きな長方形を作ってしまうと、その辺上が重なれなくなって状態が悪くなってしまいそう。
- 何も出力しなければ、50ケース 13.8Mくらい。
- いろんな場所から作り始めちゃうとかみ合わせが悪くなりそうなので、BFSっぽくやってみるか。
- 追加した長方形の近くの頂点をqueueに入れて、取り出した時に周辺の長方形を探した。[localの50ケース 28M]
- BFSだから見つかった順の貪欲になってるけど、他にもいろんなやり方がありそう。
- 最大クラスタを拡張していく
- 長方形が小さいものから置いていく
- 隣接する頂点が多いものから置いていく
- クラスタを大きくしていってもどこかで別の長方形を追加しないといけない。
- その時のかみ合わせはどうやって調整するんだ？？
- 完全になんもわからんだな。
9/18（日）
- とりあえず小さな長方形から順番に作っていくか。
- 大きさ1x1の長方形を追加→1x2の長方形を追加→...。[100case: 37M]
- 長方形の列挙が雑で70回くらいしか最後まで到達してないな。
- BFSの挙動がそれっぽかったので、同じサイズなら早く見つけた方を優先するか [100case: 38M]
- 小さな長方形から作るのは正しいと思うんだよな。
- 辺が共有できなくて使える辺の長さの総和が決まってるので、沢山頂点を増やしたければ小さな長方形じゃないといけない。
- 可視化してみたけど、最初から用意されてる頂点はほぼ使い切れてる。
- 連鎖的に頂点を追加していけるようにしたいが。
- スコアが中心からのユークリッド距離の二乗なので、個数を増やすより外側に置く方法を考えた方が良い？
- 長方形の列挙はO(K)でできるな。
- 各頂点について8方向を線形探索して、角度が90度な2つを使った3点で長方形を確定させて、違反してないか確認すればいい。
- 線形探索は重そうなので、直線ごとに二分探索すると良さそう。
9/19 (月・祝)
- 上の全列挙をやった。[LB 40M]
- まだ二分探索にしてないけど、プロファイラを見る感じ問題なさげなので後回し。
- 簡単にビームサーチにしてみるか。
- スコアを評価値にしたらスコアが下がった。
- 先を見越した評価値を作るのが難しいな
- 他のクラスタとかみ合うかどうかを評価するの、かなり難しそう。
- 絶対かみ合うようなパターンを用意してもいい？
- 見つからない。
- アルゴ緑～水でも45M出してる人がいるな。
- 天才パズルだったりするのかな
- これ、もしかして操作回数に上限がないか？
- 各頂点は次数8で最大4つの長方形で使えるけど、1つ長方形を作ると8消費するので±0。
- ということは次数を使い切れずに埋もれてしまった頂点が増えるほど苦しくなっていくのか。
- 埋もれたかの判定をできれば評価値に使えそう。
- この判定も難しいな。作成可能な長方形の中でその頂点を使っているものがあるかを見てもいいと思ったが、なんかいまいちな気がする。
- 逆に上手く使い切った個数を数えるなら簡単か。
- 「その長方形に含まれる頂点の次数の和」を評価値にした。[100case: 42.6M]
- ビームサーチでも試したけど、相変わらずスコアが低いな。
- AHC002のwalking on tilesみたいな感じで、追加できなくなったらバックトラッキングするのはどうかな。
- 外側に置いていく方針試せてないな。
- なんかうまいこと先読みして外に置けないかな。
- 「ここに置きたい」⇒「ここに置かないといけない」⇒「ここに置かないといけない」⇒「置けた！」みたいな。
- 再帰で殴ればいけなくもないのか？
- なんかうまいこと先読みして外に置けないかな。
- 根拠はないけど、天才焼きなましな気がするな。
- とりあえず長方形列挙を高速化した。[LB: 46.1M]
9/20（火）～21（水）
- 長方形列挙、直線ごとのリストでもって二分探索するやつやるか。
- ほとんど変わらないな。8方向あるから定数倍が重いのかな。
- twitterの900Kのseed0を見たけど、やっぱり頂点数が圧倒的に少ないな。まだ頂点を増やすのが大事らしい。
- 長方形列挙、差分計算できるじゃん。
- 良さげ。ここらへんで1回提出するか。[LB: 47M]
- 辺上に頂点を置くのはOKで、頂点上に辺を置くのはNGなので、先に大きな長方形を置いた方が良い？
- 特に1x1の長方形があとから置けなくなることはない。
- 依存関係がDAGになってるから、トポソすれば答えの順番はある程度弄れるのか。
- 弄って何になるかはわかんないけど。
- あれ、これ焼きなませるんじゃないか。
- テキトーな長方形と、それらに依存している長方形を削除してから貪欲で作り直す。[LB: 50.7M, 100case: 51.3M]
- ランダムな確率で長方形を削除した。
- テキトーな長方形と、それらに依存している長方形を削除してから貪欲で作り直す。[LB: 50.7M, 100case: 51.3M]
- 焼きなましの近傍をもっと追加してみる？
- ランダムな領域の長方形を削除する
- 答えをシャッフルする
- 連続したいくつかを削除する
- 直線の外側を削除する
- 全部上手くいかないな。なんでだろう。
- GA使えないかな。
- 別の解と良さげな部分をいいとこどりしたいお気持ち。
- 貪欲の評価関数を次数重視とスコア重視でランダムにした。[LB: 51.1M, 100case: 53.0M, 1000case: 51.6M]
9/22（木）
- 次数じゃなくて、隣接してる頂点の個数を使うとかは？
- 上がらないなー。密じゃないケースもあるしそりゃそうか。
- 諸々を高速化した。[LB: 53.8M, 1000case: 53.8M]
- 焼きなましの経過を可視化したら、殆ど全部の長方形が消えてた。
- 20%くらい捨てるだけで、殆ど全部の長方形が消えてる。
- 確率を小さくして、さらに時間経過も小さくした [LB: 57.3M, 1000case: 56.9M]
9/23 （金・祝）
- 少し前にやったこと、削除する確率が大きすぎて機能してなかっただけな説ある。やり直すか。
- 焼きなましの近傍
- 長方形を切り抜く [1Mくらい向上]
- 直線の外側を消す [4Mくらい向上]
- 外側を優先して消す [1.5Mくらい向上]
- 連続したいくつかを削除 [ほぼ変化なし]
- 焼きなましで一定回数改善されなければベストからやり直すやつ。[1Mくらい向上]
- 貪欲の評価値
- スコア重視の評価値 [悪化]
- 評価値を見ないでランダムに詰める [悪化]
- 焼きなましの近傍
- とりあえず一通りやり直せた。 [1000case: 64.7M]
- スコアが改善されそうなところを集中的に破壊したいな。
- 大きな長方形を優先的に削除するとか [悪化]
- 次数が小さい長方形を優先的に削除するとか [悪化]
- N, Mで結構スコアが変わるので、焼きなましの温度も調整した方が良い？
- あんまりうまくいかないな。
- 5倍の時間実行したら、100caseで70.3M出た。
- 10倍実行したら72.3M。
- 高速化頑張るか。。。。。
9/24（土）
- 一部不要な判定を削除した 。[LB: 66.0M, 1000case: 64.7M]
- なんもわからんな。あと一週間あるのやばすぎる。
- 結構時間かかるしoptunaで焼きなましの温度チューニングして今日は別のことするか。
9/25（日）
- 真心チューニングと全然違う温度だ。[LB 67.9M, 1000case: 67.0M]
- なんもわからん。スプラ楽しい。
- 結局研究とスプラしかしてないじゃん。土日。。。かえして。。。
9/26（月）
- スプラ楽しい。
9/27（火）
- 気合い入れるためにchokudaiさんの根性論の記事読み直すか。
- 焼きなましのスコア遷移。赤は貪欲回しただけのやつ。
- 密度が低いケースで結構な悪化がacceptされてるな。
- 温度を下げたけどスコアは悪化したので、温度の問題ではなさそう。
- 頂点が少ないから1つの頂点の重要度が高くて簡単にスコアが下がりやすいだけなのかも。
- とりあえずここは問題なさそう。
- 密度が低いケースで結構な悪化がacceptされてるな。
- 削除された長方形の個数と、スコアの悪化量の関係
- 長方形が沢山消されると殆ど改善されてないな。
- 多く消されると貪欲も時間がかかるし、捨ててしまってもいいかも。
- 悪化した。大きな変化をする近傍は必要か。
- でも割合は減らした方が良いよな。残り時間の割合より多ければ捨てた。[LB: 68.5M, 1000case: 68.1M]
- 久しぶりの向上だ。。。！
9/28（水）
- 長方形列挙、同じ線分を2回見てるから、配列にメモすれば2倍以上速くなる？
- というか線形探索の結果も、「その方向に最初に見つかる頂点」を差分計算すればいいのか。
- 悪化した。1x1とかの長方形が多いから効果ないのかも。
- 1位が76Mとかだから、高速化以外の改善もあると思うんだけどな。
9/29（木）
- なんもわからん。
9/30（金）
10/1（土）
- 昨日の提出、温度を間違えてた。[LB: 70.6M, 1000case: 70.0M]
- 今までやったこと見直すために、解説記事書いた。
- 悪あがきしたけど特に成果なし。
