週記(2021/08/16-2021/08/22)

08/16(月)

先週の週記を投稿してから寝るまでの話。と言っても、先週の週記の最後で宣言したように、今日は夕方くらいまで起きておいて生活リズムを無理やり整えるつもりであるから、これから寝るまでが月曜日の予定だ。普段ならこんな時は前の日の欄に全部書いて、代わりに1日ぶんの日記が消滅するのだが、たまたま週の変わり目に被ったため、このように日曜日と月曜日に分割して書いている。

また院試の過去問を解き進めていた。少し年代を遡ると、選択問題で選ぼうと思っていた分野の問題が解けないことが多くなってきたため、そのような場合でもなんとか点数を稼げるようにと分野を絞らず解けそうなものにとりあえず手を出してみる。流石に8問全部難しいということはなくて、自分でも解けるような問題が何とか少しずつ見つけられた。

そうこうしているうちに午後4時を回り、ちょっと椅子の上で意識を飛ばしてしまったので、このあたりで切り上げて布団に移動。午後5時半就寝。

08/17(火)

起きたらちょうど日付が変わったころだった。まだもうひと眠りしておきたいとは思っていたが、うっかりスマホを触り始めてしまう。YouTubeを見たりTLを眺めたりして布団の上でゴロゴロしていたら、すぐに時間が過ぎ去ってしまった。途中院試の解けていない問題を考えて解けたりもしたが、本番はそのような悠長なことはできない。構築問題なので、すぐに思いつかないならちゃんと諦める必要がある。

外が明るくなってきたので、ちゃんと意識的に睡眠する。午前5時前くらいに入眠して、今度は午前8時半に起床。いいんじゃないだろうか。2度目の睡眠は3時間ちょっとなのでかなり眠気はあるものの、足したらそれなりの睡眠時間になるので、これで起きることとする。

朝のうちに、夜中思いついた解答を実際に書いてみることにした。問題はこうだ:\{0,1\}の有限列からなる計算可能な無限列\{f_n\}_{n=0}^{\infty}であって\forall n.{\rm len}(f_n)\gt nを満たすもののうち、性質(\ast)を満たすどんな関数g:\mathbb{Z}_{\ge 0}\rightarrow\{0,1\}も計算可能とならないものを1つ挙げよ。ここで(*):\forall n\in\mathbb{Z}_{\ge 0}.\exists f_m.n\lt {\rm len}(f_m)\land(\forall i\le n.g(i)=f_m(i))

実際の問題文はもっと細かいのだが、だいたいこんな感じの問題だった。令和3年の数学基礎論分野の問題である。

自分の構築は、有限長のプログラム全体を\{\varphi_n\}_{n=0}^\inftyとした上で、{\rm len}(f_n)=n+1かつ

\displaystyle f_n(i)=\begin{cases}
1\quad(\varphi_i(\varphi_i)の計算がnステップ以下で終了する)\\
0\quad(otherwise)
\end{cases}

とするもの。これは実際にnステップ実行してみればよいので計算可能で、しかしg(i)\varphi_i(\varphi_i)の計算が停止するかどうかを判定しないと決められないので、計算不可能になりそう。

実際は何かの停止性判定問題に帰着するのではなく、もっと直接的に計算不可能性が示せる。つまり、gが計算可能だとしたら、そのプログラムを使って「Q(\varphi)が停止する\Leftrightarrow\varphi(\varphi)が停止しない」という条件を満たすプログラムQが作れて、ここでQ(Q)の停止性を考えると矛盾。この証明はくれちーさんに教えてもらった。

多分解けているだろう。計算可能な無限列の定義もちょっと怪しかったが、集合として計算可能であることは言えるはず。ある\{0,1\}の有限列(これも問題文ではちゃんと自然数エンコードされている)が与えられたとき、それがいずれかのf_nと一致するかを判定するには、列の長さから番号nを特定して、実際にf_nを計算すればよい。

