AHC 017 のおもいで (THIRD プログラミングコンテスト 2022)
AHC017 1/28(土)-2/5(日)
概要:
N個の地点とそれぞれの地点を結ぶM本の道路があり、それをD日間ですべて1回(1日)ずつ工事したい。工事できるマンパワーは1日あたり道路K本まで。
工事中の道路は通れないので、各地点にいる人たちは別の地点に行くために迂回する必要が出てくる。N*(N-1)通りの地点同士の組み合わせそれぞれでの、迂回しなくてはいけなくなった距離の合計値(というか期待値)が不満度として毎日加算される。
不満度ができるだけ低くなるような工事計画を考えよ。
制約
500 <= N <= 1000
500 <= M <= 3000
5 <= D <= 30
ceil(M/D) <= K <= 2*ceil(M/D)
制限時間 6秒
1日目(1/28 土曜日)
とりあえずABC287だけ参加。
マラソンに参加すると時間が溶けるし脳のリソースが全部持っていかれるのでその覚悟をつける日。
2日目(1/29 日曜日)
参戦。
問題文から、1つの点からは2つ以上の道路が出ているのが保証されている。
なので、できるだけ同じ日に同じ点からの道路を2つ以上潰さないようにすればいいんでは?なら、その点から別の道路通れるでしょう?
できれば遠い道路同士を工事したほうが通せんぼにならなくて良さそうだけど、それは実装がよくわからないからちょっと置いておく。
各点ごとの持っている道路のリストを作って保持。一つの点から出る線のそれぞれを、1日目から均等に振り分けていく。
なかなか良い線かと思って提出したが… 全然だめ。
得点 : 23930843999 (=2x10^10)
ビジュアライザを見ると黒くなってしまう点がいくつもある。到達できない点ということか。なんで?同じ点からの道路はできるだけ潰さないようにしたのに。
そもそも毎日全ての点に到達できるような方法が常に存在するのか?
もしくは、1日くらい到達できない日があっても他の日が全て直通になるならむしろそのほうがいいのか?
ということは平均的に工事をやっていくより、どかっとやって残りの日はフリーにしたほうがいいのか?
到達できないとペナルティは10**9だが、wの上限が10**6でMの上限が3000なら、到達できないほうがむしろ満足度高いとかある?
重みのパラメータは読み込んですらいない。どうやって使おう?
※どうでもいい苦労したこと
コードテストでのoutputをビジュアライザに貼り付けてみようと思っても、outputが長すぎて最後が省略されてしまい使えない。
google colabでやるしかない。まずは環境構築から…
入力を全部コードとして貼り付けたらcolabが固まる。
ファイルから読み込むようにする。
これで、
で、やっとスタート地点に立てた。
3日目(1/30 月曜日)
スコア計算関数を実装。
ある点を引数にとって、その点から全部の点に対してダイクストラ法をする関数を作成。
その関数に対して1から順番に点を渡して行って戻り値を合計していき、合計の戻り値を返す別の関数を作成。
流石に全部やると重すぎなので、全体の1/10くらいの点だけで評価するようにした。
2日目の結果からスタートして、randomをとって、適当に辺をswapしていく。渡した日から、一個もらう。Kの上限があるので、それを超えないようにするため。
スコアが上がれば、swapを確定。悪くなれば、swapを取り消し。
提出したところ、スコアが爆発的に高くなる。喜んで順位を見ると、AC内での順位はほぼ最下位。
得点:849794673368 (=8x10^11)
うーん。
あ!今回の場合、スコアは「不満度」なので、低いほうが良い結果なのか!
ということで、”スコアが下がれば、swapを確定"にした。
注釈を消し忘れてWA。
いつの間にかAM3時。とりあえず寝よう。
4日目(1/31 火曜日)
クラスカル法でやってみることを思いつく。
この3日間やった分はもったいないが全部消す。
とりあえず、「たどり着けない」場所があるとスコアが悪化しそうな雰囲気があるので、それを避けるような方法をとってみる。
最小全域木その1に挙げた道路がまったく全て使えない状態を作って、そこからもう一度、クラスカル法をして、最小全域木その2を作成。
作戦としては、「最小全域木その1の道路は全部開通してます」の日をできるだけ作って、その間にそれ以外を済ませてしまう。とくに、最小全域木その2はとっとと(初日に)済ませてしまう。
最小全域木その1以外の道路が全て済んだら、残りの日でゆっくりと最小全域木その1をやっていく。その間は少なくとも最小全域木その2は開通しているから、ほぼ「たどり着ける」はず。
問題点としては、
①最小全域木その2が成立するかどうかという問題
②「最小全域木その1の道路が全部開通しています」のうちに、他の部分の工事を全て終わらせられるかどうかという問題
①に関しては、もう仕方がない。できるだけ多くの場所にたどり着けるならいいでしょう。
②に関しては、まず、最小全域木その1の道路数はN-1。KがN-1以上なら1日で最小全域木が終わるのでK>=N-1を、制約からなんとか数学的に保証できないか紙の上で試行錯誤したが、どうも保証できないことがわかった。しかたなくテストケースを当てはめようとしたら余裕でKはN-1以下だったので仕方ない。諦める。けれども、実際やってみると大体のケースではうまく行っているようすに見える。
提出してみると…
あまり良くはなっていない。
得点:18682571846 (=1.8x10^10)
前回のAHCでは「焼きなまし」やらなんとかキーワードがあったな…と思い出し、スコア計算をしてなにか改善をしていく感じかとおもったが、良い計算方法がわからない。普通に計算量多そうなんですけど…。何かスコア計算の良い方法があるのか…?
ビジュアライザがめちゃ重いところから考えると、偉い人がつくった計算方法でもある程度の計算量はかかりそう。
なので、
スコア計算は難しそうなので諦める。
ランダムでうんぬんよりは、理屈で良い方法を探していく系なのだろうか。
5日目(2/1 水曜日)
ある1本の道路について考える。
その道路がないことで、その道路の両端の点同士の距離はどのくらい変わるかを考える。
すべての日で、「ある一本の道路」がない状態を仮定して、「片方の点から出発して、反対側の点についたら終了」のダイクストラ法で計算して、
「その道路がないときでも、両端の点同士の距離が一番短い」日に、その道路の工事をすることにする。その日の工事数がK以下なら。
これはいける!と提出したが、あまり変わらず。
もう、これ以上の改善は無理かも。みんなどれだけ天才なの
得点:20660002917 (=2.0x10^10)
6日目(2/2 木曜日)
考えていたら寝落ちしてしまった。
7日目(2/3 金曜日)
思いついたけど実装が大変そうすぎてやっていなかったことを気合い入れてやる。
川に橋がかかってるとするでしょう。目の前に橋が一本、もうちょっと行ったところにももう一本、橋があって、向こう岸に行くならとりあえずどっちか使えば良いかなと思っていたとする。それが2本とも工事中で、その次に(3番目に)近い橋はめちゃ遠かったら…、辛くない?ということで、
ある1本の道路について、その両端の点同士の、「2番目に近い順路(迂回路)」を検索する。
全ての道路について、tuple(道路i, set[道路a,道路b,道路c])といったような組みをあらかじめ作成する。
道路iの工事日と、(道路a,道路b,道路c)のいずれかが同じ日に工事をしていた場合は、そうはなっていない日(で、かつ工事件数がK以下の日)に道路iの工事日を投げる。swapは面倒になるのでしない。
投げた元の方の日に他の日から道路iの工事をまた渡されてしまわないように、「その日は開けとかなければいけない道路」setにメモする。
投げられた方の日は、道路a,b,cの工事はもう受け取れないので、「その日は開けとかなければいけない道路」setに道路a,b,cをメモする。
というのを、全ての道路でやる。
提出すると、スコアはものすごく改善。
得点:901396620 (=9.0x10^8)
500位くらいだったのが一気に200位台に!
でもこれ以上思いつかない。
8日目(2/4 土曜日)
ABC288がんばる。
難しいんですけど。
9日目(2/5 日曜日)
もういいか、バグ作ってWAになるのも嫌だし。
とおもいつつ、7日目のコードだと500msecで終わるのがなんだかもったいなくて、少しランダムで改善させてみる。
「ある点からある点まで」の最短経路を適当にみてやると、工事中の場所を迂回したあと、元のルートに戻らずにそのまま別ルートで進んでいることが多くあるように見える。
ということは、日によっては、「その道路ほぼ使っていないよ」な日があったりするのでは。その日にちゃっかり工事日をずらせないだろうか。という考え。
でもこれはどうやって実装すればいいのかわからない。別の点同士でとても重要な道路になっているかもしれないし…。
コンテスト期間も終わりなので、とりあえず一部分だけでもと思い、実装する。
適当な2点x,yをとって、7日目までの「出力」にしていた全ての日と、まったく工事をしない日に対してxからyへの移動コストと移動ルートを計算する。
移動コストが最大の日について、注目する。
その日に「まったく工事をしない日」のルートと同じルートを使わせられるように、その日の工事をずらせないか検討する。
まず、工事をずらさなければいけない道路をピックアップする。おそらく複数の道路が拾われるので、それぞれの道路の工事日について、適切な移動先がないか検討する。
条件は、
移動先の日で、その道路が「開けておかなければいけない日」になっていないこと。
移動先の日に、その道路の「迂回路」がすでに工事されている状態ではないこと。
移動先の日の、元々の「xからyへの最短ルート」にその道路が含まれていないこと。
計算量が多くて大して回らないうえに、条件が厳しすぎて、改善できたのは1ケースあたり道路20本程度。ただ、スコアはやや改善。
得点:777213859 (=7.7x10^8)
コードは注釈や空白行も含めてだが300行程度に。
WAがこわい。
TLEもこわい。ので4秒でbreakするようにした。
まとめ
・まずクラスカル法で基本型を構築。「行けない」状態は発生しないようにする。
・「最短路」か「最短の迂回路」のどちらかは開けるようにする。
・遠い点同士でも、コストがかかりすぎの場合は、他を犠牲にせずに「最短路」が開けられないかどうか繰り返し試してみる。
終了後の放送
・少ない点で近似スコアを得る。毎回フルスコアをとるのは時間的に厳しい。
・とりあえず高速化して山登りは基本。
・手元で1時間とか回してみるのがいい。その結果をビジュアライズすると気づくこともある。
・近い道路はむしろ一緒にやったほうがいい。工事の移動先日は隣接する道路の工事日にしてみたほうが賢い。