競プロ始めました-kaede2020-

競技プログラミング初心者向けのブログです

THIRD プログラミングコンテスト 2022 (AtCoder Heuristic Contest 017)参加記(問題:Road Repair)

0.はじめに

はじめまして、もしくはお久しぶりです、競プロ歴約3年のかえでです。

今回は、THIRD プログラミングコンテスト 2022 (AtCoder Heuristic Contest 017)に参加しました。開催期間は2023年1月28日(土)12:00から2023年2月5日(日)20:00までの9日間続いた長期コンテストになります。

この参加記が誰の役に立つかというと、おそらく最も自分の役に立ち、他の人の役に立つものではないと思っています。私にとっては備忘録的要素が強く、コンテストの途中で行き止まりに着いたときには元の道に戻ったり、何をすべきかわからなくなったときには、自分の考えていたことを思い出すために読み返したりしています。

一方、役には立たないかもしれませんが、ヒューリスティック・コンテストとは何だろうと思っている人には、その雰囲気を感じとってもらえるのではないかと思っています。

ヒューリスティック・コンテストでは、一人ひとりが違うことを考えていて、違う実装を行っているということ、また、どんなふうに解こうと思っても、それが間違いではないということを伝えたいと思っているのです。順位が上の人の考え方や実装は高得点を取るために必要なものなのかもしれません。だからといって、トップの人の考えや実装を理解する力がなければコンテストを楽しめないかといえばそうではなく、自分の考えを実装してスコアが上がっていく過程はとても面白いのです。だから、私は、私の順位を取るためには何をしたら良いのかということを伝えたいと思います。

それでは、長くなりますがどうぞ最後まで読んでくださればうれしく思います。

そして、いつもならばAtCoderのchokudaiさんやwriterのwataさんに感謝の意を述べるのですが、先日(2023/2/1)ついに、AtCoderが好きすぎて、AtCoderの社員になってしまいました。だから、これからも楽しいコントストが開催されるよう、私自身が微力ながらも力を尽くしていきたいと思っています。

1.問題文

atcoder.jp

2.最初の考察

コンテスト1日目です。先ほどコンテストが始まったところです。

問題文を一読して頭に思い浮かんだのは「ゾンビ島」という問題でした。第15回日本情報オリンピック 予選の過去問(難易度7)で、ダイクストラ法を使って解きます。これの制約はいくつくらいだっただろうかと思います。というわけで、「ゾンビ島」の問題を見に行きました。

