特異点の向こう

俺は受験生、帰国子女、プログラマ、数学者、哲学者、もうすぐ億万長者

死についての考察

「すべてがFになる」を読んで、「死」について考えてみたが、書いてみたらとても長く重い話になったので、別の記事にすることにした。

randomthoughts.hatenablog.com


先に断っておくが、これから書く内容はものすごく暗いけど、別に俺に自殺願望はない。ただ「死」についてできるだけ論理的に考察したいだけ。

俺の思考の記録としてこの記事を残しておくが、暗い話を読みたくないなら読まなくていいです。当たり前か。


真賀田四季は言う。

死を恐れている人はいません。死に至る生を恐れているのよ。苦しまないで死ねるのなら、誰も死を恐れないでしょう?そもそも、生きていることの方が異常なのです。

死ぬことが、眠りに落ちて、そのまま目が覚めないだけのことならば、それは確かに恐れるべき対象ではないし、むしろ心地よいものなのかもしれない。生きていれば楽しいこともつらいこともあるが、死んでしまえば何も感じない。絶対に苦しむことはない。

それでいて、俺は死に抵抗がある。なぜだろうか?それは多分、何もせずに死にたくないということなのだろう。俺はまだこの人生で何も成し遂げていない。せっかくこの世界に生まれてきたのだから、何か歴史に、小さくてもいいから名を残すようなことをしない限り、死にたくない。それはなぜか。それは後世の人に俺が存在したことを知ってほしいからかもしれない。しかし死んでしまえばそんなこと知りようもないし、知ろうとも思うことができない。あるいは、死に際に「俺は何もしてこなかった」と後悔したくないからかもしれない。それは結局、「死に至る生」を恐れていることになる。感情的に苦しみながら死にたくないだけかもしれない。

そもそも、生きることは生物の本能的な欲求である。しかし、だからといって生きることが正しいことになるとは限らない。生きようとする個体だけが生き残るからだ。仮に「死ぬことは喜ばしいことである」ということが真実であったとして、その真実に気付いた種が自ら命を絶ったとしたら、その種の遺伝子は保存されない。生に執着する生物は、それが真実であるかどうかに関わらず、その子孫を残すことになる。

世界が存在することは異常だ。世界が無かったら、無いだけの話であり、ある必要はない。世界がある必要がないのに、世界があるのは、オッカムの剃刀に反している。だから異常だと思う。同様に、生きていることも異常だとおもう。もともと生命が存在する必要はない。あったところで何の意味がある?そもそも意味を求めるのがおかしいのかもしれない。世界も生命も、ある。それは事実であり、それに意味はない。

そもそも、世界はそれを経験する主体がいて初めて存在しうるのであり、「俺の世界」は俺が生まれた時に始めて創造された。俺が死ねば、「俺の世界」は終焉を迎え、何もなくなる。何もないというのは、物事のあるべき最もシンプルな状態であり、ある意味理想郷であると言えるかもしれない。俺が死んでも、世界は正常に動作し、ほかの人の世界は残るのかもしれない。しかし死んだら俺はそれらを経験することができないので、俺にとっては世界は終わり、何もなくなるのである。経験できなければ何が起ころうと無意味だ。

今から書くことはもしかしたら非常識的で道徳的に間違っていることかもしれないけど、死ぬこともそんなに悪いことじゃないのかなと思う。別にみんな死ぬべきといっているわけではないが、べつに死ぬことは、そこまで忌み嫌うべきものでもないんじゃないかな。「命が何よりも大事」とは使い古された言葉で、倫理的に正しい命題だと世間一般では認識されているのかもしれないが、無条件にそれを認めるのは思考停止であるような気がする。俺は身近な人の死を経験したことがないので、何も知らないやつは黙っていろと言われるかもしれない。ちゃんと考えて、それでもそれが正しいことだというのなら、俺が間違っているのかもしれない。確かに、人が死ぬのは悲しいことである。家族や友達が死んだら俺は悲しいし、死んでほしくない。しかし、それは残された人々の感情であって、死んだ本人の世界は終わっており、そこに苦しみや悲しみはない。

これも間違っていることかもしれないけど、そう考えると、生きることが苦しみでしかないとき、自らの命を絶つことも間違いではないんじゃないかな。もちろんそれは不可逆的な決断だから、ちょっと嫌なことがあったからって自殺するのは論外である。でも、もう回復の見込みがないくらい苦しんでいるならば、それはありなのかもしれない。安楽死制度が許されるのなら、それと何が違う?回復のチャンスはゼロではないんだから、最後まで頑張るべきという人もいるかもしれない。しかしそれでは、じゃあ君、彼にチャンスを提供できるの?ってなるし、そんなこと言ったら回復の見込みのない患者だって、明日医学でブレークスルーがあってどんな難病も治療できるようになるチャンスだってゼロではないんだから、安楽死制度はダメになる。

でもこの論理の穴は、その回復の見込みのあるなしが主観的な基準で決まるということなんだな。これも部外者は口出すなとなりそうだが、例えばいじめで自殺する人のニュースをよく聞く。しかしいじめっていうのは環境を変えればなくなるかもしれないし、いろいろ解決策はあると思うんだ。いじめがなくなったとしても被害者の心に大きな傷がずっと残るのは確かなんだろうけど、それのせいでそれから一生楽しい経験ができなくなるなんてことはないだろう。部外者から言わせてもらえば、いじめっていうのは回復のチャンスが十分あることなんだと思う。でも絶望の中にある人に理性的な判断をすることは難しいかもしれないし、それでもう駄目だと決めつけて自らの命を絶つっていうことがあるのかもしれない。それはいけない気がする。

