AHC017参加記

はじめに

こんにちは、berryと申します。競プロはほぼAtCoderを中心にやっています。

今回はAHC017に参加するにあたって自分用の振り返りメモを残して自分の考え方を客観的に見てみたい&解説記事を書いてみたいというモチベーションで書いています。あまり人の役に立つ内容にはならないかもしれません。

なお、コンテスト終了時の暫定順位は261位でした。

[2/7 4:00追記] システムテストの結果は260位でした。AHC016のときはシステスでそこそこ順位が落ちてしまったので、今回は1位だけ上がってくれてホッとしました。

1/28(土) 開始前

まだ午前9時です。コンテスト開始まであと3時間ほどあります。コンテスト中の自分に向けてメモを残します。

最初は計算量が多くても愚直に書く

最初から計算量を落として実装しようとするとバグらせてしまうため、高速化が必要になったらしましょう。

パラメータチューニングは最後にやる

スコアが上がるのは嬉しいけど解法を変えたらまたやり直す必要があるのでほどほどに。

assertをいれる

Segmentation Faultは原因を見つけるのが大変な上に、最悪セグフォすら出ずになぜか低いスコアしか出ないコードが生まれるかもしれません。

メモ書きはこれくらいにして、今回はどんな問題が出るんでしょうか。最近はインタラクティブな形式のコンテストが多かった印象なのでそろそろ入力が最初から全て与えられる問題が出そうですね。ドキドキだ〜

1/28(土)

問題文を読みました。D日間かけてすべての道を1回ずつ閉鎖し、全頂点間の最短距離が伸びた分だけ不満がたまる。その不満を最小化したいようです。

とりあえず方針を考えようとしているんですが、N=1000のときにワーシャルフロイド法を使ったら何秒かかってしまうのかが気になりますが夜になってしまったので寝ます。

1/29(日)

ひとまず正の点数を得るため、D=6であれば123456123456...のような適当な解を出力するプログラムを投げ、正の点数を得ました。111122223333...の形だったかもしれません。

13,941,895,255点で249位

次に手元でスコア計算をしていきます。 全頂点間の距離を求めたいのでワーシャルフロイド法を試してみました。

N=500で108ms、N=1000で752msとなり、O(V3)なのでそれっぽい感じに落ち着きました。

でも時間がかかりすぎているような...。ビジュアライザに解を貼り付けたときはもう少し早く結果が表示されている気がします。

問題文からDLできるRustのコードを見てみると、各頂点からダイクストラ法っぽいことをやっている雰囲気を感じました。

計算量はO(V(V+E)logE)になるのでこれなら結構早くなりそうです。

書き換えてみると、N=500で37ms、N=1000で101msになりました。これならD日分計算しても手元でスコア計算が間に合いそうですね。

これで得点計算ができるようになったので、まずは自分の出力した解の点数を計算する関数を実装してみます。

ダイクストラの関数に少し手を加えて任意の状態の最短経路の平均・不満度を計算できるようにして、web版のビジュアライザと不満度が一致していることを確認しました。

1/30(月)

今日は有休を取って遊びに行く日でした。移動の時間を解法のアイデア出しに費やします。

空いた時間でなんとなく方針が固まってきました。 やりたいこととしては、ある辺を工事する日に迂回ルートとなる辺をなるべく工事しないようにする作戦です。

グラフの生成方法からして一番外側の辺以外は2つの多角形に属しているので、どちらかの迂回ルートは確保できるようにしたいです。

これを繰り返してできるだけ不満度が増加しないように工事日を決めていく必要があります。おそらくすべての辺の要求を満たすことはできないため優先度を決める必要がありますが、優先度のつけ方で迷っています。候補は2つぐらい浮かびました。

  • ある辺を工事している日に増加する不満度の最小値は2つある迂回ルートの短い方の経路がすべて工事中でないときが最良だが、工事してしまったときにどの程度不満がたまるか
  • 全頂点対の最短パスに何回登場するか(ここは厳密にはたぶん違う)

が優先度に影響しそうです。前者はうまく計算できなさそうなので、一旦後者のみを使って優先度を決めたいと思います。

なんとなく順位表を見ていたら20G~24G点付近に点数が集中していることに気づきました。今の自分の点数が14G付近だったのでもう少し気を使った初期解を投げたら何点取れるのかが気になりました。

同じ日に同じ頂点を共有する辺をなるべく工事させないようにしてみると、

21,739,584,022点で197位

となりました。元の案をちゃんと実装できれば点数もいい感じになる気がするので実装を進めます。

1/31(火)

実装を進めていると考察が進みました。月曜日に迂回ルートが確保できないときの迂回量を出すのが大変そうだと思っていましたが、なんとかなりそうです。

こんな道があるとします。

ある辺が通れなくなったときに、迂回ルートとなるパスは雑に考えると右回り、左回りで2通りあります。

この迂回ルートの長さで評価したくなりますが、この問題ではすべての辺が1回ずつ通行止めになるため、迂回ルートを用意できなかった時にどの程度スコアが悪化するのかを考える必要があります。

したがって、迂回ルートの迂回ルートを求めたいです。

赤い辺が通れないときの迂回ルートが青、迂回ルートが通れないときの迂回迂回ルートが緑

(上記の緑ルートも厳密には最短の迂回ルートではないのですが、実装が大変そうなのでおいておきます。)

ある辺が通れないときに工事日をずらすべき辺は、図の青の辺のうち、自身の迂回ルート緑の辺がより長くなってしまう辺になります。

やることが今度こそ見えてきたので、まずはある辺の迂回ルートを求める関数を作ります。

実装方法としては入力の頂点座標の情報から辺の角度を求め、その角度でソートすることによって、DFSをしたときに前回使った辺の次のindexの辺を使えばなるべく右方向に曲がり続ける閉路を見つけることができます。

