久しぶりに書くか

こんにちは。AHC017に参加したので参加記を書こうと思うのですが、滅多に書かないので参加記のフォーマットが自分の中で定まってなくて困ってます。とりあえず他の方と違うアイキャッチ貼っとくか（は？）。

これは与えられるグラフが大きすぎるのでデバッグ用に手作りしたグラフで、実は問題の要件を満たしてない（2-辺連結ではない）のだけど、でも結構役立ちました。

成績は

316位でした。今回の目標はヒューリスティックのレートが青なので青パフォを目指していたのですが 1459 ということで水パフォ止まりでした。次は頑張りたいですが、 AHC018 は MM144 と日程が重なるので、うーん。

解法は

最終的な解法としては

BFS的にグラフをたどってmodで工事日を割り振る（ばらけさせたかったので）
各日のUnionFindのグループ数を最小化するように山登りして不連続点をなくす
２辺スワップで山登り（スコア計算が遅いので数十～百数十くらいしか回ってない）

という感じでした。これだとTwitterに書いたのと同じなのでもうちょっと説明します。

BFS的にグラフをたどってmodで工事日を割り振る

コンテストの最初から最後まで工事する辺はばらけている方がいいと思い込んでいたので、グラフをたどりながら1,2,3,4,5,1,2,3,4,5,1,2,...(D=5の場合)と工事日を割り振ります。まさか工事する辺が連結の方がいいとはね…。

各日のUnionFindのグループ数を最小化するように山登りして不連続点をなくす

「不連続点」というか、非連結だと10⁹（かける非連結な頂点のペアの数）という重いペナがあって今回の相対スコアだとかなり低い点数になるので、まずは連結な解を作れるようにしようと思い、UnionFindでのグループ数が各日1で合計がD(工事日数)になるまで2辺スワップの山登りをしました。

これで提出一覧のスコアが下のスコアから上のスコアへグンと良くなって Twitter で他の方が言ってた「ようやくスタートライン」とはこれか？と思いました。

２辺スワップで山登り（スコア計算が遅いので数十～百数十くらいしか回ってない）

評価関数を軽くする方法が結局見つからないまま、残り時間でしないよりましくらいの山登りをしています。

試したあれこれ

自分はGitHubなどのバージョン管理ツールは使ってなくて、ある程度変更するたびにファイル名を変えて保存しているんですけど、今回は各ファイルのメモをファイルの先頭に書いていました。こんな感じ。

// p01.cpp
// mod割り当て
// 提出１

// p02.cpp
// スコア計算したい
// まずはべたに
// ワーシャルフロイド重すぎた

// p03.cpp
// スコア計算出来たっぽいけど重い
// （ダイクストラ）

// p04.cpp
// コードテストだと6から７倍はやい
// A＊やりかけてあきらめた

// p05.cpp
// ダイクストラ・アゲイン
// 経路復元すっぞ

// p06.cpp
// スコア計算

// p07.cpp
// 構築頑張るか？

// p08.cpp
// バックトラック

// p09.cpp
// タイムアウト対策

// p10.cpp
// 乱択にした

// p11.cpp
// 偏角ソート

// p12.cpp
// unionfindで山登り

// p13.cpp
// unionfindで山登りの後、スコア差分で山登り

// p14.cpp
// ワーシャルフロイドとかダイクストラ高速化とか試したけどダメ

// p15.cpp
// p13.cpp からコピー
// 小手先の高速化

// p16.cpp
// お試し焼きなまし -> ぜんぜんだめじゃん？

// p17.cpp
// 遷移逆だったのなおした

// p18.cpp
// 焼きなましいじってみてもスコア上がらん

// p19.cpp
// mountain()の効率をちょこっとよくしたつもり

// p20.cpp
// ???

// p21.cpp
// 初期解を偏角ソートじゃなくてグラフ順(?)

もうちょっと詳しく書きますと...。

// p01.cpp
// mod割り当て

これは辺番号順に1,2,3,4,5,1,2,3,4,5,1,2,...(D=5の場合)と工事日を割り振った解で、とりあえず入出力がちゃんとできるか確認という感じで提出しました。同じスコアの方がたくさんいて「やっぱりねー」と思いました。

// p02.cpp
// スコア計算したい
// まずはべたに
// ワーシャルフロイド重すぎた

で「次はスコア計算！」と思い全頂点間の最短距離なのでワーシャルフロイドを試してみたんですけどさすがO(N³)、重すぎました。試さなくても計算量で気付けって話なんですけど、本当にこの人アルゴ緑なんですかね。

// p03.cpp
// スコア計算出来たっぽいけど重い
// （ダイクストラ）

で、全頂点からのダイクストラで真正直にスコア計算してみました。当然重い。

// p04.cpp
// コードテストだと6から７倍はやい
// A＊やりかけてあきらめた

手元で５秒近くかかってて「山登れないじゃん！」と絶望してたのですが、コードテストで走らせたら800msくらいで「俺のパソコンおせぇ！！」となりました。どのみち大して山登りできないですが。

