競プロ始めました-kaede2020-

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

AtCoder Heuristic Contest 003参加記

 お久しぶりです。競プロ歴1年のかえでです。

この参加記では私がどのようにコンテストに取り組んだかを書こうと思っているのですが、今回は書き進むうちに、コンテスト中の自分の失敗が、次から次へと出てきて、恥ずかしい気持ちでいっぱいになりました。読んだ人はきっと呆れることでしょう。

それでも公開しようと思ったのは、ヒューリスティックコンテストに参加してみたいけど難しそうだと思っている人に、こんな雰囲気だということ感じてもらえたらなと思っているからです。

今回は特に失敗談ばかりなので、それでも良いと思ってくださる方だけ読み進めていただければ幸いです。

AHC003は 2021年5月22日(土)12:00から5月30(日)20:00まで行われていました。コンテストが終了し、システムテストが終わった後の最終結果は、1000人中498位でした。コンテスト終了後は、もっと何かできなかったのだろうか、いや、できるだけのことはやっただろうと自問自答を繰り返していました。

コンテスト終了後に、いろいろな人の解法を見聞きしているうちに、自分にとって難しかったこと、思いつかなかったこと、しなければいけなかったことについて、少しずつわかってきました。

そこで、このブログを書きながら、まちがっていた部分を修正していければと思っています。

f:id:kaede_2020:20210621194132p:plain

AHC003の最終結果は498位でした。
1.問題概要

最短経路を答える問題。

・30×30頂点の無向グリッドグラフがある。

・辺の長さは未知である。

・スタートとゴールの座標が与えられるので、ゴールまでの道順をU、D、L、Rを使って答える。

・道順を答えると、通ってきた道の、およその正しい距離を教えてくれる。

インタラクティブ形式でこのやりとりを1000回行う。

・得点は以下の方法で計算される。

AtCoderより引用)

k 番目 (1k1000) のクエリに対する最短路長を ak、出力されたパスの長さを bk とすると、以下の得点が得られる。

f:id:kaede_2020:20210704151503p:plain

得点の計算式

・ゴールにたどり着かないとき、範囲外に進んだとき、同じ道を2回通ったときは得点は0になる。(プレテストではWAが出る。)

2.方針

まず最初に思ったのは、 問題の設定が「最短路アルゴリズムを活用した道案内アプリの開発」だったので、実際に存在しそうだなということでした。「最短経路問題」で検索すると「A*探索アルゴリズム」がヒットしました。「ダイクストラ法を推定値付きの場合に一般化したもの」ということで読んでみましたが、A*探索アルゴリズムの実装は難しそうだと思いました。そこで、最初は素直にダイクストラ法を使った実装をしてみようと思いました。

3.ダイクストラ法の経路復元

自分の知っているダイクストラ法は最短距離を求めるものでした。最短距離はわかっても、どのルートを通ると最短距離になるかはわかりません。調べてみると、最短距離のルートを求めることを経路復元ということがわかりました。「ダイクストラ法 経路復元」で検索すると、経路を復元するコードの書き方がわかりました。また、頂点は座標ではなく、「x座標×30+y座標」として頂点番号をつけることにし、縦の道と横の道をそれぞれ別の配列で持つことにしました。

4.インタラクティブ形式について

今回は出題形式は、インタラクティブでした。インタラクティブ形式の問題は、競技プログラミングコンテストに参加していても、ほとんど出題されたことがありません。私が最初にインタラクティブ形式の問題を見たのは、AtCoderの常設中コンテストの中にある、「practice contest」の「B - Interactive Sorting」でした。そこには、

AtCoder「practice contest」より引用)

これはインタラクティブ形式の例題です。初心者向け問題ではありませんので注意してください。

初心者の方は、AtCoder Beginners Selectionに挑戦してみてください!

と書いてあったので、初心者だった自分は素直にとばしました。