解けたら午前10時を回っていた。部屋のゴミをまとめて出し、大学生協に向かう。お盆休みは昨日までで、今日から営業を再開しているはず。

午前11時に生協に到着したが、学食は午前11時半からだったので、その間に床屋で髪の毛を切ることにした。今日の担当者もいつだかと一緒で、すべての工程が終わった後に気に入らない部分があったのかはさみでチョキチョキしだして、勘弁してくれという気持ちになった。シャンプーの時に全然泡立たなかったが、これは自分の頭髪が汚れていたということだろう。直近でシャワーを浴びたのは月曜日の午前7時半くらいだったようだ。24時間以上経過しているため、来る前にもう一度シャワーを浴びてくればよかった。

学食で食事して帰宅。学食で集団で喋っている人間は叩き出したほうがいいんじゃないかと思った。しばらくYouTubeを見たりコードゴルフをしたりして過ごした後、午後3時から本番前最後の院試ゼミ。

今日も良かった。みんなが何を言っているかも問題なく理解できた。あとは過去問で出現していない概念が出題されないことを願うばかり。急に単語や定理のステートメントを問われると、場合によっては爆死しかねない、と思っている。対称群の部分群であって特定の位数を持つものを数え上げる問題があって、自分は対称群にも苦手意識があったのでまともに考察していなかったが、初手で数列の特徴に帰着しさえすれば、後は競プロで培った数え上げ力でぶん殴れる問題だったようで、面白かった。

午後7時までみっちりとゼミをしていた。これから本番までは共通問題の見直しをしようと思う。院試説明会で、先輩から共通問題を固めるとよい(と思う)と話をされたからだ。

途中院試の問題を解きつつ、ラノベを1冊読んだ。「鳩子さんとラブコメ」3巻。2巻までは特に興味がないということを話していたが、3巻は結構面白かった。だんだん主人公の特異性が明らかになってきて見る目が変わったことが影響している。文中に顔文字を挿入したり、文字のサイズやフォントを細かく変えてセリフの口調や盛り上がりを表現するのは、一昔前のラノベの技法という感じがして面白い。昔どこかで、文を稲妻の形に並べたり、AAでキャラクターの席順を示したりしたラノベが話題になっているのを見た覚えがあるが、そのような表現は最近のラノベでは全く見ない。

せっかく整えたはずの生活リズムだが、もうすでに日付が変わってしまった。せめて明後日の面接まで何とか保ちたい。日記を書いて就寝。午前2時半だった。

08/18(水)

午前9時起床。あまりにも理想的な生活リズムを獲得してしまった。

早起きすると、1日という時間の信じられないくらいの長さを体感する。これだけ長いなら、まだ院試の勉強始めなくても大丈夫かな……?ということで、昨日から始まっていたTCB39の問題を解いた。

https://techful-programming.com/user/event/2214

常のように、この週記が公開されるときには終了しているだろうから、ここに結果と各問題の所感を書いておく。結果はだいたい55分で理論値-12ptだった。7問目でWAを出したのが痛すぎる。

1、2、3問目はよい。サンプルコードが文字列の入力を読んでくれるので、それを流用できるのもいい感じ。4問目は面倒なだけ。5問目はやるだけ。6問目は先頭から貪欲に取ってもよい。7問目は、異なる文字から構成されるグループを作ってその中で完全グラフにするのがよい。グループ分けは出現回数を記録しておく。最初、各文字から出せる辺の本数を考えて2で割るということをしていたが、大間違い。そもそも奇数を2出割る可能性があるコードだったのだから、ちゃんとチェックすればよかった。8問目は1つのペアで操作する場合と2つのペアで操作する場合に分けて丁寧に場合分け。9問目は自明。