でもそれはなぜいけないのか?自分でだめだと思ったら、それでいいのではないか?というのも、その本人の世界はその人のものなのだから、誰にも干渉する権利はないし、自分が終わらせたいと思ったら、終わらせてもいいのかもしれない。世界が終わったら、その判断を下したことに対して自分が後悔したりすることはないし、誰も自分の世界で自分を責めることはできない。

何が正しいのかますますわからなくなってきた。

真賀田四季は答えを知っているようだが、俺は答えがわからないので、生きることにする。どうあがこうと結局いつか死ぬんだから、生きられるうちに生きておくことにする。死ぬ直前まで、答えはわからない気がする。死んでもわからないかもしれない。死んだら考えることはできない。生きている異常さを楽しみたい。

すべてがFになる ―現実とは、天才とは、死とは

森博嗣作「すべてがFになる」を読んだ。犯人が誰かとか真相の重要な部分は言わないが、多少のネタバレあり。

まずこの本の感想を述べてから、この本で提示されている問いについて自分なりに考えてみたいと思う。

すべてがFになる (講談社文庫)

すべてがFになる (講談社文庫)

  • 作者:森 博嗣
  • 出版社/メーカー: 講談社
  • 発売日: 1998/12/11
  • メディア: 文庫

感想

実はこの本は4、5年前、中学生だった時に読んだことがある。学校の図書館で、題名と表紙にひかれて手にしたのを覚えている。当時はコンピューターの詳しい話はあまり理解できなかったが、この本は一番好きな推理小説になった。

今回は、たまたま書店で目にして、久しぶりに読んでみるかと思い買った。割と分厚い本だが、面白いので一気に3日くらいで読破した。

この本の何がいいかっていうと、まず一つは、個人的な話になるが、俺は頭のいいキャラクターが好きなのだ。どんな話でも、一番頭のいいキャラクターを応援したくなる。ナルトではシカマルが一番好きだ。そしてこの本では、登場人物がみなめちゃくちゃ頭がいい。犀川は国立大の助教授でめちゃくちゃ頭がいいし、萌絵は計算がめちゃくちゃ速い。そして何より、真賀田四季の頭の良さが超人的すぎる。小さいときに2桁の掛け算と3乗根の計算が一瞬で暗算でき(掛け算はともかく、3乗根の暗算て頭おかしくね?)、11歳でアメリカの大学でPh. D.を取得するという神レベルの天才。さすがに真賀田四季は設定がバグってると思うが、こんなに頭のいい人たちが出てくる小説が、面白くないわけがない。

そして次に、これも個人的な話だが、コンピューターの話が多く出てくるのが好きだ。UNIXがどうとか、スクリプトがなんだとか、unsigned shortがどうしたとかいう話は、最初に読んだときな何のことかよくわからなかったのだが、コンピューターについていろいろ知った今読むと、作者はよくこんなことを思いつくなあと感心する。しかし思うのだが、時間を扱う変数が2バイトってありえなくないか?今回使われていた変数は時間(hour)を数えているものだからそれほどの容量はいらないが、それでも2バイトは少なすぎると思う。最初に気づかないのだろうか?そもそもOSのソースなんて読まないんだろうか?所定の時間がたつ前にバージョン5がつくられる予定だったから気にしないんだろうか?まあいい。

そして最後に、様々な書評で言われていることだが、この本はとても理系なのだ。登場する専門知識が理系であるというのももちろんあるが、真相へのたどり着き方がとても理系な感じがする。というのも、犀川は論理的な推論だけで真相にたどり着くのだ。殺人の動機とか、四季を取り巻く人間関係とか、感情論とか、常識的な行動とかといった余計な要素を一切省いて、与えられた情報から科学的に可能な殺人計画を導き出す。まるで、数学の証明を読んでいるかのようだった。この本に人間的な描写が全くないわけではない。むしろ犀川と萌絵とのやりとりには、とても人間らしいものを感じることができる。それでいて、事件の推理の過程に人間ドラマは一切なく、背景とか動機とかも省いて、一見不可能な完全密室の殺人の謎に対して科学的な仮説を打ち出す。謎が明かされるとき、その論理の正しさに感服するし、謎が解ける爽快感は、ほかの推理小説と比べ物にならない。

と、このように非常に面白い読み物であった。エンターテインメントとして非常に優れているが、途中でいくつも読者に対して哲学的な命題が提示されるのもおもしろい。そのうちのいくつかについて考えてみたい。

考察

まずは、「現実」について。現実とは何か。VRは現実か。

作中では、VRも現実であるというような発言が犀川と真賀田四季がしている。仮想世界が一定数の人間に共有されているならば、それは現実といっていいと思う。VRで人に会ったり、仕事をしたりといったことができるようになれば、VRも立派な現実となりうると思う。現実が物理的でなければならないと誰が言った?

