第4回 Asprova プログラミングコンテスト
2019/08/23~08/30にAtCoder上で開催されたマラソン型のプログラミングコンテスト『第4回Asprovaプログラミングコンテスト』に参加しました。
焼きなまし法が初めて成功して嬉しかったのと、ツカモさんにこう言われたので、記事を書いてみることにしました。
恐縮です…。
— ツカモ (@tsukammo) August 30, 2019
さぁ、ろいさんもブログ記事を書いて競プロ後継者erの糧となるのです！
ということで、この記事は、自分(Roy_R)がコンテスト期間中にやったことを時系列にまとめて、他の人の役に立つといいなっていうのとともに、マラソンマッチ楽しい！ と主張するものです。(あと、自分の復習のため)
やったことを簡潔に列挙するのが本当はいいのかもしれませんが、このブログのタイトルは『競プロ日記』ですし、僕は日記調の文章しか書けないので、日記的な感じで考えたこととかやったことを書いていきます。読み物として読んでください。
(一応、やったことを適当にまとめたものを一番下に書いたので、それだけ読みたい方は一番下へ) すみません、暇な時に追記します。
ちなみに僕のマラソンマッチの経験は、2nd Asprovaと第三回日本橋ハーフマラソンの二回だと思います。どちらも乱択解以上の点数を出せずに終わった初心者です。
(マラソンマッチ自体の説明は、ツカモさんの以下の記事とかを見るといいと思います)
また想定読者は、競プロはやっているけれど、マラソンマッチはやったことないという人になるのかなーと思います。
問題概要
まずは問題のリンクを以下に貼ります。
ただ、問題文が非常に長いので、概要を述べます。
『工場の良い生産スケジュールを作成してください。具体的には、M台の機械が与えられ、R個の生産オーダ(注文)が与えられます。オーダには品目、数量、最早開始時刻、納期、粗利金額、納期遅れ許容時間などのパラメータがあり、また、各機械である品目を生産しようとした時の生産速度などのパラメータをまとめたBOMという情報が与えられます。ある機械で生産する品目を取り替える時、段取り時間が発生し、同時に段取り時間ペナルティ金額が発生すること、また、納期に遅れるたびに納期遅れペナルティ金額が発生することに注意しながら、得られる利益を最大化してください』
だいたいこんな感じです。
いわゆるスケジューリング問題ってやつですね。
具体的には下に貼った画像を見てもらうと少しわかりやすいかもしれないです。(これは後で紹介するヴィジュアライザで生成されたものです)
(このコンテストの主催企業であるAsprovaさんはこういった生産スケジュールを解決する生産スケジューラを製作している企業だそうです)
ところで突然ですが、僕はこの問題文を自動車教習所の寮で見ました。
そうです。今、自動車免許合宿に来ているところなのです。なので空き時間が有り余っており、長時間コンテストに参加するにはうってつけです。さらに、前々回の2ndAsprovaコンテストに参加していたのですが、その時の問題と割と問題設定が似通っていて、とっつきやすい感じがしました。よって、読んですぐにフルで参加しようと決めました。
情報収拾
現代戦では情報を制するものが戦いを制します。多分、孫子か誰かもそんな感じのことを言っているはずです。なのでとりあえず周辺情報を集めました。
まず先に述べた通り、今回のコンテストは前々回のコンテストと良く似通っています。少し得点の与え方や納期遅れに対する扱いなどが違いますが、ほとんど同じです。多分。最大の違いは、一つのオーダが一工程で終わるか否かですかね。今回のは全部一工程で終わります。つまりは、前々回の問題の制約が緩和されたバージョンに見えました。よって、前々回の解答を参考にするのはある程度有益でしょう。
色々調べてみると、6位のkojimaさんの以下の記事や、
表彰式を見に行ったnekomimimiさんによる上位の人の解説(以下参照)や、
1位の人が、Greedyの後に作業を割り付ける順序を一点入れ替えてGreedyをし直して山登りする話をしてたがかなり状態が変化するようで、近傍が大きければ山登りでも谷を乗り越えられると言うことで、なるほどと思った pic.twitter.com/Sd2boJl4nA
— ねこみみみ (@nekomimimi) January 11, 2019
1位だったts_さんのtwitterでの以下のような発言を見つけました。
Asprova 2nd コンテストは運良く1位
— ts (@ts_77777) January 15, 2019
やったことは（公開承諾済み）
1. orderを納期順にソートしてorderの優先順位付け
2. 段取り終了時刻t2が一番早いoperationを探索して逐次割り当て解を構築（複数候補がある場合は優先順位順）
↓
以上を総合すると山登り法か焼きなまし法(マラソンマッチにおける超有名アルゴリズム)かなという感じです。
型にはめてとらえるのは良くないと、chokudaiさんもおっしゃっている(以下記事参照)ので、あまり固執しないように、でもこれらの解法を念頭に置いておきます。
また、ある制約下においてはスケジューリング問題は厳密に解けます。
下はABC131DのMegalomaniaという問題です。このような問題の場合、納期が早いものから順に仕事をこなすのが、全体の終了時間を最も早くします。
この知識も重要な気がしたので確認しました。
また、下のようなthereecourseさんのマラソンマッチについての有益なリンクなどを見つけたりしました。
とりあえず提出
ありがたいことに、今回の問題にはいくつかのおまけがついています。サンプルコード、ヴィジュアライザ、テストケースジェネレータ、得点チェッカーなどです。
問題に出てくる変数が非常に多くて、読み込んだり解答を出力したりするのが面倒なのですが、サンプルコードを使えばその辺りをよしなにしてくれて嬉しいです。
サンプルコードのやっていることを読みます。全てのオーダを最早開始時刻でsortして、機械番号が若いものにどんどんと詰め込んでいく貪欲解法でした。とりあえずそのままのコードを提出してみます。172204165516点が得られます。普段のAtCoderのコンテストではまず得られないほどの大量得点に喜びます。わーい！
(桁数が多くて読みづらいので、以降は1722億点という形で切り捨てて表します)
さて、サンプルコードの解答は本当にサンプルという感じで、いくらでも改善できそうです。とりあえず、最早開始時刻によるsortではなく、納期によるsortに変えてみましょう。上の厳密に解く方法を利用してみたのです。しかし、得られた得点は1698億点で下がってしまいました。出鼻をくじかれてしまいましたが、これは考えてみれば当然で、上の解析的なスケジューリングの解は、開始時刻の制限がないときのものでした。今回には必ずしも適用できません。
この方針はとりあえずおいておいて、次に考えたのは他の機械も使うことです。サンプルではほとんど一つの機械しか使っていません。これではダメなのは自明です。負担は分散させるべきです。よって、最早開始時刻でsortした後に、どの機械に割りつけるといいかも調べて貪欲に割り付けていくことを考えました。これで提出してみると2882億点が得られました。1000億点も増えました。嬉しいです。
次に、sortの部分をちょっといじってみることを再び考えました。ここで納期でsortしてみたり、納期+納期遅れ許容時間でsortしてみたり色々試してみたところ、納期+納期遅れ許容時間でsortするのが2910億点が得られていい感じでした。
実験する
さて、こうやって色々な要素を動かしてあれこれ試していたわけですが、AtCoderの提出欄に提出すると、提出制限でそれから一時間は提出できなくなってしまいます。つまり、試行錯誤が一時間に一回しかできないのです。これは不便です。
ここで考えるのが、手元に実行環境を作ることです。幸いにも、サンプルコードと一緒にテストケースジェネレータも付いています。これで大量の入力データを作ってプログラムを走らせれば、手元でどれくらい改善されたかがわかります。
しかし、当然それを手動でやっていては時間ばかりかかり、それこそ意味がありません。自動化させましょう。シェルスクリプトです。僕の環境はMacBook Airのターミナルなので、シェルスクリプトを上手く使えば、色々上手くできるはずです。全然シェルスクリプトなんて触ったことありませんでしたが、これを機にちょっとやってみました。
この辺りは、以下のhama_duさんの記事の『テストする』の項を参考にさせていただきました。
以下の記事でコルンさんがおっしゃっているように、手元の入力データに対する過剰な最適化に陥らないために、テストケースは十分多くとる必要があります。(1000件くらいいるっぽい？)
けれど、一つのテストケースに10秒かけているので、それを1000件もテストしていては、素早く結果を得ることはできません。どうやら、頑張る人は最近話題のAWSとかクラウド上の並列計算のサービスに投げてこれをササっと計算させたりするらしいですが、僕は流石にそこまではできないので、30件のテストケースだけで全部を評価しちゃうことにしました。ある程度有意に点数が上昇していればいいでしょ、と雑に考えました。正確さよりも素早いフィードバックが欲しかった、なんて言うとなんだかそれっぽいコメントです。
順位表を見る
さて、手元にある程度のテスト環境が構築できたところで、順位表を少し眺めてみます。これです。
この時点で1位の人の得点は3001億2000万点くらいで、2位の人も3001億点くらいでした。現在の自分の得点が2910億点なので、また100億点も上昇すれば1位です！ でも、それは難しいでしょう。強い人は本当に強いので。それに上位が3001億あたりにまとまっているなら、そのあたりに上限があると言うことなので。つまり、ここから得られる情報は、この先の改善は100億点のオーダではなく、10億点とか上がったら十分よい改善だったのだなと言うことでしょう。このように順位表を見ても色々と情報を得られます。
あと、単純に順位表を見ると楽しいです。この時の自分の順位が21位くらいで、順位表を見ていると、上に行ってやるぞ！ というモチベーションが湧きました。
過去を参考にする
やっぱり今回の問題は2nd Asprovaのコンテストに良く似通っています。その時の解法が一部流用できるのではないでしょうか。そのままは使えなくとも、ある程度は参考になるのでは？ そう思って、上に載せたts_さんの解法を考察しました。
焼きなまし法の部分はおいておいて、初期解を構築する部分だけをまずは考えて、それを実際に今回の問題で実装してみました。手元のテストでいい感じの点が出ました。提出してみると、2981億点が出ました。70億点もの改善です。喜びます。
でも、なんで上手く行ったのでしょう。考えてみると当然で、今までは割り付けるオーダーを決めてから、一番上手くいく機械を選ぶ貪欲でしたが、今回は、どのオーダーをどの機械でやると一番上手くいくかを考える貪欲になっていて、貪欲で見る解の候補が増えているのです。
さらに微妙なマイナーチェンジを手元でいくつか試して、上手く行ったのを提出してみると2988億点まで伸びます。着々と改善していっている感じがあって非常に楽しいです。
この改善は、自分でも気づけかったわけではないと思いますが、なんらかの前例があるならそれを参考にしてみることで、自分の考察を強化できてよいと僕は思います。たとえば強い人は、その問題に関係する実際の論文などに目を通したりすることもあるらしいです。
ところで、ここで一つ問題が生じます。
実はこの次の日、合宿免許の仮免試験があったのです。しかしマラソンマッチにかまけていて、学科の勉強にあまり手がつけられていませんでした。ネット上で運転免許の学科試験は論理的におかしかったりして、解くのが難しいみたいな話を聞いたことがあったので、夕方を過ぎた頃に流石に慌てて過去問題集を開きました。ただ数年分解いてみると意外と簡単で、ちょっと独特な感じはありますが、慣れたらなんてことはない感じでした。過去問を解くのは大事だなと思いました。
この節のまとめは過去を参考にするのは大切だなと言うことです。
逐次評価する
さて、仮免試験当日です。まずは実技試験。バスに乗せられて練習コースの横にある待合室に通されます。しばらくすると名前を呼ばれて車に乗り込みました。後ろに次の試験の人も乗り込んで来ます。緊張します。けれど、何度も練習したコースをいつも通りに進むだけです。後方に車が来ていないことを確認しウィンカーを出して走り出します。
緊張で肩が上がりながらも、いつも通り進みます。だんだんとリラックスできた頃、S字に差し掛かりました。難関と言われる箇所ですが、練習ではスムーズに行けていたので、何も考えずに進みます。途中まで非常にスムーズに曲がれます。と、後輪に衝撃がありました。よく見ると、いつもよりもカーブの内側に寄ってしまっていました。内輪差で内側の縁石にぶつかってしまったのです。教官に言われたことを思い出します。S字などでは、しっかりと曲がるところを見て、適切な距離が取れているかを逐次確認しながら、カーブに沿うように細かくハンドル操作するべきなのです。
そうです。闇雲にこちらの方が正しそうだからと思い込みで突き進んでいてはいけません。逆に、今どんな状況であるかを逐次確認しながらであれば、前に進んでいけるのです。プログラムもきっと同じです。解答の一部を変えてみて、それで得点が良くなるかを見ていけば、よりよい方向に進んでいけるはずなのです。なので、今現在の得られる得点(利益)が幾つなのかをプログラム内で調べられる関数があると嬉しいです。
そしてこれは実は簡単に実装できます。なんと得点チェッカーのソースコードがダウンロードしたファイルについているので、それをちょちょちょっと弄ってやって適当にコピペすると、あっという間に完成です。
仮免試験は実技で上記のような危ない部分がありましたが、問題なく合格できたので、昼食後にこの得点をチェックする関数をパパッと完成させます。そして、隣接する二つの注文の順番をランダムに入れ替えてみては、上手く行けばその入れ替えを採用するというようなことを行いました。カーブを曲がりながら、しっかり目視で偏りを確認してハンドルを修正するようなものです。このように、少しづつ要素を変更しながら(『近傍を見る』みたいにも言う)、点数が改善すればその変更を採用する、ということを時間いっぱい繰り返す方法を一般に山登り法といいます。山の頂上を目指して、一歩づつ高い方向に向かって動いていこうとするイメージです。
この山登り法のコードを提出してみると、2988億点でした。
……あれ？
いや、山登り法をしないときと比べると800万点くらいは改善しているのですが、正直言って微妙です。
asprova、3000億点目指したいな
— ろい (@Roy_R_) 2019年8月26日
この調子では3000億点には届きそうにないですよ。
ヴィジュアライザ
さて、何が良くないのでしょうか。改善する方向に動き続ければ、必ずより良いスケジュールが出来上がるはずです。そこで、ダウンロードしたファイルに入っていたヴィジュアライザを使って自分の解答を見てみます。
(緑色の部分が段取り時間で、その他の色の部分が個々のオーダ(注文)です。またビックリマークが上に付いているのは納期に間に合っていないオーダです)
なるほど。綺麗に視覚化されていて楽しいですね。いくつも試してみて、それを見ているだけで飽きないです。でも、なんとなく改善できそうなところがあることに気づきます。例えば先頭の方で、オレンジの品目の塊、黄色の品目の塊、オレンジの品目の塊、と品目が交互に生産されていますが、これは品目を入れ替えるための段取り時間が発生して無駄です。
こういう感じで、品目をまとめてやると良いような気がします。
けれど、今の方法ではこういった変化はほとんど起きません。
理由は簡単です。
『橙橙橙黄黄黄橙橙橙』
から
『橙橙橙橙橙橙黄黄黄』
に変えるためには、オレンジと黄色がより入り混じった状況
『橙橙橙黄黄橙黄橙橙』など
を経由せねばならず、そのような状態は概して点数が悪くなります(製品を入れ替えるたびに段取り時間が発生するので)。つまりより大きな山に登るために一度谷に降りなければいけないのです。
焼きなまし法
では、発想を転換し、その谷(点数が悪くなる方向)にも進んでみてはどうでしょうか。高い方にばかり行くのではなく、一時的には悪くなりますが、いずれ良いところに行けると信じて低い方にも確率的に移動してみるのです。これがいわゆる焼きなまし法の基本的な考え方です。
実際には低い方向に行く確率を、温度と言われるパラメータで管理して、徐々に点数が低い方向にはいかないようにしたりします。これが鉄を精錬する時に、だんだん冷えて動かなくなっていくところに似ているので、焼きなまし法と呼ばれるわけです。
マラソンマッチではよくこの焼きなまし法が使われ、chokudaiさんによれば、アルゴリズム部門におけるDPみたいな存在だそうです。(多分そういう意味ですよね)
「マラソンって大体焼きなましだよね」と「AtCoderって大体DPだよね」はほぼ等価
— chokudai(高橋 直大)🍆🍡🌸 (@chokudai) February 11, 2019
前回、前々回のマラソンマッチ参加時にもこれを実装しようとして、結局できなかった苦い思い出があります。けれど、焼きなましができなければこれから戦っていけないでしょう。そう思って色々と先人の方達の焼きなまし法についての記事を読み漁りました。
中でも、以下の診断人さんの記事が実装面についてもわかりやすく、記事内のコードを参考にさせてもらいつつ焼きなまし法を実装しました。
すると、前回までが嘘みたいに上手く実装ができました。手元のテストでも改善されていることを確認して、提出です。一気に2993億点まで伸びました。5億点の改善です。焼きなまし法が初めて成功し、ガッツポーズをしました。すごく嬉しかったです。
ところで、焼きなまし法はできる限りループを繰り返した方が点数が伸びるので、ある程度、高速化をするのが有効らしいですが、関数に対してvectorを渡す時に、 (vector<int>& x)の参照渡しか (vector<int> x)の渡し方かでは、後者が122986回程度に対して 前者が182401回程度のループ回数と有意に速度差が出てきたりとか、rand()関数は遅いだとか、C++に関するいろいろなことが知れて、へーと思いました。いつも競プロをする時はbetterCとして適当にしか使っていないのですが、こう言う時は、C++の別の側面を見られるなーなどと思いました。
寝ながら焼く
焼きなまし法が完成しましたが、2993億点で、3000億点には届きませんでした。焼きなましは、いっぱいループを回すとより良い解ができるはずです。10秒という実行時間の制限があるから3000億点に届かなかったのでしょうか。もしそうなら、どうにかしてプログラム自体を高速化してやる必要があります。でも本当に高速化が必要なのでしょうか？ わかりません。
なら、実際にいっぱいループを回してみましょう。具体的には寝ている間、7時間くらい。ということで、時間制限を7時間くらいに再設定してプログラムを走らせました。このとき、得点の遷移も知りたいので、その時々の点数をエラー出力するようにしておきます。
音を上げながら計算をするMacBook Airを横目にベットに入りました。寝ている間にコンピュータに仕事をさせておくと言うのは、なんだかIT技術を使いこなしている感じがして楽しいです。7時間ですよ。いったいどれだけすごい点数が出るでしょうか。ワクワクしながら眠りました。
ルンルン気分で目を覚まして、結果を見ようとパソコンを開きます。エラー出力を書き出したファイルを開こうとすると、しかし、vimで開こうとしたにも関わらず、ひどく重くて、vimを強制終了せざるを得ませんでした。仕方がないので、大学の春の授業で使ったgnuplotで間引きながら点数変化の推移をプロットしてもらいました。それが以下です。
また、その時点での最高点をプロットしたものが以下です。
こういうグラフは見ているだけで非常にワクワクするのですが、これから読み取れるのは、ループのはじめの方でほとんど点数は頭打ちになってしまっていると言うことです。色々考えてみると、実際の制限時間の10秒以内にはほとんど最大のところまで得点が上昇していることがわかります。
残念です。
このように頭打ちになってしまっては、どんなに計算を高速化してループを繰り返しても3000億点には辿り着けません。
では、なぜ頭打ちになってしまったのでしょうか。
探索空間と解空間
焼きなまし法では、小さな変更をいっぱい加えてどんどんと新しい解を作っていくことを繰り返します。こうやって操作を繰り返して構成され得る解の候補の集合を探索空間と言ったりします。焼きなまし法や山登り法では、この探索空間の中を彷徨って、一番良い点数となる場所を探すようなイメージです。
また、問題の答えとしてあり得るすべての解の集合を解空間と言います。今回の問題で言えば、どの機械でどの順番にオーダ(注文)を処理していくかの組み合わせがそれに当たります。この組み合わせは、例えば機械が一つだけでオーダが200個だけだとしても、200!=10^370くらいになって、とても広大です。だからこそ、厳密な最適解が求められずに、焼きなまし法や山登り法といったいわゆるヒューリスティックな解法を使って、より良い解を求めようとするわけです。
さて、この探索空間と解空間なんですが、よく考えると今のままでは二つが乖離していることがわかります。隣り合う二つのオーダを入れ替えるだけでは、あるオーダについて他の機械で生産するという可能性を無視しているのです。
これでは、限定された探索空間における良い解が求められるだけで、必ずしも実際の解空間の中においての良い解は求められません。
もちろん、探索空間が解空間の中でも優秀な部分集合であれば、そのような探索空間だけを見るだけでもいいと思いますが、今回はあるオーダに対して機械を固定化することにメリットは何もありません。
これを無理やり自動車学校でたとえるなら、教習コースという探索空間をぐるぐると回っている間は、S字が一番難しいところだと思っていたけれど、より広い公道という実際の解空間に出ていったら、もっと難しいところはいっぱいあるよね、みたいな感じですかね。すごく無理やり感あるたとえですけど。(ということで、仮免許が発行されたのでこの頃から公道を走る練習が始まっていました。いきなり公道走ってくださいとなったので、結構ドギマギしながらやっていました)
さて、このことに気づいたので、すぐに焼きなましの、『要素を少し変更する(近傍を見る)』部分に新しく『ランダムに選んだオーダを別のランダムな機械に割り当て直す』といったものを追加しました。
途中、vectorのiteratorのミスで配列外参照してしまっていたり酷いバグに悩まされますが、
— ろい (@Roy_R_) August 27, 2019
寮の消灯時間までになんとか実装ができました。手元の環境で実行しても良さそうな結果が得られたので、実際に提出してみると、2995億点が出ました。2億点の改善です。いいですね！ 着実に3000億点に向かっています！ ですが、まだ何かが足りないようです。
より良い探索空間
『橙橙橙黄黄黄橙橙橙』
から
『橙橙橙橙橙橙黄黄黄』
に変わってくれると嬉しいよね、という話を思い出します。
これを、隣接する二つを入れ替える近傍(小さな変更)を使って達成するには、得点が低くなってしまう
『橙橙橙黄黄橙黄橙橙』など
の状態を経由しなければならなくて、だから焼きなまし法を使ったのでした。
けれど、別にこのような得点が低い状態を経由しないで、直接変化させればいいんじゃないですか？ というのを思いつきます。
つまり、同じ品目のオーダ(注文)をまとめて移動させるのです。
『橙橙橙黄黄黄橙橙橙』
から
『黄黄黄』
を検出して、
『橙橙橙橙橙橙黄黄黄』
になるよう移動させるのを近傍とするということです。
これは下のツカモさんの記事でいう状態空間(探索空間)をなだらかにするということに相当すると思います。
ツカモさんの記事内の図を参考に、頑張って図にしてみるとこんな感じです。
これが元々の探索空間です。左の山から一番右の良いところに行くためには、一度真ん中の谷を経由します。
そして、新しい探索空間は次の図です。谷の部分をカットしました。
左の山と右の山が、近傍としてくっついてくれました。これなら山登り法でも右に遷移することができます(図が下手なのでちょっと谷ができていますが、気にしないでください)。このように良い近傍を取ることによって、探索がしやすい探索空間を構築できるのです。
考えてみれば、元々の解空間には近傍(近い解)なんていう概念は存在していません。図中の『状態』なんていう軸は存在していないのです。そこに人間が、この状態とこの状態は似通っていて、こっちの状態が良いなら、この変換をした状態も同じくらい良いだろうと、そういった問題固有の考察を与えてやることによって、探索可能な探索空間ができあがるのです。
(たとえ隣接二点swapとか一点ランダム変化みたいな自明っぽい近傍でも、それは人間が導入した概念であるということは念頭におくべきなのかなって思います)
今回の場合で言えば、
『橙橙橙黄黄黄橙橙橙』
と
『橙橙橙橙橙橙黄黄黄』
の良さは、そんなに変わらないけれど、黄色が後ろに行った分だけ段取り時間が少し減って、ちょっといいだろう。だからこの二つは近傍とみなせるだろうということです。
なぜか朝5時に目が覚めてしまったので、朝食までにこの3つ目の近傍をカリカリと実装していきます。同じ品目の連続を判定したりするところがまた配列外参照を起こしたりしてバグまみれになりますが、なんとかデバッグをすませると、完成したのは8時10分くらいでした。朝食が8時半までなので、AtCoderに提出だけ済ませると、慌てて食堂に行きました。
バイキング形式の朝食を美味しくいただくと、食後のお茶を飲みながらスマホでさっき提出したコードの結果を見ます。
3000億！ pic.twitter.com/xpdVih5iZz
— ろい (@Roy_R_) August 27, 2019
ついに、3000億点を突破しました！！！ やりましたよ！！
山を登っていく
この日は、3000億点を出した後、自動車学校の学科の授業がたくさん入っていたので、あまり本格的な改良はできません。けれど、せっかく一時間に一度AtCoderに提出できるのです。休み時間中に、近傍の確率や焼きなましの温度を色々といじって提出してみました。
はじめの温度をもっと高くした方が良さそうだ、とか。そうやってマイナーチェンジを施しながら、点数が改善されたらその変更を採用するということをやっていきます。やりながら、これはまさに山登り法と一緒だなと思いました。焼きなまし法や山登り法と行ったヒューリスティックな解法は、人間が実際の問題に対して試行錯誤しながら解決していく様に非常によく似ていて、そこがマラソンマッチの一つの楽しみかもしれないな、などと考えます。
時には、変更を加えてみた結果、悪い結果に行き着く時もありますが、
コードが肥大化するとバグが増えて辛い。書き直すか？
— ろい (@Roy_R_) August 28, 2019
そのような谷を抜けた先により良い結果が待っていたりして、これは焼きなまし法みたいですね。
起きて少ししたらバグが取れたので睡眠は大事
— ろい (@Roy_R_) August 29, 2019
さて、いつの間にか、8月29日です。路上教習も慣れてきて、法定速度に合わせてしっかりと運転できるようになってきました。そして、Asprovaコンテストも残すところあと24時間くらいになりました。8月30日までと言っても、朝10時までなので、実質今日が最終日です。
さて、asprovaもラストスパートだ。3001億台に乗りたいな。
— ろい (@Roy_R_) August 29, 2019
3001億点を目標に据えて最後まで頑張っていきます。
こういったヴィジュアライザの結果を眺めたりして、例えばこの一番上の機械真ん中あたりの黄緑色のオーダ(注文)はその一つ下の機械の黄緑色のオーダと合わせた方が良くないか？ などと考えて、別の機械にオーダを動かす近傍を、同じ品目のオーダをめがけて動かす確率が高くなるようにしたり、同じ品目をまとめて別の機械に動かしたり、あるいは、同じ品目が並んでいるところで、納期を使ってsortしたり(これは冒頭の方で述べた厳密な解を作るアルゴリズムを参考にした)とか、いろいろなことを試してみました。
あまりにも色々な要素を追加しすぎたために、どれの影響で点数が上がっているのかはわからなくなってしまっていましたが、それでも着実に点数が上がっていました。
けれど、3001億点にはもう少しで届きません。本当は良くないのですが徹夜することに決めてしまいました。
深夜テンションで色々なことを試してみました。コードをみると保守性も何もあったもんじゃなく、まるでハウルの動く城みたいな継ぎ接ぎだらけの見栄えが悪いものですが、だんだんと点数が上がっていきました。
近傍が6つもできていた頃には5時を回り、点数は3000億9000万点くらいになっていました。しかし、それからがなかなか上がりません。
もう一度ヴィジュアライザで自分の解答を見てみます。
気になる部分がありました。上の画像の部分の一番右の青いオーダは明らかにもう一つ下の機械の一番後ろにつけるのが良さそうです。よくみると、他にもこのような状態になっている場所がいくつかありました。多分、移動するのを選択する時にvectorの最後の要素を見てなかったのでしょう。こういったバグにも気づけるのでヴィジュアライザはありがたいです。ただ、どこでそれが発生しているのかわからなかったので、これを解消できるようにと、他の機械の一番後ろにオーダを移動させるといった近傍を用意したりしてしまいました。
他にも色々な、良さそうな改良を付け加えていると、いつの間にか朝日は昇り、8時を過ぎていました。これから朝ごはんを食べたら、すぐに複数人の路上運転実習があります。これが最後の提出になるでしょう。
祈りながら提出すると、部屋を後にし、食堂に向かいました。
今日も美味しい朝ごはんをいただき、食後のお茶を飲みます。そして、おもむろにスマホを取り出すと、AtCoderのサイトにアクセスします。スマホなので、得点部分が見切れていて、何点取れているかわかりません。
徐々に左にスライドさせていきます。
300...
3001億点！！！ pic.twitter.com/jGQo5F2BBc
— ろい (@Roy_R_) August 29, 2019
やりました！ ついに3001億点を超えました！！！
喜びのまま複数人での路上教習に挑みます。
二時間かけて、山に登って降ります。途中でつづら折りがあったり、霧が出ていたりして、なかなか簡単にはいかない道のりでしたが、三人で運転を交代しながら、ついには目的地としていた道の駅にたどり着きました。
そこで、同じの車に乗っていた他の二人と一緒にソフトクリームを買って食べました。何かをやり遂げた後の感慨深さというか、なんというかで、非常に美味しく感じられました。
(ちなみに、この道の駅でスマホからちょっとパラメータを弄って10時5分前くらいにえいやっと投げてみたら、3000億9000万点くらいで、そっか……となりました)
まとめとか感想的な何か
運転免許合宿で暇な時間を非常に有意義なことに使わせてもらえて、Asprovaコンテストには感謝しています。また、この一週間で色々なことが学べた上、色々な一喜一憂ができて、非常に楽しかったです。このような楽しいマラソンマッチという競技を他の方達もぜひ知ってもらって、みんなやってくれるといいなーと思います。
僕は、乱択解くらいしかできなかったマラソンマッチ初心者でしたが、色々な先人の方の知恵をお借りすることで、なんとか焼きなまし法を理解し、使うことができるようになりました(Asprovaコンテスト終了の次の日に突然現れたchokudai contest 004という2時間のマラソンマッチにおいて、焼きなまし法を使うことができたのがその証拠です)。本当にありがとうございます。そして、この記事が他のマラソンマッチを始めてみようかな、と思っている方の一助になれば幸いに思います。
あと……
そういえばまだ、運転免許取れてないです。まだ合宿中です。明後日くらいに卒業試験があるので、そちらも頑張っていきます。
