- 0.はじめに
- 1.問題
- 2.コンテスト開始時の複雑な気持ち
- 3.最初の提出（サンプルコードの提出）
- 2.わからないのでサンプルコードのpowerの値を変えてみる
- 3.水源をもとからある水源か家の近い方だと考える
- 4.BFSで家から一番近い水源を選ぶ
- 5.考察（巡回セールスマン問題は使ってみたい）
- 6.ローカルでの実行とビジュアライザ
- 7.ダイクストラを書き、いちばん近い水路と家をつなぐ
- 8.確定した頑丈さをもとに迂回させたい（できなかった）
- 9.考察も横道にそれてみる
- 10.確定した頑丈さをもとに迂回させたい2（できなかった）
- 11.初日の相対スコアを更新（残り4日）
- 12.コンテスト7日目（残り3日）
- 13.コンテスト8日目（残り2日）
- 14.コンテスト最終日
- 15.終わりに
- 16.最終結果（2023年2月28日更新）
0.はじめに
はじめまして、もしくはお久しぶりです、競プロ歴約3年のかえでです。
今回は、RECRUIT 日本橋ハーフマラソン 2023冬（AtCoder Heuristic Contest 018）に参加しました。開催期間は2023年2月18日(土)12:00から2023年2月26日(日)19:00までの9日間続いた長期コンテストになります。
この参加記は、ヒューリスティック・コンテストをもっと盛り上げたいという思いから書いています。冗長な部分もありますが、コンテスト期間中の私の紆余曲折をありのままに書いています。コンテストに参加している気分を味わって、楽しく読んでもらえれば幸いです。
1.問題
2.コンテスト開始時の複雑な気持ち
2月18日の12時を過ぎました。先ほどコンテストが始まったところです。Twitterで他の人がやるぞーとツイートしているのを見ても、自分の中でなんか気持ちが盛り上がりません。どうしちゃったんだろう私、と思います。
それでもやっぱり問題は気になり、コンテストページを開きました。問題文を読んでみますが意味がわかりません。
ああ、ここで解くことをあきらめてしまう人もいるのではないだろうか、と思いました。
わからないまま入力例を読んで、ビジュアライザを見ます。出力例がないので、四角と三角が点在する図が見えるだけです。
使い方の詳細を見ると、四角と三角の説明がありました。
青の四角は、水源が存在するセルを表します。
黒の三角は、家が存在し、まだ水が流れていないセルを表します。
緑の三角は、家が存在し、水が流れているセルを表します。（AtCoder Web版ビジュアライザ 使い方 詳細より引用）
ここにあったビジュアライザは出力例が入っていないので動かすことはできませんでしたが、問題文の一番上にアニメーションがあったことを思い出します。そのアニメーションは四角と三角をつないでいました。それからもう一度問題文を読み直しました。
ん、水源のある岩盤を壊して水のルートを家まで引けば良い？
問題の内容がわかってきて、やる方向がわかった瞬間、ぱぁっと世界が色鮮やかになりました。急にやる気が出てきます。コンテストが始まってから、すでに20分が経過していました。
そうか、今伸び悩んでいるから人と競って負けるのが嫌だったのかもしれない。せっかく思う存分競プロに力を入れられる環境に入ることができたのに、自分が競プロを好きではなくなってしまったら…。それを想像することは、とてもこわいことでした。問題を解きたい気持ちが変わってなかったことがわかってホッとます。さあ、問題とともに自分の世界に入りたいと思います。Twitterを見ずにがんばろう、そう決意したのでした。（後日追記：その後すぐにTwitterを開いていました。）
3.最初の提出（サンプルコードの提出）
C++のサンプルコードがついていたのでダウンロードをします。そのままサンプルコードを提出します。絶対スコアは27,173,082、相対スコアは12,263,427,128で、順位は340人中144位でした。
2.わからないのでサンプルコードのpowerの値を変えてみる
頭の中に浮かんでいるのは、重りの重さを調べる天秤。アルゴリズムは二分探索です。
ただ、サンプルコードの中身も良く読んでいなければ、何を考える問題かもわかっていません。
サンプルコードではpowerが100になっていたので、powerを変更して、違いを調べます。まずはpowerを2500に変更してみました。絶対スコアは27,173,082から77,698,041に増えました。相対スコアは3,601,741,543に減少し、順位も278位に落ちました。
なるほど。悪くなるのですね。
次にpower=1に変更してみます。数ケースでTLEしたようです（注：ジャッジ中のテストケースの進み具合からの予測で、実際にはどんな状態だったかはわからない）。絶対スコアの得点は0になりますが、相対スコアではACしたものに関して点が得られるので結果が表示されます。相対スコアは3,437,037,637、順位はさらに落ちて、281位になりました。なるほど、これも悪くなるのですね。
その後、powerの値を50、150、200、32、500と変えてみます。
powerを150に変更したときには絶対スコアがよくなっていたのですが、相対スコアではよくなっていませんでした。相対スコアは変動して比較が難しいので、サンプルコードの相対スコアを毎回メモしておくと比較が楽になりそうだと思いました。
試してみて思ったのは、powerは大きくすることにあまり意味が無さそうだということです。岩盤は5000以下で、1回の破壊ごとに体力の消費に毎回Cが加算されます。あ、Cが固定で最初に与えられることに初めて気がつきました。
Cによって、powerを変えてみると良いのかな。ついでに試しておきます。powerを150にしたときに絶対スコアが小さくなっていたのと、power=1だとTLEするので、power＝C*3にしてみます。絶対スコアは26,490,212、相対スコアは9,032,352,030、順位は551人中、303位になりました。サンプルコードの相対スコアが8,872,888,357だったので、ほんの少しですが、初めてサンプルコードのスコアより改善することができました。
やったー！
3.水源をもとからある水源か家の近い方だと考える
サンプルコードでは、水源と家を結んでいました。しかし、水源と家をつないでいくので、最終的には、家も水源と考えることができそうです。なので、各家から一番近い水源ではなく、水源もしくは家、もしくは水源が引かれる道を結ぶと良さそうだと思います。家と家の距離はすぐに求めることができそうなので、実装してみることにします。
ただ、家と途中の道のほうは、もう少し考えないとダメそうです。イメージは、各家からBFSをして、交わるところを目的地(中継ポイント）として水を引いていくと良さそうです。
ところで、初めて入力された岩盤の頑丈さを見ました。
なるほど、岩盤の頑丈さには偏りがあるのですね。そして、これは、ビジュアライザの模様と同じだということがわかりました。やっと今気がついたのですが、赤が小さい数字で、青が大きい数字なので、濃い茶色が大きな値だということがわかりました。（当たり前だと思われた方もいるのかもしれませんが、ビジュアライザの使い方詳細には説明がなかったので、今まで、ただのデザインだと思っていました。）
これでやっと方針が見えてきました。頑丈な岩盤に出合ったら、迂回をした方がよいかもしれないということです。あ、違うかも。
- 水の通り道を作るとき、岩盤が頑丈でない場所と家を結ぶと良さそう。
あ、ということは、今回の問題は、岩盤マップを作ることなのか。
頭の中に以前大失敗したインタラクティブ問題のAHC003（Shortest Path Queries）が思い浮かびました。道案内アプリを開発する問題でした。あの問題で一番のポイントはダイクストラでまだ通っていない道を優先して通ることでした。だから今回も・・・とそこまで考えて思いました。
家と水源の数が少ない！だからあっちもこっちも掘ってみるということをしたら、得点が下がらないだろうかと思います。ここは疑問点として残しておきたいと思います。
少しずつ問題がわかってきました。seed0のビジュアライザに絶対岩盤を破壊できるmaxである5000をpowerの値として、手でアウトプットを6行ほど入力してみました。
すると、岩盤を破壊して、水を引いている様子が見えました！
まだローカルでインタラクティブを実行できる環境もなければ、ダイクストラもBFSも書けていませんが、少しずつ楽しくなってきました。コンテスト2日目の夜でした。
4.BFSで家から一番近い水源を選ぶ
やっとサンプルコードの中身を見ました。全ての家一軒一軒と、ひとつ目の水源を結んでいました。そこで、まずは一番近い水源を選ぶコードに変更します。提出すると、絶対スコアは20,824,532、相対スコアは10,536,159,861、709人中379位になりました。絶対スコアは良くなっているものの、相対スコアに直すと真ん中より下の順位でした。
次は水源を含む家のグループを作りたいと思います。各水源から全ての家までの距離を求めます。と思ったものの、いまいちそうなので、もう少し考えます。
- 家からいちばん近い水源を選びます。
- 水源とつながっている家は水源に加えます。
こんな感じにすれば、全ての水源と家を結ぶことができそうです。
5.考察（巡回セールスマン問題は使ってみたい）
コンテスト4日目の朝です。今考えていることです。全部の家をTSP（巡回セールスマン問題）でまわることを考え、一番ロスが少ないように一か所水源を加えたらどうかなあと思っています。
インタラクティブなので、今はBFSの部分を、実際の岩盤の頑丈さをフィードバックさせてダイクストラで実装し直したいと思っています。なかなか時間が取れなくて思っていることを実装できずにいますが、日曜までにはがんばって仕上げたいと思います。
まずは貪欲に一番近い水源かすでに水を引いている家を選ぶコードを書きました。あ、WA。そろそろローカルのテスト環境を書くべきかもしれません。とは思ったものの、すぐに間違いに気がついたので、修正して提出します。
あ、・・・。
ローカルで実行できるようにしたいと思います。
6.ローカルでの実行とビジュアライザ
ふうっ。やっとローカルで出力できました。初めてビジュアライザを見ました。4日目が終了です。
ローカル実行できるようにする前と内容が同じコードを提出をして確認します。同じ絶対スコアが出ましたが、順位は100位ほど下がっていました。
コードを書きなおして、ビジュアライザを見ます。うん、水源ではなく家を中継しているのがわかります。よかった。
提出します。絶対スコアはベストを更新して、18,401,464になり、相対スコアは10,250,00,935、順位は799人中481位でした。
さて、この後は、BFSの部分をダイクストラに変えて、moveを変えて、岩盤地図に頑丈さをフィードバックしながらダイクストラで経路を見つけるようにしていきたいと思います。
はぁ、やっと準備が整ってきました。コンテスト5日目の朝でした。
7.ダイクストラを書き、いちばん近い水路と家をつなぐ
ビジュアライザを見ると無駄な動きがわかりやすくなりました。
- 水源と家、もしくは家と家をつないでいたけど、水路が近くにあったら、水路とつなぐ方が良さそう。
簡単に変更できそうなのでやってみます。
直しました。うん、Costも642192から527646に改善しています。
提出します。絶対スコアは15,297,993、相対スコアは11,619,929,562、順位は824人中442位でした。
さて、ダイクストラを実装したものの、うまく良い道を選ぶことができません。自分の岩盤マップは左のようにごく狭い範囲でしか頑丈さを更新できていません。
そうか、もうちょっと広い範囲に予想を広げてあげれば良いのかな。
範囲を広げてみたものの、思うようなスコアは出ません。AからBまでの水の通り道を求めてからグラフを更新しているけど、もっとこまめにグラフを更新しないとダメなのかもしれません。
そして5日目が終了しました。うーん、帰宅してから4時間。あっという間に経ってしまいました。
8.確定した頑丈さをもとに迂回させたい（できなかった）
6日目の朝です。今日の日付は2023年2月23日。待ちに待った祝日です。今日こそは良いスコアを出したい！と思っています。昨日寝ている間に考えていたことは、岩盤が頑丈になってきたら真っすぐに進まず、横にそれるコードを書きたいということです。図で書くと、下のような感じ。急に頑丈さが大きくなったらその先は頑丈さがさらに大きくなるのではないかと予想した方が良さそうだと思っているからです。
そのためにはどうしたら良いのかを考えます。今の座標の頑丈さが確定したときに、進路方向に次の予測を入れることが必要なのかなと思います。
9.考察も横道にそれてみる
考えているうちに別のアイデアを思いつきました。最初から水路を決めてしまおうかということ。あらかじめ作った十字の水路まで各家から近いところをつなげば良いのではないかと思います。ビジュアライザで左右を見比べてみますが、やっぱり無駄な部分が多そうだと思いました。
10.確定した頑丈さをもとに迂回させたい2（できなかった）
今朝考えていたことが何か違うと気づいたので、修正します。頑丈さが大きな値になったとき、動ける３方向のうち、どの方向がさらに悪くなるのかはこの状態ではまだわからないと思いました。
だから調べるべきなのは、その一つ手前の上下の座標の頑丈さだなあと思います。
うん、まずは頑丈さがどのくらいばらつきがあるのかを見るために、ヒストグラムを作ってみたいと思います。
あ、・・・。500以下をもう少し詳しく見ます。
100以下をもう少し詳しく見ます。
結果を見て、もっと早く調べるべきだったと、今更ながら思います。問題文で読み飛ばしていた入力生成方法を読みます。パーリンノイズという言葉は初めて聞きました。詳しくは理解できないけど、勾配があって自然の環境に似せているらしいので、実際の山を思い浮かべても良いのではないかと思います。こんなに平坦な（頑丈さが小さい）部分が多いとは思っていませんでした。seed1も同様に行います。ほぼ同様の結果でした。
そうなのかー。
（時間経過）
バグらせています。ローカルではスコアが出ているので、理由がちょっとわかりません。昨晩から5時間くらいかけて、岩盤の頑丈さを予想して更新する部分を書いていたのですが、5時間前のACしたコードまでに戻りたいと思います。なんかダイクストラではなく、一手貪欲でも良い気がしてきたところでした。
ところで、ちょっと休憩しているところなので、雑談を。AHC期間中の順位や得点のツイートのことです。順位と相対スコアを逐一ツイートするといろいろな情報を含んでしまうなと思ってからツイートをすることに消極的になっています。だから、自分のしたいことが実装できたらツイートしたいと思います。ただ、そう考えていると、ツイートしないまま終わる可能性もありそうです…。
11.初日の相対スコアを更新（残り4日）
そういえば、実装していなかったなと思って、水を引く順番を変えてみました。
- 各水源から一番近い家を選び、マンハッタン距離が一番近い水源と家をつなぐ
- 各家と一番近い水路を探し、一番近い家と水路をつなぐ
実装は二重ループを使って、毎回水路にいちばん近い家を調べて、水を引いた家は使用の有無を管理し、水がない家を順番に調べるようにしました。powerはCによって固定で、Cが8以下は20、32以下は50、128以下は100にしました。
提出します。絶対スコアは12,218,009になりました。明らかに下がっています。（改善しているということ。）
相対スコアは15,547,910,638になりました。順位は906人中340位になりました。
やっと、最初に提出したサンプルコードより良い相対スコアが出ました。
よかった…。ここまでつらかった…。
他の人が何をしているのかがわからず、自分のスコアが上がらないときは精神的につらいものがあります。まだ、頑丈さのフィードバッグがバグっていて書けていないので、ここからが勝負です。がんばろー。とりあえず、ツイートしようかな。単純な自分。
マンハッタン距離でのルートは改善してきているのがわかります。
今度こそ直線のルートを迂回するように書き変えたいと思います。移動平均をとって、この先に山があるみたいなことを予想できると良いのですが。
しかし、夜も更けてきました。日曜のコンテスト終了までに実装することができるのでしょうか。
12.コンテスト7日目（残り3日）
たとえば、頑丈さが2000を超えたら進まず横を掘る、全部掘ったら一番小さい値のところを進むという貪欲は実装できないかと考えます。
実装してビジュアライザを見ます。迂回し始めたけど、水路がきちんと引けていなくてバグっています。
あ、直せたかも。
提出してみます。絶対スコアは13,641,112で、相対スコアは14,617,468,787、順位は957人中408位で、下がってしまいました。
バグっている箇所を見つけました。修正して、100テストケースをまわします。待っている間にスコアの悪いテストケースのビジュアライザを見ます。迂回できていませんでした。家と家をつなぐのでなければ、もう少し柔軟に迂回路を見つけても良さそうです。水路につなぐ場合はマンハッタン距離で最短をつないでいました。だから、左右にずれることができなくなります。一度決めた目的地を実際の採掘結果をもとに修正をしたいと思いました。
再度提出します。ベストを更新することはできませんでした。
13.コンテスト8日目（残り2日）
頑丈な岩盤にあたったら、元のルートからずれることをOKとして、再度ルートを探索し直す、そんなコードに書き変えたいと思っています。
とその前に、迂回する頑丈さを2000、1000、500に変えてみました。結果はほぼ変わりませんでした。
また、目的地方向に進みながらどちらを選ぶかというのを調整しました。変更した内容は、目的地が上上上右右右といったマンハッタン距離だったとき、もし上に行って、基準より頑丈さが大きかったときは右に行くことにする。その次は右行くことにするのだけど右が良くないときには、上に行くみたいな感じにしました。seed0,seed1,seed2はこんな水路になります。
退出をすると、久しぶりに絶対スコアを更新することができ、12,161,361になりました。
また、相対スコアは15,616,591,413、順位は1022人中410位になりました。参加者も1000人を超えました。すごい！
そしてやっと、元のルートをずれてもOKな簡単な実装を思いつきました。考えてみれば単純で、進む先に水路があればOKとします。
14.コンテスト最終日
コンテスト最終日、2023年2月26日の朝です。今から実装したいのは、目的地の変更です。最初に水源と家をつないだあとは、家から水路につなげるようにしているので、岩盤の頑丈さでGOALをずらしていきたいと思います。図の左はGOALが最初の目的地で、ここを目指すために、頑丈さの大きなところを横断してスコアが悪くなっています。右のようにGOALをずらせばよいかなと思いました。条件は水平方向（もしくは垂直方向）に進めば水路があること。時間は余っているので、毎回計算し直しても問題ないと思います。
コードを書き変えながら、そういえば、powerの調整が雑だったと思います。Cが128のとき、前回の値でpowerを調節するようにしたら（単純に前回のpower×岩盤を壊すのにかかった回数をかける）、スコアが良くなりました。絶対スコアは11,865,957になり、ベストを更新しました。相対スコアは15,743,732,437、順位は1048人中419位になりました。
思った以上に効果があるので、Cが128でないときにも適用してみたいと思います。1,2,4,8のときはそれほど改善しなかったので、Cが16,32,64,128のときに適用しました。
コードを提出します。絶対スコアが下がり、改善していることがわかります。
そして、相対スコアは17,013,609,880、順位は1048人中371になりました。びっくりするくらい上がりました。
実はまだpowerの調整が雑で、1回ごとにリセットされるので、もうちょっと自然に減衰するようにしたいと思います。岩盤の断面図を見るとこんな感じなので、1回につき400くらいずつ減らしてみたいと思います。うーん、イマイチだったの8割にしてみます。
提出してみましたが、ほぼ結果は変わりませんでした。絶対スコアは悪化し、相対スコアは微増？
こういうときはもっと多くスコアケースを回さないとなあと思います。特にCが8通りあるので、とりあえず1000ケース試した方が良さそう。テストケースを1000個生成しました。時刻は13：26。お昼ご飯も食べずに朝からずっとやっていたので、少し休憩したいと思います。
お昼寝して目が覚めました。この最終日の午後に眠くなってしまうのが残念。前回も同じだった気がします。もっと体力が欲しい。
直してみました。スコアが悪くなっています。
コードの修正が間に合いそうもないので、100テストケースをまわして、直前の2つの提出のどちらが良いかを決めたいと思います。
15.終わりに
コンテストもあと1時間弱で終了します。テストケースが時間内に終わらなそうなので、このまま提出せずに終了したいと思います。
提出をしているときもしていないときも、順位表を何度も見ています。新しい人が登場したり、ぐんと順位を上げている人がいたり、試行錯誤していることが伺える人がいたり、いろんな人がいます。この順位表に、コンテスト期間中、とても励まされました。
がんばっているな、と。
苦しんでいるのは自分だけじゃない、と。
スコアが上がっていて、すごい。自分も負けずにがんばろう、と。
Twitterでもみんながんばっているなとうれしく思いました。コンテストが始まる前の気持ちはホント何だったのかな？
そして、コンテストが終わってみると、何となくいつもと同じような暫定順位にいる感じがします。本当はもっと上の順位を取りたいのですが、それでも今回も最後までがんばりました。そして、とても楽しい時間でした。問題を準備してくださったリクルートのみなさん、どうもありがとうございました！
そして今から、コンテスト終了後の時間を楽しみにしています。コンテストが終わると皆が解法を教えてくれることでしょう。自分が気がつかないことがたくさんあったと今回も思うに違いありません。
また、「AHCラジオ」の第2回も2023年3月1日（水）20時からAtCoder Liveでの放映が予定されています。今回のコンテストの簡単な解説を交えた、楽しい学びの時間になると思いますので、ぜひ多くの方に見てもらいたいと思っています。また余談ですが、放送はこれから水曜日固定になると思います。
これからますますヒューリスティック・コンテストに参加してくれる人が増えることを祈りながら、この文章を終えたいと思います。ここまで読んでくださって、ありがとうございました！そして、ヒューリスティック・コンテストに興味を持ってくださった方がいらしたら、ぜひ次は私といっしょに参加しましょう。
16.最終結果（2023年2月28日更新）
システムテストが終わりました。暫定順位は407位でしたが、最終順位は437位になりました。だいぶ順位を落としてしまったので、次はしっかりローカルでテストケースをまわして判断したいと思います。システムテストの3000ケースは全てACしていました。
ヒューリスティックのレートは9上がり、1370になりました。