じゃあそもそも現実とは何か?まず俺なりに「現実」の定義について考えてみたい。まず思いつくのは、「すべての人に共有されている、客観的な世界」ということ。しかしこれにはかなり穴がある。「すべての人」というのには無理がある。例えば自分の世界に閉じこもっている狂人は、我々が経験している「現実」とは違う「現実」を経験しているはずだ。じゃあ「すべての正常な人」とするか?それでは「正常」を定義する必要がある。もしかしたら、我々が狂人だと思っている人が実は正常で、我々自身が狂人なのかもしれない。じゃあ「過半数の人」とするか?それでは過半数の人類が狂ったらどうするのか。それにそもそも、我々「正常」な人間が見ている現実がみな同じものだと、どうやってわかるのか。客観性をどうやって調べるのか。

じゃあ現実とは主観的なものなのか?それはそれでいろいろと問題がある気がする。夢は現実か?

萌絵の「現実とは何か」という問いに対する、犀川の答えを引用する。

現実とは何か、と考える瞬間にだけ、人間の思考に現れる幻想だ。普段はそんなものは存在しない。

それはチートだろ!と思うが、確かに的を射ているような気もする。そもそも現実とは何か考えることに、何か意味があるのだろうか。俺が今経験している世界は、おそらく多くの人に共有されている現実だと思う。俺の書いたこの記事は、ほかの人と共有されている。しかし、この世界が俺だけが見ているものではないという保証がどこにあるだろうか。究極的には、俺が見ている現実はすべて俺の夢かもしれないし、あるいは俺は脳に電極を埋め込まれて感覚を刺激されているだけで、本当は檻の中に飼われているのかもしれない。自分が現実だと思っているものが本当の現実であると知ることは絶対にできないし、それならば現実について考える意味はどこにもない。現実は幻想なのかもしれない。現実が存在しないわけではなく、そもそもその概念自体が幻想なのである。


次に、「天才」について考える。犀川は、「人間は誰もが最初は天才で、だんだん凡人になる。真賀田四季のような人は、もっとも純粋な人間だと思う」というようなことを言う。

人間は生まれた時、生物的にプログラムされたOS以外には、何も入っていない。だから多分、思考の柔軟さとかは子どもの時が最高なんだろう。買いたて新品のラップトップがすいすい動くのと同じように。でも最初はまともなソフトウェアが全然入っていないので、特に有益な情報処理はできない。成長するにつれて、いろいろなことを学んで、いろんなことができるようになってくる。難しい文章を理解したり、複雑な計算をしたりできるようになる。一見頭がよくなっているように見えるけど、それはいろいろなことを記憶し、ソフトウェアがアップデートされているだけだ。純粋な情報処理能力とか思考の柔軟性とかの、脳のCPUとしての能力は、10代でピークを迎えるらしい。常識とか人間関係とかいろいろな余計なことにとらわれて、バックグラウンドプロセスが増え、ストレージが埋まっていくにつれ、天才的な思考というのはどんどん難しくなっていくんだろう。

人間は、どんどん常識を覚えこまさせられているうちに、頭が悪くなっていく。常識に汚されていない真賀田四季は、生まれた時の天才さをそのまま持ち続けている、純粋な人ということなのだろう。

確かに俺も、最近頭が悪くなっている気がする。中3のときは、俺は天才だった。今考えると驚異的な学習能力だとか思考力を持っていた。でもその時は社会性のかけらもないようなやつだった。今も大してないけど、ここ数年で常識を覚え、すこしは常識的な人づきあいができるようになってきた。でも、もう天才じゃなくなった。知識は増え、能力は高まったが、思考力は確実に低下している。

じゃあ常識はいけないことなのだろうか?そうではないと思う。円滑なコミュニケーションをとるうえで常識は必要だし、そっちの方が楽しい。しかし、その楽しさは低俗なものではないだろうか?常識的で人並みの思考しかできないが友達がたくさんいるのと、例えば社会性はないけど深淵なる数学の世界に使っているのと、どっちが楽しいか?どっちが高尚か?

理想はどっちも楽しめることだが、結局自分の好きなバランスを選べばいいんだと思う。そもそも頭の良さで人の価値が決まるわけではないので、好きにすればいいんじゃないか。悔しいが、この結論はあまりにも常識的で、人並みの思考なんだな。俺は多分、何年かかっても真賀田四季にはなれないんだと思う。


最後に「死」について考えようと思ったが、書いてみたらめちゃくちゃ長くなったしめちゃくちゃ重い話になったので、別の記事にする。

randomthoughts.hatenablog.com



とにかく、この本はめちゃくちゃ面白い!コンピューターの知識がなくても十分楽しめる(実際俺は知識がない時に読んでめちゃくちゃおもしろいと思った)ので、文理関わらずオススメ!

あとアニメもある。これもおもしろかったが、俺は本の方が好きだった。

もうすぐバレンタイン!数学とともに届ける愛の言葉10選

2月14日は待ちに待ったバレンタインの日ですね!皆さん、誰かにチョコをあげる/もらう予定はありますか?僕は自分のために買いますけどね!

そんなわけで、今日は、数学とともに届ける愛の言葉を紹介したいと思います。神秘的な数学の世界で愛を伝えるなんて、ロマンチックだと思いませんか?あなたの大切な人に、数学で思いを伝えてみてください。僕は伝える相手がいませんけどね!

