この手法のコツは、できるだけお相手が理解できなさそうな証明を利用することですね。よって僕は君を愛している」みたいなことを言うと「ふざけてるの?」となりますが、このような意味の分からない証明ならばきっと大丈夫です!バリエーション相手が高校生以下または文系大学生および社会人たぶんこの「最大フロー最小カット定理」で十分です。相手が理系なら、この定理の証明を理解してしまう恐れがあるので、フェルマーの最終定理の証明でとどめを刺しましょう。彼らはフェルマーの最終定理の証明ですら理解してしまう恐れがあるので、ここは望月新一教授の宇宙際タイヒミュラー理論(IUT)の論文を用いて攻めましょう。理解している人は世界に数人しかいないようです。600ページもある論文なので音読の途中に相手が飽きて帰らないように注意してください。まとめいかがでしたか?バレンタインの日にふさわしい、数学で愛を伝える言葉を10個紹介しました。なんでこんな思いつくの?と思うかもしれませんが、彼女がいないとこれくらいしか考えることがないのです!僕なんかは、「あなたは私の秘密鍵。今日は中学からの友達と、六本木ヒルズの森美術館に行ってきた。六本木は初めて!六本木ヒルズはめちゃくちゃ高かった。エレベーターに乗って、気づいたら52階に。展望台があったので外を眺めてみると、眼前に東京タワーの姿があった。東京タワーは遠くから見ると大して高くないなという印象を受けるけど、近くで見るとやはり高い。奥の方にスカイツリーも一緒に見えた。こちらは何度見てもバカ高い。東京タワー、こんなに近くで見るのは初めて今日見た展示の題名は、「未来と芸術展:AI、ロボット、都市、生命~人は明日どう生きるのか」。連れが美術館に行きたいと言っていたので、候補を見せてもらったところ、俺の興味のあるテック系の展示が見れそうだったので、森美術館を選んだ。日本科学未来館のような雰囲気を感じたので、これは楽しめそうだ。ところで彼は(ガチの)アーティストで、やっぱり芸術家と美術館を回るのは一味違って面白い。入って最初に、AI美空ひばりに出迎えられた。日本を代表する歌手(といってみたものの、俺は知らない)である故人美空ひばりの姿と声を、AIテクノロジーによって復活させようという試みで、2019年の紅白歌合戦で見た人も多いだろう。このプロジェクトは死者への冒涜だという批判もあるらしいけれど、とりあえず倫理的な問題は置いといて見て思ったことを書きたい。俺が彼女(あえて、「それ」ではなく「彼女」といってみる)を紅白で見た時、そのクオリティに驚いたのを覚えている。本人がそこにいるようななめらかで自然な動きが表現されており、声もまるで人間が歌っているような響きがあった。俺は本人の声を知らないので似ているのかどうかは判断できないが、たぶん似ているのだろう。ボカロの声とかは、どこか機械的な、人工的な響き(全然聞かないので最近はどうなのかわからないけど、少なくとも数年前はそうだった)がするけれど、AI美空ひばりの声はとても自然だった。今回、彼女を間近で見てみて、改めてその質の高さに感動した。AIが人の声をまねできるというのはだいぶ前からニュースになっていて知っていたが、実際に見てみるとやはり迫力がある。AI美空ひばりは、不気味の谷を優に超えている。この技術はもちろん悪用は可能で、実際ディープフェイクとかが問題になっている一方、このようにエンターテインメントとしてうまく活用すれば、新しい領域が開けるのかもしれない。展示は「都市と建築」→「ライフスタイル?」→「生命?」→「AI?」みたいな感じで並んでいる。最初の都市・建築のコーナーでは、現在進行している急進的な都市計画とか、面白い形をした建物の構想案とかが展示されていた。前から思っていたことだが、大体の「未来都市」の想像図みたいなものは決まって、超高層ビルから植物が生えているような感じである。建物は高くなりかつ密度を増していくが、それと同時に街に緑があふれている、というようなイメージが共通している。環境にやさしいとか、持続可能な社会みたいなことを表現しているのだろう。ありふれたイメージだけども、俺はこれが結構好きで、こんな街に住みたいなと思う。六本木ヒルズの展望台から東京を一望したとき、視界に入ってくるのはただひたすら地平線まで届く、灰色のビル群だった。広い関東平野が無機的な人工物によって覆いつくされ、それから出る煙で空はかすんでいる。これが世界最大の都市・東京かと思うと、何か少し悲しみのようなものすら感じる。語彙力がなさすぎるんだけど、なんかもっと、自然と調和しなきゃなって思う。自然と融合した、地球と調和した未来が来ることを願うばかりである。これは中国の先進的な建築ライフスタイルについての展示では、食に関するアートが目を引いた。近年昆虫食が注目を集めているが、ここではカラフルな遺伝子組み換えゴキブリの広告を模したアートが展示してあった。気持ち悪いし絶対に食いたくない。あとは3Dプリンターで寿司を作る機械の展示があった。実際にこの機械を使ったレストランが数年後に東京で開かれるらしい。寿司といってもいつも見るようなものとは全く違う形をしており、何かとげがたくさん生えていたり、立方体の形をしていたりと様々だ。食べ物が3Dプリンターで作られるようになれば、レシピはデジタル化して共有することができるし、今までにできなかったようなものも作れるようになるはずだ。テクノロジーと食の融合はまた新しい可能性を秘めている。寿司の3Dプリンター。(寿司の特異点)犬ロボットaiboと、よくわからないけどかわいいペンギンのようなロボットの展示もあった。なでると鳴いたり喜んだりする。いつかロボットがペットとなることのできる時代が来るのかもしれない。かわいいこれは次の生命に関する展示にあった、心臓の模型。生命の象徴である心臓を神聖なものを祭るように展示することで、生命工学はどこまで踏み込んでいいのかという問いを提示しているらしい。なんだかゲド戦記を思い出すこれは半分人間、半分チンパンジーの親子を想像して作られた模型。このようなことも技術的に可能となるのだろうが、そんなことをしていいのだろうかという倫理的な問題が残る。親はチンパンジー似で、子どもは人間似。最後はAIについての展示。有名な「トローリー問題」を扱ったアニメーションだとか、AIを裁く裁判の映像作品だとか、観客の顔を認識・追跡してスクリーンに表示する、中国の監視社会を彷彿とさせる展示などがあった。中でも特に考えさせられたのは、AIによって作られたアートである。これはAIではないんだけど、コンピューターがランダムに決めた長さや太さの金属パイプをたくさんつなげた作品。「人間にはこれを作ることは不可能」という説明書きがされていた。確かに、この大量のパイプの形をすべてランダムに決めてつなげるというのはとても人間にできることではない。コンピューターによって作られた幻想的な空間これは、どこかのウェブサイトで"everything"というタグがつけられた画像をAIに学習させて作った映像。「すべての歴史」みたいなタイトルだったと思う。花や建物、宇宙などのオブジェクトのぼんやりとしたイメージが、シームレスに流れていく様子は、何か神秘的であり、ほんとうに「すべての歴史」を体現しているような印象を受けた。これが、すべての歴史AIは芸術家になれるのかという問いがあるけども、俺はあくまでAIは創造を手助けするツールであると思う。AIは自分で何かを作りたい、表現したいという欲求は持たないが、アーティストがその目標を達成する手段として、活用することはできる。それでいて、AIが作り出すアートは、芸術家が何億人集まろうとも作れないものである。俺はアートには詳しくないけれども、思うに、AIによるアートっていうのはもっとも純粋な形の芸術なのだと思う。AIは文化的、社会的なバイアスを全く持たない。それは、膨大なデータに基づいた、客観的な統計なのである。AIによって作り出されるアートは、人種や世代を超えることのできる、最も普遍的な形のアートなのではないだろうか。AIのバイアスをなくそうという動きが最近大きくなっているようである。会社の社員を採用するアルゴリズムが、人種や性別によって判断を下したりといった問題が起きているからだ。このあいだも、日本のAI研究者の大澤昇平が「うちは中国人は雇わない」などとツイートして大炎上したが、彼はそれはAIによる判断だったと説明した。おれは、アルゴリズムはあくまでも客観的な判断を下しているのだと思う。これは人種差別を助長したり大澤氏を擁護したりするために言っているのではないが、明らかに人種や性別と能力に大まかな相関関係はあると考える。実際黒人は身体能力が高いだとか、アジア人は数学が得意だとかという特徴はある。そのステレオタイプをその集団全員に当てはめることはいけないということを私たちは知っているし、人種を基に何かの判断を下すのも倫理的にいけないことを知っている。私たちは、AIのバイアスをなくすのではなく、AIに「人種・性別を基に判断を下してはいけない」という正のバイアスを組み込んでいるのではないだろうか。バイアスのない純粋なAIは時に倫理的に間違った行動をするから、私たちが倫理的なバイアスを組み込んでやらなければいけない、そういうことだと思う。話がそれてしまったが、アルゴリズムの客観的な統計によって作り出されるアートは、人間の文化的、倫理的バイアスにとらわれていないという点で、ある意味、人間を超越しているのかもしれない。AIが学習するデータが人間によって作られるものなら多少のバイアスは含まれるけど、意思決定の段階では全く純粋な判断をするのだ。宇宙人がいたとして、彼らが人間のアートを理解できなくても、AIのアートなら理解できるのだろうか。考えさせられる展覧会であった。アートっていうのは、何かに解決策を提示するものではなく、解決されるべき問題を提示するのが役目なのだと思う。例のチンパンジーの展示は、生命倫理についての問いを提示しているし、ゴキブリだって、「食べ物とは何か」といった問いを発しているととらえることもできる。その問いにテクノロジーが答えていく。過去のSFは今の日常となり、今日の不可能は明日の常識となる。このプロセスを繰り返していくことで、歴史が形作られていくのではないだろうか。アートが社会に対して未来の方向性を問うことによって、人類が進むべき方向が決定されるんだと思う。それじゃあ、AI美空ひばりは社会に対する何かの問いかけなのだろうか?例えば、「死とは何か」。このプロジェクトで姿と声は死後もよみがえることができることが証明された。いつか思考もデジタルに保存できるようになったとしたら、死とは何を意味するのだろうか?生物的な生というのは大して本質的に重要なものではなくなるのか?その人に関するあらゆる情報が死後も生き続けるのなら、それは生きていると言えるのだろうか?問いはいくらでも出てくる。アートは問題提起の一つの手段でしかなく、それにはほかにもいろいろな方法がある。本を書くとか、テレビに出るとか、ブログやソーシャルメディアで発信するとか、友達と話すとか。未来に対する問いかけができる能力は、これからどんどん重要になっていくんじゃないか。身の回りに情報があふれる中で、しっかり自分の考えや方向性を決めるためにも、問題提起の能力は必要だと思う。した能力をしっかり育んでいきたいと思った。学ぶことの多い一日であった。日本科学未来館は、未来的なテクノロジーがたくさんあって理系の人間としては聖地のような場所だが、美術館ではアートから現代・未来の科学技術について考えることができたとおもう。参加記プログラミング競プロの記事を書くのはこれが初めて。興味のない人は読み飛ばしてください。Contestに参加した。マラソンマッチに参加するのは初めてなのでいろいろ勉強になったことやコンテストの感想を書く。コンテストについて工場の生産スケジューラーを開発しているAsprovaが主催するマラソン型のコンテスト。第5回の問題は、とても簡単に言うと「ある工場において、注文の数量や納期、機械(主資源)の性能や従業員(副資源)の仕事の有無などのデータが与えられ、それぞれの注文に適切な資源を割り当てて利益を最大化するスケジュールを組め」というもの。一週間の間に、もっとも効率的な解を求めるプログラムを書く。年末年始に行われる異常なコンテストだったが、参加者は50人以上いてびっくりした。第4回は80人くらいいたらしいのでそれよりは少ないが、年末年始にもプログラミングをする競プロerたちの意識の高さ(?)がうかがえる。上位10位には賞金が与えられる(俺がこのコンテストに参加した最大の理由)。レートの代わりに賞金がもらえるというのは、また違ったわくわく感が味わえる。したことマラソンマッチは全く初めてで、何をすればよくわからなかったが、とりあえず問題の理解に努めることにした。マラソンマッチの問題は普通の競プロの問題に比べてはるかに長く複雑であり、一筋縄に理解できるものではない。Docsに入力の情報や制約などをまとめていって、少しずつ理解していった。ある程度問題の概要を理解したところで、サンプルのコードに目を通した。これも読むだけでは何をしているのかよくわからない。サンプルコードはC++で書かれているので、ここでこれをPythonで書きなおすことにした。俺はC++はググりながらなら読めるが書けない(書いたことない)ので、結局あとで俺の知っている言語で書くことになるから、問題を理解するためにPythonでサンプルを組みなおすことにした。1、2時間かけてサンプルを翻訳して、さっそく実行!、、、したがサンプルの出力と全然違うものが出てきた。フォーマットは大体あっているようなのだが、数値が全然違う。付属の出力チェッカーを走らせてもエラーになる。したものかと思い、ここからまた1、2時間デバッグに時間を費やした。結果タイポが2、3個あったことが発覚し、それらを直して再び実行したら、正しい結果が出て一安心。このプログラムを提出してみた。サンプルのC++のコードをそのまま提出すれば多分142452035096が出る(この得点の人がめちゃくちゃ多いから多分これ)はずなのだが、俺のPythonのコードはC++のコードを忠実に翻訳したはずなのにちょっとそれよりも高いスコアが出た。この時点ではまだサンプルしか提出してない人がほとんどだったので、いきなり3位か何かになってとても喜んだ。サンプルをPythonで書き直したことで問題の理解がかなり深まった。Pythonは可読性が非常に高いので、コードが何をしているのかを理解しやすかったし、実際に書いてみることでコードの流れを体で覚える(?)みたいなことができた。コードを理解したところで、すぐにとても単純な改善策を思いついた。サンプルコードでは生産の機械を番号が最も若いものに割り当てているが、これをその品目の生産速度が最も速い機械に割り当てればいいんじゃないかと思い、それを実装して提出してみたところ、得点が大幅に伸びて1700億点くらいになった。ここでもうアイデアが尽きてしまう。ここから何をすれば得点がさらに上がるのか。コードを眺めているだけじゃ何も思いつかないので、付属のビジュアライザーで出力を可視化してみることにした。段取りに多くの時間を取られていることがわかるすると、品目を変えるときにかかる段取り時間を表す緑色の枠で、出力のほとんどが埋め尽くされていることに気づく。それもそうで、サンプルコードは注文を開始時間でソートして最初のやつから割り当てていっているので、生産する品目の順番はバラバラになる。段取り時間を最小限に抑えるためには、同じ品目の注文をすべて処理し、次に品目を変えてそれをすべて処理する、、、という風にすればいいはずだ。そこで、注文を生産品目でソートして、提出してみた。すると、さらに得点が伸び、1900億点台に到達した。これでぶっちぎりの1位。あまりにもあっさり通ってしまったので、調子に乗る。マラソンマッチは所詮こんなもんか~w余裕~wasprovaコン暫定1位。ここで終わってほしい。2019さらにいろいろ改善策を考えてみる。従業員の割り当ては、番号が一番若いやつになっているから、ランダムに選べば均等に分散されて効率よくなるかな~とか、完全に品目ごとに分けちゃうと最初の方の注文が大幅に遅れるから、注文を時間ごとに区切って、その中で品目ごとにソートしてみたりとか、いろいろ試した。機械は生産速度が最速のものに割り当てる。注文を時間でソートして、3つの部分に分けて、その中で品目ごとにまとめる。従業員は、稼働可能な時間が最も早いものに割り当てる。これで1973億点を記録した。さっきよりはだいぶいい感じ。作業の自動化これまではテストケースのファイルをコードの中に書いて、コードからそれを開いて入力するというようにしていたが、テストケースを変えたいときにいちいち書き換えるのは面倒だし、AtCoderのサーバー上では標準入出力なので、提出するときに書き換えるのを忘れててREみたいなのが何度かあったので、テストを自動化することにした。具体的には、コマンドラインで入力ファイルを指定して、それを標準入力でプログラムに渡して、標準出力をファイルに書き込むというスクリプトを書いた。ついでに付属のテストケースジェネレーターでテストケースを20個作り、それらすべてでテストして合計点数を出力するという、実際の得点方法を模したスクリプトも書いた。最初はPowershellで書いたが、何かファイルに出力するときになぜかすべての文字の間に空白が入るので、Pythonで書き直した。Pythonからシェルコマンドを呼ぶ方法がわからなかったうえ、いろいろバグらせまくってたので、これの実装に3時間くらいかかった。このおかげで、テストが簡単になり、提出するときに入出力のところを書き換える必要がなくなった。その後の開発がスムーズにできるようになった。マラソンマッチにおいてこういうところの整備は必須だと思う、知らんけど。山登り法の導入ここでアイデアが尽きてしまった。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つの近傍ができた。2操作swapまとまりを別の位置に移動させる(品目のまとまりの順番が変われば、段取り時間とかも変わってくるのでやってみた)まとまりを納期でソートする(開始時刻でソートするだけだと納期が早いやつが先に来るとは限らないから)まとまりを1つ選んで機械の割り当てを変える2つのまとまりを結合する(まとまりが散乱していると段取り時間がかかるので)これを提出してみると、1994億点を記録し、点数があがる。俺はこの時点で10位だった。下がってるじゃん、と思うかもしれないが、強い人がどんどん参加してきてよいプログラムを提出するので、抜かされるのは仕方ない。このとき1位は1999億点で、1位とは5億点の開きがあるが、1990億点台のトップ集団(と俺が勝手に呼んでいる、ちょうど箱根駅伝をやってたのでそれっぽく)にはぎりぎり入っているので、これからさらに強い人が入ってきたとしても、まだ10位入賞の希望はあるといったところだ。ここで、それぞれの近傍がどれくらいスコアの改善に貢献しているのか見てみる。10個のテストケースに対して、それぞれの近傍でスコアが改善する確率を計算して出力してみたところ、近傍4はほとんど使われなく、近傍2と3は思ったより使われていることが分かった。これを踏まえて、それぞれの近傍が実行される確率をもっといい感じに割り当ててみた。すると、1995億1000万点となり、さらに1億点改善された。順位は変わらなかったが、スコアが着実に伸びているので楽しかった。近傍だけではなく、貪欲解もいじってみた。注文を3つに分けるのではなく、4つや5つに分け、代わりに近傍5(2つのまとまりを結合)の確率をあげてみたら、1995億8000万点となり、9位に浮上した!Asprovaコン9位に浮上。2020ここでコードを眺めていたら、近傍5のコードがバグっていた(エラーが起きるわけじゃないけど、ロジックが間違っていてうまく結合されてなかった)ことに気づき、書き直して再び提出してみた。すると、1996億点を記録し、一気に7位に浮上した!1位は相変わらず1999億点だったので、トップとの差も3億点まで縮まり、優勝も夢じゃなくなってきた。これ以上の改善は難しくなってきた。ビジュアライザーとひたすらにらめっこして、これいけそうだなっていう近傍を追加したりしても点数は伸びない。明らかに並べ替えたらよくなるような操作があっても、それを本質的な改善につなげることはできなかった。アイデアが尽きる中、また少しずつ抜かされ始め、焦りが募った。しようもないので、パラメーターを色々いじって提出しまくることにした。貪欲解の分割の数とか、各近傍に割り当てる確率の値とかを変えてこれよさそうだなーって思ったやつを適当に提出していった。2020なんか上から4桁目が見たことない数字になっていて、10億点くらい下がったのかなと思ったら、2億点も上がっていた!とてもうれしかった。この辺で10位入賞を確信して調子に乗っていた。マラソン初参加のまだ大学にも行っていないやつが優勝したらかっこいいよな~wwwみたいな妄想を膨らませて、賞金で何買おうとか考えていた。執念の高速化1月5日、コンテストは最終日に突入した(コンテストは1/6の朝10時までなので実質この日が最後)。ここからスコアが全然伸びなくなった。ビジュアライザーを細かく見て、近傍ごとの点数上昇率とかを計算して、パラメーターをいい感じにいじっていって、ローカルでは点数が伸びているのだが、提出しても全然伸びない。近傍の細かい実装のところをいじったり、もう一度焼きなましを試したりいろいろやった。速くなるかなと思って、5時間くらいかけて頑張ってRustで書き直したりもした(なぜかスコアが大幅に下がり、調べてみたら、ループがPython並みにしか回ってなかった。RustはC並みに速いと聞いていたし、AtCoderで精進するときも実行速度がPythonよりも圧倒的に速いのでおかしいな。実装の仕方が下手だったんだろう)。試してもスコアが伸びず、そんな間にもまた抜かされていき、9位まで下がった。最終日で多分みんな頑張ってスコアを挙げようとしていたのだろう。2020あまりにも点数が伸びず、1998億点どころか1997億点にも届かない提出があまりにも多かったので、これはおかしいなと思い、1998億点をとったプログラムを何も変えずにもう一回提出してみたら、1996億9000万点くらいだった。1998億点を取ったときは乱数がたまたまいい感じに出てくれたおかげで、点数が高いところにはまったんだろう。2回目の提出が逆にたまたま悪かったという可能性もあるが、実際の点数が1998億点からかけ離れていることを知り、かなり焦った。1997億点じゃ10位には入れない。この時点で9位で、まだ10位以内には入っているが、残り半日の激しいデッドヒートの中で9位では心もとないので、もう少し点数を伸ばしたい。これ以上の本質的な改善は見込めない。これ以上改善策が思いつかない。そこで、苦肉の策で、コードをひたすら高速化してループを回す回数を少しでも増やすことにした。根性でやれることをやっておこうと思った。それに、いろいろ試行錯誤をしているうちにコードが肥大化してきていたので、整理して可読性を高めるのにちょうどいいと思った。試しに書いて没になってコメントアウトしてたところを全部消した。HashMapやArrayListなどのデータ構造は、可能なところは配列や2次元配列で置き換えたり、乱数生成のクラスをより高速なもので代用したりした。あと時間を取得する関数にものすごい時間がかかっていることが分かったので、イテレーションごとに時間を取得するのではなく、400イテレーションごと(これ以上にするとTLEすることがある)に時間を取得するようにした。可読性を高めるために、共通のコードがある部分は関数で処理をまとめた。このような高速化/リファクタリングの結果、コードがかなりすっきりした。600行以上あったのが500行程度にまで減り、プログラムの流れがかなりつかみやすくなった。20201998億7000万点、かなりの点数の向上に成功した!!!この時はかなりうれしかった。実際にどのくらい速くなったのか見てみたら、イテレーションの数が約3倍になっていた。イテレーションの数が増えてくるとスコアの上昇が鈍くなってくるが、今までのコードでは、特に大きいテストケースでは全然収束していなかったので、ループが3倍回るのはかなりでかい。残り時間もわずかなので、8位もあれば10位入賞は十分可能だろう。入賞を確信したのでこんなツイートをしたりした。2020もっと続けていたかったが、時間は夜中の1時を回っていたので、とりあえず寝ることにした。衝撃の結末1月6日朝6時半、俺は目覚ましの音に目覚めた。順位表はどうなっているかな、と思い、さっそくスマホをポチポチして確認する。2020こんなことある????????展開完璧すぎない?昨晩のツイートのフラグを見事に回収した。この展開はある程度予測していたが、当然起こってほしくないのであまり考えないようにしていた。その予想は見事に的中、ピンポイントで11位だった。今までずっと潜伏してきて、残り数時間で初提出でかなりいい点数を取った人とか、昨晩は俺より下だったけど点数を大幅に伸ばした人とかがいて、11位まで下がった。こんなに頑張ってきて、今までずっと10位以内に入っていたのに。最後の最後で大逆転敗北はつらすぎる。諦めたらそこで試合終了と自分に言い聞かせ、いつもなら二度寝するところを、ベッドから這い出てもうちょっと頑張ってみることにした。いってもこれ以上できることは高速化とパラメーターいじりだけだが。評価関数は実際のスコアを計算する必要はなく、ペナルティーだけ計算すれば機能することに気づいたのでそうして高速化を図った(大して影響ない?)。あとはパラメーターいじり。近傍ごとのスコア上昇率を見て確率をいい感じに割り当てる。昨晩の1998億7000万点はまたまぐれだった説はあるが、その後も1998億点台は何回か出ているので、だいぶコードの質は良くなっていっていると思う。コンテスト終了の10時ぎりぎりまでもがいてみたが、結果は変わらず、11位で終了した。いや、こんな悔しい思いをするのは久しぶりだ。悔しすぎて笑うしかない。いうかフラグ回収が見事すぎて普通に面白い。年末年始の時間を削ってこのコンテストに費やして(といってもほかにすることもなかったが)頑張ってきたが、最後の夜まで夢を見せておいて目が覚めたら負けてるというのはつらすぎる。待て、コンテストはまだ終わっちゃいない。システムテストに賭けるしかないか。2020コンテストが終了すると、それまでの提出に対してシステムテストが実行される。コンテスト中は20個のテストケースに対して得点が計算されるが、システムテストでは(確か)180のテストケースに対して実行される。コンテスト中のテストケースとシステムテストのテストケースは結構違うらしく、ここで逆転をする可能性もなくはない。順位が下がることもあり得るが、おれはもうこれ以上下がってもどうでもいいので、システムテストで10位に食い込む可能性に賭けたい。10位との差は4000万点くらいあり、もしかしたらそれは俺みたいにまぐれで取った点数かもしれないので、それくらいは誤差の範囲といえる。システムテストの結果が出るのは2、3日後なので、それまでは受験勉強をすることにする。いえば俺受験生じゃん。プログラミングしてる場合じゃ無くね?翌日、ツイッターを見ながらとてもまじめに勉強していると、システムテストで順位がかなり変動しているとの情報が流れてきた。システムテストで順位が変わることは半分諦めていたが、これを見てまた希望が湧いてきた。順位表を見てみると、俺は11位ではなかった。202017位だったwwww。順位が大幅に変動していたものの、俺ほど落ちた人はなかなかいないんじゃないか。落ちすぎなのでおかしいと思ってしらべてみたら、180のテストケースのうちの一つでTLE(時間制限超過)していた。時間ギリギリまでループを回していたし、乱数生成のところでうまく出ないと何回もループが回ることになるので、大きいケースの一つでTLEしたらしい。TLEで10億点近く損し、今のスコアに10億点くらい足すとちょうど10位に入るか入らないかくらいなので、もしかしたら入賞できたのかもしれない。本当に惜しいことをした。17位まで落ちたことで少し吹っ切れた感はある。11位ぎりぎりで負けるよりも、17位まで落ちてしまった方が、後味がすっきりする。結果オーライということでいいか。学んだこと、感想マラソンマッチに初めて参加し、得られたものは大きかった。いつものようなアルゴリズム力を競う競プロとは全く違う思考方法を迫られた。マラソンマッチでは、「正しい解を求める」プログラムではなくて、「より良い解を求める」プログラムを書くことが求められる。最初こそ貪欲法しか知らなかったが、そこから少しずつ解に磨きをかけていくというプロセスを踏んで、マラソンマッチで戦えるようになるのである。そのために山登り法や焼きなまし法などの汎用的なメタヒューリスティックがあるが、それだけではなく、その問題に特有のアドホックな思考が必要でもある。それには柔軟な発想だとか、ビジュアライザーとにらめっこしながら改善点を探していく忍耐力も必要である。初心者の分際で偉そうなことを言ってみるけど、俺が受けたマラソンマッチの印象はこんな感じである。あとは実装力が伸びた気がする。Schedulingとか組み合わせ最適化の知識とかあったらだいぶ有利になりそうだが)、実装力がものをいう。コード量がABCとかで書くようなやつより圧倒的に多いので、コードを簡潔に書く力がないと何書いているのかすぐわからなくなりそうだし、何より思いついた解法を素早く正しく実装する力は必要である。今回多分トータルで1000行以上書いたが、実装のいい練習になり、純粋なプログラミング能力が上がってきている気がする。開発の手法における様々なノウハウを得られた。入力を外部のスクリプト経由でプログラムに送ったり、テストを自動化したりすることを今回やったおかげで、次回からはこのようなことがよりスムーズに行えるはずだ。これからは、俺もマラソンマッチに積極的に参加していこうと思う。プログラミング二度とやらないとか言ったけどもちろん続ける。今回のは本当に惜しかったので超絶悔しかったが、次回はこんな思いをしないようにもっとプログラミング頑張るぞ。受験が終わるまで極度の精進とか時間のかかるマラソンとかは控えるが、それが終わったらプログラミング三昧の日々を送りたい。今年の目標はAtCoder黄色。このテストケースはもう改善の余地がない感じ。懇親会にも参加してきた1/10に開かれた、コンテストの懇親会に参加した。入賞者のプログラム解説を聞きたかったし、競プロ界隈の人と絡んだことないので、いい機会だと思い行ってみた。入賞者のプログラムの内容をここで書いていいのかわからないから詳しいことは書かないけど、どのプログラムも思ったよりシンプルだなと思った。俺は近傍を5個も用意して、もっと増やそうとしていたけど、上位者は近傍がそんな多くなかった。代わりに、最初の貪欲でソートのパラメータを工夫したりだとか、オーダーをまとまりで扱うとか、オーダーの挿入の場所をもっとちゃんと計算したりとか、より深い考察ができているのかなと思った。おれはとりあえず近傍をたくさん作ればそのうちいいのができるかなと思ってやっていたので、こういうところは反省点。あと上位者は大体やっぱり焼きなましだったようだ。なんで俺がやったら点数が下がるのかわからないけど、もしかしたらループを回す回数が少なすぎたのかもしれない。みなループをより多く回す工夫をしていたから、焼きなますなら試行回数を多く稼がなきゃならないのかな。あと、やっぱりJavaでマラソンやるのはきついかもということも言われた。そりゃPythonよりは断然速いけど、やっぱり上位陣はみんなC++を使っていて、ループも何十万回も回っていたらしい。おれもC++を勉強するか、それともRustをもっとちゃんと書けるようにするか...。あとはAsprovaの社長がTLEの理由を教えてくれた。俺は200か400イテレーションごとに時間を計測していたが、そのイテレーションの途中にTLEしたらしい。Javaの時間を計測する関数はバカ遅いのでできるだけ少ない回数やろうと思ったが、それが裏目に出てしまった。100とかなら行けたのかな。いろいろなことが知れてとてもためになった懇親会だった。第6回Asprovaコンでは、今回の教訓を生かして、10位入賞を狙いたい。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。