- 0.はじめに
- 1.問題文を読む
- 2.ビジュアライザを見る
- 3.最初の考察
- 4.最初の提出
- 5.スコア計算を実装する
- 6.サンプルコードで100テストケースを回した結果を出す
- 7.汚れやすさの値の分析をする
- 8.サンプルコードに汚れたマスの掃除を追加する山登り
- 9.近くにある汚れやすいマス、一番汚れているマスへの往復を挿入する
- 10.初期解の改善（全てのマスを掃除したらスタート地点に戻る）
- 11.ビジュアライザを見ながら考察する
- 12.考察（エリア単位での掃除・巡回ルートを作りたい）
- 13.余計な掃除をカットする（ルートの削除）
- 14.巡回ルートを作りたいと思ったけど保留
- 15.考察（隣接セルの汚れがたまっていたら掃除する）
- 16.考察（ルートの無駄な部分を考える）
- 17.初期解を書き直す（サンプルコードの使用をやめる）
- 18.汚れたエリアの掃除の巡回ルートを作り、定期的に挿入する
- 19.入力生成方法を読む
- 20.巡回ルート（汚れやすいエリア）の範囲をmedianで調整する。ルートの重複を減らす。
- 21.ルートを短くする（重複を減らす）
- 22.ルートを長くする（挿入）
- 23.ルートを短くする（削除）
- 23.ルートのswapを考える
- 24.終わりに
- 25.最終結果（2023年12月14日更新）
- 26.おまけ（今後の予定）
0.はじめに
はじめまして、もしくはお久しぶりです、競プロ歴約4年のかえでです。
今回は、HACK TO THE FUTURE 2024 （AtCoder Heuristic Contest 027）に参加しました。開催期間は2023年12月1日(金)19:00から2023年12月10日(日)19:00までの10日間の長期コンテストでした。
毎回参加記を書くようにしているのですが最初は「ヒューリスティック・コンテストって何？」と思っている人にどんな問題をどのように解いているのかが少しでも伝われば良いと思ったのがその動機でした。しかし実際に書き始めてみると、思考の過程を記録することが自分にとっても問題を解く際の役に立つことがわかりました。ヒューリスティック・コンテストではアイデアは思いつくものの実装のしかたを思いつかないことがよく起こります。そんなときは一旦アイデアを記録して別の方法で取り組み、実装方法を思いついたらまた後から戻ってくれば良いのです。
そんな風にヒューリスティック・コンテストは自分のできる実装でより良い解を得るために試行錯誤できるところがその醍醐味です。実際に参加してみると他の人は今いったいどんなことを考えているのだろうかと気になってきます。だからコンテストが終わったら、多くの人に解法を書いてもらいたいと思っています。AtCoderのAHCの解説には誰でも投稿することができるので、これを読んでいる参加者の方にもぜひ投稿をしてもらえたらと思っています。
それでは、始めたいと思います。
1.問題文を読む
問題文を読みます。要約するとかなりシンプルに感じます。
- ストーリー：ロボット掃除機のオフィス内のルートを作り、できるだけきれいなオフィスを維持する。
- N×Nのマスがある。Nは20以上40以下。
- 掃除機は全てのマスを通る必要がある。
- 壁をまたいで通ることはできない。
- スタート地点(0,0)に戻ってくる必要がある。
- ルートの長さは100000を超えてはならない。
- 平均の汚れを小さくしたい。
その分Nが一定ではなかったり。壁ができていたりするのかなと思います。ビジュアライザを見ることにしました。
2.ビジュアライザを見る
問題文にある例を見るからWeb版ビジュアライザを見ます。
seed0のサンプルの出力が入っているので再生してビジュアライザを動かします。白いマスが掃除機で、白マスが通過したところが水色に変わります。赤いところが汚れの大きいところなのかなと思いました。
3.最初の考察
ビジュアライザを見て問題のイメージがだいたい湧いてきたので、お風呂に入ることにします。お風呂の中で考察を進めます。たとえば汚れにくいところを1回、汚れやすいところは3回みたいな形で全部のマスを通過して元の場所に戻ればいいのかなあと思います。
どうすればいいのか。
Nが40のとき一番遠いところに行って戻ってくるのに160くらいだと思うと、汚いと感じたらその場所に行って戻ってくるといったことをすれば良いように思います。例えば区画割りをして区画1→区画2→区画1→区画3みたいな形にすると、区画1の掃除回数を多くすることができます。区画の分け方はいろいろとありそうです。この前のアスプローバコンが頭に浮かんでいます。
Nが一定ではないので複数のseedを見ること、複数のテストケースを試すことを忘れないようにしたいと思います。
4.最初の提出
Pythonでのサンプルコードがついていたので、C++に書き直して提出します。絶対スコアは1,579,298,812、相対スコアは46,604,995,572で現在3位のスコアです。提出者は48人で20人が正の得点を取っています。相対スコアは提出してみないと自分のポジションがわからないので、定期的に提出をしていきたいと思っています。
5.スコア計算を実装する
スコアは平均汚れのroundを取った数とのことなので、これを実装したいと思います。問題文を読みながら、Introduction to Heuristics Contestが頭に思い浮かびました。Introduction to Heuristics Contestの「コンテストが開催されるとそのコンテストの不満度が0になり、それ以外の不満度が増える」という設定と、「マスを通ると汚れが0になり、それ以外のマスの汚れが増える」という設定が同じように感じられました。
今のサンプルコードにスコア計算を足します。そのためにサンプルコードの出力部分をansという配列に入れます。スコア計算を書き終えて実行してみると、seed0のスコアが2443552になりました。3302174になってほしいのでどこが違うのかを考えます。Lから2L-1までという部分と0からL-1までのスコアの違いを考えると、累積されている汚れが違うことに気がつきます。最後に掃除をされた日を先にLの長さ分1周計算します。それにより正しいスコアが出ました。
今後のことを考えて、ansは最後に置き換えることにして、座標を記録するようにコードを修正します。
6.サンプルコードで100テストケースを回した結果を出す
スコア計算が書けたので、100テストケースを実行してみたいと思います。サンプルコードがよくできている（WAが出ない）ので、今はこれをもとに改善していきたいと思っています。
自分のスコア計算結果とジャッジのスコアを比べます。差が1生じていテストケースがありました。roundにしていなかったので修正します。
スコアを小さくしたいので、スコアが大きかったテストケースを見ます。seed71のスコアは86158794でした。長さは3198です。改善していくときの参考にしたいと思います。
7.汚れやすさの値の分析をする
seed0とseed71の汚れやすさ(d)の値をヒストグラムにしてみます。
汚れやすいマスは全体の割合からするとそれほど多くないようです。
8.サンプルコードに汚れたマスの掃除を追加する山登り
これから実装する山登りの方針です。
- サンプルコードで初期解を作る。
- ターンの途中で、ある一定の数値より汚れが大きくなったら、そのマスを掃除して戻ってくるルートを挿入する。
- 行き帰りのルートはランダム。
- 長さの制限を超えていたら採用しない。
- 長さ制限がOKな場合はスコアを計算する。
- スコアが改善されていたら採用し、改善しなかったら戻す。
- これを制限時間(2sec)できるだけ多く行う。
ある1定の数がどの程度にしたら良いかはわからないので、seed0を見ます。汚れが多そうなときのマス(13,19)を見ます。a=92610,avg_a=213969,d=630という情報を得られました。ビジュアライザの使い方詳細を見るとaはそのターンの汚れ、avg_aはt=L～2L-1の汚れの平均、dは汚れやすさです。
とりあえず50000くらいに設定することにします。
んー、やっぱりランダムで挿入しようかと思います。
バグを見つけるのに手間取りましたが何とか書けました。
提出します。絶対スコアは1,514,079,386、相対スコアは24,581,730,890で497人中146位でした。
汚れやすいマスのリストを作ってその中からランダムに選ぶことにします。
ランダムで選ぶ箇所のコードを配列外参照にしてしまいREが出てしまいました。と思いましたが汚れやすいマスのリストを汚れやすさが100以上のものにしていたら、空の配列を作ってしまっていたようです。ここは汚れやすいもの上位1割といったものにしたいかなと思います。
やっとACしました。絶対スコアは1,440,427,214、相対スコアは26,105,515,641、552人中158位でした。
これからの方針です。
- 初期解をサンプルコードからもう少しきれいな一筆書きに近いコードにする
- 近くにある汚れているマスを選ぶ関数を作る
- 高速化
ローカル実行をしていて制限時間いっぱい回しても500回くらいだった試行回数ですがコードテストで実行すると10倍くらい回っていました。はっと思い出して最適化オプションをつけたら5000回くらい回るようになりました。ただ、まだまだ試行回数が足りていないので、高速化できる箇所を考えたいと思います。
9.近くにある汚れやすいマス、一番汚れているマスへの往復を挿入する
- 近くにある汚れやすいマスへの往復を入れる・・・あまり良くならなかった
- 一番汚れているマスへの往復を入れる・・・あまり良くならなかった
うーん、パッとしないので初期解の改善をしようかな。
とりあえず記録代わりに一番汚れているマスへの往復を入れたコードを提出しておきます。
うん、想像通り、というか100テストケースの結果と同様に、絶対スコアは少し良くなりましたが、順位は1つ下がったという、ほぼ変わらない結果になりました。
10.初期解の改善（全てのマスを掃除したらスタート地点に戻る）
初期解の行った道を戻ってくる実装がイマイチな気がしてきたので全てのマスを通ったらすぐに(0,0)に戻るコードに変えたいと思います。
うーん、うまくいかない。
試行錯誤して、何とか全てのマスを通ったらすぐに(0,0)に戻るコードに書き変えました。100テストケースの結果は3%くらい改善していたので提出します。
途中でWAが出たので、絶対スコアは0点でした。順位は提出前の171位から514位に。ん！これは自分のスコア計算が正しくないかもしれません。配布されているジャッジツールを使います。
100ケースのうち72ケースで「The output route hits a wall.」というコメントが出てスコアが0になっていました。移動経路を出力して確認します。同じ座標が連続していました。コードを修正して100ケースでスコアが正しく出ることを確認します。
もう一度提出します。
まだ30分の提出制限がかかっていて提出することができませんでした。30分でバグを修正して100テストケースを回して結果のスコアを確認することまでが30分以内でできるなんて、私も成長したなあと思います。以前よりデバッグが上手になった気がします。（と思いましたが、それは嘘でした。昨日は山登りの実装で半日バグらせていたのでした…。）
提出制限が解除されるのを待って再度提出します。今度はACが出ました。絶対スコアは1,363,610,170、相対スコアは、27,045,268,722で579人中167位でした。
少しずつ改善しているものの、もう少し考察を進めたいところです。
11.ビジュアライザを見ながら考察する
いったいどこを掃除するかという話で、挿入するときは、汚れがたまっているところを列挙して、TSPでまわって元に戻ってくるみたいな方が良いのかもしれません。最初に考えていた汚れやすい場所の区画を作るという話に戻ってきた気がしています。
スコアの悪いseed71のビジュアライザを見ます。
右下のエリアを掃除するときに、赤い部分は全部掃除しておきたいなと思います。やはりエリアを作ってお掃除をしたいと思いました。
12.考察（エリア単位での掃除・巡回ルートを作りたい）
方法です。
- 汚れやすいマスを全体から1割くらい抽出する。
- Union Find でグループ分けをする
- 各グループのまわりかたを求める
- 等間隔で初期解にグループを1つ挿入する
- グループがたくさんできたときは孤立しているものはカットしてとりあえず2個程度にする
とりあえず、どのくらいグループができるかを試してみます。やっぱりUnion Find はやめようかな。seed0を試した結果です。本当は2グループに分けたいものの、最初はこんな風に1つのエリアを作って掃除をすることができればなぁと思います。
汚れやすいエリアの作り方
- その行のminからmaxを塗る。（左端と右端）
- その列のminからmaxを塗る。（上端と下端）
- 何もない行があったらグループを分ける
エリアを作成したら全てを通る経路を作りたいと思います。
書き上げてエリア掃除を挿入する山登りやってみました。結果は、良くなっているテストケースと悪くなっているケースがあります。ビジュアライザを見ていたのですが、きれいなところを何度も掃除しているのを見るので、掃除コースと削ることを考えたいと思います。
13.余計な掃除をカットする（ルートの削除）
バグらせるのがいやでずっとルートの追加のみしてきましたが、スコアが良くなりません。余分なルートを削除することを始めたいと思います。難しい実装はできできないので、下図のような場合のみ削除することにします。条件は「きれいなエリアが1回以上掃除済み」のときです。ルートは座標を記録しているので、削れば良いだけです。
実装します。
と、その前に記録として1回提出しておきたいとおもいます。スコアは悪くなると思いますが。
提出前の相対スコアは26,153,605,249、順位は196位に落ちています。提出結果は相対スコアが25,404,783,211、順位は634人中202位でした。
さて、削除部分を入れました。時間いっぱい追加する山登りに削除を入れます。100テストケースを回してもあまりパッとしません。とりあえず提出します。
うーん…。
Highestを更新できないまま時間が過ぎます。疲れてきたので今日は終了したいと思います。コンテスト3日目の夜でした。
戻ってきました。3日目の夜です。上の行から1時間程度経過しています。寝支度をしていたのですが、お風呂に入っていたら、ミスをしている箇所に気がつきました。削除するのを3回以上通ったマスとしていましたが、2回以上でよかったなと思います。
修正しました。
いくつかのseedを試すと、スコアを更新しているのがわかりました。思わず100テストケースを試す前に提出してしまいました。
ドキドキしながら結果を待ちます。
上がりました。
絶対スコアは1,284,655,224、相対スコアは27,739,718,057になり、順位は650人中182位に上がりました。
うれしい！
100テストケースもまわします。絶対スコアははっきりと良くなっていました。これまで一進一退だったのが少し前進したのを感じました。
さてこの後寝たのかと思えば、お布団に入りながら汚れエリアの割合を変えてもう1回提出しました。すると28Gに。この辺はいろいろと考えたいなと思いました。
4日目の朝です。
汚れエリアの割合を1割にしたつもりでしたが、計算を間違っていましたので修正します（Nが20のときで5%、Nが40のときだと2.5%になっていました…）。汚れエリアを2割にしました。
1割と3割も試します。いちばんよかった2割をそのまま採用します。この辺は後からもう少し調整しても良さそうです。時間いっぱい山登りをする際、「削除する」は10回に1回くらいにしていましたが、もう少し頻度を上げてみます。
変わりませんでした。戻します。
時間を延長してスコアが変わるかを見ます。制限時間を100倍にしてみました。
変わりませんでした。別のアイデアを考えたいと思います。
14.巡回ルートを作りたいと思ったけど保留
汚れやすいエリアを一巡するルートを作って、定期的に巡回ルートを掃除する作業を入れたいと思います。今は汚れエリアの左上からスタートするコースしか作れていないので、巡回ルートのどこからでも始められるようにしたいと思います。そうすれば汚れエリアまでの移動ルートが短縮でき、効率が良さそうです。
何度か似たようなアイデアを考えてはうまく実装しきれていないので、この辺りがステップアップ（上位との差を詰めること）の鍵なのかなあと感じています。
15.考察（隣接セルの汚れがたまっていたら掃除する）
巡回ルートを作るよりも先にできそうで改善が見込めそうなものを思いついたので、先にやりたいと思います。先ほどの13で行った削除の逆、隣接セルのルートへの追加です。
スコアが改善するかどうかはこれまで全体を計算していました。差分計算にできれば試行回数を増やせて、隣接セルのルート追加でスコアの改善ができそうな気がします。
んー、とりあえず削除の逆の条件にしたいと思います。隣接セルが汚れやすいセルならルートに追加することにします。
イメージは2マス増やすみたいな形です。進行方向に対して時計回りか反時計回りの2種類を考えます。増やす2マスのうち汚れやすいセルなら掃除します。できれば累積汚れにしたいけどなぁ。
コードを追加しました。seed0ではスコアを更新しています。100テストケースをまわすと23ケースでスコアが0でした。壁の判定が間違っているようです。
コードを修正して100テストケース回してみましたが、思ったほどよくなっていません。うーん。
提出した結果は絶対スコアは悪くなり、相対スコアは少し上がりました。
16.考察（ルートの無駄な部分を考える）
コンテスト5日目です。停滞期間が続いています。いちからコードを書きなおすことも視野に入れています。もう一度seed0のビジュアライザを見て考察をします。
seed0のビジュアライザを見ると、掃除をしている場所はかなり良くなったように感じています。しかしルートに「戻り」が多いことに気がつきます。今掃除したばかりのマスをもう一度通るのは明らかに無駄です。サンプルコードのDFSもそうですが自分の作成したBFSでの経路も行きの道を探索した後、帰り道は行きの道を戻るコードを書いていました。行きの道と戻る道を重複しないようにしたいと思います。
その後は、いくつもの関数に分けて書いているので「挿入」や「削除」、「スコア計算」等の各部分はパーツ化していますが、solve関数で山登りをしている部分が煩雑になってきたので、リファクタリングを行いたいと思います。
ルートのことを考えていたのですが、お掃除ロボットなのだから、DFSしなくてもいいんじゃない？という気持ちになってきました。戻らなければいけないのは行き止まりのとき。行き止まりで戻らなければいけないマスだけ先にチェックしておけば、あとは多分残りNマスくらいまでは重複しない道を作れるような気がしてきます。
17.初期解を書き直す（サンプルコードの使用をやめる）
コンテスト6日目です。昨日は戻りを別のルートにする実装を書きましたが、スコアは良くなるものと悪くなるものが混在して、結果としては良くなりませんでした。本当は相対スコアなので提出した方が良いのですが、テストケースだけでストップしました。
初期解をシンプルな貪欲に変えました。未訪問マスを優先し、未訪問マスがなくなったら一番近い未訪問マスを探してその距離が近い方に移動することにします。未訪問マスがなかったら(0,0)に最短で戻ります。それだけでもこれまでより改善するseedがありました。汚れの少ないseed3のスコアは4,931,303になり、サンプルコードよりも3割程度スコアが良くなっています。
100テストケースを回した結果は、これまで改善してきた結果とほぼ同等くらいでした。提出します。ん、REが出ています。何でだろう？
REが2ケースあったので絶対スコアは0点、相対スコアは提出前の28,145,019,104から26,903,434,513に下がり、順位も291位から315位に下がりました。
それでもほとんど変わらない結果に驚きました。もっと早く初期解を書き直した方がよかったのだなあと思います。
18.汚れたエリアの掃除の巡回ルートを作り、定期的に挿入する
次は汚れたエリアの掃除を定期的に入れたいと思います。このとき、
- 汚れたエリアは汚れやすさの値の大きいもの1割を抽出する
- 頻度は汚れエリアの汚れやすさ平均を残り9割の平均で割った回数とする
- 汚れエリアの巡回ルートを決める
この3つを行いたいと思います。
回数を調べてみると、汚れの少なそうなseed3で3回、seed0は24回になりました。なかなか良さそう。念のためExcelでもseed0の値を計算します。合っていました。seed0の汚れやすさの平均は約226、それ以外のエリアの平均は約9でした。随分差があるようです。
巡回ルートを作ります。当初考えていたようにTSP（巡回セールスマン問題）を使いました。
やっと書きました。
定期的に掃除をするようにしたらスコアが悪化したものが増えました。思ったより改善が難しいので、ランダムに挿入場所を決めて汚れやすいエリアの巡回掃除を入れてみて山登りをすることにしました。
100テストケースを回した結果は前回より13%ほど改善していそうです。
提出します。
上がったー！提出前の321位から202位に上がりました。
ついに32Gを超えました。
まだお掃除巡回エリアの選択方法や削除や追加、高速化等まだまだできることは残っています。ここからできるだけスコアを改善できるようにがんばりたいと思います。
残りは4日あります。ここからがんばるぞ！
さて、ビジュアライザを見ます。
seed25、汚れエリアは1割も無さそう。適切な範囲を見つけてあげる必要がありそうです。また汚れたタイミング（間隔）についてもやはり適切なときを見つけたいと思います。
1000テストケースを実行したところ、6ケースでスコアが0になりました。(0,0)が未訪問が4ケース、壁を通ろうとしていたのが2ケースありました。見直します。(0,0)が未訪問なのはファイルの中身が空でした。Segmentation faultが起きていたようなのですが、再現できませんでした。うーん、困った。
さて、seed0の重点お掃除ルートを見てみました。同じ道を戻っているので、そこを変更したいと思います。
うーん、難しい。
19.入力生成方法を読む
めずらしくというか前回のAHCできりさんが入力生成方法はきちんと読もうという記事を書いてくれていたので、早速実践します。（というか思い出したのが6日目という…。）記事はこちらです。
焼きなまし法が使えなくても AHC 橙になれたよ - Kiri8128の日記
入力生成方法は自分にとって理解するのが難しい箇所なのですが、どうも汚い領域は壁を越えることはないけど連結したままある程度広がってクラスターを形成するようです。値は10倍以上大きくなりそう（dの最大値は1000）。すると割とはっきりと汚れやすいエリアときれいなエリアの2つに分けることができるかもしれません。
変更してみました。標準偏差が10以上のときに汚れやすいエリアと判定することにします。
提出してみましたが50ケース中REが1つ出て絶対スコアは0点。相対スコアも下がりました。
疲れてきたので今日はもう寝たいと思います。
20.巡回ルート（汚れやすいエリア）の範囲をmedianで調整する。ルートの重複を減らす。
ビジュアライザを見ます。汚れたエリアをTSPで求めていたのですが、どうもイマイチな様子。戻りが多く、明らかに無駄な掃除をしています。汚れたエリアをおおよその長方形エリアとして、そこを貪欲で雑巾がけのように掃除するルートに書きかえたいと思います。
と思ったのですがまずはお掃除エリアの確認をします。微妙にずれていたので平均ではなく中央値を使用することにします。中央値とのずれで汚れエリア判定をしました。すると理想的な形になったのがseed25。ビジュアライザを見ると、定期的に汚れエリアとそのエリア以外を交互に掃除していました。やはり気になるのが「戻る」動作。単純に1マス他のマスを経由すれば戻りが改善される場所が2箇所あります。
書きかえました。100テストケースでは良くなっているようです。しかし100個のテストケースのうちSegmentation faultが4個で出ました。原因はわかっていませんが、一度提出してみたいと思います。いきなりTLEになり、その後REの表示が出ます。
そういえば、Nが30以下ではTSP、それより上では貪欲に分けたのを忘れて、時間配分を修正するのを忘れました。ショック…。
16ケースがACで相対スコアは10,871,445,430でした。この結果から推測をすると、50ケース全てACしたとすると、16/50*10,871,445,430=3,478,862,537.6になり、34Gを超えるのですが、本当でしょうか。また32ケースがTLEだったのでNが30以下のテストケースが32個あるということが意図せずわかりました。
30分待ってもう一度出し直します。待っている間にREの原因を調べましたが、初期解の生成中だということがわかりましたが、対策はまだできていません。
また、先ほどはNで場合分けをしていましたが、まずはお掃除エリアを貪欲にしたものだけにして提出します。
やはり2ケースでREが出たため、絶対スコアの得点は0点です。相対スコアはミスして提出する前の237位32,390,183,130点から 少し落ちて32,049,848,509点、順位は242位でした。
次は場合分けをして提出します。30分待っている間に、初期解に出ていたREのバグを修正することができました。
提出しました。
絶対スコアは991,642,328、相対スコアは33,553,493,362で886人中212位になりました。久しぶりの青パフォです。
うーん、疲れた～。そして口内炎ができて痛いです。
コンテストは残り3日。最後までがんばりたいです。
21.ルートを短くする（重複を減らす）
お掃除ルートの戻りを減らしたいと考えているのですが、まずは確実に良くなりそうなものを考えます。下図のようなルートの重複を減らすコードを追加したいと思います。
書いたので提出します。あまり良くなりません。（バグっていたことが後ほど判明）
22.ルートを長くする（挿入）
15で書いていたルートを広げるコードを書きます。
ランダムでルートを追加する山登りにしました。100テストケースを実行するとスコアが0になるものが出現します。その度にデバッグして修正を重ねます。21で実装していた重複を減らすコードのバグも見つかりました。
何とか100テストケースでバグが出なくなりました。スコアもほんの少し良くなった気がします。
コードを提出しました。
238位から220位になりました。
上下も同様に追加します。100テストケースの結果を見てほんの少し良くなった気がするので提出します。絶対スコアはHighestを更新しました。相対スコアの差は縮まっているものの、順位は上がりません。厳しい。
気になっていることがあります。自分のスコア計算がバグっているようなのです…。最初にきちんと合っているのを確認していました。何度も見直しているのですが、どうして…。
バグを修正しました。ルートを挿入するところで間違っていました。まだエラーが残っているので21の追加はいったんやめました。100テストケースの結果がよくなったので提出します。相対スコアは35Gに上がりました。少し改善しました。
23.ルートを短くする（削除）
さすがに疲れがたまってきたのでお昼寝をします。寝て起きたら2時間経っていました。
13で書いていたルートを削るコードを書きます。バグらせつつも何とか書きます。諸条件を変えてみましたがあまり変化はありません。
Nが30以下と30より上で初期解の場合分けをしていたのをやめて、全て貪欲解にすると少し100テストケースの結果が良くなりました。
提出してみると絶対スコアと相対スコアが少しだけ良くなりました。
次に行って戻るマス（1→2→1）があったときに汚れがたまっていなかったら2マス削除することにします。絶対スコアはほんの少しだけよくなりました。
相対スコアは…
おお！36Gを超えました。うれしい。
でも疲れがたまってきました。
コンテスト9日目もあと30分ほどで終わります。明日が最終日です。
23.ルートのswapを考える
コンテスト最終日です。今考えていることはルートの一部を切り取って向きを変えられないかということです。隣接するマスにある2つの掃除する順番をLとRとすると1→2→(L)3→4→5(R)→6→7みたいなときに、1→2→(1マス追加)→(R)5→4→3(L)→(1マス追加)→6→7みたいにすると、ルートの向きを変えることができそうです。2マス追加するのが無駄なのかもしれないのですが。ホントは逆向きのU字を＝（二本の直線）にするのが良さそうですが、自分の実装だとあまり現れません。（説明がわかりにくいので後で図を追加したいところ。今は実装優先にしたいので文字のみでの説明でごめんなさい。）
いろいろと他にすることがあってコードを実装する時間が取れませんでした。今から実装が間に合うでしょうか。
…ダメです。時間がなくなってしまいました。エラーを何とかなくしたと思ったら、全然山登りで採用されません。どこかコードが違うのかもしれません。名残惜しいですが、今回はこれで終了したいと思います。
現在1043人中254位ですのでさらに下がると思います。
もっとがんばりたかったー！
24.終わりに
10日間のコンテストが終わりに近づいています。今の気持ちは、ただ一つ。
「眠い！」
早くぐっすりと眠りたいです。なかなかスコアが改善しないので、眠るタイミングがなくズルズルと長時間をコンテストに費やしてしまいました。私の今回コンテストに使った時間は…（あ、これを書くと良くない気がしてきました。ご想像におまかせします。）
そして、抜きつ抜かれつのライバルが現れ、とても楽しかったです。抜き返すとすぐに抜かれてしまって悔しかったです。もっと強くなりたいなぁ。
さて、コンテストが終わった後は解説放送に出演するためにF社に向かいます。今回もとても楽しい問題でした。どんな解説を聞くことができるのか、今からとてもわくわくしています。（今日は解説放送があるので終了後に感想会スペースは開きません。）
この参加記を読んで自分もコンテストに参加してみようと思ってくれた方がいらしたらうれしく思います。ぜひ次は私と一緒にコンテストに参加しましょう。そして、参加している方からの宣戦布告もお待ちしています。
ここまで長い文章を読んでくださりどうもありがとうございました！
25.最終結果（2023年12月14日更新）
システムテストが終わりました。2000ケース中8ケースでREが出ていました。得点は、1,430,154,954,754、順位は1067人中271位、パフォーマンスは1569、レーティングは21上がって1502になりました。システムテスト前は272位だったので、ひとつ順位が上がったようです。
公式解説の詳細順位表（AHC Standings）よりX軸がN、X軸がdのグラフを引用しました。かなり値がバラついています。スコアはNが小さいとき、汚れが少ないときの方が良さそうでした。
ついにレーティングが1500を超えたのはうれしい限り。青になりたいなぁ。青まであと98です。
26.おまけ（今後の予定）
この後年末は、2023年12月18日からのCodinGameのFall Challenge 2023、2023年12月22日からのRECRUIT 日本橋ハーフマラソン 2024冬（AtCoder Heuristic Contest 029）、2023年1月13日のALGO ARTIS プログラミングコンテスト2023 冬（AtCoder Heuristic Contest 028）とまだまだ予定が目白押しです。
実は現在もTopcoderのMarathon Match 150が開催中。体調がやっと戻ってきたところで、今から参加しようかどうか悩んでいるところです。
また、今日2023年12月14日午後9時からは当日開けなかったスペースを開く予定。ゲストはrinrionさん。以前お会いしたときにレベル別の感想会があると参加しやすいかもと伺ったので、初心者限定で行います。rinrionさんとは久しぶりに話すので楽しみにしています。他の人もお気軽に参加してもらえればうれしいな。
それではまた、次回のコンテストでお会いしましょう。
