第5回 Asprova Programming Contest 参加記

競プロの記事を書くのはこれが初めて。興味のない人は読み飛ばしてください。

12/30から1/6にかけてAtCoderで行われた、第5回Asprova Programming Contestに参加した。マラソンマッチに参加するのは初めてなのでいろいろ勉強になったことやコンテストの感想を書く。

コンテストについて

工場の生産スケジューラーを開発しているAsprovaが主催するマラソン型のコンテスト。第5回の問題は、とても簡単に言うと「ある工場において、注文の数量や納期、機械(主資源)の性能や従業員(副資源)の仕事の有無などのデータが与えられ、それぞれの注文に適切な資源を割り当てて利益を最大化するスケジュールを組め」というもの。一週間の間に、もっとも効率的な解を求めるプログラムを書く。

年末年始に行われる異常なコンテストだったが、参加者は50人以上いてびっくりした。第4回は80人くらいいたらしいのでそれよりは少ないが、年末年始にもプログラミングをする競プロerたちの意識の高さ(?)がうかがえる。

上位10位には賞金が与えられる(俺がこのコンテストに参加した最大の理由)。レートの代わりに賞金がもらえるというのは、また違ったわくわく感が味わえる。

まずしたこと

マラソンマッチは全く初めてで、何をすればよくわからなかったが、とりあえず問題の理解に努めることにした。マラソンマッチの問題は普通の競プロの問題に比べてはるかに長く複雑であり、一筋縄に理解できるものではない。

問題を読むだけだと情報量が多すぎて処理できなかったので、Google Docsに入力の情報や制約などをまとめていって、少しずつ理解していった。

ある程度問題の概要を理解したところで、サンプルのコードに目を通した。しかしこれも読むだけでは何をしているのかよくわからない。サンプルコードはC++で書かれているので、ここでこれをPythonで書きなおすことにした。俺はC++はググりながらなら読めるが書けない(書いたことない)ので、結局あとで俺の知っている言語で書くことになるから、問題を理解するためにPythonでサンプルを組みなおすことにした。

1、2時間かけてサンプルを翻訳して、さっそく実行!、、、したがサンプルの出力と全然違うものが出てきた。フォーマットは大体あっているようなのだが、数値が全然違う。付属の出力チェッカーを走らせてもエラーになる。どうしたものかと思い、ここからまた1、2時間デバッグに時間を費やした。結果タイポが2、3個あったことが発覚し、それらを直して再び実行したら、正しい結果が出て一安心。

とりあえずこのプログラムを提出してみた。サンプルのC++のコードをそのまま提出すれば多分142452035096が出る(この得点の人がめちゃくちゃ多いから多分これ)はずなのだが、俺のPythonのコードはC++のコードを忠実に翻訳したはずなのにちょっとそれよりも高いスコアが出た。この時点ではまだサンプルしか提出してない人がほとんどだったので、いきなり3位か何かになってとても喜んだ。

サンプルをPythonで書き直したことで問題の理解がかなり深まった。Pythonは可読性が非常に高いので、コードが何をしているのかを理解しやすかったし、実際に書いてみることでコードの流れを体で覚える(?)みたいなことができた。

コードを理解したところで、すぐにとても単純な改善策を思いついた。サンプルコードでは生産の機械を番号が最も若いものに割り当てているが、これをその品目の生産速度が最も速い機械に割り当てればいいんじゃないかと思い、それを実装して提出してみたところ、得点が大幅に伸びて1700億点くらいになった。

ここでもうアイデアが尽きてしまう。ここから何をすれば得点がさらに上がるのか。コードを眺めているだけじゃ何も思いつかないので、付属のビジュアライザーで出力を可視化してみることにした。

f:id:pepsisoda:20200109214621p:plain
段取りに多くの時間を取られていることがわかる

すると、品目を変えるときにかかる段取り時間を表す緑色の枠で、出力のほとんどが埋め尽くされていることに気づく。それもそうで、サンプルコードは注文を開始時間でソートして最初のやつから割り当てていっているので、生産する品目の順番はバラバラになる。段取り時間を最小限に抑えるためには、同じ品目の注文をすべて処理し、次に品目を変えてそれをすべて処理する、、、という風にすればいいはずだ。そこで、注文を生産品目でソートして、提出してみた。

すると、さらに得点が伸び、1900億点台に到達した。これでぶっちぎりの1位。あまりにもあっさり通ってしまったので、調子に乗る。マラソンマッチは所詮こんなもんか~w余裕~w

