解説
方針
配列AからLBの長さ固定で配列Bへコピーするように制限した場合、配列Aが決まるとdpで最適な動きを決めることができます
そのために、配列Aを出来るだけ良い状態に作ろうとします（貪欲法）
配列Aの生成
目的地の組み換え
LBが5以下の場合のみ、以下のような移動経路の変更をしました
0→1→2と移動するとして、0→2→1と移動しても大きく悪化しない場合はそのように経路を結びました
1-2間の経路を使い回すことが目的ですが、LBの小さい時にしか機能しませんでした
共通辺の探索
バラバラな経路を使うより、出来るだけ似たような経路を使いたいため、辺に重みを付けて同じような辺を多くの経路で使われるようにしたいです
蟻コロニー最適化からヒントを得て、1000回シミュレーションをして使われた辺の重みを増やし、そうでない辺の重みを減らす処理を行いました
シミュレーション中も辺の重みに応じた乱数で経路を選択しています
辺の重みの初期値は1000として、接続している頂点が目的地に含まれない場合1/10、1/100と減らして使われにくくしました
目的地間の重み付き最短経路探索
直前の処理で得られた辺の重みを使って最短経路を１つ取得します
分岐があるごとに一番重みの大きい辺を選択して経路を作ります
経路全体の重みの最大化をした方が良かったかな。と終わってから気付きました
配列A候補の生成
目的地間の経路のT通りに対して、優先度を付けて順に候補へ追加していきます
優先度については、(まだ候補に含まれない頂点集合)と(経路で使用する頂点集合)の積集合の要素数が多い順にしました
始めは経路の長いものが選ばれ、徐々にまだ使われていない頂点の多い経路が選ばれるようになります（連続した経路の多様化の目的があります）
追加の仕方は以下のようなイメージで、既にある候補とマージできるならマージをしますが、出来ない場合はそのまま追加します
配列A候補同士のマージ
各候補の端同士を比較して、隣接頂点であればマージします
これを、距離がLBの範囲まで内側へ拡張して全探索します
配列Bへコピーした際に、同じ集合に含まれていれば移動できるためこのような処理が有効でした
近い距離の同じ数字を削除
候補内の距離max(2, LB//3)以内に同じ数字があった場合、片方を削除します
LBの長さでコピーする際に同じ数字が含まれていると明らかに無駄です
その場所にその数字がいることに意味がある場合もあるため、あまり広い範囲ではなく最大でもLB//3までとしました
ランダムに隣接頂点を追加
前の処理で要素数がLAに満たない場合があるため、ランダムに候補と先頭or末尾を選び、その隣接頂点を適当に追加します
その際、一つ内側と同じ数字は選ばないようにしています
再度配列A候補同士のマージ処理を行い、候補をそのまま連結したものを配列Aとしました
dpによる最適化
配列AからLBの長さ固定で配列Bへコピーするように制限した場合、LA-LB+1の状態を作ることが出来ます
配列Bの一部だけを変更した方が自由度が高く、良い解を作れる可能性がありますが同時に探索が難しくなるためこのように制限しました
配列Bの数字によって、移動できる都市が決まるため下のようなレイヤー構造のグラフをイメージすることで見通しが良くなります
今いるレイヤー内で移動する場合はコスト0で移動することができ、レイヤーを跨いでの移動はコスト1で行うことができます
コストが0と1のため01BFSで実装すると高速に探索することができます
実際に重み付き辺を用いてグラフを生成しても良いのですが、移動コスト1がかかるレイヤー移動はどのレイヤーからどのレイヤーへ動いても同じであることを利用して以下のようなdpを考えます
dp[i][u] i番目の目的地への移動で、頂点uにいる時の最小信号操作回数
dpテーブルはinfで初期化して、dp[0][0]=0から開始します
探索後に復元をする必要があり、復元時にはどの頂点とレイヤーを使うのかという情報が必要です
そこで、木構造のビームサーチのような遷移をイメージして以下のようなノードを考えました
Node=(到達目的地数, 現在レイヤー, 現在頂点, 親ノードindex, 移動コスト, 到着フラグ)
ビームサーチでは、ビーム幅で探索量の制限をするのに対して、今回はdpテーブルを更新できた時のみノードを追加します
最後の目的地へ到達したノードから親ノードを辿っていけば、移動してきた頂点とレイヤーを復元することができます
特例として、各目的地へ到達した際はレイヤーが違えばノードへ追加してその先を探索します
理由としては、目的地から信号を切り替えることなく更に同じレイヤー内で移動することができるため、どのレイヤーで到達したかによってその後の移動最適が変わってくるからです
高速化の工夫
他のレイヤーへ移動することを探索する際に、全レイヤーをチェックすると大変なため、現在の頂点から隣接した頂点を含むレイヤーを前もって列挙しておきます
そのレイヤーのみ探索することでループ数を減らすことができます
現在頂点から各レイヤーに移動した際にどの頂点へ到達できるのかを毎回調べていると、これもまた時間がかかります
(レイヤーi, 頂点u)から直接移動できる頂点リストを、要求される毎にBFSで探索しメモ化しておくことで探索量の低減ができました
集合の判定などで、HashSetでなくBitSetを使うことで処理が早くなる場合もありました(初期化サイズによってはパフォーマンスが逆転する)
余った時間の使い方
以上の処理をしても、seed=0などでは200msec程度で終わってしまいます
配列A候補の繋ぐ順番のシャッフルや、候補列の反転、一度も使われなかった数字をランダムに変更するなどをして、最もよいスコアとなる配列Aを探しました
最大でスコアが10程度改善する場合がありました
提出コード
Nimで書いています
ビジュアライザ
参加記
1.問題
個の都市と
本の道路があり、双方向に通行できる
配列と配列
があり、
に含まれる値の都市は信号が青となる
今いる都市から信号が青の都市へのみ移動することができる
配列のうち、
までの区間を自由に配列
へコピーすることができ、この操作により信号を切り替える
旅行計画 の都市を順に訪問したい
信号の切り替え操作を最小化することが目的
制約
都市の数
道路の本数
訪問都市数
配列長さ
配列長さ
2.最初の考察
ベストスコアを考えてみる
訪問都市間の最短距離の合計値を として、配列
の長さを無駄なく使って移動できた時のスコアは
となる（はず）
(例えばseed=0では、 となる)
逆に最悪スコアは、信号切り替え1箇所と移動を繰り返した場合でとなる
長期AHC特有の相対スコア形式なため、ベストスコアが達成できるかは必ず確かめたい。が、ビジュアライザを見る限りそんなパターンはあまり無さそうにも思える
現時点では、焼きなましよりビームサーチ方針の方がありえそう
思いついた方針
- 配列
を決めて、信号切り替えと移動経路を探索する
- 移動経路を探索しつつ、矛盾しないように配列
- 最短経路を組み合わせ、配列
少し実装を進めてみるも、解の出力までたどり着かず。一旦寝る
3.考察2
サンプルコードのビジュアライザを眺めてみる
旅行計画によっては、右端左端右端のように動かされる場合がある
多少遠回りでも、連続した頂点を一気に進めるようにしたい
木構造のような経路のつなぎ方をすると、同じ経路を使いまわせるので良さそう
というか、信号の文脈から普通の道路と同じように考えられそう
主要な幹線道路があって、脇道があってのような感じ
一旦、使う頂点数を最小化してみる
目的地となっている頂点同士を直接結ぶ辺があれば結ぶ
その後、多始点BFSの要領で最短距離で全体を一つのグループにする
seed=0では、使うべき頂点数を400以下にはできた
その頂点のみを使った移動の最短経路を一つ選び、移動経路を先に決定
経路を ごとにハッシュ化してカウント、よく使われる経路を優先して配列
に並べていく
seed=0では、Score=4242が出た
ビジュアライザを見ると、基本1頂点ずつしか進まないが時々一気に進める信号状況があるような感じ
WAとTLEで2ケース落ちたものの、約10Gの得点
1位は更に5倍(1/5)なのでもう一度方針から考える
4.考察3
が小さい時は1マスずつ進むのとそれほど大差はないが、
が大きい時はかなり差が出るためケースによって解法が変わる気がする
ビジュアライザから考えてみる
左：連続で進めるパターン、右：1マスずつしか進めないパターン
明らかに左のパターンが強いが、そうなるためにはグラフ上の距離が近い頂点が配列の中で
以内の距離にいる必要がある
5.貪欲解法
全頂点間の最短距離を求め、目的地間の最短経路を一つ選ぶ
経路で使う2頂点のペアをハッシュ化してカウントする
この時、現れなかった頂点は今後使わない
新しい頂点集合で、再度全頂点間の最短距離を求めておく
頂点ペアの出現回数降順でソートして、その順に配列候補へ入れていく
その際、既に候補にある配列の先頭or末尾にマージできるならする
→経路となり得る連続した集合になりやすい
経路決定パートでは、配列から配列
を抜き出した時に最も次の目的地へ近づける位置を全探索する
6.dp解法
経路探索をdpで最適化する
dp[i][u]=(cnt, layer, parent) i番目の目的地について、頂点uへ行く(最小操作回数, 配列Bの状態, 遷移元頂点)
割と良い動きをしてくれるようにはなった
ただ、目的地を最初に見つけた配列Bの状態で、次へ遷移するので最適ではない
配列Aの良さでかなり変わってくるので、次は配列Aを最適化する
7.配列Aの再検討
候補にした数値列の端同士を比べて、隣接頂点であればマージとしている
ただ実際には、len(B)-1の距離離れていても一緒にコピーできる場合がある
端だけでなく、端と一つ内側なども徐々に許容してマージする
ついでにバグも取って、動作させると長い経路から長い経路へ上手く乗り換えできるような動きを見ることができた
また、候補へ追加する辺の優先度も再検討した
目的地間の経路が長い順に採用していたが、既に候補へ追加した頂点を除いた経路長さでその都度ソートして採用するようにした
これはかなり効果があり、経路として選ぶ多様性が得られたからだと思われる
8.ビームサーチ
dpでは、目的地に着くまでを最適にして、その後は考えられていない
最短で目的地に着く経路で、複数のレイヤーを発見して次の経路への影響も評価するためにはビームサーチが必要
頑張って実装するもまともに動かず。。。
仕方ないのでdpを拡張したものを考える
多分木のような構造で、各ノードには(目的地到達数, 現在のレイヤー, 現在位置, 親ノードindex)を持たせる
探索自体は01BFSで行えるため、スコア計算はなし
目的地への遷移は最速で到達するだけでなく、+1回操作分まで許容した
(到達したレイヤーによってその後の動きの最適が変わるため)
実装すると、LAやLBが大きいパターンだとかなり遅いが、明らかにスコアが向上した
(TLEしなければ40G狙えそうな程度)
バグを取って、色々高速化してTLE回避までしたところ結構なスコアが出た
40G越えの人はまだまだ増えそうなため、もうひと伸びする方針を考えたい
9.経路探索
今のプログラムは、以下の流れになっている
- 目的地間の最短経路を一つ選ぶ(最初に見つけた経路)
- 長い経路から順に辺を選んでマージして配列Aを作る
- 拡張dpで解を出す(恐らく最適解)
最短経路を選ぶところがまだ適当なためここを考える
以下のような感じにしたい
他の経路で使っている辺と同じところを通ることで、配列Aの区間を使いまわせるようなイメージ
フロー問題に落としたり、と考えたが分からず
グラフの問題で何かないか考えていると、蟻コロニー最適化を思い出した
全く同じではないが、同じ辺を多く使うほど辺のスコアが高くなっていく点が利用できれば、良さそうな気がする
実装してみると、辺の選ばれやすさに応じて辺の重みに差ができるため、最短経路を選ぶ際に他の経路でも使っている辺を選びやすくなる効果があった
最短経路を選ぶ前処理として行うことでスコアが改善された（1~2%程度？
10.傾向把握
これ以上スコアを伸ばすのに何をすれば良いか分からなくなったため、あまり気は進まないが提出で細工をして傾向を把握することにした
まず、手元で1000ケース回した時の結果が下のグラフ
横軸がLBで縦軸がscoreで、LBがかなりスコアに影響を与えていることが分かる
そこで、LB<=5 のケースのみ解を出力するコードで提出してみる
結果はACが4ケースで、相対スコアは3.84Gでベスト解の約95%だった
逆に、LB>=20 のケースのみ解を出力するコードでも提出してみる
結果はACが17ケースで、相対スコアは12.2Gでベスト解の約72%だった
明らかにLBが大きいケースで負けていることが分かった
LB=24のケースで一番若いseed=27で確認してみる
seed=27の時スコアは606で、目的地Tの数=600より6多いだけである
目的地1つにつき一度信号を切り替えるとこのスコアになるが、仮に最上位が約72%のスコアを達成しているとすると、スコアは約440となる（本当に？
そのスコアを達成するためには、160回程度、信号を切り替えることなく連続して目的地へ辿り着ける必要がある
そのためには、目的地経路のマージをうまいことできれば良さそうに思える
以前の図を使って考える。理想の「0→1→2」という順番を、「0→2→1」の順に置き換えてみる
その経路を元に配列Aをつくった場合でも、元の経路を辿れそうに見える
貪欲に入れ替えを実施してみるが、LBが小さいケースでは多少効果はありそう
LBが大きいと、遠い頂点同士をつなぐような長い経路がある方が大事らしい
終わりの4日程度は細々した工夫をいれて終了
11.終わりに
直前にビームサーチの勉強をしていた甲斐もあって、dpで最適解を作ることができ自分でもすごく嬉しい気持ちです
他の上位の方の解法は、概要だけ教えられても実装出来なさそうなものばかりなので、実力がまだまだ足りていないと思い知らされました
勝っても負けても、長期コンに取り組むのはとても楽しいので、次はもっと良い結果が出せるようにまだ頑張りたいと思います