10問目は難しい。まず、ある連続部分列が操作によって空文字列にできる条件を考える。しばらく悩んでいたが、ふとインデックスの偶奇で±1を割り振り、文字ごとに足して総和がどちらも0になることが必要十分条件であることに気づいた。ド典型っぽいので、どこかで見たのを何とか思い出せたのだろう。あとは部分列を重複がないように数え上げればよく、dpの遷移は追加できる(間を空文字列にできる)文字のうちそれぞれ最も近くにあるものに飛ばせばよい。最も近いものだけ考えてよいことも、先の必要十分条件から言える。もらうdpで書いた。

院試の問題を解く。今日は本番前日ということで、以前に院試ゼミで他の人が解いていた去年の共通問題の解答を再現してみた。ところが思ったより難しい。2時間粘って、結局院試ゼミのSlackに上がっていた当時の解答を見てしまった。

学食に行って昼食。その後購買で買い物をしたが、パンが大量に割り引かれていた。昨日はお盆明け初日ということで客入りが少なかったのだろう。見れば今日のパンも、昼過ぎであるにも関わらずかなり残っている。このように大学生協の売り上げ不振を目の当たりにすると非常につらい気持ちになる。頼むから潰れないでほしい。

院試が終わったらすぐ2回目のワクチン接種で、以降8月いっぱい副反応で身動きが取れなくなる可能性がある。CHUNITHMの現行イベントのうち1つが09/01で終了してしまうようなので、今のうちに走り切っておくのが良いようだ。ということで、今日はこれからゲーセンに行くことにした。

午後2時過ぎにゲーセンに着いて、午後9時までプレイ。そこそこで切り上げるつもりだったのに思ったより熱が入り、結果この時間までプレイしてしまった。今日は理論値を狙っていて、見事新規に4譜面で達成した。他にも「アポカリプスに反逆の焔を焚べろ」のSSSも達成した。正直なぜ出たのかよくわかっていない。クソ速い片手2連打とそのあとの鍵盤がたまたまうまくいったようだが、再現性が一切ない。

理論値、多少は譜面を選んだものの、それでも頑張ったら案外出るものらしい。今日の教訓としては「目で押さずに曲をよく聞く」「Fastが多いので判定を少しいじる」「集中が切れたら赤が出る」くらい。

夕食は立ち食い蕎麦屋。ざるうどんを頼んだらうどんのコシが強すぎて顎が負けていた。二度と頼まないようにしたい。ドンキで明日の朝ご飯を買って帰宅。

数学基礎論特選のClassroomが更新されていて、提出されたレポートの出来が良かった解答を集めたPDFがアップロードされていた。僕のレポートも2問ばかり選出されたようで、誇らしい気持ちになった。一方僕が匙を投げた問題も実際に解いてきた人がいるのを知り、差を感じることにもなった。以前の週記で言及した論理パズルとモデルについての話だが、これに関しても実際にモデルを用意して考察している解答があった。

与えられた論理パズルについて「共有知識」の定義を参考にしつつ論じよという問題があった。何か適当なモデルを用意するのかと思ったがどういう感じになるかちっともわからない

週記(2021/08/02-2021/08/08) - kotatsugameの日記

家に帰ったら院試の勉強をしようと思っていたが、コードゴルフしていたら日付が変わってしまった。もうジタバタせずに寝たほうがよさそう。ということで午前1時に布団に入り、冴える目を何とかなだめすかして就寝。

08/19(木)

午前6時くらいに目を覚ました。予定ではあと1時間くらい寝ているはずだったのに、全然二度寝できる気がしない。しばらく布団でスマホを使って院試の過去問を眺めていたが、諦めて身を起こした。

食事をしたり体温を測ったり(36.5度)院試ゼミのSlackで過去問の解答を眺めたりして朝の時間を過ごし、午前8時過ぎに家を出た。先頃までとは違い今日は非常に天気が良く、青空を見ているとなんだか元気が出てきた。今日は地下鉄で山に登る。試験会場についてからは、1年以上ぶりに対面するクラスメイト達と喋っていた。