さらにいろいろ改善策を考えてみる。従業員の割り当ては、番号が一番若いやつになっているから、ランダムに選べば均等に分散されて効率よくなるかな~とか、完全に品目ごとに分けちゃうと最初の方の注文が大幅に遅れるから、注文を時間ごとに区切って、その中で品目ごとにソートしてみたりとか、いろいろ試した。

最終的に落ち着いた解は、

  • 機械は生産速度が最速のものに割り当てる。
  • 注文を時間でソートして、3つの部分に分けて、その中で品目ごとにまとめる。
  • 従業員は、稼働可能な時間が最も早いものに割り当てる。

これで1973億点を記録した。

f:id:pepsisoda:20200109215009p:plain
こんな感じになった。さっきよりはだいぶいい感じ。

作業の自動化

これまではテストケースのファイルをコードの中に書いて、コードからそれを開いて入力するというようにしていたが、テストケースを変えたいときにいちいち書き換えるのは面倒だし、AtCoderのサーバー上では標準入出力なので、提出するときに書き換えるのを忘れててREみたいなのが何度かあったので、テストを自動化することにした。

具体的には、コマンドラインで入力ファイルを指定して、それを標準入力でプログラムに渡して、標準出力をファイルに書き込むというスクリプトを書いた。ついでに付属のテストケースジェネレーターでテストケースを20個作り、それらすべてでテストして合計点数を出力するという、実際の得点方法を模したスクリプトも書いた。

最初はPowershellで書いたが、何かファイルに出力するときになぜかすべての文字の間に空白が入るので、Pythonで書き直した。Pythonからシェルコマンドを呼ぶ方法がわからなかったうえ、いろいろバグらせまくってたので、これの実装に3時間くらいかかった。

しかしこのおかげで、テストが簡単になり、提出するときに入出力のところを書き換える必要がなくなった。その後の開発がスムーズにできるようになった。マラソンマッチにおいてこういうところの整備は必須だと思う、知らんけど。

山登り法の導入

ここでアイデアが尽きてしまった。何かヒントを得るために、第4回Asprova Contestの情報が何か転がっていないかとググってみると、とても参考になる記事が見つかった。勝手にリンク張ります。

roy-r.hatenablog.com

この記事を読んで、初めて「山登り法」や「焼きなまし法」の存在を知った。マラソンマッチでは、ある程度良い解(貪欲解)を求めた後、それをさらに改善するために、これらの探索アルゴリズムが使われるらしい。探索アルゴリズムといっても、ダイクストラ法のような厳密な最短路を見つけるみたいなものではない。

山登り法は、いまある解をちょっといじって、それがもとよりよかったらそっちを採用する、ということを繰り返してどんどん改善していくというかなり直感的なアルゴリズムである。点数があがったらその方向に進む、というのが山を登っているようなのでこの名前。焼きなまし法はもうちょっと複雑だけど、基本的な概念は同じ。この記事ではこれらのアルゴリズムの深い説明はしないので、ほかの人の記事を当ってほしい。

いろいろ調べていくと、焼きなまし法最強、マラソンは大体焼きなましみたいな感じで語られていたが、まずはシンプルで実装しやすい(といっても焼きなましとほとんど同じだが)山登り法を試しに書いてみることにした。

ループを回す時間は、入出力や貪欲解の計算も含めての2秒の制限時間に間に合うように、1800ミリ秒回すことにした。評価関数は、付属の得点チェッカーのC++コードをそのまま翻訳した。

山登り法で重要なのは近傍の取り方(解のいじり方)だが、まずはとりあえず2つの操作をランダムに選んでそれらの場所を入れ替えるという近傍を取ってみた。

これを提出してみると、1977億点となり、スコアが4億点上昇した!やはり制限時間を使い切って、さらに良い解を探すという方法は必要なようだ。

高速化のためにJavaで書き換え

Pythonで書いた山登り法のループが何回くらい回っているか見てみたところ、小さいケースで数千回、大きいケースだと数百回回っていることが分かった。2秒も走らせた割には少ない気がしたが、Pythonだからこの程度が限界か。

山登りや焼きなましはループをできるだけ多く回すために高速化することが重要だといろいろな記事で書いてあったので、Pythonより速い言語で書き直すことにした。最初はRustで書こうと思ったが、Rustは先月勉強し始めたばかりで、AtCoderの精進は結構Rustでやってるけどこれほど複雑なプログラムを書ける自信がなかったので、書き慣れているJavaで書くことにした。