で「そういえばA＊ってダイクストラより早いんだっけ？」と検索して書いていたんですが、A＊はゴール地点が一点決まっているときに使うアルゴリズムで、今回のスコア計算では全頂点から全頂点へA＊回さないといけないとなると、むしろ遅いのでは？となってやめちゃいました。書く前に気づけ、それはそう。

// p05.cpp
// ダイクストラ・アゲイン
// 経路復元すっぞ

やっぱり全頂点からダイクストラすることにして、経路復元すればそこから高速化できないかと思いました。具体的には最短経路はその途中の区間もそれぞれ最短経路になっているはずなのでその区間は計算済みとしてチェックしていけば、全頂点からダイクストラしないでもいいかも？とか試してみたんですけど、余計重くなってしまってやめました。

// p06.cpp
// スコア計算

これはスコア計算の間違ってた部分を直した、気がする。

// p07.cpp
// 構築頑張るか？

スコア計算が重いけど、多くの人が割と簡単にもっといいスコア出しているように見えて、これは初期解の構築に何かうまい手があるのかも？と思いました。

// p08.cpp
// バックトラック

それでバックトラック法でまずは連結な解を一つ作ってみたんですけど、頂点数多すぎて時間かかりすぎました。

// p09.cpp
// タイムアウト対策

で時間計測してバックトラック中断したりとか。

// p10.cpp
// 乱択にした

バックトラックで解の候補を順番に試すんじゃなく乱択してみたりとか。

// p11.cpp
// 偏角ソート

時間内にバックトラックで解が作れなければ、辺の中点の座標で偏角ソートしてmodで工事日を割り振ってみたりとか。

...と色々試してみたものの「これじゃないな」ということでバックトラックはここまでにしました。

// p12.cpp
// unionfindで山登り

で、まずは連結な解を作るために各日のUnionFindでのグループ数が各１になるように2辺スワップの山登り。ダイクストラでのスコア計算はまだ高速化出来てなかったので、より軽いUnionFindでとりあえず連結な初期解を作りました。これで大きくスコア改善して順位表でも22Gに乗りました。多くの人が20G超えてる中で自分はさっぱりスコア伸ばせず20G行けずに終わるのかなと思っていたので、本当にほっとして嬉しかったのを覚えています。

// p13.cpp
// unionfindで山登りの後、スコア差分で山登り

で、残ってる時間で2辺スワップした2日分のスコアだけ計算して山登り。

// p14.cpp
// ワーシャルフロイドとかダイクストラ高速化とか試したけどダメ

やっぱりスコア計算が重いので捨てたはずのワーシャルフロイドまたやってみたり。本当にこの人アルゴ緑なんですかね（2回目）。そのほかもいじってみたけど、さっぱりでした。

// p15.cpp
// p13.cpp からコピー
// 小手先の高速化

でp14.cppは捨てちゃって、検索して出てきた定数倍高速化を試してみたり。

// p16.cpp
// お試し焼きなまし -> ぜんぜんだめじゃん？

試行回数が全然足りないのに焼きなましにしてみたり。

// p17.cpp
// 遷移逆だったのなおした

よく見たら焼きなましが最大化する遷移になってたのでなおしてみたり。

// p18.cpp
// 焼きなましいじってみてもスコア上がらん

温度とかいじってみたり。でもそもそもの試行回数が足りないのでダメでした。

// p19.cpp
// mountain()の効率をちょこっとよくしたつもり

焼きなましはあきらめて、山登りで都度グラフをコピーしてた部分をコピー回数減らしてみたり。

// p20.cpp
// ???

ここはメモるのを忘れていた部分。

// p21.cpp
// 初期解を偏角ソートじゃなくてグラフ順(?)

初期解を偏角ソートじゃなくてBFSでたどった辺の順にしてみたりして、終了。

結局、スコア計算を高速化できずにもがいていた一週間でした。いや、途中で全頂点からのダイクストラじゃなくてもいいのでは？と雑にN/2頂点にしてみたりとかしたんだけど、スコア悪くなったので「やっぱり全頂点からの正確なスコアじゃないとちゃんと山登りできないか～」とすぐやめちゃいました。雑に試して捨てちゃうの、良くないなぁとも思うんだけど、ハズレ方針にいつまでも時間を掛けちゃうのも怖いし、悩ましいです。

おわりに

終わってみれば「スコア計算を高速化して山登りor焼きなまし」っていうある意味オーソドックスな問題で、AHCの中でももっと初めの方で出してても良かったんじゃないかなとも思いました。自分としては特に個性的な解法も思いつけず、よくやるテキストでのビジュアライズとか、それをTシャツにしたりとかしておちゃらけたりも出来ず、なんともパッとしない回だった印象ですが、今回の試行錯誤が今後のAHCやMMに生かせればと思います。とりあえず計算量くらいは実装しなくても判断できるようになれよと。はい。

mooakiのブログ

貪欲に出来ることはまだあるかい？乱択に出来ることはまだあるかい？

AHC017参加記