と思ったところで、ビジュアライズを見てみると、外周を形成している迂回ルートはとても長くなってしまうので先に見つけてマークしておくことにしました。このDFSを町の中で最も左に存在する頂点から出発させることで外周を形成している辺たちが求められます。

道路の外周が求まった様子

これを一般的に使えるようにして任意の多角形を求められるかを試してみます。

特定の辺の迂回ルートを探索している様子、seed=31

うまくいっていそうです。あとはこれを使って全頂点の迂回ルートを求め、迂回ルートの迂回ルートを求め、迂回の迂回によって伸びる距離が長くなってしまうものにより大きなペナルティを付けて焼きなましをしていきます。

2/1(火)~2/5(土)

一日あたりの工事数を管理するのが大変なので焼きなましの近傍は適当に選んだ2辺の工事日を入れ替える実装にして提出をしてみました。

焼きなましをして提出したもの、

ひととおり工夫して提出した時のスコアは885,665,478点、1Tを切ることができました。

以下、試したこと

  • 辺の迂回ルートを再帰的に調べ、より正確に工事日が被ってはいけない辺を計算する(スコア変化なし)
  • 同日に工事する辺同士の距離を開けるようにする(スコア悪化したのでやめた)
  • グラフが連結でないときに悪い評価をするようにする(一部のケースでスコアが極端に悪くなるのを避けられた)
  • 一旦1日にK本以上の工事をしてしまってもデカい減点にとどめる
  • ある辺を選び、工事日を別のランダムな日に変える近傍を追加(スコア変化なし)
  • 2つある迂回ルートの最小値ではなく、両方を取り入れた(スコア変化なし)
  • 一回の2辺の工事日入れ替え近傍で、残り時間が多いほど一度に入れ替える辺の本数を多くする(スコアの収束が早くなった)

以上でした。見ての通りスコアが向上したものはあまり多くなく、ずっと885Mあたりを漂っていました。

また、制限時間をのばして手元で実行してもスコアは上がらなかったため、評価関数がそもそもよくないということがわかります。

そして土曜日も終わり、厳しい気持ちで眠りかけているとき、「なんか長くてまっすぐなパスをまとめて同じ日に工事した方がよくない?」と思いつきました。

2/6(日)

就寝間際の思いつきをもっと考えてみます。ある辺(赤)を迂回する必要があるとき、その辺に直接つながっていて、方向がほぼ同じ辺(青)を通れるようにしていてもあまり意味がなさそうです。

赤い辺を迂回するときはすでに上下に迂回してしまっているため、青い辺の端点にもう一度寄る必要がないように見えます。

であればあまり途中で曲がらなくて済むようなパスを見つけて辺グループにし、それらの辺をまとめて同じ日に工事するようにしてあげるとスコアが上がりそうです。

とりあえず辺をDFSして辺グループを長さ3000のbitsetで作り、d(1<=d<=D)日目に通行止めになっている辺のbitsetをこれまた作って達成できているかを確認して、できていれば評価用スコアにボーナスを加えるようにしました。

が、スコアはあがりませんでした。今思い返せば1週間手塩にかけて実装したからと言って従来の焼きなましにこだわる必要はありませんでしたが、その時は無意識に焼きなましに合流させようとしてしまいました。

ひとまず辺グループが作りやすそうなm/n>2.5ぐらいのパターンのみでこの方法を適用してみることにしました。

すると、これまでseed=0で9.4M~9.6Mだったスコアが7.2M程度まで改善しました。

seed=0での様子、score=7284485

この時点で残り時間もなくなってきたので、あとはパラメータ調整をして最終提出をしました。

おわりに

今回のコンテストの全体的な感想です。

結果論にはなりますが、本質に気づくのが遅かった&方向転換が遅かったと思われます。

  • 焼きなましを頑張って評価関数を変えてもスコアが上がらない、という時点で方向転換を考えたかったです。
  • 土曜日の夜に思いついた新しい方針も、焼きなましと合わせてしまったせいで中途半端になってしまい、新方針に振り切れていませんでした。
  • 焼きなましで制限時間を変えて、すでに収束しているにもかかわらずスコアが悪いという点に気づいて、プログラムの高速化に時間を使わなかったのはよかったと思います。
  • また、コンテスト終了後にツイッターでちらほら見かけた、距離計算をするときに代表点を10個ほどだけ選んで高速化するという方法は候補にもあがりませんでした。このへんの考察の視野は広げていきたいですね

最後の最後に、こうして1週間丸々熱中できる問題をつくってくれたwataさん、記事を書くモチベをくれた先人たち、プラットフォームを用意してくれているAtCoderさんに感謝を述べたいと思います。ありがとうございました。次回以降も参加するぞ~

おまけ

seed=48, 76で見かけたものですが、一見おかしな三角形ができている場所がありました。

seed=48の左端の様子、縦に長い三角形がある

画像はseed=48の左側で、ここは三角形の長辺が115352、他の二辺が13038, 102313で、115352>115351となっており「2つの辺の長さの和は残りの1つの辺の長さより大きい」を満たすことができていません。

これは小数点の桁数の問題で、それぞれの座標が(11, 572), (10, 559), (2, 457)なので、計算するとそれぞれの辺の長さが13.0384, 115.3516, 102.3132となり、小数点第4桁を四捨五入すると115.3516だけ上方向に丸められるため、重みが1ズレるという 事態が発生していました。

ここまで書いて気が付きましたが、入力のWとして与えられるのはあくまでも辺の重みであって、辺の正確な長さではないのでなにもおかしくはないですね。

長辺を迂回した時に、迂回したにも関わらずコストが低くなっていたので調べた次第でした。