この記事では、男性が女性に伝えるための言葉を紹介しますが、言葉遣いを変えれば誰でも使えるようになると思います!数学に詳しくない人でも楽しめるように分かりやすく説明したつもりですので、ぜひ最後まで読んでみてください。

f:id:pepsisoda:20200205202553j:plain

1. 「君は僕の補集合なのさ。」

You are my complement.

補集合というのは、いい感じのたとえで言うと「パズルを完成させるための残りのピース」のことです。2人あわせて初めて完全になる、という意味の素敵な言葉です。ベタですけど、やっぱりこのようなシンプルでストレートに刺さる言葉がかっこいいですよね~!

同値な命題(同じ意味の言葉)
「君は\(\overline{僕}\)なのさ。」
「君は僕の論理否定なのさ。」
「君は全体集合と僕の差集合なのさ。」
「君は\(\{x | x \notin 僕\}\)なのさ。」

2. 「僕たちの愛は1次元だ。なぜなら、三角関係が存在しえないから。」

Our love is one-dimensional, because there can't be a love triangle.

1次元空間とは、一つの方向にのみ広がりを持つ空間、つまり直線のことです。直線上に存在しうる図形は、点と線のみです。三角形のような、面積を持った図形が存在する余地はありません。第三者の介入を許さないあなたたちだけの世界で、いつまでもお幸せに…。

同値な命題
「僕たちの愛はユークリッド空間\(\mathbb{R}\)だ。」

3. 「複素平面の中心で、\(i\)を叫ぼう。」

Let's call for love at the center of the complex plane.

複素平面の中心は0であることはさておき、「世界の中心で、愛を叫ぶ」的な感動的なセリフです!

小学生の時に、数直線というものを習ったと思います。あらゆる数字は、数直線上の点として表せるのでしたね。ところで、数直線の外側には何があるのか、疑問に思ったことはありませんか?(思ったら天才)

数直線の外側には、「複素数」という世界が広がっています。実数が直線状の点なら、複素数は平面上の点です。複素数は、2乗して-1になる不思議な数\(i\)を用いて書き表されます。

複素平面の中心は0なのですが、\(i\)で愛を伝えれば、誰しもがあなたの虜になるはずです!

同値な命題
「ガウス平面の中心で、\(i\)を叫ぼう。」(ガウス平面の中心は0です。)
「リーマン球面の南極で、\(i\)を叫ぼう。」(リーマン球面の南極は0です。)

4. 「君が素数なら、僕は君2乗。僕は1と、僕自身と、君でしか割り切れない数なんだ。」

If you were a prime number, I'd be you squared. I'm divisible by 1, me myself, and you only.

素数というのは、1とそれ自身でしか割り切れない数のことというのはわかると思います。そして素数pの2乗は、1と、それ自身と、pでしか割り切ることができません。3と9、5と25、10007と100140049のような関係ですね。

運命的な出会いを表すロマンチックな言葉です。今までずっと生きてきて、1人も自分を割り切る人を見つけることはできなかったけど、やっと君を見つけたよ…という。お相手があなたの運命の人であるということを、論理的に証明できています!しかし残念なことに、あなたはお相手を割り切ることはできません!

同値な命題
「僕を素因数分解すると、君が2人あらわれる。そして君しか現れない。」
「僕は試し割り法で、素数判定をしてみたんだ。僕もまた、悲しい素数の一人なのかなって。ずっと素因数が見つからなくて、諦めかけてたんだけど、ループの最後の最後でやっと僕の素因数を見つけたんだ。それが君だった。」

5. 「君は、\(e^{i\pi}+1=0\)の次に美しい。」

You are the second most beautiful one, after \(e^{i\pi}+1=0\)

「より美しい」ではなく、「次に美しい」ということに注意してください。\(e^{i\pi}+1=0\)が世界一美しいことは変えようのない事実なので、嘘を言うとお相手も怒るでしょう。それでも、オイラーの多面体定理\(v-e+f=2\)より美しいのですから、十分すぎるほど美しいです!

ちなみになんで\(e^{i\pi}+1=0\)が美しいのかというと、5つの最も重要な数学定数である、加法の単位元0、乗法の単位元1、自然対数の底\(e\)、虚数単位\(i\)、そして円周率\(\pi\)が一つのシンプルな等式で結ばれているからなのです!さすがにこれより美しい人なんて存在するわけがないですよね!?ね!?リチャード・ファインマン大先生だってこれが「我々の至宝」とおっしゃったんですよ!?

同値な命題
男:「オイラーの公式って知ってる?」
女:「うん知ってる。\(e^{i\theta}=\cos\theta+i\sin\theta\)でしょ?」
男:「その通り。じゃあ\(\theta\)に\(\pi\)を代入して、すべての項を左辺に集めてごらん。」
女:「\(e^{i\pi}+1=0\)。わあ、きれい…。」
男:「君はその次にきれいだよ。」
女:「○○くん…♡」

6. 「君とのラブストーリーの続きを書くには、余白が狭すぎる。」

The margin is too narrow for the sequel of our love story to fit in.

これはピエール・ド・フェルマー大先生が、フェルマーの最終定理の発見に際して放たれた名言「私は真に驚くべき証明を見つけたが、この余白はそれを書くには狭すぎる」から来ています。