試験は午前9時半から正午までの共通問題、午後1時半から午後3時半までの選択問題、午後4時から午後5時までの英語の3回。試験後の解答用紙回収・チェックの時間が長いのは大事な試験の常だろうが、そのせいで英語の試験が10分繰り下げになったりもした。そういう合間の時間は大学入試だと何もできないが、大学院にもなるとそこそこ緩くなるので、僕は持ってきたラノベを読んで無聊を慰めていた。久しぶりに長時間シャーペンを握ってガリガリ書いたところ、10年来の付き合いであったペンだこが消えかけていることに気づき、かなり感傷的になった。

終了後は数学科の人十数人で別の建物まで行き、そこの黒板で出題された問題に関して議論を交わした。感染症対策的にはあまり褒められた行動ではないのだろうが、それでも久しぶりに持てたこういう時間は信じられないほど楽しかった。結局5時間くらい喋って帰宅。実のところ真面目に議論していたのは最初の3時間くらいな気もする。

明日の面接のために、今日の試験に対する自分の所感をまとめておこう合格体験記に移した。

kotatsugame.hatenablog.com

総評して、別に易化傾向でもなんでもなかったが、出題難易度に助けられた感じこそあるもののそれなりに戦えているようなので、試験の結果には満足している。

帰宅してシャワーを浴び、洗濯機を回し、ラノベの新刊チェックをし、日記を書いて午前4時に就寝。明日は面接だが、午後からなので心に余裕がある。

08/20(金)

午前10時半に起床。面接で必ず聞かれるらしい「好きな定理」について考えながらゆっくり朝食を摂って、昼前に大学に行く。2-SATが多項式時間で解けることについて喋ろうと決めた。

集合が午後の人々と合流し始めた。分野によってスーツが推奨されるところとそうでないところが分かれるという話は聞いていたが、実際に集まってみてみんながスーツを着用しているのを目の当たりにすると、Tシャツを着てきた自分としてはちょっぴり肩身が狭い。

面接の待ち時間で、最近読んでいたラノベを最後まで読み切った。「鳩子さんとラブコメ」4巻。シリーズ完結である。主人公のたくらみに関する才能が明らかになって、3巻から何となく面白く感じられてきたが、そのままシュッと終わってしまった。

面接自体は10分程度で終了。細かい話はこれも合格体験記に書いておいた。1人、たくさん質問してくださる先生がいて、これは自分に興味を持っていると解釈していいのだろうか……?ドキドキした。

面接が終わってからは図書館に移動し、午後5時の合格発表を待つ。ちょっとだけ昨日の問題について話していたが、気が抜けてあまり身が入らない。合間に読む別の本を持ってきていないので図書館から1冊借り出したが、すぐに別の人がSwitchを持ってきたので、それからはスマブラで対戦していた。僕はWiiスマブラをそれなりにプレイしていて、いつもピットを使っていたので、今日もそれを選択。上必殺技の自由度がかなり制限されていてびっくりした。Switchのコントローラーを横持ちしてゲームするのはかなり無理があるということも感じた。

午後5時になったので掲示板を見に行く。何気に掲示板で合格発表を見るのは人生初かもしれない。高校受験の時は寝ていたら親が見に行ってくれた覚えがある。大学受験の合格・不合格発表はネットで見た。数学棟の前につくと、ぽつねんと掲示物が立っていて、ヌルっと合格していた。一安心。

3人で打ち上げと称して食事しに行く。駅前の商店街を歩いて牛タンの店を探したが、どれもちょっとお高いことに気づいてしまったので、ファミレスに行くことにした。途中もう1人参加することになって、待ち時間にゲーセンに入り、僕がCHUNITHMをプレイしているのを見せるやつをした。音ゲーだから音楽が聞こえなければ話にならないのに、プレイヤー以外には筐体の音があまり聞こえない(聞こえたら逆に問題か)ので、周りで見ていてどうなのかはよくわからない。譜面が流れる速度が速すぎてよくわからないというような感想を貰った。