次に見たのは、「AtCoder Petrozavodsk Contest 001」の「C - Vacant Seat」でした。これは、AtCoder Problems のTraining問題のHardの100番目に置いてある問題だったため、解きました。難しそうだと、どきどきしながら解きましたが、一回でACすることができたことを覚えています。そして、最後は、CodinGameの「SPRING CHALLENGE 2021」です。

したがって、インタラクティブは全く初めてというわけではありませんでしたが、実際に始めてみると、自分にとっていろいろと難しい点が出てきました。

それは、手元で実行するコードと、提出するコードを変えなくてはならなかったからです。

5.ローカルテスト用コードと提出用コード

実際にコードを提出する際には、インタラクティブ形式に対応した形にする必要があります。スタートの座標とゴールの座標を入力として受け取った後、それに対して、経路を出力します。すると出力した経路の実際の距離に誤差を加えたおよその距離が返されるので、入力として受け取ります。これを1000回繰り返します。

一方、手元で実行する際には、ローカルテスト用のデータを最初に入力として受け取ります。入力用のデータは、正しい横の辺の長さ29個×30行、正しい縦の辺の長さ30個×29行、1000個のスタート座標、ゴール座標、最短距離、最短距離をおよその距離に変えるための倍率のセットです。その後、1000回、セットに合った経路を出力します。

この違いのせいで、自分は最初の約10回ほどの提出を全てTLEにしてしまいました。原因は、ローカルテスト用の辺の長さを受け取る入力用のコードを消し忘れていたからです。それに気がつかずに、延々と、どうしてTLEになるのだろうとコードを提出しては悩んでいました。(結局自分の間違いに気がついたのは翌日でした)

6.最初の得点とWeb版ビジュアライザ

さて、ダイクストラを書くつもりだったのですが、出すたびに提出がTLEとなっていたので、一番シンプルな答えを書くことにしました。すなわち、スタートとゴールの差を取り、L字のように1回だけ曲がる経路です。このコードを提出すると、63179310956点になりました。この結果を見て、思ったよりも良いスコアが出るのだなと感じました。

実際に、入力データseed0の1個目のスタート(7, 28)からゴール(29, 8)までの経路を公式ビジュアライザで見てみることにします。

Web版の公式ビジュアライザでは、下の図1のように表示されました。最短距離は118730、自分の提出したL字ルートの距離は181875で、118730/181875を計算すると、約65%になります。図1の下にあるグラフが、正しい最短距離をaとし、自分の出力した経路の距離をbとしたときの、a/bを表しています。1000個のケースが左から順に並んでいます。これらの値をできるだけ1に近づけるようにすることで、得点が上がると考えられます。

ところで、図1の上の経路を表示した図は、緑(正しい最短ルート)と赤(自分の出力したルート)が少しずらされて表示されています。また、格子が赤やピンク、青や紫等の色付けがされているのですが、これについての説明がどこにも書いておらず、悩んでいました。どうやら正しい辺の長さにおいて、辺の長さが長いほど赤く、辺の長さが短いほど青く表示されているようです。

また、Rustを使った出力は、図1の下のグラフ、すなわち1000個の「最短路長 / 出力のパス長」を並べたグラフのみが表示されるので、今回はWeb版のビジュアライザの方が情報が豊富でした。

f:id:kaede_2020:20210701194941p:plain

図1 公式ビジュアライザで見た最初の提出
7.ダイクストラでの提出

無事にACすることができたので、ダイクストラを実装しました。提出してみると、85448920166点でした。最初の提出より、ずいぶんとスコアが良くなりました。本当は喜ばしいことなのですが、この結果について、どうしてなのかがよくわかっていませんでした。

この段階では、まだスコアの計算を実装していなかったので、提出して自分の得点を調べていました。最初に調べたのは未知の距離の初期値です。ふだんダイクストラの実装をするときには、辺の長さ自体を入力として受け取るので、辺の長さを未知の値として初期値を設定したことがありませんでした。

辺の長さの初期値を変えると、得点が大きく変動しました。試した結果を提出順に並べると下のようになります。