余白がないなら裏紙でも持ってきてそれにかけ!と思うのはさておき、フェルマーの最終定理は、「すべての自然数\(n \ge 3\)に対して、\(x^n+y^n=z^n\)を満たす自然数の組\((x,y,z)\)は存在しない」という定理です。主張自体は極めてシンプルで、その意味は中学生でも理解できるものですが、実は数学史上最大の難問の一つです。フェルマーの最終定理はこの記述の後、オイラーをはじめとする世界の名だたる数学者たちが証明を試みましたが、誰も成功することはありませんでした。フェルマーの死後360年たった1995年に、イギリスの数学者アンドリュー・ワイルズによってついに画期的な証明がもたらされ、その長い歴史に幕を閉じました。

この言葉を送れば、あなたたちのラブストーリーもきっと360年間終わることはないでしょう!末永くお幸せに!

7. 「僕らの愛の大きさは、非可算集合の濃度に等しいんだ。」

The size of our love is equal to the cardinality of an uncountable set.

一口に「無限」といっても、いろいろな「無限」があります。一つは、自然数の個数。自然数の個数は、1、2、3、…と数えることができる(数え終わるとは言ってない)ので、自然数は「可算集合」と呼ばれ、自然数の「個数」(正確には、濃度という)は\(\aleph_0\)(アレフ・ゼロ)といいます。

それでは、整数ならばどうでしょう?整数ならば、1、2、3、…といった自然数に加えて、0、-1、-2、…といった0や負の数も含まれるので、自然数よりもたくさんあるように思えます。しかし、整数の個数もまた、\(\aleph_0\)となることがわかっています。なぜならば、整数も工夫することで「数える」ことができるからです。数えることのできるものの個数は、すべて\(\aleph_0\)なのです。

有理数(分数で表すことのできる数。0.1とか、0.11とか、0.333...とか)は数えられないように思えますが、なんとこれもうまく工夫することで数えることができます。では、あらゆる数の個数は、\(\aleph_0\)なのでしょうか?

そうではありません。実数(あらゆる「普通の」数。有理数に加えて、\(\sqrt{2}\)(=1.41421356...)のような分数で表すことのできない数)の個数は、\(\aleph_0\)より多いことがわかっています。つまり、実数は数えることができないということです。実数は数えることができないので、「非可算集合」なのです。
(どうしてそうなるか気になる人は、「カントールの対角線論法」で調べてみてください)


「愛の大きさは無限大」みたいな言葉は面白くありません。真の理系なら、ただの無限ではなく、数えきれないどころか、数えることすらできない無限で、あなたたちの愛の強さを示しましょう!

同値な命題
「僕らの愛の大きさは、\(|\mathbb{R}|\)なんだ。」
「僕らの愛の大きさは、\(\aleph\)なんだ。」
「僕らの愛の大きさは、連続体濃度に等しいんだ。」
「僕らの愛には、自然数の集合からの単射は存在するが、全射は存在しないんだ。」


「無限」という言葉にアレルギーを感じる人は、巨大な有限数を用いてもいいでしょう。少なくとも、「愛は無限大」とかというよりは、ずっと知的に聞こえます。数字の小さい方から例を挙げると、
「僕たちの愛は、ジンバブエドルのインフレ率\(6.5\times10^{108}\)より大きいのさ。」
「僕たちの愛は、グーゴルプレックス\(10^{10^{100}}\)より大きいのさ。」
「僕たちの愛は、第2スキューズ数\(e^{e^{e^{e^{7.705}}}}\)より大きいのさ。」
「僕たちの愛は、トリトリより大きいのさ。」

(注)トリトリとは
関数\(G(n)\)を\(G(n)=3 \uparrow^n 3=3 \rightarrow 3 \rightarrow n\)と定義すると、トリトリとは、
\[
G(3) = 3 \uparrow\uparrow\uparrow 3 = 3\rightarrow3\rightarrow3 = 3↑↑7625597484987
= \underbrace{3^{3^{3^{ \cdot ^{ \cdot^ { \cdot^ { \cdot^ { \cdot^ { \cdot^ {\cdot^ { \cdot^ { \cdot^ { \cdot^ { 3^{ 3^ 3}}}}}}}}}}}}}}}_{7625597484987}
\]
かわいい名前とは裏腹に、見た目はえぐいですね!

「僕たちの愛は、グラハム数\(G^{64}(4)\)より大きいのさ。」
グラハム数は、数学の証明で使われたことのある最大の数としてギネス世界記録に認定されているので、最強です!

8. 「僕たちの愛はNP困難問題だ。」

The problem of our love is NP-hard.

NP困難な問題とは、クラスNPに属する任意の問題と同等かそれ以上に難しい問題のことです。意味が分からないと思うので、できるだけわかりやすく説明していこうと思います。

数学の問題というのはその解き方によっていろいろ分類されていて、その中にPとNPというものがあります。こんな適当なことを言うと数学者に怒られるかもしれないけど、超簡単に言うと、P問題というのは、効率的に解くことのできる問題で、一方NP問題は、「めんどくさい」問題のことです。
(数学がわかる人向けにもうちょっと正確に言うと、P問題とは、多項式時間で解くことのできる問題で、NP問題は解の一つが与えられたときにその解が正しいことを多項式時間で示すことのできる問題です。なのでP問題はNP問題でもあります。)