Javaは記述量が多いのでPythonより好きじゃないけど、俺が書ける言語(といってもJavaとPythonしかないけど)の中では最速なので仕方ない。

Javaで書き直すときもグローバル変数とかディープコピーの間違いとかPythonにはない間違いでバグらせまくり、かなり時間がかかったが、無事実装に成功し、提出してみる。

ドキドキしながら点数を見てみると、なんと、1991億点!!!14億点の大幅な改善である。やはり、山登り法においてスピードはかなり重要なファクターのようだ。

ループが何回回っているか調べたところ、小さいケースでは数十万回、大きいケースでも数千回回っていることが分かった。Pythonにくらべて10~100倍速い。桁が2つくらい違うwwwと大喜びしていた。


さらなる改善を求めて、最強とうたわれている焼きなまし法を試しに実装してみたが、実装の仕方が悪いのか、この問題にこの手法があっていないのかどうかはわからないが、スコアがかなり下がってしまった。まあでも直感的には、解をいじって点数があがる確率は低く、下がるときは多分大幅に下がるので、焼きなましよりも山登りの方が探索空間の遠いところまで行けるのかな、、、とか考えてみたが、よくわからない。とりあえず、この問題は山登り法で行くことにした。

近傍のさらなる改善

ここからは主に近傍の取り方を、試行錯誤を重ねて改善していくことになる。2操作のswapだけではなく、操作を一つ選んで機械の割り当てを変えたりだとか、swapの代わりに操作を一つ選んで別の場所に入れてみたりというのを試した。点数が上がったり下がったりしながら、1993億点まで改善した。

アイデアが尽きたので、ビジュアライザーを眺めていたら、全く使われていない機械や大きな空白の時間がある機械がいくつかあることに気づく。多分性能が悪いので貪欲解を作る時点で割り当てられなかったのだろうが、それでも機械の割り当てを変更する近傍があるので、全く使われないというのはないはずである。考えてみると、操作を1個だけ変更しても大勢にほとんど影響がなく、いくつかの操作をまとめて移動させることで初めて効果が表れそうである。なので、操作をいくつかまとめて機械の割り当てを変更するという近傍を取ることにした。

操作のまとまりを検知するには、順番的に(時間的にとは限らない)連続している、同じ品目の操作を見つけるだけにした。順番が連続しているところでも開始時間の関係で時間的に途切れていることもあるが、それも実装するのはめんどくさいので今はとりあえず順番の連続だけを考えることにした。同じ品目のまとまりをすべて取得して、その中から1つ選び、割り当てる機械を変更するプログラムを実装した。

せっかくまとまりを取得するプログラムを書いたので、それをもっと利用しようと、まとまりを対象に操作する近傍を何個か実装した。結果、この時点で5つの近傍ができた。

  1. 2操作swap
  2. まとまりを別の位置に移動させる(品目のまとまりの順番が変われば、段取り時間とかも変わってくるのでやってみた)
  3. まとまりを納期でソートする(開始時刻でソートするだけだと納期が早いやつが先に来るとは限らないから)
  4. まとまりを1つ選んで機械の割り当てを変える
  5. 2つのまとまりを結合する(まとまりが散乱していると段取り時間がかかるので)

これを提出してみると、1994億点を記録し、点数があがる。

俺はこの時点で10位だった。めっちゃ下がってるじゃん、と思うかもしれないが、強い人がどんどん参加してきてよいプログラムを提出するので、抜かされるのは仕方ない。このとき1位は1999億点で、1位とは5億点の開きがあるが、1990億点台のトップ集団(と俺が勝手に呼んでいる、ちょうど箱根駅伝をやってたのでそれっぽく)にはぎりぎり入っているので、これからさらに強い人が入ってきたとしても、まだ10位入賞の希望はあるといったところだ。


ここで、それぞれの近傍がどれくらいスコアの改善に貢献しているのか見てみる。とりあえず、10個のテストケースに対して、それぞれの近傍でスコアが改善する確率を計算して出力してみたところ、近傍4はほとんど使われなく、近傍2と3は思ったより使われていることが分かった。これを踏まえて、それぞれの近傍が実行される確率をもっといい感じに割り当ててみた。すると、1995億1000万点となり、さらに1億点改善された。順位は変わらなかったが、スコアが着実に伸びているので楽しかった。