ガストで食事。ポテトが思ったより多かった。入店した時間が遅かったので、すぐ閉店時間になってしまい、慌てて店を出る。そこからはもう帰宅する流れで、僕は途中で別れて再度ゲーセンに入った。

改めてチュウニズムをプレイする。今日は「星色夜空」の理論値を狙ってみたが、軍手をしていないのが影響したのか、今日は赤JがかなりLATEに振れていた。またエアーやエアー後の同時押しで死ぬほど赤を出し、非常に嫌な気持ちになった。必死に頑張って50回くらいプレイし、ようやく出せた。

閉店直前のラスクレで4曲チケットを使ったら、終わり際に店員さんに帰る準備をしてくれというようなことを言われてしまった。まだ1人ほかに残っていると思っていたが、どうやら店側の人間だったらしい。慌ててゲーセンを出て帰宅した。

内定が出てから院試終了まで待ってもらっていたインターン先に、無事合格したことをメールした。当時は本当に院試勉強で忙しくなるのか疑問に思っていたが、結局かなり頑張ったので、インターン開始を待ってもらったのは非常にありがたいことであった。

このインターンに内定が出た。ありがたい限り。手続きはすぐに行うが、実際に働き始めるのは僕の院試が終了してから、つまり9月くらいからになるようだ。

週記(2021/06/07-2021/06/13) - kotatsugameの日記

午前1時半くらいに急激に眠くなったので、慌てて布団に倒れこんだ。そのまま就寝。

08/21(土)

午前11時過ぎ位に目を覚ます。なんとなく眠気を感じたため二度寝しようと思い、ずっと布団でゴロゴロしていたが、全然眠れないので起きることにした。

生協の弁当配達の注文をしてからABCまではずっと合格体験記を書いていた。途中で生協の弁当が配達された。今日の分を注文したことをすっかり忘れていてパックご飯を温めたところだったので、かなりびっくりしたが、二度寝していて受け取れないというようなことにならなくてよかった。

午後9時からABC215。

AtCoder Beginner Contest 215 - AtCoder

7完。Hも解けそうだったが、2WAが取れなかった。なかなか全完できない。

Aはよい。Bは何か簡単な方法がありそうだが、すぐには思いつけなかったので2進数表示した桁数を見た。Cは順列を全列挙。Dはエラトステネスの篩と同時に素因数を前計算しておいて素因数分解し、答えの候補を全探索してこれも素因数分解でチェックした。Eはちょっと面倒なbitDP。状態が2^10\times 10\times Nくらいあってかなりびっくりした。Fはx座標でソートしておくと尺取り法のようにして二分探索の判定が線形時間で行える。

Gはdp配列を多項式だと思いながら計算すると(1+x)のべき乗いくつかの和を計算する問題に落ちる。これは(1+x)を掛けつつ0次の項をいじることである程度まとめて計算できて、O(N^2)に定数倍2分の1がついたくらいになる。900msで通った。HはHallの結婚定理を考えると、キャベツの集合Sに対して「Sに含まれるキャベツの個数」引く「Sからしか出荷できない注文の個数」を計算して、これが負になるようなSを作れればよい。この計算自体はゼータ変換で行えるが、場合の数を求めるのが難しく、結局通せなかった。

コードゴルフをする。A問題は通した後も別の問題の合間を縫ってテストケースハックをしており、コンテスト中に現在の最短である19Bのコードが完成していた。B問題は解説を読んで整数のmsbを答えるだけだったことに気づき、慌ててRakuで取っておいた。CはRakuが短かったが、RubyVimから呼び出すコードに負けた。しかし何とか取り返すことに成功。空白を含めて9文字で順列を生成しても答えは変わらないが、実行時間はかなりギリギリだった。DはPerl。Eは手つかずで、FはRubyのbsearch。

D問題の素因数分解は、O(\sqrt A)で行っても間に合うらしい。Eのdpはこの状態数107が想定解でびっくり。