当たり前のことですが、今回の問題の方がいろいろと難しくなっていました。ん、当たり前か。(問題の比較に関しては後ほど行う予定。←後日追記:そのときは書こうと思っていたのですが、結局振り返ることはありませんでした。また、今回の問題の概要を追記すると、1回ずつ全ての道をD日間で工事したいというものでした。全ての頂点から全ての頂点へ遠回りをする分がスコア減少に影響します。各辺の工事日をM個出力します。

まずは、ビジュアライザを見ます。

day0のときは何日目に工事するかに応じて各辺が色付けされて表示されるとのこと。

うん。

例を見る day0のビジュアライザ

day1以上のときはその日に工事する辺のみがピンク色で表示されるとのこと。

そうですか。

例を見る day1のビジュアライザ

…。

ビジュアライザから何を読み取れば良いのでしょうか?

スコアに関して、ぱっと目を通すと、各日のランダムな異なる二点間の最短距離の増加量の期待値の平均の総和が低くなることを目標としているので、「見てわからない」→「まんべんなく工事をしている」状態なのかと推測します。

とりあえずは入力の受け取りとダイクストラの実装を行いたいと思います。その後、全ての道の数をD日で割った数を求め、一日にちょっとずつ道を修理していくというコードを書きたいと思います。

修理する道の数が複数になるので、全ての組み合わせの道の最短距離がどの程度増加することかを調べることはできないと思います。なので、大きな迂回路が生じないような組み合わせを考えるところが重要なのかと思います。

ん、これは差分をとって、うまく高速化できたら良さそうな気がします。お、ということは、少なくとも焼きなましはできそう。

最初の考察はこの辺でストップして実装に取り掛かりたいと思います。

3.最初の提出

コードを書こうとして、先ほどまでの自分がもう何を言っているのか理解できなくなります。というわけで、Dでわった余りで辺の数をD等分にして、提出したいと思います。

(時間経過)

ええと、入力の受け取りで、構造体を書いていたら、バグらせました。

はぁ、どんだけバグらせれば気が済むのか。

やっと入力を受け取りました。答えは1からDまでの数をD/N個ずつ作り、出力すれば良いはずです。そして最初の提出をしました。

最初の提出 得点:45705748031

順位表は相対スコアなので、こんな感じに表示されました。

最初の提出(相対スコア:18082996880, 77位/179人中)

1、1、1、・・・、2、2、2、と出力したので、1、2、3、・・・、1、2、3・・・の出力に変えてみようかと思います。その方が自然ですね。順位表の自分のもう少し上に、横並びのスコアがあるので、その数字を出しておきたいと思います。

seed0のスコアが、前者が10080844、後者が10298786。

この結果からもそんな気がしています。まだスコア計算もしていなければ、連続でテストケースもまわしていません。

そうそう、思いついたことをメモ。

  • これ、Nが小さければ、全探索等で解が求まるので、Nを分割して、エリアごとに計算することにしたら、割と良い値が求まるのではないかと思いました。

さて、2回目の提出です。

2回目の提出 得点:47705877230

順位表を見ると、想像していた通り、横並びの一群と同点になりました。

2回目の提出(相対スコア:19,612,283,796 順位41位/204人中)

さあ、一つずつパーツを実装していきたいと思います。

あ、その前に、Kという値があります。一日に通行止めにできる道の数のMAXです。もしかしたら、一斉に通行止めにすると良いことがあるかな?

多分なさそうと思いつつ、seed0の結果を見ます。

やはり、先ほどよりも大きなスコアになりました。情報を得るために、提出をします。K-1とM/Dで大きい方の数値を取ります。絶対スコアでの得点が3倍近くになりました。(今回は得点が低い方が良いのでスコアが悪くなった状態。)

得点:143408182139

したがって、相対スコアで表示される順位表では6357915045点となり、順位は245位になりました。

相対スコアは6357915045、順位は245位/335人中でした
4.うだうだと考える(実装をする気にならない時間)

Nが1000以内、Mが3000以内という制約です。6秒という制限時間でどのくらい計算できるのでしょうか。ワーシャルフロイドO(N^3)ができるのかな?

いつも通りうだうだと考えています。実装はまだしていません。全然わからないので、何か楽をできないかなあと思っています。コストで辺を並べ替えてみようかな。

structにoperatorを入れて、コスト順でソートします(私の使用言語はC++です)。

seed0のスコアは10408176。良くなってはいない感じ。ただ微妙なので、テストケースをそろそろまわしたい気持ちになります。ん、でもビジュアライザを見ると偏った感じがするので、あんまり良くなさそう。

良い日(f=8898)

悪い日(f=13491)

やっぱり、最小全域木かなあ。

もうすぐ21時なので、一旦やめて、ABC287に参戦してきます!

(時間経過)

翌日です。ふと思い出したのですが、この形のビジュアライザ、HTTF本選で見た気がします。問題を解いていないので、Twitterで見かけた程度なのですが、使い方が説明に書いてある以上にあるかもしれない、と思います。

いろいろと試してみましたがそうでもない?

とはいえ、使い方に書いてあった、「頂点をクリックすると色付けされる」という部分を見落としていたので、よかったと思います。ただ、増加量に応じて何色になるのかが書いてないので、まだよくわからずにいます。

頂点をクリックすると、その頂点からの最短距離の増加量に応じて各頂点が色付けされます。

(ビジュアライザ使い方より引用)

ちなみに、これがどこに書いてあるのかというと、Web版ビジュアライザを開いて、上から3行目の「▶詳細」をクリックすると、使い方についての文章を見ることができます。

ビジュアライザの3行目の「▶詳細」を開くと使い方を見ることができます。

ビジュアライザはどんどん親切になっていて、使い方の説明なども増えているのですが、このような箇所に気がつかない人もいるかもしれません。

さて、スコアの計算を書かねば。これができないと評価ができないので必須部分なのですが、ここがいつもネックです。今回書くのはこれ。

AtCoder問題文より引用

スコアの部分だけを取り出すつもりでしたが、関係のある部分を含めたら、結局問題文全体を載せることになってしまいました。工事前と工事後で、ランダムの2点を選んだ時に最短距離は同じか増えます。到達できないときにはその距離を1000000000にするとのこと。んー、書き写していて、やっとわかってきたかもしれません。

到達できないときのペナルティが大きい!

そうかー、工事をしても行ける必要があるということは、最小全域木の方が考え方に近そう!Union Find で考えても良さそう。連結グループが複数になるから。交通網が分断されない方が良いのですね。

というわけで、2点間の距離を求める関数をダイクストラで書こうと思います。

あと、Union Find も準備して、連結グループ数を出すような関数を作ろうと思います。

ちゃんとしたスコアを出す前に無駄なスコア計算を省くことができると、候補を減らせて良いのではないかと思います。

というわけで、ダイクストラを書いているところなのですが、私が持っているプログラミングのダイクストラのコード(アルゴリズム別にABCの提出コードを保存している)にABC252のE問題がありました。Road Reduction という問題名がついたこの問題、今回のAHCの問題と同じように見えました。

頂点0から各頂点への距離を求めたものの、この値が合っているかがわかりません。ビジュアライザで対応した点を探したいと思いましたが、難しい…。やっと見つけたものの、これをどうすれば良いのか…。

seed0の頂点0の座標(190, 512)を探したところ。

んー、頭がついていかないので、もっとシンプルに考えたい。

迂回ってこういうことでしょ?(赤線が通行止め)

上の図では、赤線が工事中で通れない辺です。そのときは、水色と黄色の辺を通れば、通れなくなる頂点はないはず。重みによっては、水色と黄色の道を通った方が近いということもあるかもしれません。

ダイクストラを実装して、ある頂点からの距離は出せるようにしましたが、これだと、全ての頂点から計算し直すと時間が足りなくなるのかなぁ。

最近アルゴのABCに出ていても思うのですが、いろいろなことが理解できていないなぁ、実装力が成長していないなぁ、などと落ち込みがち。インプットだけはたくさんしているのですが。わからないままインプットを続けて、いつかわかるところまで来たら、全てがわかるのではないかと思っているのですが、このままわからないまま終わってしまうかもしれません。

ダイクストラで頂点1から頂点Nにたどりつくまでに使った辺を1にして、使わなかった辺を0にしたら、使った辺の集合は最小全域木と同じ考えになるのかな?

0と1の割合を同じにして出力したら、今より良い結果が出そうな気がしてきました。

やってみました。seed0ではほとんど結果が変わらなかったのですが、seed1のスコアが15053510から271136946になりました(悪化したということ)。ビジュアライザを見たら、day19のあたいがf=6433727.298になっていました。

お、これは通れなくなったときのペナルティがあるに違いありません。場所を特定したい!

わかってもらえるかな、これ。喜んでいるのです。今回は特に感じていますが、とっかかりがなくて、ホント難しい…。こんな風にちょっとでも自分の理解できる何かを見つけたい。

seed0の19日目のビジュアライザ

ビジュアライザを見てわからないかと思いましたが簡単に見つかりました。これです。たどり着けない頂点は。

たどり着けない頂点

頂点から出ている辺を同じ日に全て工事中にしてしまわない必要があるということがわかりました。各頂点から出ている辺はわかるから、工事日を変更したいと思います。どうしよう。他の辺の工事日とのスワップでいいのかな。それとも最終日を変更した日用に取っておこうか。

全然わからないままだったけど、少しずつ情報を整理しようと思うようになりました。

まず、今の得点からわかることをまとめます。

50ケースで絶対スコアが47705877230だったので、50で割った平均は9541175444.6。seed0の得点は10298786だったので、seed0は到達できない頂点のない、とても良いテストケースなのでした。

テストケースの平均値

あと、考慮しないといけないのは、増加量だということですね。

seed0の辺の重みの平均は37168.1でした。seed0のScoreを辺の数で割ると4522.9です。これを増加量の平均と考えてよいのでしょうか。うーん、まだよくわかりません。

5.ローカルでのテストケースを実装して5回目の提出をしました

こんなちょっとしたヒントで急にやる気が出るのが不思議なものです。ローカルでテストケースを実行できるようにしました。やったことはこれだけです。

  • 各頂点からのびている辺にできるだけ違う日を割り当てる

100テストケースをまわして、初期解と比べます。40ケースで良くなって、60ケースは悪くなっていました。提出をした結果、絶対スコアは下がりました(結果が良くなったということ)。

絶対スコア:41856112375

相対スコアも上がりました。(提出をしていない同点だった人のスコアが13,583,645,753だったので上がったことがわかりました。)

相対スコア:14,371,516,443 251位/588人中

というわけで2日目が終了しました。自分にしては順調かも。

6.たどり着けない頂点がなくなるまで時間いっぱい山登り

3日目朝です。何でたどり着けない頂点があるのだろうと考えていましたが、図にするとこんな感じのところができていそうです(下図)。自分の書いた条件だと、1本は他の頂点とつながっているというこしか表せていません。離れ小島みたいなものがありそう。

連結されていないたどり着けない頂点

というわけで、Union Find で連結を確認したいと思います。倍近くのところに横並びの得点集団ができていて、そこが、この条件を追加した場所なのではないかと思っています。今の相対スコアで自分は13百万なのですが、20百万くらいの得点です。がんばろー。

帰宅しました。日中、考えたことを書きます。

  1. それぞれの辺をいつ工事中にするかを決める
  2. 各日の辺をつないでUnion Find で連結グループが1であるかを確認する。
  3. 全ての日が連結だった場合はそのまま出力する
  4. 連結グループが2以上になったら、工事中の1辺と今通れる1辺を入れ替え、2に戻るを時間いっぱい(6秒)行う。

おー、良さそう(自画自賛)。シンプルだし、自分でも実装できそうです。なんかお風呂に入っている間に、高得点を出してピースをしているツイートを想像しちゃったから、フラグ立てちゃったなと心配しているところです。

書いた!

6秒を使っているので、100ケース回す時間が待ちきれなくて、テストケースを5個試しただけで提出します。でも、確実に良くなってる!!!結果がめちゃめちゃ楽しみです。

絶対スコアは4185611235から10275422022に下がりました!

相対スコアは21,801,711,828点、順位は216位/691人中でした

おおー、上がった!

そして予想した場所に来た気がします。ここからが本当の勝負なのかな?ただいまの時刻は2023年1月30日の23時12分。今日はここで寝たいと思います。

7.順位表のトップが50,000,000,000点!?

翌日の朝です。昨日はにやけながら寝ていました。

こういうときは、ホント楽しいのです。ヒューリスティック・コンテストは。

まだまだやりたいこともいっぱいあります。

ところで、Twitterを見ると、タイムラインがざわざわとしていました。理由はトップのPshyoさんの得点です。理論値だということでした。私には口々にツイートしている内容の意味がよくわかりません。それでも何だかがっかりした雰囲気を感じ取りました。

トップのPhyhoさんの得点が50,000,000,000になっていました

問題文を確認しました。

相対評価スコアの出し方(AtCoder問題文より引用)

なるほど。現在、50のテストケース全てでPsyhoさんがトップだということなのですね。最適解が求まったというツイートも見ましたが、どうなのでしょうか。1ケースでもPsyhoさんを超えることができれば崩れると思うのですが。もし、この得点を取る人が複数現れたのなら、本当に最適解が求まってしまったのかもしれません。私は自分のしたいことをするだけなのですが、トップの得点にも注目していきたいと思います。

8.ライバルには負けたくない

夜です。帰宅しました。昨日は216位だったのに、今の順位は270位。提出者も747人に増えていますが、それでも下がり方がすごい。この辺りの順位は皆点数が似通っているので、突き抜けたいところです。

いやがって後回しにしていたスコアの計算を書く日がきました。

Rustからコピペができる人はうらやましいなぁと思います。Rustは未履修なのですが、toolsフォルダ内のsrcフォルダ内に入っているlib.rs(問題文のツールのローカル版をダウンロードします)を開くと、compute_scoreなる名前がついているものがあって、これがスコア計算をしているっぽいのです。

  • 工事をしていないときの2頂点の距離を求める。
  • 各日の工事中のときの2頂点の距離を求める。
  • 差を足す。
  • N(N-1)で割る。
  • 各日の不満度を1/Dずつ足す。
  • 1000倍する。

ここで悩んでいるのが、全点間の距離を求めるのにすごく時間がかかるのではないかということです。ここがわからない~!

ああ、お風呂入ろ。こういうときは。

問題文を読み返していたら、リンクがありました。「2-辺連結」をクリックすると、「k-辺連結グラフ」に飛びました。う、難しい。一生懸命読んでみます。今回の場合、各頂点からの辺は2本であるということでいいのかな?

入力例の1日目の502(358,663)を選択したところ

入力例のビジュアライザをじっと見ます。ブルーの頂点は良い値な気がしてきました。黄色や黄緑の頂点の方が悪そう。そして、赤い頂点が一番悪そうです。赤い頂点を囲む辺を見てみました。

推測でしかないのですが、矢印の3か所で、最短距離の辺を3つ連続で工事中にしているように見えました。その結果、だんだんその後の頂点が影響を受けているように見えます。

最短距離の辺を3つ連続で工事中にしている?

Q:最短距離を連続で工事中にしないようにできる?

A:ん、これは最小全域木に使う辺のことでは?

おー、何か結びつきそうな。でも実装するにはもう少し考察を深めたい。

最初にやった最小全域木とそうでない辺をブレンドするのが意外に良いのかもしれません。それに連結グループ数1にする部分を足せれば。

そうかー。初期解を変えてみよう。今は、1,2,3,・・・,Dを繰り返したものを初期解としています。ええと、最小全域木を初期解としたコードはどこ?

変えてみました。

たどり着けない頂点ができてしまうようです。5個試しただけだと原因がわからないので、100ケース回してみます。途中バグっていたので、修正します。100ケース回した結果は…。え、良さそう!合計は明らかに減っています。100ケース回した結果は、51/100ケースで良くなっています。

提出します。

結果は下がってしまいました。夜も更けてきたので、結果についての考察は明日に繰り越したいと思います。

提出前

提出後
9.天啓が降ってきた(と思ってからの暗黒の3日間)

時間がだいぶ経ってしまいました。今日の日付は2023年2月2日です。

この間、手をつけることができませんでした。というのは、熱が出たからです。最初は吐き気でした。その後、熱が上がって起き上がることができません。今日は微熱になり、午後に発熱外来に行ってきました。結果はコロナもインフルエンザも陰性でした。熱も下がりました。

ずっと寝ていたのですが、ひらめきました。

工事中にする辺の両端からの距離を計算して、各日の距離の増加が等しくなるようにしていったらどうかということです。できるだけ差が少ないように工事にする辺を振り分けるようにします。工事中にする辺からの距離を調べるだけなら、計算量を減らすことができます。ええと、増加量ではなく、素直に増加率の和が一番少ないものを出力すれば良さそうです。

  1. 工事0の全距離はワーシャルフロイドで求める
  2. 初期解は最小全域木の辺を求め、最初の辺を1、次に使う辺を2、3、・・・と順に工事日を割り当てる
  3. 工事予定の辺の両端からの距離を求め、元の辺の重さと比べた増加量を足していく
  4. ランダムで辺の工事日を交換し、時間いっぱい山登り

4の辺の工事日を交換する方法はランダムではない方が良いかもしれないなと思いつつ、1から4を実装します。

うーん、実装してみたものの、得点がよくなりません。どこが間違っているのだろう。今日はここまでにします。

翌日です。2023年2月3日になりました。寝ながら考えました。方針を変更します。

  • 工事がないときのワーシャルフロイドはやめて、辺の重みを使う
  • 到達できない頂点があった場合、それより後ろの辺で別の工事日の辺とswapする

実装をしてローカルで100テストケースをまわしますが、思ったような結果が出ません。思ったような結果というのは到達できない頂点があったとき、距離が大きくなるので、自然になくすことができるかと思ったのですが、そうならないということです。

初期解を変えてみようかな。

どうしたら良いかわからずに途方にくれていたところ、テストケースをまわしたときの違和感に気がつきました。100ケース終わるのが早すぎます。これまで、5ケースとかで試していたので、その違和感に気がつきませんでした。

コードを見直します。

すごいバグに気がつきました…。

入力1ケースにつき6秒を使っているつもりが100ケース全体で6秒になっていました…。

何をやってるんだか...。100ケース、時間を使って、ちゃんとやりました。すごく上がってます。ローカルだけでなく、一度提出するべきでした…。え、ホント泣けるんですが。提出してきます。

これまでの提出履歴

提出してみたら下がりました。記憶を思い返してみれば、結果がおかしいので、昔のコードに戻していたのでした。自分の結果が何一つ信じられない状態です。

んー、ここは前向きに、今やっと確かな何かにたどり着いたと思うことにします。

唯一救いがあるのは、良い結果が出なかった未提出のバグっていたコードを保存していたことです。コードを入れ替えて、今度こそ、今度こそ、と願いながら、100ケースをローカルで実行します。

上がってる!距離の計算はバグってそうですが、Union Find も組み合わせているので結果は良くなっていそうです。ドキドキしながら提出します。

あ、...。結果が出る前にわかったことがあります。TLEしています。

TLEしています

今回は相対スコアなので、絶対スコアは0点になりますが、相対スコアの順位表にはTLEしていなテストケースの得点が反映されると思います。出ました。

え???TLEしたのに得点が今までより高くなっています!

相対スコアは21,287,605,256点、順位は342位/878人中でした。

どういうことだろう?と思って、提出の詳細を見ます。TLEは50ケース中1ケースだけでした。

TLEは50ケース中1ケースでした。

久しぶりの得点更新にほっとしました。やっと体調も回復してきたので、明日もがんばりたいと思います。

10.コンテスト8日目(最終日前日)

2023年2月4日です。最終日前日の土曜日。

ついにバグを見つけました。ダイクストラのコードを一部間違えていました。バグはまだありました。入力を参照するときの添え字を間違えていました。やっと、もっともらしい増加率が出てくるようになりました。

さて、テストケースをまわします。どんな結果が出てくるのでしょうか。2、3個試した結果は、ベストに近い点数になっています。極端に悪い数値がなくなった気がします。

100ケースのうち、50個くらいの結果をみて、もういいや、提出しようと思います。100個終わるのが待ちきれなかったのです。

ところで、提出している間に、ちょっと余談を。

毎回、AHC終了後には感想会スペースを開いています。今回も最初はスペースを開こうと思っていました。一方で、スペースの画面の共有ができないという欠点を何とかできないかという思いがありました。かといって、Discordで限られた人だけで感想会を行うというのも、自分の理想とは異なっていました。しかし、AtCoder社員になった今は第三の選択肢が浮上しました。そう、AtCoder Live での公式YouTube配信です。(中略)というわけで、2月5日20時半からYouTubeでAHCの放送を配信したいと思っています。タイトル「(仮)AHCラジオ第1回」。ただ、これまでスペースで開いていた感想会とは異なり、もっと気楽に、親しみを感じてもらえるような放送を行いたいと思っています。楽しんでもらえると良いけど。ドキドキします。ホントに。

さて、結果が出ました。前回はTLEだったので得点が0。今回の絶対スコアは1,631,823,748でした。前回と比べて今回の得点が良くなっているのか悪くなっているのかわかりません。相対スコアは21,272,092,397点、360位/906人中でした。順位を見ると特に変わっていないようでした。

得点はいつのまにかものすごく低くなっていました。だから上がると思ったのですが。残念。

絶対スコアは1,631,823,748でした。

相対スコアは21,272,092,397点、360位/906人中でした。

こつこつとコードを修正します。そして、今度こそ上がったでしょうと思うようなローカルの結果が出たので提出します。ローカルの結果はこんな感じでまとめています。これまでの全ての出力より、16ケースで最小値を更新し、前回の結果よりも100個中72個で良くなっています。

Excelでテストケースの結果をまとめています。

結果が出ました。絶対スコアは1,631,823,748から1,006,020,148に減っているのに、順位はそこまで上がりませんでした…。

やったことです。

  • 到達できない頂点があったとき、これまでは1つずつ交換していたけど、1度に全部ランダムで入れ替えるようにした。
  • 到達できないときのペナルティで1000000000点を足すようにして、増加率が一番少ないものを出力するようにした。

絶対スコアは1,006,020,148でした。

相対スコアは21,615,805,710点、327位/913人中でした。

思いっきり突き抜けたいという思いは持ち続けているものの、現実はなかなかうまくいきません。それでも順位が少しよくなったと思うべきでしょうか。きっとアイデアが足りないのでしょう。テストケースで山登りの様子を見ます。思ったよりまわっていないようでした(10回くらいでした…)。Union Find の部分を削りました。

絶対スコアは998,250,880でした。

ついに絶対スコアが1億をきり、998,250,880になりました。しかし相対スコアは21,672,448,930点で、順位はほとんど変わらず、328位(918人中)でした。いつのまにか参加者が900人を超えています。

相対スコアは21,672,448,930点、順位は328位/918人中でした。

うーん、初期解が悪いのか、高速化が足りないのか、近傍の良い選び方があるのか…。悩みます。初期解を一番最初の1,2,3...と並べていくようにして、隣と入れ替えるようにしてみたらどうでしょうか?

  • まずは初期解に戻してみました。

ちょっと悪くなりました

ちょっと悪くなりました

→結果はちょっと悪くなりました。

  • 2回作っていたグラフを1回だけにしました。

わざわざ工事中を除いた辺でグラフを構築していましたが、よく考えたらダイクストラで工事中のときにcontinueすれば良いだけだったことに気がつきました。

少し上がりました

少し上がりました

→結果は少し良くなりました。

一か所ずつ変更してみましたが、もっと根本的に考え方を変える必要がありそうです。明日は最終日ですが、そろそろ21時になるので、今からABC288に出てきます。トヨタプロコンのオンサイト予選です。私はきっとお仕事で当日会場にいると思います。

11.コンテスト最終日(2023年2月5日)

2023年2月5日の朝です。距離を求める際にメモ化すれば、少し早くなりそうです。

ところで、今回、文字ばかりで読みづらいと思うのですが、それは私も同じです。どういうことかというと、ビジュアライザをうまく活用できていません。イメージとしては、1頂点から他の全ての頂点へ向かうとき、ある1辺が良くない値だと、そこを通過しないと先にいけない全ての頂点が影響を受けそうです。問題文をもう一度読み直して思ったのは、そのようなネックになる最初の辺を見つけることができるのかということ。

というわけで、ビジュアライザをじっくり見ることにします。1辺を工事中にしたときに、迂回路が長くなってしまうと、良くないことがわかります。

工事中にした1辺の迂回路(左右)

ということは、辺の重みよりも、何頂点を経由している方が大事なのでは?

時間いっぱい辺を交換して山登りをしている基準は、辺の増加率を見ていました。それでは効率が悪そうに思えてきました。

  • 2辺を経由したらたどり着くのは一番効率が良さそう(経由頂点数は1)→OK
  • 5辺を経由してたどり着くのは遠回りをしていそう(経由頂点数は4)→工事日変更

こんな感じで実装を変更したいと思います。

(時間経過)

実装が進まないまま時間が経ちました。Twitterで得点を伸ばしているらしきコメントを見て、うっかり順位表を見に行ってしまいました。そして今、心がざわざわとしています。やってはいけないことをしてしまいました。落ち込む、もしくは焦るだけなので。AHC期間中にやってはいけないことのひとつです。特に最終日は。

落ち込んで、お皿を洗っていたのですがひらめきました!

さっきの経由頂点数を多い順に並べて、上位10個くらいずつ、工事日を入れ替えてあげればどうでしょう。今度こそ良くなる気がします。残り時間が心配ですが。

書きました。3個みたくらいだと、良くなった感じはしません。悪くなった感じもしないので、100テストケースをまわしてみて、結果を比較したいと思います。

提出した結果は、絶対スコアが1,037,248,776でした。

絶対スコアは1,037,248,776でした。

相対スコアは21,255,585,558点、順位は413位(964人中)でした。

相対スコアは21,255,585,558点、413位/964人中でした。

うーん、あがらない。がっかり。あ、でも評価を経由頂点を少なくなるようにしていたので、スコアに戻してみようと思います。あ、そうだ。あと交換する辺をランダムにしていたのを、次に交換したいと思っている辺と工事日が違うなら入れ替えてみたいと思います。

seed0の値は10050431になりました。

seed0のスコアは10050431でした。

時刻は14時48分。ここで残念なことが起こりました。眠くなってきてしまいました。なので、お昼寝したいと思います。起きたらもう取り組む時間がないかもしれません。

絶対スコア1,024,445,053

相対スコア21,432,257,758点、389位/966人中

wataさんからの連絡が来て目が覚めました。AtCoder Live で「AHCラジオ」の配信枠を作ってくれていました。うん、集中力が完全に切れました。今回はここで終了したいと思います。

緊張してきてしまいました。

がんばってきます。

12.終わりに(2023年2月7日更新)

2023年2月7日の朝です。今回の問題の復習がまだできていません。思った以上に仕事が忙しくて、競プロの時間が取れていません。二分探索でいうところの上限付近にいます。早くちょうど良いところを見つけて、競プロの時間を確保したいものです。

今回の問題の難しかったポイントをあげると、

  • 正しいスコア計算をしようとすると時間がかかる(1~2秒かかる)

ということでした。だから、スコア計算は「全部ではなく、いくつかに限定して計算する」ということが必要でした。

うーん、難しかった。1個だけだとダメだったので、もう少し増やしてみるといった考え方が必要だったのですね。早くいろいろと試してみたい。

最後に「AHCラジオ」の話を書きます。

コンテスト後に何がいちばんあると良いのかを今考えています。それぞれが自分の解法を話す場所なのか、解説なのか、1位の解法なのか、基本的な解法なのか、その日が良いのか、後日でも良いのか、など。

これまでAHCに参加してきて思っていたことは、解説が欲しいということでした。解説放送にするにはクリアできていない部分が多くて別枠になりましたが、ご覧くださった方、いかがでしたか?蓋を開けてみれば、がっつり解説してもらったなと感じたのですが。

どういう方向になるのかはまだわかりませんが(先ほど挙げたように何を優先するのかで変わってくるため)、社員になるとこんなことも実現できるのだなあと驚きとともにうれしく思っているところです。AtCoderすごい!(←心の中のファンの声)。第1回にしたのは、これからも続ける私の意志表示です。未熟な私ではありますが、これからも自分のできることしていきたいと思っています。

ここまで読んでくださり、ありがとうございました。そして、コンテストに興味を持ってくださった方、親しみを持ってくださった方がいたら、うれしく思います。

www.youtube.com

13.最終結果(2023年2月7日更新)

システムテストが終了しました。暫定スコアのときは418位でしたが404位に上がっていました。最終提出者は1002人でした。2000テストケース中、7ケースでTLEしていました。

最終順位:404位/1002人中

1993ケースの結果(TLEの7を除きました)

AHCのRatingは10上がって1361になりました。

AHCのレートは10上がって1361になりました