近傍だけではなく、貪欲解もいじってみた。注文を3つに分けるのではなく、4つや5つに分け、代わりに近傍5(2つのまとまりを結合)の確率をあげてみたら、1995億8000万点となり、9位に浮上した!

ここでコードを眺めていたら、近傍5のコードがバグっていた(エラーが起きるわけじゃないけど、ロジックが間違っていてうまく結合されてなかった)ことに気づき、書き直して再び提出してみた。すると、1996億点を記録し、一気に7位に浮上した!1位は相変わらず1999億点だったので、トップとの差も3億点まで縮まり、優勝も夢じゃなくなってきた。

しかしこれ以上の改善は難しくなってきた。ビジュアライザーとひたすらにらめっこして、これいけそうだなっていう近傍を追加したりしても点数は伸びない。たまに明らかに並べ替えたらよくなるような操作があっても、それを本質的な改善につなげることはできなかった。アイデアが尽きる中、また少しずつ抜かされ始め、焦りが募った。

もうどうしようもないので、パラメーターを色々いじって提出しまくることにした。貪欲解の分割の数とか、各近傍に割り当てる確率の値とかを変えてこれよさそうだなーって思ったやつを適当に提出していった。すると、なんと1998億点を記録し、再び7位に舞い戻った!!!

なんか上から4桁目が見たことない数字になっていて、10億点くらい下がったのかなと思ったら、2億点も上がっていた!とてもうれしかった。この辺で10位入賞を確信して調子に乗っていた。1位まであと1億点。マラソン初参加のまだ大学にも行っていないやつが優勝したらかっこいいよな~wwwみたいな妄想を膨らませて、賞金で何買おうとか考えていた。

執念の高速化

1月5日、コンテストは最終日に突入した(コンテストは1/6の朝10時までなので実質この日が最後)。しかし、ここからスコアが全然伸びなくなった。ビジュアライザーを細かく見て、近傍ごとの点数上昇率とかを計算して、パラメーターをいい感じにいじっていって、ローカルでは点数が伸びているのだが、提出しても全然伸びない。近傍の細かい実装のところをいじったり、もう一度焼きなましを試したりいろいろやった。もっと速くなるかなと思って、5時間くらいかけて頑張ってRustで書き直したりもした(なぜかスコアが大幅に下がり、調べてみたら、ループがPython並みにしか回ってなかった。RustはC並みに速いと聞いていたし、AtCoderで精進するときも実行速度がPythonよりも圧倒的に速いのでおかしいな。多分実装の仕方が下手だったんだろう)。いろいろ試してもスコアが伸びず、そんな間にもまた抜かされていき、9位まで下がった。最終日で多分みんな頑張ってスコアを挙げようとしていたのだろう。

あまりにも点数が伸びず、1998億点どころか1997億点にも届かない提出があまりにも多かったので、これはおかしいなと思い、1998億点をとったプログラムを何も変えずにもう一回提出してみたら、1996億9000万点くらいだった。めちゃくちゃ焦った。たぶん1998億点を取ったときは乱数がたまたまいい感じに出てくれたおかげで、点数が高いところにはまったんだろう。2回目の提出が逆にたまたま悪かったという可能性もあるが、実際の点数が1998億点からかけ離れていることを知り、かなり焦った。1997億点じゃ10位には入れない。

この時点で9位で、まだ10位以内には入っているが、残り半日の激しいデッドヒートの中で9位では心もとないので、もう少し点数を伸ばしたい。しかし、これ以上の本質的な改善は見込めない。もうこれ以上改善策が思いつかない。そこで、苦肉の策で、コードをひたすら高速化してループを回す回数を少しでも増やすことにした。根性でやれることをやっておこうと思った。それに、いろいろ試行錯誤をしているうちにコードが肥大化してきていたので、整理して可読性を高めるのにちょうどいいと思った。

まあとりあえず試しに書いて没になってコメントアウトしてたところを全部消した。そしてHashMapやArrayListなどのデータ構造は、可能なところは配列や2次元配列で置き換えたり、乱数生成のクラスをより高速なもので代用したりした。あと時間を取得する関数にものすごい時間がかかっていることが分かったので、イテレーションごとに時間を取得するのではなく、400イテレーションごと(これ以上にするとTLEすることがある)に時間を取得するようにした。また、可読性を高めるために、共通のコードがある部分は関数で処理をまとめた。

このような高速化/リファクタリングの結果、コードがかなりすっきりした。もともと600行以上あったのが500行程度にまで減り、プログラムの流れがかなりつかみやすくなった。これを提出してみる。すると、、、