Hの解説を読んで、自分の間違いに気づいた。上のようにキャベツの集合Sに対してf(S)を「Sに含まれるキャベツの個数」引く「Sからしか出荷できない注文の個数」と定義したとき、{\rm argmin}f(S)には複数の集合が含まれ得る。僕は、キャベツの集合TUについてf(T\cup U)f(T)以下またはf(U)以下になると考え、このことから{\rm argmin}f(S)のうち包含関係について極大なものたちは互いに交差せず、よってそれぞれ考えればよいだろうと思っていたが、f(T\cup U)の評価が違っていた。この場合、数え上げのためにはさらに何度かゼータ変換とメビウス変換を行う必要があって、大変に面倒だったので、気づけてもコンテスト中に通せたかは微妙だろう。

Hのupsolveをした後は合格体験記を書く作業に戻り、朝方になって投稿した。

kotatsugame.hatenablog.com

午前6時就寝。

08/22(日)

午後0時半に目を覚ます。食事して午後1時から技術室奥プログラミングコンテスト#6 Day1に出た。

技術室奥プログラミングコンテスト#6 Day1 - AtCoder

Aはカス。適当に引き算すればいいだろうと思っていたが、念のためサンプル2も確認したら微妙に違う。そこで問題文に戻ってよく読んでみると、何やら怪しげなことが書いてある。実際トップページから過去のコンテストの日程を確認すると、2017年だけ開催されていなかったので、それと2015年、2016年を場合分けしてAC。カス。聞いた話によるとサンプル2は最初置かれていなかったらしい。ありえん。お誕生日コンテストだったのならお誕生日コンテストと書いておいてほしい。

Bは色が十分多いので適当にやってよい。Cは平均値だと誤読して1WA。Dは累積和をソート、mod取り忘れとソート範囲ミスで2WA。Eは最後に答えを2倍するところでオーバーフローして1WA。このあたり、焦っているのに出すコードが軒並み落ちてしまってかなり辛かった。Fは適当にdp。Gは謎の条件を使ってLISの更新をセグ木の範囲取得2回で行う。Hは冷静になるとソートして貪欲に足すのを2回行うだけでよい。オーバーフローで1WA。

Iが解けなかったのでいったん飛ばす。Jは負辺ありの最小費用流。Kは数字がループしているのが怖いが、適当に±100くらいの幅でdpしたら通ってしまった。Lは2行に置かれた多角形の差を持つdpで、2個飛ばしのimos法で高速化した遷移を2N回行うと答えが出る。Iに戻る。整数N=lrと積で表示したとき、|xl-yr|=2となるようなx,yを探し、kを復元したい。これは拡張ユークリッドの互除法を使うと何とかできるが、微妙に見つからない値もあるので、x-\frac r g,y+\frac l gとちょっとずらしたところ(gは最大公約数)もチェックしてみた。小さいケースを全部試して通ったので提出、AC。

Mも解けなかったので飛ばし、N。最初はO(\min(\frac{N^2}{K},NK\log N))で解こうとしていたが、TLEが全然取れない。残り時間も少なくなってきた中、ふと2次元セグメント木で書けることに気づく。dpの更新順を逆にすると、自分が持っている区間取得の2次元セグメント木で十分対応できたので、それを実装してAC。

解説を読む。Jのdpは結構面白い。Kの想定解はなるほどな~という感じ。そもそも隣接項の差の絶対値をとったものについて、総和の半分が操作回数となることに気づいていなかった。Iは答えの関数が乗法的関数らしく、素因数ごとに確かめることで答えが必ず2べきであることがわかる。実験でもそれっぽさは出ていたが、理論的にはわかっていなかった。

コードゴルフをする。Aはdcで場合分けを頑張る。今のところはN-2014を計算し、3になったら0に置き換え、1,2だったら1を足し、最後に0とmaxを取って1を引いている。Bは解説の式をRakuで書く。Cも解説にある方針で、-1A_1に置き換えて実際に中央値を求めるコードをPerlで書いた。DはRuby。EはPerlで、なかなかTLEに苦しんだ。他に、今のところHをRubyで、IをPerlとfactorコマンドでゴルフしてある。