①辺の長さを4000+2000*rand()%2000とすると、85448920166点

②辺の長さを5000+1000*rand()%1000とすると、80231748303点

③辺の長さを3500+3000*rand()%3000とすると、87101133991点

④辺の長さを3000+4000*rand()%3000とすると、56078225734点

(4000*rand()%4000のつもりが間違えて%3000にしていました。)

⑤辺の長さを3000+4000*rand()%4000とすると、86744020816点

⑥辺の長さを3000+4500*rand()%4500とすると、86744020816点

この結果を見て、どういうことか予想がついたでしょうか。

私には、初期値を変えることで、スコアが上下する理由がわかりませんでした。わからないまま続けたので、これから導き出される結果を、結局信用することができませんでした。

理由は、コンテストが終わった後に知ることになります。

この問題の一番肝心なところは、通ったことのない道を通ることだったのですが、初期値を小さくすることで、通ったことのない道を自然に通ることができるようになるというのです。それが精度の向上へとつながるのでした。

私は、せっかくわかった良い道があるのならば、その道を通った方が良いのではないかと考えていましたが、これが間違っていました。

 8.辺の長さの特徴(M=1とM=2)

 話は変わりますが、ここで問題文の条件に戻ります。それは道の特徴についてです。問題の概要には入れなかったのですが、辺の長さには特徴があって、M=1の場合とM=2の場合という2種類がありました。このことを説明した部分が、私にはよく理解できませんでした。

今ではその内容を理解しましたが、コンテスト期間中は、M=1の場合しか考慮することができませんでした。

この違いについては、グラフで見ると、その特徴がよくわかりませす。

M=1のときです。

f:id:kaede_2020:20210703171218p:plain

図2 1本隣の道は、今選んでいる道と大きく違うことがあると考えられる

f:id:kaede_2020:20210703171317p:plain

図3 同じ道を進んでいれば、大きく差はない。

f:id:kaede_2020:20210703171709p:plain

図4 左:隣の道との差 右:同じ道を進むときの差

M=2です。

f:id:kaede_2020:20210703172127p:plain

図5 M=2では、道の途中で、距離が変わります。

f:id:kaede_2020:20210703172314p:plain

図6 同じ道を進んでいても、途中で距離が大きく変わってしまう。

 私はM=1しか見えていなかったので、平均にならしたものを道の端から端まで、通らなかったところも含めて、変更しました。この実装をすると、入力データのseed0からseed99のうち、極端に悪い結果が出るものがありました。それが今思えがM=2だったのだと思います。M=2の場合は、通ったところだけの値を入れ替えた方が良さそうです。

9.コンテスト中の失敗と最終提出

私自身の最終提出は、以下のようなものでした。

・初期値は5000。

・200回まではL字出力をして、距離の平均でその道の値を置きかえる。縦横のどちらか一方向が長いほど、信頼度が高いとして、その道全体の値を置きかえ、そうでなければ前の値に今の値を混ぜるといった方法で通った辺の長さだけを更新する。

・201回から1000回まではダイクストラ。10回ごとに、全部辺の値をクリアして、もう一度つなぎなおす。

プレテストの得点は、80237290367点でした。そしてこれを最終提出としました。

これは、最初のダイクストラをしただけのコードより低い得点です。

ちなみに自分の提出したコードで一番得点が高かったのは87900831417点だったのですが、80237290367点のコードを最終提出としたのには、理由があります。

それは、ローカルで出していたスコアと、提出したスコアが違い過ぎていて、どちらを信じて良いのかわからなかったのです。

これは、本当に書くのも恥ずかしい話なのですが、ローカルで実行していたときに、フィードバックするおよその距離を、自分の出した経路で計算せずに、最初の入力で受け取った正しい最短距離に誤差をつけて出力していたのです。言いかえると、bの値にaの値を使っていました。

結局スコアの違いがどこから出てくるのか気がつかないまま、ローカルでの点数を信じて、最終提出としてしまいました。