1998億7000万点、かなりの点数の向上に成功した!!!この時はかなりうれしかった。実際にどのくらい速くなったのか見てみたら、イテレーションの数が約3倍になっていた。イテレーションの数が増えてくるとスコアの上昇が鈍くなってくるが、今までのコードでは、特に大きいテストケースでは全然収束していなかったので、ループが3倍回るのはかなりでかい。

残り時間もわずかなので、8位もあれば10位入賞は十分可能だろう。入賞を確信したのでこんなツイートをしたりした。

もっと続けていたかったが、時間は夜中の1時を回っていたので、とりあえず寝ることにした。

衝撃の結末

1月6日朝6時半、俺は目覚ましの音に目覚めた。気持ちのいい朝だ。さて、順位表はどうなっているかな、と思い、さっそくスマホをポチポチして確認する。

こんなことある????????展開完璧すぎない?昨晩のツイートのフラグを見事に回収した。

この展開はある程度予測していたが、当然起こってほしくないのであまり考えないようにしていた。しかしその予想は見事に的中、ピンポイントで11位だった。今までずっと潜伏してきて、残り数時間で初提出でかなりいい点数を取った人とか、昨晩は俺より下だったけど点数を大幅に伸ばした人とかがいて、11位まで下がった。

俺は絶望した。こんなに頑張ってきて、今までずっと10位以内に入っていたのに。。。最後の最後で大逆転敗北はつらすぎる。。。。

しかし、諦めたらそこで試合終了と自分に言い聞かせ、いつもなら二度寝するところを、ベッドから這い出てもうちょっと頑張ってみることにした。といってもこれ以上できることは高速化とパラメーターいじりだけだが。

評価関数は実際のスコアを計算する必要はなく、ペナルティーだけ計算すれば機能することに気づいたのでそうして高速化を図った(大して影響ない?)。あとはパラメーターいじり。近傍ごとのスコア上昇率を見て確率をいい感じに割り当てる。昨晩の1998億7000万点はまたまぐれだった説はあるが、その後も1998億点台は何回か出ているので、だいぶコードの質は良くなっていっていると思う。

コンテスト終了の10時ぎりぎりまでもがいてみたが、結果は変わらず、11位で終了した。

いや、こんな悔しい思いをするのは久しぶりだ。悔しすぎて笑うしかない。というかフラグ回収が見事すぎて普通に面白い。年末年始の時間を削ってこのコンテストに費やして(といってもほかにすることもなかったが)頑張ってきたが、最後の夜まで夢を見せておいて目が覚めたら負けてるというのはつらすぎる。

待て、コンテストはまだ終わっちゃいない。

コンテストが終了すると、それまでの提出に対してシステムテストが実行される。コンテスト中は20個のテストケースに対して得点が計算されるが、システムテストでは(確か)180のテストケースに対して実行される。どうやらコンテスト中のテストケースとシステムテストのテストケースは結構違うらしく、ここで逆転をする可能性もなくはない。もちろん順位が下がることもあり得るが、おれはもうこれ以上下がってもどうでもいいので、システムテストで10位に食い込む可能性に賭けたい。10位との差は4000万点くらいあり、もしかしたらそれは俺みたいにまぐれで取った点数かもしれないので、それくらいは誤差の範囲といえる。

システムテストの結果が出るのは2、3日後なので、それまでは受験勉強をすることにする。そういえば俺受験生じゃん。来週センターじゃん。プログラミングしてる場合じゃ無くね?

翌日、ツイッターを見ながらとてもまじめに勉強していると、システムテストで順位がかなり変動しているとの情報が流れてきた。正直システムテストで順位が変わることは半分諦めていたが、これを見てまた希望が湧いてきた。さっそく順位表を見てみると、俺は11位ではなかった。


17位だったwwww。順位が大幅に変動していたものの、俺ほど落ちた人はなかなかいないんじゃないか。さすがに落ちすぎなのでおかしいと思ってしらべてみたら、180のテストケースのうちの一つでTLE(時間制限超過)していた。結構時間ギリギリまでループを回していたし、乱数生成のところでうまく出ないと何回もループが回ることになるので、大きいケースの一つでTLEしたらしい。TLEで10億点近く損し、今のスコアに10億点くらい足すとちょうど10位に入るか入らないかくらいなので、もしかしたら入賞できたのかもしれない。本当に惜しいことをした。