このコンテストはAtCoderのトップページから辿れないので、AtCoderProblemsでもatgolferでも専用のコードを用意してクロールしている。そのためのプルリクエストを出しておいて、atgolferのほうは自分でマージしてしまって早速botに反映しておいた。

github.com

昨日投稿した合格体験記の中で、院試の共通問題3番(3)が解けなかったという話をしたが、今朝方針がリプライされていた。自分でちゃんと細部を詰めてみると納得がいったので、証明を追加して記事を更新しておいた。わかってみるとそれはそうという感じがするが、試験中に解けなかったのは確か。

東北大学大学院理学研究科 数学専攻 合格体験記 - kotatsugameの日記

午後9時からARC125に出た。

AtCoder Regular Contest 125 - AtCoder

4完遅解き。頭が回っておらず、BもCもDも均等に30分くらいかけてしまった。

Aはすぐわかった。最初にちょっと回したら、あとは小刻みに振動させるだけになる。丁寧に実装してAC。

Bは式変形を頑張ると、d^2\le x^2-N-1を満たすようなx0\le d\lt Nそれぞれに対して数え、和をとる問題に落ちる。条件がx\ge d+kと同値になるようにkを定めると、対応するdの範囲(の下側)がd\ge\left\lceil\frac{N+1-k^2}{2k}\right\rceilになるので、k\sqrt Nまで動かしつつ範囲ごとにまとめて数えた。かなり大変だった。

Cは最初に(3,2,1),(5,4),(8,7,6)のようなブロックに分かれる構築をしてWAを貰い、そこからずっと悩んでいた。この1を2番目に持ってこれることに気づいて愕然。実装ミスでさらに1WAした。

Dは、部分列dpっぽく考えると、スキップしたものと同じ要素を直前と直後で取らないような遷移だけすれば数え上げられる。あまり詰めずに書き始めたら全然答えが合わなかった。ちゃんと考え直すとセグメント木またはBITの区間和で書けて、スキップする区間の直前の要素の条件はダメな位置の値を0に戻すことで達成でき、直後の要素の条件は取得範囲を絞ることで対応できる。

Eを考えていたが一切わからず、コンテスト終了。赤になってから2回のARCはどちらもひどい順位を取ってしまっており、かなり絶望的。

コードゴルフをする。Aは手つかず。Bはdc。微妙にTLEしていたがコードを縮めると通った。dcにおけるループは再帰関数で書かれるが、では関数呼び出しは内部でどのように行われているかというと、コマンド文字列を毎回evalしているのである。なので、ループ用関数のコードが短くなれば、その分実行時間も短くなるという寸法だ。CはRuby。DはとりあえずC++で清書したものが最短になっている。

TCB39が終了していた。結果発表前、8問時点の結果では僕より点数が高く解答時間も短い人が数人いたが、蓋を開けてみると全完者は10人、その中でも自分は2位に20点差をつけ、合計解答時間でも最速と文句なしの優勝だった。かなり気分がいいが、それだけに理論値を逃したことが悔やまれる。

10問目はかなり難しかったらしい。上のほうで書いた判定方法を思いついたのは、まさに天啓という感じだったが、これは実際どこかのAGCの問題で出ていたという話を聞いた。どの問題かはわかっていない。

夜、日記を書く。明日月曜日はついにワクチン2回目の接種をする日だ。1回目ですでに副反応がだいぶ厳しかったので、今回はちゃんと買い物をして備え、しばらくは家でおとなしくしていたい。1回目の副反応は喉元を過ぎたので熱さを忘れてしまったが、確か冷えピタがかなり欲しくなったことを覚えている。ほかにもTLを見て、解熱剤(カロナールがいいのか?)とゼリー飲料も買い込んでおくべきと判断している。