AHC003は本当に問題文の意味を理解することができなくて、大変でした。理解できた今なら、読んでも意味がわかるのですが、わからないときは、何回読んでも、書いてある意味がわからないままでした。

10.復習タイム(失敗したことをまずは修正)

さあ、気を取り直して、自分の経路の距離をきちんと計算するように実装しなおしましょう。ここからはコンテスト中の話ではなく、このブログを書いている今に時間を移します。本当は図7のグラフをコンテスト中に見ていなければいけませんでした。

f:id:kaede_2020:20210704145513p:plain

図7 正しいグラフ

f:id:kaede_2020:20210704110205p:plain

図8 コンテスト中に使っていた正しくないグラフ

(後半になっても精度が上がらない←おかしいことに気がつきましょう)

正しいグラフと言っているものについてもう少し詳しく書くと、インタラクティブで1000個の受けこたえを続けて、その結果を戻してあげれば、終盤になるにつれて、正しい距離に近づいていくはずです。それがコンテスト中は、いつまでたっても改善された様子がわからないグラフばかり出てきました。(図8、図9参照)

f:id:kaede_2020:20210704193144p:plain

図9 左:正しいフィードバックがない状態 右:正しいフィードバックがある状態

どうしてそんなことが起きたのかと読んでいる人は思うことでしょう。

実際は改善されていくプログラムを自分は書いていたのですが、良くなっているように見えない出力がローカルテストではされていました(図9の左側の状態)。

提出先のインタラクティブ形式では自分の経路に対しておよその距離を返してくれましたが、ローカルテスト用では返す距離の部分も自分で書いて出力しなければいけなかったからです。

自分でb(自分の経路のおよその距離)を出力しなければいけないのにa(最短距離のおよその距離)を使っていました。

そして、間違えていることに気がつけなかったのには理由がありました。

自分でスコアの計算式を実装できなかったのです。

スコアの計算式でわからなかったのは、図10の赤枠の部分です。赤枠の部分が0.998の右肩に乗っているように見えたり、0.998の(1000-k)乗に赤枠をかけているように見えたりしました。

何度も繰り返しますが、問題文を正しく理解していれば正しい式に見えると思います。

AtCoderの問題文より引用)

f:id:kaede_2020:20210704151743p:plain

図10 計算式でわからなかった部分

さて、スコアの計算式がわからなくても、実は問題文にヒントが書いてありました。図11の赤線部分です。

AtCoderの問題文より引用)

f:id:kaede_2020:20210704153050p:plain

図11 ジャッジ用プログラムの例(疑似コード)

さて、現在に戻ります。スコアの計算式を書きました。上記の式を入れて、最後にround(2312311)をかけると、だいたい正しいスコアに一致しました。(コンテストのときにここまで気がつければよかったのですが。)

ローカルテスト用と提出用のコードの切り替え方も、この「ジャッジ用プログラムの例(疑似コード)」を見ると書いてありました。

繰り返しますが、問題文を理解できることで、用意されたプログラムや計算式を理解できるのです。

11.一番スコアがよかった時点に戻ってみる

さあ、やっとスタート地点に戻りました。スマホでコーディングして提出していたコードです。提出すると87900831417点だったものです。やっとどのように改善されていたのかをビジュアライザで確認することができました。

f:id:kaede_2020:20210704191300p:plain

図12 コンテスト中、いちばん得点がよかったコード

スタート地点に戻ったので、ここからもう一度コードを書き直そうと思っていたのですが、ここまで書くのに一週間かかってしまいました。実装しながらとなると、さらに時間がかかりそうです。というか、今の実力では、考えたことを実装することができなそうです。ここでいったん終わりにして、実装力が上がったら、もう一度この問題に挑戦してみたいと思います。私自身、間違えていたコードを修正をすることができ、つらかったコンテストの思い出がやっと整理できました。

長くなりましたが、ここまで読んでくださり、本当にありがとうございました。