NP困難な問題とは、どんなめんどくさいNP問題よりもめんどくさい問題のことです。つまり効率的に解くことができない、とても難しい問題のことです。効率的に解くことができないというのは、スーパーコンピューター京を1京個、1京年走らせても解けないというレベルの難しさです(適当)。

つまり、あなたたちの愛は不可思議な未知の世界で、誰もその解を知ることはできないということですね!ロマンチック~!

NP困難と似た概念にNP完全というのがありますが、こちらは使わないようにしましょう。NP完全の方が強そうですが、NP完全というのはNPかつNP困難な問題のことです。もしP=NP予想(めんどくさい問題も効率的に解けるんじゃね?という予想)が証明されてしまえば、あなたたちの愛も効率的に解けてしまうことになります!NP困難といえばそんなことはないので、そう言うようにしましょう!

9. 「君は僕の不完全性定理。君無しでは僕を証明も反証もすることができない。」

You are my incompleteness theorem. Without you, I'm unprovable.

もはや意味が分かりませんね!ゲーデルの不完全性定理「自然数論を含む帰納的公理化可能な理論が、ω無矛盾であれば、証明も反証もできない命題が存在する。」を使ったつもりなんでしょうけど、なんか意味をはき違えてる気がしますね!てかゲーデルの不完全性定理が難解過ぎて僕には理解も説明できませんね!なんか「数学に矛盾がないことを数学を用いて証明することはできない」みたいな意味らしいですけどよく分からないですね!ω無矛盾てなんですかね!でもなんかかっこいいですね!こんなこと言われたらときめきますね!

10. 「二端子フローネットワーク\(Ν (G(V, E), c, s, t)\)が与えられたとき、最大フローの残余ネットワークは、\(s\)から到達可能なノード群\(S\)と到達不可能なノード群\(T\)に分けることができる。残余ネットワーク上では\(S\)から\(T\)へのエッジは存在しないから、もとのネットワークにおいて、\(S\)から出るエッジ\((u, v)\)はすべて、\(f(u,v)=c(u,v)\)となっており、また、\(S\)に入るエッジは流量が0である。よって、\(|f_{\mathrm {max} }|=c(S,T)\geq c((S,T)_{\mathrm {min} })\)である。また、任意のフロー\(f\)に対して、\(T\)へ流れこむエッジ\((u, v)\)の流量は最大で\(c(u, v)\)であり、これの和は\((S, T)\)のカットの容量である。一方、\(T\)から\(S\)へ逆流するエッジの流量の最小値は0以上である。フローの流量は\(T\)に流入する流量から逆流する流量を引いたものであるから、\(f\)の流量は最大でカット\((S, T)\)の容量となる。よって、\(c((S,T)_{\mathrm {min} })\geq |f_{\mathrm {max} }|\)である。以上より、\(|f_{\mathrm {max} }|=c((S,T)_{\mathrm {min} })\)である。よって僕は君を愛している。」

Blah blah blah. Therefore I love you.

これは、最近知った「最大フロー最小カット定理」の証明です。Wikipediaの記事を参考に書きました。意味わからないですね!僕もよくわかりません!(でもこの記事書いてちょっと分かった気がする。)しかしこんなことを言って愛を伝えれば、きちんと愛が証明できているように聞こえます!「○○くん、その証明よくわからないけど、とにかくあなたは私を愛しているのね…。」となります。なりません。この手法のコツは、できるだけお相手が理解できなさそうな証明を利用することですね。例えば「1+1=2である。よって僕は君を愛している」みたいなことを言うと「ふざけてるの?」となりますが、このような意味の分からない証明ならばきっと大丈夫です!

バリエーション
相手が高校生以下または文系大学生および社会人
たぶんこの「最大フロー最小カット定理」で十分です。

相手が理系大学生および社会人
相手が理系なら、この定理の証明を理解してしまう恐れがあるので、フェルマーの最終定理の証明でとどめを刺しましょう。

相手が数学者または理論物理学者
彼らはフェルマーの最終定理の証明ですら理解してしまう恐れがあるので、ここは望月新一教授の宇宙際タイヒミュラー理論(IUT)の論文を用いて攻めましょう。理解している人は世界に数人しかいないようです。まあ600ページもある論文なので音読の途中に相手が飽きて帰らないように注意してください。

相手がIUTの理解者の一人
諦めましょう。

まとめ

いかがでしたか?バレンタインの日にふさわしい、数学で愛を伝える言葉を10個紹介しました。なんでこんな思いつくの?と思うかもしれませんが、彼女がいないとこれくらいしか考えることがないのです!僕なんかは、「あなたは私の秘密鍵。誰も私たちの秘密を知ることができない」なんて言われたら、一瞬で恋に落ちちゃいますね!でも量子コンピューターならRSA暗号が効率的に破れるのでだめなんですけどね!

アートが問い、技術が創る未来

今日は中学からの友達と、六本木ヒルズの森美術館に行ってきた。

六本木は初めて!六本木ヒルズはめちゃくちゃ高かった。エレベーターに乗って、気づいたら52階に。展望台があったので外を眺めてみると、眼前に東京タワーの姿があった。東京タワーは遠くから見ると大して高くないなという印象を受けるけど、近くで見るとやはり高い。もうちょっと奥の方にスカイツリーも一緒に見えた。こちらは何度見てもバカ高い。

