参加しながら考えたこと試したことの源泉かけ流し。
最終的な方針は まとめ にまとめてあります。
問題概要
1 日目
ふ〜〜〜んむ、2 段階の最適化が必要なやつだ。
とりあえず推定要素がなさそうなので胸を撫で下ろしている。
まずは環境構築。
久しぶりに参加したらローカルテスタの Score の出力先が標準エラー出力に変わった？お手製スクリプトが動かなくなってたので修正。
あとWeb 版ビジュアライザに当ててるユーザースクリプトも動かないな...。output のテキストフィールドに js から値書き込んでもビジュアライザが更新されない？以前の AHC でも動かなくなってるからブラウザの仕様が変わったのかな...？ンモー
うーん、ちょっと直せそうにないのでビジュアライザ標準のディレクトリアップロード使おうかな。
問題の考察を。
配列 A 決定パートと旅行パートがあるので、旅行パートを貪欲めにやって配列 A 決定パートを山登りしたい気持ちになる。
なるが...、旅行パートの計算それなりに重いような気がして、あんまり山登りできないんじゃないかなあ。
中途半端な山登り頑張るよりは天才決め打ちを探した方が良いかもしれない。そしたら旅行パートも工夫できるし。
僕の直感も旅行パートの方が 7:3 くらいで大事そうと言っているし、そっちに時間を割きたい気がするなあ。
道の本数の下限が N-1 なのエッ！？って思ったけど、ビジュアライザと入力生成方法チラ見した感じだと理論上という話で実際はそこまで極端なケースはなさそう？レアケースの対応面倒そうなのでちょっと安心。
サンプルコードの動きを眺めていると、スコアの理論値と自明解（ダイクストラして信号操作 + 移動を繰り返すやつ）のスコアの差が高々 2 倍程度しかないことに気付いた。
あ、ウソウソ。スコアには移動の回数は含まれないんだ...。理論値と自明解の差が 2 倍程度しかない問題が出るわけないだろ！
んじゃ低コストでめちゃ移動できたりもするんだ。
配列 A 決定パート。
連続して通りそうな都市は近いところに置くのが嬉しいというのはそうだと思う。
クラスタリングみたいなことする？それともハミルトン路を探す？
なんとなく、細長い繋がりを全体に張り巡らせておきたい気持ちになるんだよな。同心円状 + 放射状に張り巡らされた高速道路をサーッと移動して細かいところは固まりクラスタを伝って移動する、みたいな。
まぁ〜この辺は旅行パートある程度詰めた後に色々試してみるでも良いかもしれない。
旅行パート。
ここだけでも考えること多いよな〜。どのパスを通るか。配列 A のどこで配列 B のどこを上書きするか。
信号操作回数をコストとしてダイクストラっぽいことしようとしても、信号操作の方法で分岐しちゃうもんなぁ。
パスを決め打ちしたら信号操作回数の最適値は求まるのか？ただ遠回りしたほうが信号操作回数は減るみたいなケースもあるからパス決め打ちの仕方も難しいんだよな。
ん、待てよ。信号操作の方法で分岐するとはいえど、新たに上書きしたところのみ使えるという制限を付けたらそんな難しくもないか。
B の長さが 4 のとき、次に都市 3 の信号を青にしようとすると A 上でその 3 つ隣までは同時に青にできるから、そこまではコスト 1 で移動できる。
コスト 1 の都市からコスト 2 の都市に移動するときはまた同じ考え方でコスト 2 で行ける先を特定して...というダイクストラ。まぁできそう。
B のどこを上書きするかという話はあるが...そのあたりは後回しでも良いかな。
これやろうとすると配列 A 決定パートもちゃんとそれなりに繋がりのあるものを作らないと試せなそうだなぁ。
配列 A 決定パート。
同心円を作りたい。これは多分そんな難しくはなくて、外周上のある都市から外周を辿ってぐるっと一周をする。その途中で孤立した都市が発生したら適宜仲間に入れてあげる。一周したら次は未使用の都市に対して同じことをやる。これの繰り返し。でどうかな！？
なんか中央に行くにつれてぐじゃぐじゃになりそうな気はするけど、初手としては良いんじゃないでしょか。
A の長さが 2N あるなら縦横に線を引くでも良いんだけどね。というかこっちの方が楽？まぁ同心円の方が垂直方向にゴリ押ししないといけない最大長が短いので A の長さが短いときは嬉しそうな気はする。
まぁ最初は縦横で良いか。同心円よりバグらせにくそうだし。
やること決まったところで眠いのでまた明日。
2 日目
とりあえず自明解を書いた。サンプルの謎 DFS を経由した都市数ベースの BFS に置き換えたやつ。動作確認は OK。
次は配列 A をある程度連続性のある感じにする。隣接する都市を左上→右上→右下→左下の順の優先度で DFS して訪問順に A に突っ込むやつを書いた。若干取り残されてる都市があるけどまぁ初手はこんなもんで良いでしょう。
次は昨日書いた信号操作回数ベースのダイクストラを書きます。
書きました。
良い感じ良い感じ。思ってたよりちょっと計算が重い（500msくらいかかる）がまぁ許容範囲という感じ。
いろんな配列 A で試してベスト解を選ぶをやりたかったけどちょっと厳しいかも。
こうして見ると配列 A の決め方が俄然重要な気がしてきたな。
あと、今は次の目的地に向かうことしか考えてないので目的地に到着するときの信号の区間の選び方に隙があって、ここはその次の目的地へ向かうことを見据えた方が良い。
さて、余らせてる A の末尾の使い方を考えたいな。
一周目で横にしましまを作って二周目は縦のしましまというのを考えていたが、一周目の時点でぐちゃぐちゃなので難しいかもしれない。
二周目は一周目の補助的な使い方になると思うのだが、なら補助するべき箇所はというと...実際の距離に反して信号操作コストが大きい 2 点間に対してバイパスを通してあげたい気持ちになった。
実際に使いそうな近道かどうかも考慮に入れた方が良いのかな？うーむ。この辺は実際にシミュレートした結果使われてなかったら次回 A から外して別の近道作って再度シミュレートみたいな試行を回せると良いのだが...。
その前に今の一周目で孤立した点がちらほら残ってるの解消した方が良いな。
→ 直したらケースごとに微増したり微減したりして全体としてはちょい悪化した。そう...。
やはり固まりよりも細長い道を用意するべきという話かな？
3 日目
うーん、自作ビジュアライザ作るか。A がどういう並びになってるのか図示したい。
作った。
A の一周目で都市にグラデーションを付けて、二周目以降のバイパス部分を黒線で示している。
（今は試しに信号操作コストの大きい 2 点のペア一つを選んで一本だけバイパスを引いている。）
これ見るとバイパスの引き方は単純に縦に引くでもある程度良いかもしれないなぁ。
というのも、信号操作コストが大きい 2 点を探す処理でそれなりに時間を食っているため...。
もしくは斜めにおっきい ✕。こっちかな。
js と C++ いったりきたりすると脳がバグるな。C++ にも filter みたいなの欲しいな...。
（追記：C++20 から filter_view というのがあるらしい。へー！比較的直感的な見た目をしていて良いな）
✕ だけだとだいぶ余るので縦にも引いた。順当にスコアも伸びている。20% くらい減ったかな？
このケースとかはだいぶ縦にも引いてるんだけどまだ余るんだよな（まぁ最大 2N だしそれはそう）。どうしようこれ。横にも引く？
旅行パートは信号操作回数ベースのダイクストラ以上のことを上位陣みんなやってるだろうし、差をつけられるとしたらここになると思うんだけど...。
横に引いても余るなぁ。なんかもうここまで張り巡らせられるのなら A 作成パートにあんまり工夫の余地もないような気がする。
もしくは、一周目のロジックを変えるとか？
ここらで一回提出してみるか。
お、だいぶ良いぞ！やっぱりハーフマラソンの問題は相性が良いのかな。
B のどこに上書きするかについて。
今の方針ではある点からある点に移動している際はどこに上書きするかなんてどうでも良くて、気にするべきなのは目的地について折り返しが発生するようなときだけなんだよな。
それとも違う方針だと大事になってくるのかしら。
A の一周目を渦巻きにしてみて、主に A の長さが小さいケースでスコア微増した。（一周目も含め A 上で隣り合う道路はすべて黒線にしてみている。）
同心円って言ってたのがほぼこれになると思うんだけど、思ってたよりは伸びなかったね。
それとももう少し間を開けて同心円にすると違ったりするのかなぁ。
うーん、やっぱり旅行パートもうちょい高速化したいなぁ。せめて 1 回 100ms くらいになると配列 A 決定パートでやれることも増えそうなんだけれど。
→ 250ms くらいにはなった。
他のシード見てたら渦巻きがかなり途切れ途切れになっていたりする。こりゃいかん。
でもこのケースは前の方法でも途切れ途切れになっている。なるほど、辺の数が少ないケースでこういうことになりがちなのか。ビジュアライザ自作して良かった〜。
あ〜〜でも A 上で隣り合ってない辺もノーコストで通りうるのか。この黒線紛らわしいな。
渦巻きの実装が微妙にバグっていたので修正。
順位表 1 ページ目から追い出されそうになってるので提出。33.3G(19位) → 35.2G(13位)
提出では実行時間が 159ms になってる（手元では 100 ケース走らせて 100ms 台のケースは一つもない）のでジャッジサーバの方が実行速い説がある。助かる〜。
（追記：これ MacBook Air で YouTube 再生しながら並列実行なんかしてるからだぞ！）
試しに長いパスを 1 つ見つけて全部隣り合わせにしてみたけど、残された都市をどう繋ぐかが難しいなぁという印象。
ただ、例えば一周目から高速移動用道路で全体を区切るみたいなことをしようと思ったら、結局考えないといけないことなんだよなあ。
というか今残された都市はランダムな順で A に突っ込んでいるが、これでもスコア平均 5% 増くらいに収まっているので、真面目にやったら伸びそうな雰囲気がある？
...と思って各連結成分内で最長のパスを繋いでいってみたけど、ダメっぽい。
うーん、まぁさすがにここまで細かいのが散らばるとマズいということか...？
やはり理想は都市数 B の連結成分に分割するような道路を張り巡らせるになるんだろうが、果たしてそんなことは可能なのか...？
ルールベースな構築だと厳しい気がしていて、これちょっと焼き鈍しのニオイがしてきたな...？
一回の旅行パート計算で 200ms くらいなので多少なら A を変えて再計算もできるんだけど、それしなくてもまだ伸びしろありそうだから後に取っておきたいんだよな。
4 日目
配置焼くの無理だろという気持ちになってきた。むしろルールベースの方が可能性がありそう。
まずは頭使わないことからということで A 生成パートとシミュレータ部分を分離するリファクタをやった。
ついでに盤面を 90 度ずつ回転させて A を生成して 4 パターンの解を作るやつをやったけど微増も微増だったので一旦消した。（これはそれはそうで、渦を回転させても渦なんですよね...。）
こういう配置はどうかな〜ということを考えていた。
うーん、違うな。こうか？
赤が一周目、青がそれ以降。
今までは一周目で渦（同心円）を書いてたけど、逆に一周目で放射状に都市を繋ぎ二周目で同心円を書いて補助するイメージ。
......いや違う違う違う。旅行パートで都市を巡る順番はあらかじめ決まってるんだから、その情報を活かした配置にした方が良いに決まってるな。
なんかこう、素のグラフ上で一度旅行してみて、よく通る経路とかを特定するとなんかできたりするかな？
...？や、信号は道じゃなくて都市に対してだからなんかちょっと違うな？うーん。違うかもしれない。
よく通る都市が分かると嬉しい？うーん...？
いやでも、事前に分かる情報を活用しない手はないはずなんだよなぁ...。
ふと思ったんですけど、A 上で隣り合う都市間の道のコストを 1/ L_B くらい、そうでない道のコストを 1 くらいとして普通のダイクストラしてざっくり旅行パートのコスト見積もれたりしないかな？
...ただその見積もりも焼き鈍しの遷移の度に計算できるような処理時間では済まなそうだし、差分計算もできなそうな気がするので、A の順序を焼き鈍すには使えないか。むーん。
あと、L_A がデカいケースだと A の末尾普通に余らせてるのでコレ、伸びしろです。
A の一周目で全都市列挙する前提で（これは後でそうじゃなくなるかもだが）、二周目の選び方も工夫したいところ。
昨日信号操作コストが大きい 2 点を探すのが大変という話をしたが、これ木の直径求めるやつみたいに適当な点から 2 回一番遠いとこ選んだら手軽に信号操作コスト大きい 2 点が得られるんじゃないかな。
そうやって得られた 2 点を繋いで再度遠い 2 点計算して繋いで...を繰り返すのはどうかなあ。
これなら今やってる最初に ✕ 書くのも勝手に再現されそうな気がするし。
明日の自分にお願いしようかな。お願いします。単純に信号操作コストだけ見ると単に遠い 2 点になっちゃうから、実際の距離と信号操作コストの比率とかを見るといいかもですよ。でも単純に (信号操作コスト) / (実際の距離) だと短い線ばっかり引くことになるかもだからそこも注意して。
5 日目
旅行パートの高速化案が生えたので先にそれをやります。
ギャハー！1 回の旅行パートが 10ms くらいで終わるようになった！
いや、そりゃそうなんだよな。さっきまでダイクストラって呼んでたけど実装 BFS だし、辺数が高々 1800 のグラフ上での BFS を 600 回で数百 ms もかかるわけないんだって。
やったことは単純で、今までは下図のコスト 1 で行ける範囲を毎回 1 ノードずつ探索してたんだけど、これを事前計算で擬似的にコスト 1 の辺（赤矢印）を張ってその疑似グラフ上で BFS をするようにした。
最初からやれという話なんだよな〜アルゴぢからが衰えすぎている。
ともあれこれで A 構築パートでやれることの幅がグンと広がった。
かつて旅行パートシミュレーションの結果はその計算時間から A 構築に活用できないとされていた...だが今は違う!! ギュッ
ニンダイを見ていた。
面白そうなインディーゲームが多すぎる。
さて、旅行パートシミュレーションを A 構築に活用する方法。
旅行パート 10ms になったとはいえ最大でも 300 回くらいしか試行錯誤できないから当てずっぽうに山登りするわけにはいかなくて、ある程度有効そうな選択肢を選びつつ試行を回さないといけなそう。
とりあえず昨日言ってた実際の距離と信号操作コストの比率でなんか良さげな 2 点を繋いでみるみたいなのをしてみるか。
長さ 20 くらいで信号操作コストが重い 2 点を雑に繋いでみた図。黒以外の同じ色の道が連続して A に追加された経路。スコアは微改善程度。
うーん、途中で結構共通の経路を通っちゃってるな...。既に近しい関係にある点は避けつつ長い経路を選びたいな。
しかしまぁ、この雑さでスコア微改善してるのでそれなりに期待しても良いか？
6 日目
A が長いケースでは信号操作コストが大きい 2 点を単純に繋いでいくと同じ経路を通りがちになるので、少しバラしたい。
一方、A が短いケースでは余計なバイパス引いてる余裕はないので、効率が良さそうなところにスパッと引きたい。
両方満たせるのは、ランダムな 2 点を結ぶバイパスを追加したり削除したりする山登りなのかな〜と思った。
↑の山登りを書いて、一応 5% くらい改善したかな？
seed=0（一本しかバイパス引けないケース）とかは確かに最適っぽいなぁみたいなバイパスの引き方をしている。
うーん、もう少し伸びて欲しかったが。
まだ山を登りきれてない感もあるが、さすがにこれ以上の回数回すことはできないし、これ以上伸ばすならバイパスの選び方（今は単純に距離 20 くらいの 2 点をランダムに選んで最短路に引いてる）か、1 周目の決め方か、はたまた旅行パートのロジックあたりを改善する必要がある。
↓とかも、結構悪くなさそうなんですよねえ。
逆にあんまりよくなさそうなのはやっぱり A が長いケースだろうねえ。こういうケースは昨日のイソギンチャク + 同心円（or 渦）みたいな繋ぎ方が良さそうな気がするし。
イソギンチャクは書いてみても良さそう...とは思いつつ、旅行パートのロジック改善の方が全ケースに効いてくるので、そっちかな〜。
一応アイデアはあって、今は次の目的地に到着して折り返すときのことなんか考えずに 2 点間移動を繰り返してるから、目的地に到着するときの信号の状態を次の出発時に合わせて最適なの選べば多少良くなるんじゃないかな〜と思っている。
7 日目
それよりも、単純に最短路を取って旅行したときに通る経路どのくらい偏るんだろうみたいなのが気になってきた。極端によく通る経路があるならそこを 1 周目で繋いだほうが良いだろうし。
こんなんになった。黒線が両都市が A の 1 周目上で隣り合ってる辺で、色付きが 2 周目で隣り合ってる辺、太さが単純に最短路で旅行したときに通った回数。
お〜、これは面白い。重要そうな経路に A の 2 周目でちゃんとバイパスが引かれている。
ただ、1 周目ではどうかというと、
あー！これはいけません！！どうみても繋ぐべき経路があるのにめちゃ途切れ途切れになっている。
L_A が小さいケースだとこれはちょっと致命的かもしれないねえ。
あと辺のユークリッド距離って全然気にも留めてなかったけどこれも長い辺のほうが当然利便性が高いんだよな。
しかしまぁ、この情報を 1 周目でどう活用するかと言われると難しいな。
L_A = N のケースとかもあるから、ひとまず 1 周目は各ノード 1 回ずつ使用するようにしたいんだよね。
思いつくのは、しきい値以上の太さの辺だけで森を作って、その中で最長の長さのパスを選んでいく、とかかねえ。
残った都市は以前と同様適当に DFS して順に拾っていく。
やってみた。が、スコアは伸びなかったなぁ。あれ？
うーん、太い経路以外が分断されるのがマズいのか？
あ、あと A の 2 周目で繋ぐパスの選び方がランダムな 2 点の最短路だから、1 周目と被りがちになって嬉しくないんだ。
試しにまだ A 上で隣どうしになっていない都市だけをランダムに辿って一定の長さのバイパスにするなどやってみたが、全然ダメだった。むーん。
となると、次はイソギンチャクか旅行パートの改善かねえ。
イソギンチャクです。誰が何と言おうとな...。
これに 2 周目で渦巻きを重ねると、こう。わちゃわちゃ。
スコアは、伸びないねぇ...。
うーん、確かに 1 周目渦巻きは 2 週目でランダム 2 点の最短路バイパス引くのと相性が良いんだよねぇ。最短路バイパスが必須となると、結局この組み合わせになっちゃうのか...？
旅行パート改善かぁ...。バグらせる気しかしなくて逃避していたがさすがに手を付けるか...。
これがダメなら結構マズいんですけど、ダメだったら結構マズいのでさっさと手を付けないといけないんですよね。
8 日目
なんか旅行パートやりながら A 構築するみたいなことできないかなぁ。
...想像してみたけど、あまり上手くイメージが沸かなかった。とりあえず手持ちのアイデアを潰そうね。
9 日目
実装途中で寝ていた。
ちゃんと寝たことによる収穫もあって、これ多分 1 回の 2 点間の移動ごとに BFS するんじゃなくて、[次のターゲットidx][今いる都市] な空間で BFS を 1 回すれば良いんじゃないかなあ。
今は 1 回 1 回 BFS を分けてるから、なんか折り返し時に良い選択をする実装に苦労してるんであって、多分そこを連続で探索すればもうちょい楽に実装できる気がする。
ん〜〜〜〜〜〜〜〜、実装できたっぽいけど、微妙。。。。。
確かに 1 回あたりの旅行パートのスコアは気持ち改善してる（でもこれもほんと気持ち程度...）が、計算時間がかなり膨れ上がってしまって A の 2 周目の山登りの回せる回数が激減し結果トントンくらい。
もうちょい高速化できる気はするけど、どうもあまり本質ではなさそうな雰囲気があるし、他の改善点探したほうが良いかなぁ...。
だって今 31M 点だから、こっから 40% 近くスコア減らせるわけでしょ？
このレベルの差があるときは方針から違いそうな気がするよねえ。
今の自分の解法の伸び代がありそうなところについて考えてみる。
- A の 1 周目で各都市を 1 回ずつしか使わないという制約を課している
- その 1 周目も各テストケースに寄り添ったものではなく、平均的に無難な点が出せる配列を使用している
- B の書き換えで毎回すべての要素を上書きしている
B の書き換えで一部分残しておいたら嬉しいケースってそんなにあるかな？
都市間を移動してるときは全力で進みたいし、途中にちらほら残すよりは進むことに全部使い切っちゃったほうが良い気がするんだよなぁ。
あとちらほら残られても探索中にそんなものを考慮に入れられる気がしないし...。
あるとしたら都市について折り返す際に直前に使ってたところ再利用するケースだけど、さっきやった旅行パート改善が言うほど効かなかったからこれもそんなに効かない気がするんだよねえ。
10 日目
やっぱり単純に最短路で旅行したときによく通る道を考慮するべきかなぁと思い、その旅行やったときに 1 回も通らない道を一回消して眺めてみるかと思って試してみると、
ん、なんか孤立してる都市があるな...。ログ出力と自作ビジュアライザのバグどっちだろう。
......いや、どっちもバグってなさそうだな。そんな複雑なロジックでもないし。
.........え！？もしかして、
ウワーーーーーーー！！！！各都市を 1 回ずつ巡るなんかどこにも書いてない！！！！！！あっぶね〜〜〜〜〜〜〜〜〜
N = T なことで完全に早とちりしてしまった。。。。。。
てことは、まず A の 1 周目で必ず各都市 1 回ずつ使ってるのがまず無駄で、不要な都市は切り落として良い。
ただ単純に旅行の目的地に含まれない都市を使わないようにするのは違って、経由地として使い得るのが難しいなぁ。
いや、最短路で一通り旅行したときに通らない都市、もしくは辺は存在しないものとしても良いかもしれないな。
うん、最短路で一通り旅行したときに通らない辺は存在しないものするで確かに A のバイパス山登りをする直前までのスコアは 10% くらい改善しているっぽい。
ただ、その後バイパス山登りをすると改修前と同じ程度に落ち着いてしまう。
バイパス山登りでは目的地間旅行で通らない辺も必要ということか...と思って直してみたけどダメっぽい。
う〜〜ん、バイパスの決め方がランダムな 2 点間を最短路で繋ぐだから、最短路のみで構築されたグラフで作った A と被ってしまってあまりウマみがないということ...？本当か...？
アッ！ウソウソ、不要な都市切り捨てて 1 周目が短くなった分を 2 周目の山登りパートに回すの忘れてたわ！ガハハ
コレ直したらちゃんと 4% くらい改善した。ほっ
いや〜、6 日目からほんとに進捗がなかったので一安心といったところ。
とりあえず提出して 31G(70位) → 32.5G(57位)。まぁ、うーん...。
一応制限時間 10 倍にして回すと 3% くらいスコア改善するから山登りパートで高速化するなりもうちょっとめぼしい候補を絞るなりできると嬉しそうなんだが、多分あんまり本質ではないんだよな〜。
あ〜〜〜〜〜！！！B を全部上書きしない方が良いケース、ある！！！！！
これだ！この青丸！！
こういう次数 1 かつ A 上でも孤立してる都市が目的地の場合は前の信号はほとんど青のままにしておいて、目的地だけ単独で青に変えるのが良いに決まっている！前回更新した青信号のみ通れる制限付きだとちょっと厳しさがある。
いや......まぁこれ次数 1 の孤立都市に限った話でもないか。ちょっと行ってまた戻って来るなら目的地までの信号だけ青にするのが良いのはそう。
問題は、これやったらまた旅行パート計算重くなるんだよな...。今キツいケースだと山登りパート 20 回くらいしか回せてないから、結構キツい。
え、もしかしてこれビムサだったりします？なくはない気がしてきたが、そっちに切り替えるなら A 決定パートを山登りなんかに頼らずにスパッと良いものを決める必要があるんだよな...。
どちらにせよまずやるべきは山登りパートで決めてる内容について天才評価値を見つけることかなぁ。
ちょっともっかい今そこで決めてる内容ビジュアライズさせよう。
都市は A の一周目の順で赤→青。灰色は最短路旅行で通らない都市。
辺は色付きのが A の山登りパートで決めた経路。実線は最短路旅行で使う辺で点線は使わない辺。
なんかこのケースみたいに経路が 4 つ程度だとなんとなく点対称っぽい位置関係の 2 点をまんべんなく選べば良さそうに見えるのだが、
こういうのになると、いやこれはもう山登らんと良い組み合わせなんかわからんだろという気持ちになる。
うーん、無理か...？
それはそうと、[次のターゲットidx][今いる都市] な空間で BFS を 1 回にしたせいで直前の信号情報が扱いにくいのでは？という気がしてきた。
複数の信号パターンで次の探索に進みたいならコレで良いんだけど、信号パターンは固定で良いから前々回の信号パターンも覚えときたいみたいなケースだと次の目的地までの最短コスト経路を都度計算してその分状態を進めるの方が楽、な気がする。
ギー！今から戻すのか...？
（無駄な辺切り落としたグラフ上で）次数 1 の目標都市ってどれくらいあるだろうなぁ。と思って調べたら、seed=0~4 がそれぞれ 30, 97, 115, 78, 81 個。え、そんなに！？
雑にこういう都市 1 個あたり 1 回信号操作を減らせると仮定すると 2~10% くらいスコア削れる計算になる。さすがにそれは見通し甘すぎか...？
まぁでも、わざわざそういう問題設定になってるのにそれを活かさずに終わるのも変な話だしなぁ。少なくとも試してはみるべきでしょうなあ。
11 日目
う〜〜〜〜〜ん、袋小路に入るときはそこだけ信号青にして前回青になってる信号を活かすようにしてみたけど、目に見える改善はなかった。え〜？本当か...？
時間も残り少ないので小手先でできる改善を模索している。
最短路 BFS の探索順を、目的地として設定されてる都市優先にするようにした。
これにより最初に最短路で旅行してみて不要な都市を削除する際、一度も目的地にはならないし迂回路はあるのに最短路に含まれる形で保持されてしまった都市を少し切り落とすことができ、気持ち効率的に巡回できるようになった。
2% くらいの改善。
あ、これはバイパス引く際に訪問頻度が高い都市を含む経路が選ばれがちになったのか。こっちの方がデカいかな。
ということは BFS の探索順だけじゃなく、経路として最短かつ目的地回数の総和が最大なものを選ぶと嬉しそうな気がする。
→ やってみて 0.3% くらいの改善。誤差の範囲だがまぁ採用で。
提出して 31.9G(81位) → 32.4G(76位)
山登り時のバイパスの始点/終点として一度も目的地にならない都市を選択しないようにした → 0.7% 改善。
う〜ん、こんなとこかな。懇親会くらいは行きたいなぁと思っていたのでだいぶ悔しい結果になってしまった。
まとめ
暫定順位 / スコア
80 位くらい / 32.6G 点くらい
方針
- 最短路で一度旅行してみて、一度も通過しない都市・辺をグラフから削除。
- 残った都市を左上から渦巻き状に DFS で探索。訪問順に A に追加していく。
- できた A を基に旅行パートを解く。次の目的地への到達するための信号操作回数が最も少ない手順を BFS で探して実行、次の目的へ〜を繰り返す。
- 次の操作を時間いっぱい繰り返す
- 距離 23 前後のランダムな 2 都市を選んでその最短路上の都市を A に追加。
- A の長さがオーバーしたら以前に a. で追加した都市の経路を削除。
- できた A を基に旅行パートを解き、スコアを更新したら保持。悪化したら a. b. の操作を取り消す。