まあでも、17位まで落ちたことで少し吹っ切れた感はある。11位ぎりぎりで負けるよりも、17位まで落ちてしまった方が、後味がすっきりする。なので結果オーライということでいいか。

学んだこと、感想

マラソンマッチに初めて参加し、得られたものは大きかった。まず、いつものようなアルゴリズム力を競う競プロとは全く違う思考方法を迫られた。マラソンマッチでは、「正しい解を求める」プログラムではなくて、「より良い解を求める」プログラムを書くことが求められる。最初こそ貪欲法しか知らなかったが、そこから少しずつ解に磨きをかけていくというプロセスを踏んで、マラソンマッチで戦えるようになるのである。そのために山登り法や焼きなまし法などの汎用的なメタヒューリスティックがあるが、それだけではなく、その問題に特有のアドホックな思考が必要でもある。それには柔軟な発想だとか、ビジュアライザーとにらめっこしながら改善点を探していく忍耐力も必要である。と初心者の分際で偉そうなことを言ってみるけど、俺が受けたマラソンマッチの印象はこんな感じである。

あとは実装力が伸びた気がする。マラソンマッチはアルゴリズムの知識がそこまでいらない分(あるに越したことはないと思うし、今回の問題もJob Shop Schedulingとか組み合わせ最適化の知識とかあったらだいぶ有利になりそうだが)、実装力がものをいう。コード量がABCとかで書くようなやつより圧倒的に多いので、コードを簡潔に書く力がないと何書いているのかすぐわからなくなりそうだし、何より思いついた解法を素早く正しく実装する力は必要である。今回多分トータルで1000行以上書いたが、実装のいい練習になり、純粋なプログラミング能力が上がってきている気がする。

また、開発の手法における様々なノウハウを得られた。とくに入力を外部のスクリプト経由でプログラムに送ったり、テストを自動化したりすることを今回やったおかげで、次回からはこのようなことがよりスムーズに行えるはずだ。

これからは、俺もマラソンマッチに積極的に参加していこうと思う。プログラミング二度とやらないとか言ったけどもちろん続ける。今回のは本当に惜しかったので超絶悔しかったが、次回はこんな思いをしないようにもっとプログラミング頑張るぞ。とりあえず受験が終わるまで極度の精進とか時間のかかるマラソンとかは控えるが、それが終わったらプログラミング三昧の日々を送りたい。今年の目標はAtCoder黄色。

f:id:pepsisoda:20200109215256p:plain
最終的にこんな感じ。このテストケースはもう改善の余地がない感じ。

懇親会にも参加してきた

1/10に開かれた、コンテストの懇親会に参加した。入賞者のプログラム解説を聞きたかったし、競プロ界隈の人と絡んだことないので、いい機会だと思い行ってみた。

入賞者のプログラムの内容をここで書いていいのかわからないから詳しいことは書かないけど、どのプログラムも思ったよりシンプルだなと思った。俺は近傍を5個も用意して、もっと増やそうとしていたけど、上位者は近傍がそんな多くなかった。代わりに、最初の貪欲でソートのパラメータを工夫したりだとか、オーダーをまとまりで扱うとか、オーダーの挿入の場所をもっとちゃんと計算したりとか、より深い考察ができているのかなと思った。おれはとりあえず近傍をたくさん作ればそのうちいいのができるかなと思ってやっていたので、こういうところは反省点。あと上位者は大体やっぱり焼きなましだったようだ。なんで俺がやったら点数が下がるのかわからないけど、もしかしたらループを回す回数が少なすぎたのかもしれない。みなループをより多く回す工夫をしていたから、焼きなますなら試行回数を多く稼がなきゃならないのかな。

あと、やっぱりJavaでマラソンやるのはきついかもということも言われた。そりゃPythonよりは断然速いけど、やっぱり上位陣はみんなC++を使っていて、ループも何十万回も回っていたらしい。おれもC++を勉強するか、それともRustをもっとちゃんと書けるようにするか…。

あとはAsprovaの社長がTLEの理由を教えてくれた。俺は200か400イテレーションごとに時間を計測していたが、そのイテレーションの途中にTLEしたらしい。Javaの時間を計測する関数はバカ遅いのでできるだけ少ない回数やろうと思ったが、それが裏目に出てしまった。100とかなら行けたのかな。

いろいろなことが知れてとてもためになった懇親会だった。第6回Asprovaコンでは、今回の教訓を生かして、10位入賞を狙いたい。