f:id:pepsisoda:20200126200723j:plain:w500
東京タワー、こんなに近くで見るのは初めて

今日見た展示の題名は、「未来と芸術展:AI、ロボット、都市、生命~人は明日どう生きるのか」。連れが美術館に行きたいと言っていたので、候補を見せてもらったところ、俺の興味のあるテック系の展示が見れそうだったので、森美術館を選んだ。日本科学未来館のような雰囲気を感じたので、これは楽しめそうだ。ところで彼は(ガチの)アーティストで、やっぱり芸術家と美術館を回るのは一味違って面白い。

入って最初に、AI美空ひばりに出迎えられた。日本を代表する歌手(といってみたものの、俺は知らない)である故人美空ひばりの姿と声を、AIテクノロジーによって復活させようという試みで、2019年の紅白歌合戦で見た人も多いだろう。このプロジェクトは死者への冒涜だという批判もあるらしいけれど、とりあえず倫理的な問題は置いといて見て思ったことを書きたい。

俺が彼女(あえて、「それ」ではなく「彼女」といってみる)を紅白で見た時、そのクオリティに驚いたのを覚えている。まるで本人がそこにいるようななめらかで自然な動きが表現されており、声もまるで人間が歌っているような響きがあった。俺は本人の声を知らないので似ているのかどうかは判断できないが、たぶん似ているのだろう。ボカロの声とかは、どこか機械的な、人工的な響き(全然聞かないので最近はどうなのかわからないけど、少なくとも数年前はそうだった)がするけれど、AI美空ひばりの声はとても自然だった。今回、彼女を間近で見てみて、改めてその質の高さに感動した。AIが人の声をまねできるというのはだいぶ前からニュースになっていて知っていたが、実際に見てみるとやはり迫力がある。AI美空ひばりは、不気味の谷を優に超えている。この技術はもちろん悪用は可能で、実際ディープフェイクとかが問題になっている一方、このようにエンターテインメントとしてうまく活用すれば、新しい領域が開けるのかもしれない。

展示は「都市と建築」→「ライフスタイル?」→「生命?」→「AI?」みたいな感じで並んでいる。

最初の都市・建築のコーナーでは、現在進行している急進的な都市計画とか、面白い形をした建物の構想案とかが展示されていた。前から思っていたことだが、大体の「未来都市」の想像図みたいなものは決まって、超高層ビルから植物が生えているような感じである。どんどん建物は高くなりかつ密度を増していくが、それと同時に街に緑があふれている、というようなイメージが共通している。環境にやさしいとか、持続可能な社会みたいなことを表現しているのだろう。ありふれたイメージだけども、俺はこれが結構好きで、こんな街に住みたいなと思う。六本木ヒルズの展望台から東京を一望したとき、視界に入ってくるのはただひたすら地平線まで届く、灰色のビル群だった。広い関東平野が無機的な人工物によって覆いつくされ、それから出る煙で空はかすんでいる。これが世界最大の都市・東京かと思うと、何か少し悲しみのようなものすら感じる。語彙力がなさすぎるんだけど、なんかもっと、自然と調和しなきゃなって思う。もっと自然と融合した、地球と調和した未来が来ることを願うばかりである。

f:id:pepsisoda:20200126201005j:plain:w500
これは中国の先進的な建築

ライフスタイルについての展示では、食に関するアートが目を引いた。近年昆虫食が注目を集めているが、ここではカラフルな遺伝子組み換えゴキブリの広告を模したアートが展示してあった。めちゃくちゃ気持ち悪いし絶対に食いたくない。あとは3Dプリンターで寿司を作る機械の展示があった。実際にこの機械を使ったレストランが数年後に東京で開かれるらしい。寿司といってもいつも見るようなものとは全く違う形をしており、何かとげがたくさん生えていたり、立方体の形をしていたりと様々だ。食べ物が3Dプリンターで作られるようになれば、レシピはデジタル化して共有することができるし、今までにできなかったようなものも作れるようになるはずだ。テクノロジーと食の融合はまた新しい可能性を秘めている。

f:id:pepsisoda:20200126201217j:plain:w500
寿司の3Dプリンター。このプロジェクトの名前は、"Sushi Singularity Tokyo" (寿司の特異点)

犬ロボットaiboと、よくわからないけどかわいいペンギンのようなロボットの展示もあった。なでると鳴いたり喜んだりする。いつかロボットがペットとなることのできる時代が来るのかもしれない。

f:id:pepsisoda:20200126201415j:plain:w500
かわいい

これは次の生命に関する展示にあった、心臓の模型。生命の象徴である心臓を神聖なものを祭るように展示することで、生命工学はどこまで踏み込んでいいのかという問いを提示しているらしい。

f:id:pepsisoda:20200126201441j:plain:w500
なんだかゲド戦記を思い出す

これは半分人間、半分チンパンジーの親子を想像して作られた模型。このようなことも技術的に可能となるのだろうが、そんなことをしていいのだろうかという倫理的な問題が残る。

f:id:pepsisoda:20200126201550j:plain:w500
親はチンパンジー似で、子どもは人間似。

最後はAIについての展示。有名な「トローリー問題」を扱ったアニメーションだとか、AIを裁く裁判の映像作品だとか、観客の顔を認識・追跡してスクリーンに表示する、中国の監視社会を彷彿とさせる展示などがあった。中でも特に考えさせられたのは、AIによって作られたアートである。

これはAIではないんだけど、コンピューターがランダムに決めた長さや太さの金属パイプをたくさんつなげた作品。とても幻想的できれいだ。「人間にはこれを作ることは不可能」という説明書きがされていた。確かに、この大量のパイプの形をすべてランダムに決めてつなげるというのはとても人間にできることではない。

f:id:pepsisoda:20200126201734j:plain:w500
コンピューターによって作られた幻想的な空間

これは、どこかのウェブサイトで"everything"というタグがつけられた画像をAIに学習させて作った映像。「すべての歴史」みたいなタイトルだったと思う。花や建物、宇宙などのオブジェクトのぼんやりとしたイメージが、シームレスに流れていく様子は、何か神秘的であり、ほんとうに「すべての歴史」を体現しているような印象を受けた。

f:id:pepsisoda:20200126201826j:plain:w500
これが、すべての歴史

AIは芸術家になれるのかという問いがあるけども、俺はあくまでAIは創造を手助けするツールであると思う。AIは自分で何かを作りたい、表現したいという欲求は持たないが、アーティストがその目標を達成する手段として、活用することはできる。

それでいて、AIが作り出すアートは、芸術家が何億人集まろうとも作れないものである。俺はアートには詳しくないけれども、思うに、AIによるアートっていうのはもっとも純粋な形の芸術なのだと思う。AIは文化的、社会的なバイアスを全く持たない。それは、膨大なデータに基づいた、客観的な統計なのである。AIによって作り出されるアートは、人種や世代を超えることのできる、最も普遍的な形のアートなのではないだろうか。

AIのバイアスをなくそうという動きが最近大きくなっているようである。会社の社員を採用するアルゴリズムが、人種や性別によって判断を下したりといった問題が起きているからだ。ついこのあいだも、日本のAI研究者の大澤昇平が「うちは中国人は雇わない」などとツイートして大炎上したが、彼はそれはAIによる判断だったと説明した。おれは、アルゴリズムはあくまでも客観的な判断を下しているのだと思う。これは人種差別を助長したり大澤氏を擁護したりするために言っているのではないが、明らかに人種や性別と能力に大まかな相関関係はあると考える。実際黒人は身体能力が高いだとか、アジア人は数学が得意だとかという特徴はある。しかしそのステレオタイプをその集団全員に当てはめることはいけないということを私たちは知っているし、人種を基に何かの判断を下すのも倫理的にいけないことを知っている。だから私たちは、AIのバイアスをなくすのではなく、AIに「人種・性別を基に判断を下してはいけない」という正のバイアスを組み込んでいるのではないだろうか。全くバイアスのない純粋なAIは時に倫理的に間違った行動をするから、私たちが倫理的なバイアスを組み込んでやらなければいけない、そういうことだと思う。

だいぶ話がそれてしまったが、アルゴリズムの客観的な統計によって作り出されるアートは、人間の文化的、倫理的バイアスにとらわれていないという点で、ある意味、人間を超越しているのかもしれない。もちろんAIが学習するデータが人間によって作られるものなら多少のバイアスは含まれるけど、意思決定の段階では全く純粋な判断をするのだ。もし宇宙人がいたとして、彼らが人間のアートを理解できなくても、AIのアートなら理解できるのだろうか。

などと、いろいろ考えさせられる展覧会であった。アートっていうのは、何かに解決策を提示するものではなく、解決されるべき問題を提示するのが役目なのだと思う。例のチンパンジーの展示は、生命倫理についての問いを提示しているし、ゴキブリだって、「食べ物とは何か」といった問いを発しているととらえることもできる。そしてその問いにテクノロジーが答えていく。過去のSFは今の日常となり、今日の不可能は明日の常識となる。このプロセスを繰り返していくことで、歴史が形作られていくのではないだろうか。アートが社会に対して未来の方向性を問うことによって、人類が進むべき方向が決定されるんだと思う。

それじゃあ、AI美空ひばりは社会に対する何かの問いかけなのだろうか?例えば、「死とは何か」。このプロジェクトで姿と声は死後もよみがえることができることが証明された。いつか思考もデジタルに保存できるようになったとしたら、死とは何を意味するのだろうか?生物的な生というのは大して本質的に重要なものではなくなるのか?その人に関するあらゆる情報が死後も生き続けるのなら、それは生きていると言えるのだろうか?問いはいくらでも出てくる。

アートは問題提起の一つの手段でしかなく、それにはほかにもいろいろな方法がある。例えば本を書くとか、テレビに出るとか、ブログやソーシャルメディアで発信するとか、友達と話すとか。しかし、未来に対する問いかけができる能力は、これからどんどん重要になっていくんじゃないか。身の回りに情報があふれる中で、しっかり自分の考えや方向性を決めるためにも、問題提起の能力は必要だと思う。こうした能力をしっかり育んでいきたいと思った。

学ぶことの多い一日であった。日本科学未来館は、未来的なテクノロジーがたくさんあって理系の人間としては聖地のような場所だが、美術館ではアートから現代・未来の科学技術について考えることができたとおもう。

第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位入賞を狙いたい。