週記（2021/08/23-2021/08/29）

08/23(月)

先週の日曜日は、週記を投稿してから布団に入り、少し本を読んで寝た。午前6時半だった。

午後1時起床。ワクチンの予診票を印刷して記入し、家を出る。まず大学生協でゼリー飲料をミールカードの1日分限度額いっぱい、6パック買った。ゼリー飲料はもともと好きだが、こういう機会でもないと食事としてたくさん買い込むのはためらわれるので、ちょっとワクワクした。地下鉄に乗って駅前まで出て、丸亀製麺で昼食を済ませる。今日も仙台駅にあるアンパンマンの石像を写真に収めた。

ほぼ予約通りの時間に接種会場に到着。今日は1回目のときよりも人が少ない気がするが、タイミングの問題だろうか。問診で、1回目の副反応で腕の痛みがひどかったことを訴えたら、氷嚢で冷やすくらいしかないと言われた。これは冷えピタではいけないらしい。氷嚢と冷えピタで患部を冷やすメカニズムが異なるというのは、あまり意識したことがなかった。

特に問題なく接種完了、15分経過観察して接種会場を去る。薬局に寄って冷えピタと解熱剤を買う。解熱剤がどこに売っているのかわからなくてしばらくウロウロしていたが、レジに立っている人が薬剤師さんだったらしく、話しかけるとレジの後ろにある薬棚からいろいろ紹介してくださった。先週の週記ではカロナールがいいのかもと書いていたが、置いていないようだし、薬剤師さんのおすすめを買うべきだろうと思って、結局イブクイック頭痛薬というものを買った。

まだ駅前で買い物を続ける。まずLOFTに入って洗面所にかけるための手拭きタオルを購入。前にもここで買ったことがあって、その時は1枚700円くらいのタオルしか見つからなかったのだが、今日は2枚組で1000円のタオルを発見した。次に本屋に行ってラノベを購入し、いよいよ帰宅した。

腕が痛くなることを見越して、帰ってきてすぐにシャワーを浴びた。その後、CF #739 div.3を解いた。

Dashboard - Codeforces Round #739 (Div. 3) - Codeforces

Aはよい。Bは-1を出力する場合分けが面倒だが、サンプルを合わせれば通る。Cも面倒なだけ。Dは適当に259まで調べたら通ったが、ちょうどそこまで調べればよいということに理論的な裏付けがあるらしい。つまり、答えが18桁以下となることが示せるようだ。Eは難しいと思ったが、まず文字が消える順番がわかり、各文字の出現場所を見てsとしてあり得るprefixを調べたら一意的に定まるのでOK。Fはよくわからない。出現した数字を10bitで持つ桁dpで解こうとしたがTLEしてしまった。まずF1は、10bitのうち高々2bitしか立っていないものだけ考えればよい。F2も同じ感じで計算量が削減できて、K\ge 7の場合は桁dpせず実際にインクリメントして探すことにしたら、639msで通った。想定解はprefixを固定してなんやかんやするらしい。

午後9時になって、ゲノコン2021に出た。AtCoderのトップページからリンクを辿れないので、かなり不便。

Genocon2021 ー DNA Sequence Analysis Challenge - AtCoder

今日はA問題だけが公開された。問題を一読してy/ATGC/TACG/だと思い込み提出、WA。実は答えをreverseしなければならなかったらしい。sedでreverseは難しいので、bashを使う。その場合はsedを呼び出すよりtr ATGC TACGのほうが短くなる。10分間の提出制限を悶々として待ち、2回目の提出でACした。21B。

布団に入って本を1冊読了。「世にも美しき数学者たちの日常」で、院試の面接後に図書館で借り出したもの。面白くはあったが、数学科の院に進むことを決めた今読むと、いろいろ思うところがあって素直に楽しめなかった。あとは、数学が苦手な人間が数学の面白さを知る、みたいなことに興味を持てないのも大きい。

なんとなく熱っぽいが、体温を測ると36.4度だった。しかし寒気がひどい。タオルケットしかないので、それに無理やりくるまるようにして就寝。午前0時だった。

08/24(火)

夜中から朝方にかけて何度か寝たり起きたりを繰り返していた。記録を残してある。

まず午前3時半ごろに頭痛と喉の渇きで起床。脱水症状で苦しむ人が多いらしいので、意識的に水分をたくさん摂る。熱を測ると38.3度だった。腕や足が熱を持っていて、寒気という意味では多少マシになっていた。次に午前5時半ごろ、また喉の渇きで起床。38.5度だった。頭を少し動かすと頭痛がひどいので、ゼリー飲料を食べて頭痛薬を服用。さらに冷えピタを貼った。さらに午前7時半ごろにも起床。頭痛は収まったかと思ったが、やはり頭を動かすとかなり痛む。今になってようやく少しばかり汗が出てきた。38.5度。

それからしばらくはスマホを触っていた。ワクチン1回目の時は、どんな体勢でも左腕が痛くてたまらなかったものだが、今回はそこまで痛くない。やはり1回目接種の直後にしこたまチュウニズムをやったのがマズかったのだろう。しばらくpixivで小説を漁ったりYouTubeを見たりしたあと、昼前にまた寝て、午後3時に目を覚ました。37.3度。

しばらく布団でゴロゴロした後、いよいよ起きることにする。食欲は全くないが、頭痛薬を服用するために食事はしなければならない。ゼリー飲料でもよかったが、多少元気があるので生協の冷凍弁当を温めた。熱を測ると37.5度だったので、まだ微熱がある。

7セメスターに取った全学教育の成績が出ていた。定理証明支援系を実装して提出した論理学はAA、数理統計学はAだった。まあいい感じじゃないだろうか。結局GPAがいつ使われるのかわからないまま院に進もうとしている。AとかAAを気にする必要は、今はもうないように思われる。

先週金曜日のyukicoderの問題を少しだけ解いた。なかなか難しめの回だったようで、3問だけ。

No.1650 Moving Coins - yukicoder

操作回数はすぐわかるが、実際に構築するのがちょっと面倒。ほかのコインに邪魔されずに目的地までたどり着けるコインを優先的に動かし、それが動いたことによって新たに目的地にたどり着けるようになったコインを操作待機キューに入れるという、bfsみたいなことをして解いた。解説は右に動くコインと左に動くコインの操作範囲が被らないことを示していて、非常に頭が良い。

No.1651 Removing Cards - yukicoder

実験すると、最後に残るカードというのはある程度一定らしい。しかもそのようなカードの種類はそれほど多くなさそう。なので、うまいこと最後に残るカードだけを前計算して、クエリには二分探索で答えるという方針が立つ。前計算はちょっと難しい。カードを0-indexedにするとX_{i+1}-\left\lfloor\frac{X_{i+1}}K\right\rfloor=X_i+1なるX_{i+1}が計算できればよくて、僕はX_{i+1}=X_i+1とした後条件を満たすまでX_{i+1}\leftarrow X_i+1+\left\lfloor\frac{X_{i+1}}K\right\rfloorと更新し続けたが、解説のようにO(1)で求めることもできるようだ。

No.1653 Squarefree - yukicoder

ちょっとTLでヒントを見てしまったかもしれない。区間篩を使って\sqrt[3]{R}までの素数で割り算した後、残ったものが平方数かをチェックすれば十分。

午後9時になって、ゲノコン2021にB問題が追加された。

Genocon2021 ー DNA Sequence Analysis Challenge - AtCoder

今日の問題はいつものdp。復元がかなり面倒。この問題のFAが3分を切っているのはかなり驚きであったが、どうやら事前に予想して問題を解いておいたタイプのFAらしい。

夜になって熱が下がり、頭痛も収まったように思える。寝たり起きたりを繰り返していたので眠気もあるはずだが、ともかく思ったより元気なので、CF #740 div.1に出ることにした。

Dashboard - Codeforces Round #740 (Div. 1, based on VK Cup 2021 - Final (Engine)) - Codeforces

4完86位で2886→2844(-42)。コンテスト中はpredictorが動いていなかった（プロフィールページへのアクセスが禁止されていたことが原因らしい）ためわからなかったが、自分のレートが上振れしすぎていて、生半可な順位を取るとすぐ落ちてしまうような位置にいたらしい。

Aはよい。先手2通りとAliceが自分のサーブをどれだけキープできたかを全部試すことができる。これが場合の数を求めさせる問題であっても面倒なだけだったろう。Bはメモリが制限されていて、空間O(n)が許されないのか？と不安になったが、調べたら余裕だった。最初に貰うdpを書いたらO(n\sqrt n)でかなり時間がかかっていた。これを高速化するのかと途方に暮れそうになったが、配るdpのほうも試してみたらO(n\log n)になっていてびっくりした。後者のまとめ方のほうがより多くの要素をまとめられるようだ。

Cは、偶数番目と奇数番目をそれぞれ独立にソートすることしかできないことがわかる。後ろから2番目の要素を正しいものにするとき、どうやっても最後尾の要素と一緒に動かしてくるしかないので、その2つの最初の位置関係2通りで場合分けしてみると、どちらもちょうど5手で達成可能なことがわかる。その操作を使って後ろから2つずつ決めていくとちょうど\frac{5(n-1)}2手で達成可能なので、想定解であることに確信を持った。毎回の操作で愚直にreverseしてよい制約なので実装も簡単。

Dは難しい。まず操作列の情報から、出来上がったソート済みの列の大小関係において\geと\gtがそれぞれどこに入るかを決められる。それがわかったら、対応して適当に値をいくらか引くことですべて\geに置き換えることができ、そのとき答えは重複組み合わせで計算できる。よって問題は最初のパート、操作列の情報を処理する部分だけになる。\gtの場所を管理することを考えると、「y-1以上の値をインクリメントする」「yを挿入する」ができればよい。この方針からbitsetなどを使って解くこともできるようだが、思いつかなかったため別の方法で解いた。

まず、新しく挿入する要素を、以前のインクリメントが適用されていた場合の数に置き換え、最後に一気にインクリメントする方法を考えた。しかしこれは置き換え先のちょうど良い値を確保できず失敗。次に、操作列を逆から見て、インクリメントされる先をありうるすべての値に対して管理することにした。こちらは、例えばy=3での更新を考えると、(0,1,2,3,4)\mapsto(0,1,2,3,4)だったのが(0,1,3,4,5)に置き換わり、次にy=1での更新を考えると(1,3,4,5,6)になる。つまり、列の途中を抜き去るような形で実現することができて、これは双方向連結リストで効率よく実装できる。どこを更新すればよいかは、消されていない数字を管理するBIT上の二分探索で判定できる。

実装はちょっとだけ面倒で、テストケースごとに初期化することを許されていないので、更新された部分だけ最後にロールバックする必要があった。

コンテスト後はラノベを読んでいた。途中でatgolferを確認したら、先週日曜日の技術室奥プロコンのA問題が縮められていた。どうやら数式を弄って場合分けするのではなくて答えをスタックに積んでRで持ってきたほうが短くなったらしい。そのコードには縮む余地が残っていたので、そこを縮めて取り返した。

CFのシステムテストを見届けてからベッドに移動し、それからもしばらくラノベを読み続けていた。残り100ページを切ったところで眠気に耐えられず就寝。午前6時だった。

08/25(水)

午後1時半ごろ起床。もうちょっと寝ようかどうしようかと2時間以上ゴロゴロしていたら眠気が消えてしまったので、ベッドから身を起こした。

昨日読んでいたラノベを読了。「辺境都市の育成者」4巻。カバー折り返しの著者コメントに「5巻出せたらいいなあ」と書いてあって、お前……打ち切られるのか？と焦ったが、後書きを読んだ感じでは普通に出そう。よかった。この作者の文章は読みづらいということを週記で何度も言及してきたわけだが、今巻でも読みづらさに新たな発見があった。とにかくセリフや描写の文章を最後まで書かないのだ。例えばそれは、視点人物の驚きを表現するためであったり、ここまで書けばわかるでしょう？という感じで省略したり。

……ということをここまで書いて、改めて本を確認したところ、別にそうでもないような気がする。体言止めが多い気もしたが、主に戦闘シーンだし疾走感の表現と解釈できるだろう。この独特の癖がある文章は、一体何に由来するんだろう。これまで文体に注目していたが、実は単純にセリフ回しが特徴的なだけかもしれない。どうであろうと、読みにくさをこらえて読むだけの面白さは十分ある。

「東方遺骸王」の更新が来ていた。最近は旧作1作目の東方靈異伝の話をやっていたのだが、一区切りついたらしい。東方古代スタートのオリ主ものは、原作が始まったら自機組に対応して動く必要が出てくるので、存分に無双できるのは原作前と、あとはクライマックスにありがちなオリジナル異変のみとなる。そういう意味では今作も例に漏れず、この章では主人公の雄（？）姿があまり見られなくてちょっと残念だった。

章題が「東方靈異伝」になっていた。ついに旧作突入らしい。感慨深い。

週記（2021/05/17-2021/-5/23） - kotatsugameの日記

東方遺骸王 - ハーメルン

GCJ Tシャツが届いた。間違えてSサイズを注文してしまっていたが、着てみると案外Mサイズより体に合っていた。やはりアメリカとのサイズ感の違いは大きい。これまでずっとコンテストTシャツはMサイズを注文していたが、そんな中で同じくらい体にフィットしていたものがあったのも確かで、この違いはどういうことだろう？と確かめてみたら、TCO RegionalのTシャツだったから、日本サイズのMだったということか。

GCJ Tシャツのサイズ表記はSM、MD、LGなどと書いてあって何のことかよくわからなかったため、胸囲と身長の対応など調べてSMにしておいたが、どうやらこれらはSMall、MeDium、LarGeの意味らしい。これまでは確かMサイズを注文していたので、間違えてしまったか？

週記（2021/05/24-2021/05/30） - kotatsugameの日記

学食に行って夕食を食べ、図書館で本を返却して帰宅。山の上で借りた本を下で返せるとは便利なものだ。本当はこの本は暇つぶしにちょっと借りただけで、返却してから下山するつもりだったのが、下でも返せるということを聞いてそのまま読み通すことを決意した、という背景があった。

今日もゲノコン2021。今日はC問題のマラソンが公開された。

Genocon2021 ー DNA Sequence Analysis Challenge - AtCoder

largeで正の点数を取るのが非常に難しかった。今のところようやく100点くらい取れて、もう限界。方針としては、まずすべての文字列を部分文字列として含むような文字列を作り、適当に文字を削除しつつ一致する文字数が最大になるようにうまいことあてはめてみている。1回の計算にかなり時間がかかるので全然試行回数が稼げず、最初のほうは一気に100文字くらい削除したりしつつ山登り法で頑張っている。一度に削除する文字数を増やしたことが、largeで正の点数を取れるようになった改善点だった。

マインスイーパを久しぶりにプレイしてみたが、トラックボールマウスだと難しい。細かい制御が簡単になるかと思っていたのだが、今のところ（慣れていないだけか）全然そんなことはないし、大きな移動はどうやっても難しくて散々。ボールに指を突き立てるのがよいとアドバイスをいただいたがこれもなかなかうまくいかない。

トラックボールの掃除ということも指摘されて、調べてみたら、実は掃除だけならドライバなど持ち出す必要はなく、ボールを裏から押し込むだけで取り外せたらしい！取り外してみると信じられないくらいのゴミが溜まっていて、取り除くと格段にボール操作がスムーズになったが、逆に転がりすぎてまた操作精度が悪くなってしまった気もする。まあ練習あるのみだろう。今はもうそこまでマインスイーパに対するモチベがなくなってしまったが……。

マラソン問題に対する別の方針を思いついたので試してみたが、全然ダメだった。各文字のインデックスを管理して適当に±1する焼き鈍し、文字列の表現では'-'を適当に挿入したり移動させたりして焼き鈍す方針だったが、文字が左右に散らばりすぎてしまった。

日記を書いた後、ふと大学生協で本を注文しようと思い立った。買っていない新刊はそれほどなく、今日は6冊注文した。週明けに届くだろう。

布団に入り、ラノベを読み始めた。適当なところで切り上げて寝るつもりだったが、週末は夜よりむしろ昼間にコンテストが集中しているようなので、このあたりで生活リズムを1周させておこうという気持ちになって、とりあえずそのままラノベを読み切った。

「英国カノジョは“らぶゆー”じゃなくてスキと言いたい」。あまり面白くなかった。最近似たような話が多すぎて設定に既視感があるとか、ヒロインの好意が1巻時点ですでに駄々洩れになっているとかは大きな問題ではなく、主人公の初恋相手が悪女で、かなり不穏な動きをしていたことが受け入れられなかったのが一番の原因。主人公は初恋相手をまだ好いていて、逆に手玉に取られておもちゃ扱いされそうになっているという展開で、1巻からする話ではないだろうと思ってしまった。

そのあと別のラノベに手を付けたが、眠気に耐え兼ね午前2時就寝。

08/26(木)

消えた。

08/27(金)

08/26 午後10時半くらいに目を覚ます。CFで謎のテストラウンドが生えていたので出ようかと思ったが、眠気が勝った。

次に目を覚ましたのは、午前2時くらいだった。スマホでTLを眺めていたら眠気が消え失せたので、午前5時くらいになって布団から身を起こし、パソコンの前に座って開いていた問題の考察をした。

Submission #25355266 - CODE FESTIVAL 2016 qual A

ちょっと前に橙diffを何問か解いたとき、一緒に考察も大体終わっていて、しかし実装する前に飽きてしまったらしく、未ACのままだった。当時の考察を思い出して解こうとしたが、実装している最中に全然詰め切れていなかったことに気づき、そこからさらに数日空いた。

2×2マスの条件は、マス目の縦横の差を見て一致していることと言い換えられる。すでに値がわかっているマスから、その差分に関する条件を取り出すと、矛盾していないなら適当に0埋めすることで全体のマスについての縦横の差が復元できて、差を累積的に足していって縦が最小になり、かつ横でも最小になるマスの値が非負かをチェックすればよいと考えていた。しかし実際にやってみると、復元できるのはある種の連結成分ごとに限られて、いくつかの連結成分が成立していても全体で成立しているとは言えないかもしれない。適当に手で試してみてよさそうだと感じ、提出すると、ACできた。

解説では、差を取った後適当に戻して、マス(i,j)の値がx_i+y_jとなるようなx,yを考察していた。これだと、値がわかっているマスから復元した情報を元に、ストレートにマスの最小値が非負であることを確かめられそうだ。

数学基礎論の単位が出ていた。AAだった。レポートを頑張った甲斐があった。4年ゼミは通年の講義として扱われるので、火曜日に出た2講義と合わせて今セメスターの成績が確定したことになった。しかし3つしか講義を取らなくてよいとは！2、3年生のときの頑張りがあって今、4年生でこんなに楽ができている。

またマインスイーパをしばらくプレイしていた。ボールに指を突き立てるとよいというアドバイスは、ボールを強く押さえながら操作するのが良いということだと考えているが、なかなかうまくいかない。細かい移動でもすぐ積み重なってボールから指がずれていってしまう。頻繁に指を置きなおすのもタイムに影響がありそうだ。ということでこのアドバイスはうまくいかず、今のところは諦めてポインタの移動速度を1段階下げることで対処している。

何度かプレイしていたらそこそこ良い記録が出たので、動画をキャプチャしてTwitterに上げた。中級で21.69秒。

昼過ぎ、外出する。学食で昼食を食べてゲームセンターに向かった。道中は信じられないくらい暑くて大変だった。いつもゲーセンに着くころにはマスクがしっとりしていて、そのままプレイしてさらに汗をかくものだから、かなり不快感がある。替えのマスクを用意しておくのも手だろう。

今日の成果は12の理論値が1譜面、13のAJが4譜面。おねがいダーリンの譜面が追加されたとき、当時実力が同じくらいだったFFがポンと理論値を出していたのを覚えていたのでプレイしてみたが、かなり精度を取りやすかった。といっても10回ちょっとプレイしている。途中FASTが少し出るようになったので判定を前にずらしてみたところ、なぜかさらにFASTが出るようになってびっくりした。結局この譜面は±0.0でプレイするのが一番らしい。

たいぺーと合流して夕食に向かおうとしていたら、インターン先から電話がかかってきた。ゲーセンの中だったので、折り返し電話しますと言って静かな場所を探したが、周りも繁華街でどうしようもなく、結局壁に向かって耳を塞ぎながら通話する羽目になった。何とか聞き取れたので安心。

夕食はガスト。魚介類は意識しないと全然食べないので、今日はネギトロ丼を注文した。帰りに本屋に寄ったが、水曜日に大学生協で新刊を注文してしまったので店頭では買えず、歯がゆい思いをした。

帰宅してyukicoder 311に参加した。

yukicoder contest 311 - yukicoder

ABDEFの5完。Gはともかく、Cが全然わからない。solvedが100を超えていて精神にダメージ。

Aはよい。Bは\frac{B(B+1)}2-\frac{A(A-1)}2=\frac{(B+A)(B-A+1)}2と式変形して、B-A+1の値で適当に場合分けする。するとB\le A+1であることがわかるので、適当に素数を前計算したあと全探索でよい。次にCを開いたが、わからなかったので、BのHard VersionであるFに移った。こちらは制約が1010くらいになっている。素数を列挙するのは不可能だが、知りたいのは個数だけであり、Library Checkerの素数カウントの制約が1011なので、そこからライブラリを盗んでくれば通る。

Dは素因数分解して適当に二項係数の計算をする。Eは(A-0E)^m=Oと見て、院試のことを思い出して固有値0だの広義固有空間だの考えそうになったが、サイズの制約105を見て冷静になった。非零要素のことを列から行への辺だと思うと、行列の積はパスの集まりと見ることができる。これでグラフの問題に落ちたので、あとはそこから最長パスを探せばよい。トポロジカルソートしながら計算できた。

Cの希望が見えないのでGを考えていたが、急激に眠たくなってしまった。コンテスト中だがさすがに耐えられない。午後11時前、ベッドに倒れ込むように就寝。

08/28(土)

何度か目を覚ましたり寝たりしていた。朝方目を覚ますということに慣れておらず、かなり現実感が希薄。結局午前11時くらいに起床した。しばらくコードゴルフをして、学食に行った。帰ってきてから午後2時までは、FHC Qualの問題を読んでいた。実装は後回しにして、午後2時から日本橋ハーフマラソン 2021に参加した。

RECRUIT 日本橋ハーフマラソン 2021 - AtCoder

まずAに1Bの解を提出してFAとshortestを取り、続いてBのゴルフをした。ちゃんと40x40マスに並べて出力しなければならないようで、Vimが最短となった。改めてマラソンに取り掛かる。

まずAにとりあえずの解を出した。\frac K 2以上で最小のものを\frac K 2未満で最大のものに足して1回オーバーフローを起こす。起こせないなら\frac K 2以上の要素を未満のほうに回して同じことをする。これを一通り行った後、\frac K 2以上の要素をそれぞれオーバーフローさせて、余った操作回数では適当に2倍してみたりする。これで86216点だったが、周りと比べてかなり低いので、見切りをつけてBに移った。

Bは、性能が高い椅子だけを抜き出してパワーを1増やす焼きなましをした。40個抜き出すと156656点だったが、全体のちょうど半分、800個の椅子を抜き出すと191210点と急激に伸びた。実はこの時、過去のAHCで目にした解法を真似して椅子のパワーを0に戻す更新もたまに行っていたが、後に無駄であったことが分かった。実際、椅子のパワーを0に戻す更新の確率を引き下げた提出は194644点と少し伸びていた。

そのあとしばらくパラメータを変えて投げ続けていたが、全然変わらない。と、ふと、焼きなましの更新処理に間違いがあることに気づいた。今見ている椅子の動作音の範囲にほかの椅子が入っていたらその椅子のパワーは0にしなければならないが、ほかの椅子の動作音の範囲に今見ている椅子が入った場合は、その椅子のパワーを下げるにしても0にする必要はない。ここを直したら一気に209130点と1桁順位に入った。さらに、出力する直前に空いているマスがあった場合はそこの椅子を動作させることにしたら、209413点になった。

これまでTL目いっぱい焼きなましをしていたが、時間を短くしてもスコアにはほとんど影響がないようだ。なので、同じ焼きなましを15回行い、最良の解を出力するようにした。これで211058点となり、B問題の最終結果となった。

ここまででコンテスト時間は残り40分くらいであった。A問題でまともな点数を取れれば景品がもらえる可能性があるので、改めて挑戦してみる。値の大きいほうから順に相方を探して小さくしてみたが、全然スコアが出ない。ビジュアライザを見ると謎の挙動をしている。コードを読み直してみると、大量のバグが見つかった。不等号の向きが違うので値を大きくしてしまっていたり、更新前の値をそのまま参照しているため意図しない足し算をしたり。ここを直すとそれなりにまともなスコアが出た。相方を探す処理のループを増やし、そちらでは自分を2倍して試してみるという処理を追加して115146点。残り時間がほとんどないが、自分を4倍する処理も無理やり書ききってギリギリで提出したら、122478点になった。

最終結果はA問題267位、B問題8位で積の順位は37位。景品は上位40名までは必ずもらえるので、何とか滑りこめたようだ。

コンテスト後に少しTLを眺めていたが、A問題は\frac K 2で分けるのは良くて、そのあと一旦0とKに少しずつ寄せてから、改めて0に寄せるのが良いらしい。そうでなくても、みんなある程度アルゴリズムで押していて、試行回数がどうのという問題ではなかったようだ。B問題は、動作させる椅子の集合を決めると設定すべきパワーがわかるので、動作させる椅子の集合を焼きなますと良かったようだ。これは非常に面白い。できるだけシンプルで根本的なものを焼きなますのが一般に良いのだろうか。

今日はこの後何もコンテストがない。電車で街に出て碧黴さんと食事した。土曜日の夜、この時間に出歩くのはなかなか新鮮な気持ち。赤達成のお祝いに日本酒を下さるという話を前からしていて、ついにそれを受け取った。

帰り道で別れた。ゲーセンに行こうとしたが、お腹がいっぱいなのでしばらくブックオフで休んでいこう、と久しぶりに入店した。棚を見ていると、文庫本でシリーズ11冊全部そろっているものを発見し、思わず買ってしまった。重い荷物を抱えてブックオフを出て、ゲーセンに向かった。今日は特に成果なし、素手だったのでスライダーが滑らなくて大変だった。2時間くらいプレイして帰宅。

atgolferに流れてきた更新ですごいものがあった。2数のbitwise andとしてありうる最大値を求めるのは上位桁から決めていけばよかったが、これは区間の左端を0、右端を2^{31}にした二分探索で実現できる。挙動を思い浮かべれば確かにという感じだが、これに気付くのはすさまじいとしか言いようがない。

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

Facebook Hacker Cup - 2021 - Qualification Round

今朝読んでいたFHC Qualの問題を実装する。提出しようとしたら、今年から入力ファイルがパスワード付きzipで渡されるようになったらしく、かなり困惑。自分のパソコンに7-zipが入っていたので事なきを得たが、エクスプローラーでできないことを要求されるとびっくりしてしまう。取り合えずaABcを解いた。このことは順位表からわかる情報だが、問題の内容に関する言及が許されていたかどうか記憶にないし、この日記が公開される時点でまだコンテストは終わっていないので、特に何も書けない。

Cを考えていたらうっかり意識を飛ばしてしまったので、素直に布団に入って就寝。午前1時だった。

08/29(日)

午前7時半起床。かなりまともな生活リズムになってしまい、夜中のコンテストに不安がある。なのでもう少し寝ておこうと布団でゴロゴロしていたが、全然眠れなかった。YouTubeを見たりなろうを読んだりしていた。

昼前になって起きだして、食事したりコードゴルフしたりした後、午後1時から技術室奥プログラミングコンテスト#6 Day2に出た。

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

ABCDFHjKの4300点で11位。

Aはかなり迷走して、小さなケースを実験してようやく気付いた。挿入dpのようなことを考えれば自明。4分ちょっとかけて出したdc 15Bは、コンテスト後に見たところ、何とか最短を取れていた。Bは文字列の先頭に'A'をつけて、隣接する文字が異なるかどうかを管理することにした。適当に操作を言い換えると、前から貪欲に揃えるのが楽に書ける。Cは実験して規則性に気付いた。コードゴルフ的には、N=4のときの解としてサンプルにある[2,3,2,1]ではなく[3,1,3,1]を使うと、繰り返しになるのでちょっと短く書ける。Dは01を繰り返してYesが返ってくる文字列を作成し、後ろから削っていく。N=1のときに空文字列をクエリとして投げてしまい、WAを何回か食らった。

Eが解けなかったのでFに移る。FはD_1との偶奇の違いを見て、もし異なっていた場合はそれ同士でうまいこと構成しておく。最後に辺が規定量に達するまで重み最大の辺を追加する処理が面倒だった。1点、D_1=0のときに奇数長のパスを求められるとうまく構築できないケースがあって、それにも引っかかった。

次にKがたくさん解かれていたのでそちらに移った。二項係数をバラしてみると、前の答えに何をかければよいかがわかる。具体的には\prod(A_i+x)をx^Mで割った形をしている。割り算のほうは適当に計算することにして分子を考えると、多項式を計算して多点評価すれば求める値が得られる。1次式の積を高速に計算する方法がわからず、logでも取ってみようかといろいろ調べていると、分割統治法で計算すればよいという言及を見つけたので、セグメント木に乗せてall_prodした。多点評価はうしさんのライブラリを盗んできたが、多項式が0と等しくなってしまった場合に配列外参照をしてしまうバグがあってREとなり、大変だった。適当に試したケースが当たらなかったらバグの原因は一生わからなかっただろう。

次にJ。500点は一瞬だが800点は全然わからない。多分速いんじゃないかと思って書いたコードは普通にTLEを食らってしまったので、部分点のまま放置。順位表を見る感じ解けそうな問題が全然ないが、気力を奮い立たせて問題を読んでいると、Hが解けた。操作をまとめると、隣接しない駒を選んでひっくり返したと見ることができて、値の最大化も含めてセグメント木に乗る。

コードゴルフはCをRubyで、DをPerlで。DのN=1のケースで空文字列をクエリにしない場合分けが難しい。

多点評価のハックケースをLibrary CheckerのGitHubにissueとして上げておいた。

github.com

またしばらくFHC Qual Cを考えていたが、結局解けずじまい。諦めることにした。

午後9時からABC216に出た。

AtCoder Beginner Contest 216 - AtCoder

7完。Eで詰まってペナが大変なことになったほか、Hが何一つわからなくてかなり衝撃的。

Aからやや面倒。最初どう実装したものか迷って、とりあえずsedで出した。BはRaku。CからC++。DはBFSっぽく操作可能なボールを管理する。Eは二分探索して落ち続けていたが、原因は、ちょうどボーダーとなるような値も使いながら計算していたからだった。ボーダーとなる値は最後にあまりとして使わなければならない。コンテスト時は結局stackを使い、値が大きいものから順にまとめて操作するように書き直した。FはAをソートして\maxとなるインデックスを固定すると、残りは部分和問題になる。Gはrでソートして大きいほうにできる限り詰めつつ構築したいが、これはsetで使っていないインデックスを管理すれば可能。

Gは牛ゲーらしい。なるほどという感じ。Hは解説を読んでいないが、LGV公式を使うらしい。それがわかっていてもまだACまでは遠い。

コードゴルフ。Aはdcになった。BはVimらしい。Cもdcだが、文字列を出力する代わりに12進数で適切な数字を出力するというのはなるほどなあ、という感じ。Dはakouryyさんのコードがとても上手くて唸らされた。各列を直接持っておいて、先頭要素を取りだしてみて1回目の出現だったら残りの列を保管、2回目だったら保管しておいた列と一緒に次に調べる列のqueueにpushする。縮む余地を発見したので縮めた。

Submission #25454127 - AtCoder Beginner Contest 216

EはRubyのコードをVimで書くやつ。似たようなコード片が何度か出てくるので、変なところで入力を中断して、直前に挿入モードで入力した文字列を再度入力するコマンドを多用すると短いらしい。FはとりあえずRuby。

今朝早く起きてしまったので眠気がちょっと怖いが、CF combinedに出た。

Dashboard - Deltix Round, Summer 2021 (open for everyone, rated, Div. 1 + Div. 2) - Codeforces

6完97位、2844→2823(-21)。Fにかなり時間をかけてしまった。

Aはよい。Bはどちらかのパリティの要素だけ抜き出して前から順に並べ、元の位置との距離の和を計算する。Cはかなり迷走したが、括弧を±1と読み替えて累積和を計算したとき、谷として複数回出る値「だけ」をstackで管理するとそれなりに簡単に書けた。そこだけが何回も答えにカウントされる可能性があって、それ以外は累積和の変化を見るだけでわかる。Dは3要素のbitwise and/or 6通りを書き並べてみると、元の要素3つが一意的に定まることがわかる。これを配列の先頭3要素で行い、あとはそれとほかの要素のbitwise and/orをそれぞれ計算することで、すべての値を復元することができる。

Eは数列aのみに対する操作に言い換えると、±1で均せばよいとわかる。これまた括弧列を思い出すようなチェックを行えばよい。具体的には、累積和が区間の左端と右端で一致していることと、累積和の区間minが左端の値未満になっていないこと。操作回数の最少は、括弧列でいえば最もネストした括弧の数、累積和においては区間maxから左端の値を引いたものであった。Fは「ある部分集合が強連結成分となる」ようなdpを考えて除原理。3^Nのループ内部で、固定した強連結成分とそれ以外の頂点の間の辺を向き付けて係数を計算するところがO(N^2)かかるが、必要なインデックスだけ先に抜き出しておいたら1secを切った。

今日は合計で10時間近くコンテストに出ていたらしい。夜中、眠気に耐えつつ日記を書いていた。来週からいよいよインターンだ。日記に書いてよいことと書いてはいけないことをしっかり区別するようにしたい。

週記（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が短かったが、RubyをVimから呼び出すコードに負けた。しかし何とか取り返すことに成功。空白を含めて9文字で順列を生成しても答えは変わらないが、実行時間はかなりギリギリだった。DはPerl。Eは手つかずで、FはRubyのbsearch。

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

Hの解説を読んで、自分の間違いに気づいた。上のようにキャベツの集合Sに対してf(S)を「Sに含まれるキャベツの個数」引く「Sからしか出荷できない注文の個数」と定義したとき、{\rm argmin}f(S)には複数の集合が含まれ得る。僕は、キャベツの集合TとUについて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も解説にある方針で、-1をA_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を満たすようなxを0\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を見て、解熱剤（カロナールがいいのか？）とゼリー飲料も買い込んでおくべきと判断している。

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

はじめに

この度院試に合格し、晴れて修士課程に進学できることになりました。日記の一部として、あるいは院試の体験記として、この記事を書きます。公開してはいけない情報が含まれている場合はこっそり教えてください。以下、院試の体験記として読む場合の注意点です。

  • 東北大学理学部数学科から進学する、いわゆる内部生の視点で書かれていること

  • 院試はコロナ禍の中で行われたため、例年とは異なる可能性があること

出願

7月中旬の5日間です。僕は調査票の内容、特に「読んだことのある数学専門書あるいは論文、興味を持った点」と「興味を持っている数学の定理・理論・問題」を書くのにかなり苦労したので、ある程度余裕を持っておいたほうがいいです。また、これらの内容は面接時に聞かれる可能性があります。周りの人に聞いた感じでは、数学科の4年ゼミで読んでいる本に関連した定理を書く人が多かったです。

僕は「『純粋関数型データ構造』に載っている計算量解析のテクニック」と「形式的冪級数の高速な計算アルゴリズム」についてを書きました。

そのほかの出願書類についても軽く触れておきます。まず写真は願書に貼るものと写真票に貼るものの2枚必要です。僕は襟付きの服を着た写真を証明写真機で撮りましたが、顔さえわかればいいはずなのでTシャツでもよいと思います。入学検定料はATMで振り込み、その時の利用明細書をコピーして添付しました。

院試に向けての勉強

4年ゼミで同じ本を読んでいる他2人と、違う分野の人1人の計4人で院試ゼミを作り、過去問を割り振って解答作成・発表を定期的に行っていました。過去問は公式ページから直近の5年分を手に入れることができます。それ以前の問題も結構出回っているので、知り合いを当たってみるといいでしょう。特に数学サークルには過去ウン十年分が保存されているそうです。ちなみに僕は持っていません。

過去の大学院入試問題 | 東北大学大学院理学研究科数学専攻

ゼミの細かな日程も記録しておきます。結局東北大学の過去問しか解きませんでした。選択問題については、各自解こうと思っている分野の問題をメインに担当していました。ゼミの4人は代数・代数・幾何・基礎論と結構バラバラで、その分いろんな問題の解答を見ることができてかなり良かったと思います。

日付 解いた問題
07/18 共通H29,H30
23 共通H31,R2
28 共通R3,H27,H28
08/01 共通H25,H26,H27
04 選択H31
07 選択R3
09 選択H30
12 選択R2
14 選択H26（模試形式）
17 選択いろいろ

そのほか、対面で集まった日に夜を徹して共通H21からH24までを解きました。英語の問題は他の人が解いた回答を読んで語彙を確認するくらいでした。

院試勉強についての所感ですが、共通問題はできるだけ解いておいたほうが安心、選択問題は過去5年ぶんで十分、英語は無視、という感じです。できるだけ共通を固めておくべきと院試説明会で先輩から言われていましたが、これには同意できます。1か月前から対策を始めたぶん、それなりに余裕をもって解き進められたかなと思っています。

試験1日目・筆記試験

持ち物は受験票と筆記用具と昼食（あるいは金銭）です。教室には時計がありませんが、先生が持ち込んでくださりました。不安な人は時計も持って行ったほうがいいでしょう。

共通問題と選択問題はPDFにして載せます。この2つはいずれ上にリンクを貼った公式ページで公開されるので、多分今載せても大丈夫だと信じています。英語の問題は載せません。

TohokuUniv_math_R4.pdf - Google ドライブ

（2021/09/08追記）共通問題と選択問題では解答用紙のほかに計算用紙も配られ、どちらも回収されます。解答用紙はB4サイズが解く問題数の枚数、計算用紙はA4サイズが2枚で、それぞれ二つ折りになっています。開いたときにB4またはA4サイズになるという意味です。表面上下に記名欄等少し文字が書いてあるほかはほとんど白紙で、両面使うことができます。ホッチキス止めはされていませんでした。特に紙が足りなくなるということはなかったと覚えています。

共通問題

午前9時半から正午までの2時間半で、一番長いです。時間的な余裕はそれほどありませんでした。

1問目

線形代数です。この問題は多くの人が解けていました。過去問では毎年対角化の計算が出題されていましたが、今年はありませんでした。広義固有空間の話はH30の問題でも出題されていました。

(1)(A-2I)vはAの固有値2に対する固有ベクトルなので、固有空間が\langle e_2,e_3\rangleであることを言えばよいです。僕は広義固有空間が\langle e_2,e_3,v\rangleであることとvが固有ベクトルでないことからわかると思っていますが、(A-2I)v\ne 0から固有空間が3次元でないことを言うほうが正しそうです。

(2)Aの元を全部変数でおいて3つの式を代入すればよいです。僕はAの固有値が2のみであることも用いましたが、必要ありませんでした。

2問目

位相です。この問題も簡単枠です。

(1)\bigsqcup_{b=0}^4 A_{1,b}=\mathbb{Z}であることから従います。

(2)x,y\in\mathbb{Z}に対して5^n\gt|x|+|y|となるようにnを取り、開近傍としてA_{n,x}とA_{n,y}を取れば交わらないことが示せます。

(3)連続です。特に開基の逆像が開集合になることを示せばよいですが、これはf^{-1}(x)=\{5x\}の場合とf^{-1}(x)=\{x,5x\}である場合に分けるとそれぞれ具体的な形が分かります。

3問目

難しいです。

(1)絶対収束は収束半径の議論から言えるし、普通に式を上から抑えてもよいです。f(x)と等しくなることは示せませんでしたが、テイラーの定理の剰余項を正確に見ればちゃんと0に収束するようです。

(2)負の2項定理として（競プロ界隈で）有名な式でしたが、示せませんでした。帰納法を少し考えた後、(1)を使ってみましたが、どちらも失敗しました。(1)を使って各点ごとに近傍を取って示す方法もあるようですが、maspyさんのブログにあるような帰納法が最も単純に見えます。左辺を微分するとちょうどnを1つ進めた形になることは気づいていましたが、それは帰納法を棄却した後でした……。

[多項式・形式的べき級数]（３）線形漸化式と形式的べき級数 | maspyのHP

(3)誰かが解けたという話を聞いていません。

2021/08/22追記：b2563125さんに解いていただきました。以下証明です。

g(x)の収束半径を考えると\limsup_{n\rightarrow\infty}\sqrt[n]{|a_n|}\le\frac 1 rが成り立ちます。ここで適当に0\lt r'\lt rなるr'を取ってくると、ある番号Nが存在して\sup_{n\ge N}\sqrt[n]{|a_n|}\lt\frac 1{r'}とできます。そこで定数CをC=\max\{1,\max_{1\le n\lt N}|a_n|r'^n\}と定めると、\forall n.|a_n|\le\frac C{r'^n}が成り立ちます。

べき級数は収束半径の中では何回でも項別微分可能ですが、この定数を用いると、任意のn\ge 0,-r\lt-r'\lt x\lt r'\lt rに対して|g^{(n)}(x)|=\left|\sum_{k=n}^\infty \frac{a_k k!}{(k-n)!}x^{k-n}\right|\le\sum_{k=n}^\infty\frac{C k!}{r'^k(k-n)!}|x|^{k-n}=\frac{C n!}{r'^n(1-\frac{|x|}{r'})^{n+1}}と評価できます。最後の等号は(2)式によります。

今J=(-\frac{r'}2,\frac{r'}2)\subset(-r,r)とすると、任意のn\ge 0とx\in Jに対して|g^{(n)}(x)|\le\frac{C n!}{r'^n(1-\frac{|x|}{r'})^{n+1}}\lt\frac{Cn!2^{n+1}}{r'^n}と評価できるため、A=2C、B=\frac 2{r'}と置くとA,B\gt 0かつ任意のn\gt 0に対して\sup_{x\in J}|g^{(n)}(x)|\le AB^n n!が成り立ちます。これが示したい式でした。

4問目

答えは出たはずだったのですが、ボロボロでした。

(1)ガウス積分です。\thetaの範囲を間違えかけました。

(2)何を示せばいいのかよくわかりませんでした。被積分関数のx\rightarrow\inftyでの一様収束性を示してお茶を濁したつもりでしたが、ほとんど関係はありません。聞いた話では、あるN以降の積分値を評価して\epsilonに収めればよかったらしいです。(3)で見るようにJ(t)=\frac t 2 I(t)という関係式が成り立つので、示すのはJ(t)の一様収束性だけでよさそうです。

(3)一様収束を示したのだから微分の極限と積分を交換してもいいだろう、と思って交換しましたが、してはいけない操作のようでした。これも聞いた話ですが、微分後の形と差を取って0に収束することを言う必要があったらしいです。被積分関数をtで微分した後は、部分積分でJ(t)=\frac t 2 I(t)を示して代入すれば求める式が出ます。

(4)微分方程式を解きます。(2)と(3)ができなくても解けます。被積分関数が常に正なのでI(t)\gt 0がわかり、(3)式の両辺をI(t)で割ることができ、さらに両辺をtで積分すれば求まります。僕は肝心かなめの積分で計算ミスしてしまい、非常に残念でした。

だいたい2完2半くらいでしょうか。聞いている感じでは周りの人もそのくらいのようでした。答案の回収・確認に30分くらいかかっていたので、昼休憩は午後0時半から午後1時15分まででした。学食が営業しているので、そこで昼食を摂りました。

選択問題

午後1時半から午後3時半までの2時間です。

2、4、8を解きました。数学基礎論を志望しているので8を選び、あとはその場で解けそうなものを決めました。といっても過去問では多様体と群・環を重点的に見ていたので、ある程度想定通りの選択です。今年は8問目が非常に簡単だったので誰にとっても得点源とはなり得ましたが、自分の志望と違う分野の問題ばかり解いていると面接で突っ込まれるそうですから、そのあたりも考慮して問題を選択するべきのようです。8問目がすぐに終わったので時間的には余裕がありました。

2問目

(3)が難しいです。

(1)Rの完全代表系としてa+bXを用いることができるため、それを2つ掛けて0にならないことを頑張って示せばよいです。

(2)Iより大きなイデアルを持ってきたとき、その元でIに入っていないものをa+b\overline{X}と取れて、このとき\overline{X}+1を使ってb-aもそうなることが言えます。今2がIに入っているので、b-aは奇数です。ユークリッドの互除法より整数k,lが存在して(b-a)k+2l=1となり、持ってきたイデアルには1が入っていること、つまりRであったことがわかります。あるいは同様の議論でR/Iが2元集合、つまり体であることを示してもよいです。

(3)より一般に、\mathbb{Z}\left\lbrack\sqrt{-5}\right\rbrackのような環を単項イデアルで割った環の位数は、イデアルを生成する元の（複素数としての）ノルムに等しいことが示せるらしいですが、それにはいくらかの準備が必要そうでした。単因子論を用いて示せるという話も聞きましたが、よくわかっていません。

(4)(3)を認めると簡単です。(2)の議論よりR/Iが2元集合であることが分かっていますが、それはa^2+5b^2の形で表せないため、Iは単項イデアルとはなりえません。

4問目

これも(3)が難しいです。

(1)普通のユークリッド空間でヤコビ行列を計算するだけです。座標近傍を定める必要がなくて助かりました。

(2)いつもの正則値定理です。今回はヤコビ行列のサイズが大きいので、ちょっと面倒でした。臨界点を求めるときは、形がきれいなので、小行列式を見るよりは3つの行が線形従属であることを示したほうが楽らしいです。

(3)同相になりそうだというのはちょっと計算するとわかりますが、何を示したらいいのかがよくわかりませんでした。そもそも正則値定理で得られた部分多様体に定まる位相を知らなかったのですが、実は一般に部分多様体に入る位相は元の多様体の双対位相に限られるらしいです。それを用いて位相空間としての同相を示せば十分のようで、試験後にいくらか議論した結果S^1\times S^1\rightarrow V;(\theta,\varphi)\mapsto( (\cos\theta,\sin\theta,0),(-\sin\varphi\sin\theta,\sin\varphi\cos\theta,\cos\varphi))が求める同相写像になりそうだとわかりました。連続性・単射性は形から言えて、全射性も三角関数の加法定理など使うと示せて、コンパクト空間からハウスドルフ空間への連続全単射なので逆も連続になります。

8問目

僕が過去問を見た限りでは最も簡単な問題だと思います。

(1)問題文に書いてある定義を確認すればよいです。

(2)背理法で示しました。ある集合とその補集合が両方F'に入ってしまいます。

(3)僕は両方の包含を示しましたが、実は(2)よりF\subseteq F_xだけ言えばよかったらしいです。

(4)これも背理法で示しました。

ということで1完2半、半といってもそこそこ解けているのでいい感じだったと思います。数学基礎論の問題があり得ないほど簡単だったので拍子抜けしていましたが、聞いた感じでは僕が解いた問題以外で1問目の(4)、6問目の(1)もかなり難しかったそうなので、全体としては難しめだったのでしょうか。

英語

午後4時から午後5時までの1時間の予定でしたが、選択問題の答案回収にこれまた時間がかかり、10分後ろにずれることになりました。

1問目

数学書の英文を読んで日本語に訳したり読解したりします。ほとんど受験英語で、そもそも文法が難しく感じられ、よくわかりませんでした。

2問目

数学に関係する短文を英訳します。数学用語の英語における表現を知らないと解けませんが、知っていたら普通に直訳するだけです。スペルミスをいくつかしましたが、おおむね書けたと思います。

試験後は合同C棟に移動し、明日の面接対策として今日の問題をみんなで議論しました。

試験2日目・面接

昨日の時点で面接の日程が発表されており、集合時間は人によってバラバラです。持ち物は特に必要ありません（受験票も使いませんでしたが、さすがに持っておいたほうがいいでしょう……）。服装は、僕はTシャツで行きましたが、分野によっては先生が厳しいらしく、スーツを着ている人がかなり多かったように見えました。僕と同じ教室で面接される人が結構いて、数学基礎論にそれだけ人が集まったのかと思いましたが、実際は解析の人が溢れていただけのようでした。

面接は、受験者が教卓に立って、面接官からの質問に（黒板を使いつつ）答えるという感じでした。今回はコロナ禍ということもあり、面接官の半分以上はZoom経由での参加でした。

面接前に収集していた情報としては、好きな定理とそのステートメントを聞かれるらしいこと、昨日の試験で解けなかった志望分野の問題について聞かれるらしいこと、がありましたが、結論から言えば、僕の面接ではそのどちらも聞かれませんでした。まず最初に昨日の試験についての感想を聞かれ、解いた問題それぞれについて上に書いたようなことを述べたら、それ以降はノータッチでした。

興味を持った専門書として『純粋関数型データ構造』を挙げたと上に書きましたが、それについて、純粋関数型言語における計算量解析と一般的なチューリングマシンにおける計算量解析がちょっと違うということを突っ込まれたので、正直に、適当に手元にある本を挙げたと答えました。

ほかには「データ構造を何か挙げてください」「グラフに関するアルゴリズムで知っているものはありますか」「素数判定が桁数の多項式時間で解けることを知っていますか」「PとNPの定義を言えますか」ということを聞かれたと記憶しています。ちなみにNPの定義は言えませんでした。

面接は10分程度で終了しました。これも人によってバラバラのようで、1時間近く出てこなかったという人や、何も質問が来ず一瞬で終わったという人もいました。

合格発表

面接の日の午後5時に掲示されるので、それまで数人と一緒に図書館にいました。午後5時になって数学棟の前に行くと紙が張り出されていて、ヌルっと合格していました。

まとめ

院試は、自分が受験者の中でどのような位置にいるのか、そもそも点数がどれだけ合否に影響するのかなど不安になる要素がたくさんありますが、実のところほとんど落ちないので、その事実だけを頼みにしていました。僕は何かしらの強制力がないと直前まで勉強しなかったと思うので、うまく院試勉強の仲間を見つけられたことが一番良かったことでした。

週記（2021/08/09-2021/08/15）

08/09(月)

先週日曜日の寝るまでの話。週記を投稿してから、再度院試の過去問に挑戦していた。問題が解けると楽しいので、今はかなり過去問演習のモチベがある。これも院試ゼミのおかげだ。1・2年の頃の知識をみんなで復習することで、着実に解けるようになっている。もしくは最近数学をしなさすぎていたのがさび落としされてきたのかもしれない。

と言っておいて先に手を付けた問題は結局解けなかったが、もう1問数学基礎論の問題を読んで、そちらは解けた。超限帰納法を使った。初対面だ。名前だけは聞いていたが、この度ようやくステートメントを調べた。

布団に移動してしばらくスマホと戯れ、午前11時就寝。

院試ゼミは午後3時からなので、その時間と30分前とに目覚ましをかけていたが、どちらも寝過ごしてしまった。思ったより疲れがたまっていたのだろう。午後3時ちょっと過ぎ、LINE通話がかかってきて、それで起きた。他にもLINEやSlackでメッセージが来ており、みんなありがとう……という気持ちになった。急いでZoomにつなぐ。

今回も有意義だった。多様体については曖昧な理解しか持ち合わせていないが、自分の持っている感触を他の人に伝えてみることで、自分の中でも整理されるし、もし間違いがあれば指摘される機会も得られる。全員間違っていたらみんなで落ちるしかない。また、昨日の朝方解けなかった問題は微分方程式に関する話だったが、アスコリ＝アルツェラの定理を用いるようで、かなり懐かしい気持ちになった。もはやステートメントどころかその周辺の言葉の定義も忘れ去ってしまっていた。数年に1度しか出ない分野のようだが、今やっておいて損はなかっただろう。

担当する問題以外にも発表し、その関係で話が弾んで、院試ゼミが終了したのは午後6時半だった。選択問題にも太刀打ちできるようになってきたことで、だんだん自信がついてきた。あと10日、精一杯頑張っていきたい。

そのあと夜までコードゴルフをしていた。一気に何個か取られてしまったので、いくつかを無理やり取り返した。dcをbashから呼び出すコードのはずが、Vimから呼び出したほうが1B短くなるような問題もあり、自分でもそこまでするか……という気持ちになった。この辺りは複数の言語が入り乱れており、縮めていてかなり辟易している。しかし1Bでも短くなるのならそれが絶対的な正義である。

Submission #24916483 - AtCoder Beginner Contest 210

次回の院試ゼミで担当することになった問題を解いた。また数学基礎論。見た目はゴツいが、手を動かしたらあっさり解けた。全能感が湧いてきたが、これまで見た過去問で解けない数学基礎論の問題というのはやはり存在するので、本番ではちゃんと問題の難易度を推し量る必要がある。

いつだかの問題文1行コンテストはまだupsolveし切れていなかったので、2問ほど解いておいた。

No.1619 Coccinellidae - yukicoder

かなり嫌な気持ちになっていたが、実装してみると案外楽だった。数列の総和に関しては最大の要素に適当に足しておけば達成できるので、転倒数のみ気を付ければよい。0\dots N-1を用意して、数列の先頭から構築していくのだが、このとき「使っていない要素のうち最大・最小のもの」しか考えなくてよい。こうすると、0\le i\lt N番目に未使用かつ最大の要素を入れると転倒数をN-i-1増やすことができ、最小の要素を入れると変わらないことが言えるので、達成可能な任意の転倒数が先頭からの貪欲で構成できることがわかる。

No.1620 Substring Sum - yukicoder

自明。

やることがないなあと思いながらTLを見たら、どうやらコンテスト直前らしい。CF #737 div.2を完全に忘れていた。仕方ないのでextra registration。

Dashboard - Codeforces Round #737 (Div. 2) - Codeforces

全完12位。Eをあきらめなかったのが偉い。

Aからよくわからない。なんとなく、正の数があるならその中で最大の要素を1つ独立させるとよさそうな気はする。ここでサンプルを見ると、負の数しかなくても最大の要素を1つ独立させているので、これが答えだろうと思って実装した。落ちたらその時はその時だと思って投げた。Bは、もともと連続している部分を壊さないように分割したらいくつになるかを考える。

Cは上の桁から決める。今見ている桁より上の桁で大小関係が決定しない決め方tを持っておいて、今見ている桁でbitwise andが1になる場合と0になる場合を考える。nが偶数のときは、bitwise andが1になるときbitwise xorは0になるため、大小関係が決定する。bitwise xorが0になる場合はほかに2^{n-1}-1通りあり、それらはこの桁で大小関係が決定しないため、次に回す（tにかける）。nが奇数の時は、大小関係は決定できず、次の桁に2^{n-1}+1通り回すことになる。あとは、すでに決まった数列の新しい桁のために答えに2^n通りかけたりもしておく必要がある。ちょっとややこしいが、サンプルを合わせて投げたらすんなり通った。

Dは遅延セグメント木。適当に書いてからサンプルを試していたら、復元が要求されていてびっくりした。その時書いていたことも全然違っていたので、修正にかなり手間取った。遅延セグメント木には、残せる行数とそれを達成するときの一番下の行を保存する。各行ごと、その行とそれ以前で残せる最大の行数を遅延セグメント木で計算し、直前にくる行を保存して、今の行と残せる行数を組にして遅延セグメント木を区間更新する。復元は保存しておいた行番号をたどる。遅延セグメント木は区間chmaxしているように見えるが、実のところ対象となるノードすべてより大きな値で更新しているので、区間更新で書ける。

Eは全然わからず、考えていたら途中椅子の上で意識を飛ばしていた。キングがいる可能性のあるマスは、減ることはあっても増えることはない。よって、確実に減らしていくことを考える。クイーンから縦横1マスずつ離れたマスにキングを捉えたときに減らせる可能性があるようだ。逃げる方向は限られるため、それを追って壁際まで行くことで可能性が消せる。標的にするマスを選んで消えるまで追い続けるのを繰り返したら通った。

またしばらくコードゴルフをした後、人の日記を読んだり、書いたりした。

朝方布団に移動して、読み止しのラノベの続きを少し読む。少し読むつもりだったがあまりに面白かったため、そのまま読了してしまった。「サイレント・ウィッチ」。Web版で一度完結まで読んだが、書籍化したので購入したもの。書籍もかなり売れているようで、手に入れたのが遅かったこともあり、すでに第2版であった。

非常に面白かった。オチまで全部知った状態で改めて読み返すと、いろいろと発見（書籍化に際しての加筆かもしれないが）があってよかった。細々とした描写が小気味よく、ちょっと笑える感じで書かれているのも好み。つまりは文章が好きであるということ。あとがきにも書かれていたことだが、なろうでは200話以上かけて一つながりの物語となっていたわけで、その最初の数十話（調べたら30話未満）を取り出して1冊の本に仕立て上げるというのはかなり難題のように見える。しかし加筆修正によってちゃんとラストの盛り上がりも含めまとまっていて、感動した。改めてWeb版を読んでみると結構大胆な修正があったようだが、まあ細かい流れは大体忘れてしまっているので特に違和感はなかった。

本を読んでいたら今日もまた昼前になってしまった。明日は院試がオンラインになった場合に備えて接続テストが行われるので、午後2時には起きている必要があるらしい。徹夜することもちょっと考えたが、結構眠気があるので急いで寝ることにした。午前9時半だった。

08/10(火)

午後2時過ぎに起床。目覚ましが鳴ってからも少し眠っていたらしく、焦る。まずメールで連絡が来るらしいので、スマホでチェックしたところ、どうやら接続テストは指定された時間帯にZoomに接続してメールを1本送信するだけの形式らしかった。拍子抜け。

しかして午後4時までにメールを送信する必要がある。眠気をぐっとこらえて一旦パソコンに向かい、パパッと所定の操作を済ませ、またすぐ布団に戻った。ちょっとスマホを触ってから再度就寝、次に起きたのは午後8時だった。

まだ微妙に眠気があって何もする気が起きない。布団に倒れたままスマホを弄っていたが、空腹により起床。食事してパソコンに向かい、また動画など見てしまうが、さすがに思い直して院試の過去問を少しばかり解いた。

それなりに問題を解けるようになってはいるが、実をいうと手が出ない問題と半々くらい。幸いにして8問中3問選択して解く形式なので何とかなりそうではあるが、難易度がバラバラでちゃんと分野を選定する必要があり、最悪の場合は……最悪の状態になってしまう可能性を否定できない。問題文に登場する単語の定義もところどころ危ない。今日は2問くらい解いた。

昨日のCF div.2 Aの証明を解説を見て確認したが、やはり難しい。数列を2つの（連続するとは限らない）部分列に分割したとき、それぞれの平均の和を最大化せよという問題で、解法は上でも述べたように、最大の要素を1つだけ独立させることになる。解説の方針を真似る感じで自分なりに証明をつけてみた。

まず、分割する要素数を固定したときを考える。この時、要素に適当に係数を割り振って足し合わせると言い換えることができて、ソートして先頭と末尾で分割するのが最も良いとわかる。次に、値が小さい方の数列から大きい数列に要素を移動させても損しかしないことを示す。この操作で2つの数列の平均値がどちらも小さくなる（または変わらない）ことが言えて、具体的には値が小さいほうの数列は平均値「以上」の要素が抜けるのだから当然平均値は小さくなり、大きいほうの数列は逆に平均値「以下」の要素が加わって小さくなる。この2つをまとめて、解法の正当性がわかった。

今日も本を読む。「幼女戦記」8巻。記録によれば7巻を読んだのが2020年1月で、そのとき8巻を100ページ弱読みかけていた。栞にしていた紙が挟んであったので、今日はそこから読み始める。結構衝撃的な展開の箇所だったので、何とかそのシーンのことは覚えていた。

午前1時から読み始めて、読み終わったのが午前7時。1ページ1分ちょっとという計算になる。出現する語彙に馴染みのないものが多く、かなり読むのに疲れた。そもそも意味を知らない語彙もあり、調べる手間もあった。内容も、作者が軍隊行動に関する話を入念に描きたがっている感じがして、安直にチート戦闘を求めていると息切れしてしまう。実際これまで何度も息切れした結果が、読み止しにしたまま1年以上放置するというこの有様に繋がっているわけだ。それでも定期的に読みたくなるのだから、間違いなく面白さはある。多分、アニメを観る習慣のある人はアニメで観たほうがいいのだろう。

第7回PASTの解き残しを埋めた。KLNOが残っていた。最終問題に近いのでどれも大変だと思っていたものの、個人的には前にコードゴルフのために解いておいたM問題が最も難しかった。

第七回 アルゴリズム実技検定 - AtCoder

Kはいつもの。Lは何をやってもできる気がする。僕は最小値をセグメント木で、値に対するインデックス集合をmap<int,set<int>>で持った。公式解説の方法は頭が良い。NはABC211Fで見た。Oは区間chminになるようだったのでbeatsを探しそうになったが、冷静になってもうちょっと考えると必要なかった。セグメント木上を左から右へ走査しつつ、今見ている要素から右にいくらかの範囲に対しchminし、取得は単一の要素のみとなるため、優先度付きキューで書ける。

布団に移動してからしばらく、本棚から久しぶりに掘り返したラノベを読む。積読本を綺麗に詰めすぎたため、表紙が見えず本棚のどこに何があるかわからない。今日取り出すときも難しかった。目的の本の列のすぐ上に別の本をもう1列乗せていたため、抜き出した穴をそのままにするわけにもいかず、別の本を見繕って当てはめる作業も発生した。

適当なところで切り上げて寝ようとしたが、眠れず、延々スマホを触り続けていた。途中頭皮のかゆみが気になりシャワーを浴びたりもして、午後2時くらいに寝落ちした。

08/11(水)

午後8時半起床。またラノベを読み続ける。日付が変わるあたりで読了。

「異世界管理人・久藤幸太郎」。設定とストーリーが面白かった。扉を開けると異世界につながるアパートが存在し、主人公は1部屋1国家が入居するそこの管理人、つまり国家間の問題を解決する役割を担っている。そのために特別に与えられた権能や持ち前の特技を生かして活躍する、という話。主人公がかなり有能らしく、読んでいて心地よかった。一方ヒロインはある国家のお姫様だが、悪意を知らない底抜けのお人好しで、能力的には外交を担えるものではないとされている。結局このお人好しという設定もストーリーに絡んでくるのだが、それ以外で考えなしに勝手なことをしたり、人を疑うことを知らなかったりという描写が読んでいてちょっと気に障った。

少しコードゴルフをした後、AOJ-ICPCから1問解いた。

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=5774311#1

よくわからないが、たぶん3つの要素それぞれについて考えてもよいだろう。期待値の線形性というやつらしいが、特に意識せず勝手に分割した。自分がアピールする回数を決め打ったとき、ある人が自分以上のポイントを獲得する確率が計算できる。適切な前計算をしておけばよいが、値が大きくなるのでlong doubleが必要らしい。とにかく、それを全員分集めて、自分が3位以上・または最下位である場合の確率を求めることができる。あとは特に工夫せず、アピール回数の割り振りを全探索できる。

別の問題を考えていたら椅子の上で意識を飛ばしてしまったので、すぐ布団に移動。今日は早めに寝られそうだとホクホクしていたものの、なんとなくスマホを触ってしまい全然眠れない。仕方なくいったん寝るのを諦め、ラノベを読んでしばらく過ごすことにした。午前8時くらい、さすがに寝なければまずいという気持ちになったので、頑張って就寝。

08/12(木)

午後2時起床。非常に眠い。今日は午後3時から院試ゼミで、それまでにお盆休み前最後の大学生協に行きたいと思っていた。今日は雨が降りそうなので徒歩で大学に向かうが、シャワーを浴びていたら結構ギリギリの時間になった。

購買しか開いていないが、そこで買い物をする。これから数日休みということで、菓子パンが20%オフになっていて喜ばしかった。コンビニにも寄って帰宅。結局院試ゼミには少し遅れてしまった。

午後7時前までゼミ。今回もいい感じ。解答を3問分くらい用意してあって、2つを発表し、1つは他の人の発表を聞いてところどころ自分の方針を喋ったりしていた。本番で選択する分野も大体見当はついたかな、という感じ。ちょっと古い過去問のほうを見ると、それでも手も足も出ない問題が散見され、自分の狙っている分野に難しい問題が出題されたらまずいな……と思うものの、ここ5年分の問題に限ればそれなりに健闘できそうなので、院試が易化しているのではないかと思っている。

このゼミも残り2回の予定らしい。両方の日程と内容を決め、解散。すでに午後7時だが、せっかくシャワーを浴びて着替えてあるので、遊びに行くことにした。霧雨が降っているので、地下鉄に乗って仙台駅まで出た。本屋で本を買い、つけ麺屋でつけ麺を食べ、ゲーセンに到着。

今日の成果は微妙だが、新曲の13でAJが出たのはよかった。曲が良い。譜面動画を見ながらエアプしている段階では、序盤、なぜかうまく腕が動かせなかったが、実際にプレイするとそこそこゴリ押せた。逆に「アポカリプスに反逆の焔を焚べろ」は全然ダメ。譜面動画や人の手元動画を見ていたのより、自分でプレイしてみると100倍速かった。何をどうしたら間に合うのかわからない。ただの鍵盤としても普通に難しいのに、超高速にされるともう手も足も出なかった。

閉店までいて、帰宅。なんとなく地下鉄を使わずに歩いて帰ることにした。帰宅してシャワーを浴び、AOJ-ICPCから1問解いた。

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=5778119#1

面白い。bit演算・値を大きくするゲーム・木など、いかにも上位桁から分解してくださいねという形をしているのに、実はそうではない。考慮すべき値が8種類しかないことを利用して、それらの間の大小関係を全探索してそれぞれ前計算し、先に計算した結果を参照してクエリに答える。最近取り組んだ問題の中では一番、解法を思いついたときに爽快感があった。

ラノベを1冊読んだ。「異世界管理人・久藤幸太郎」2巻。前巻と似たような感想だが、今巻は敵役がかなりあくどい感じで、その分ラストシーンは爽快だった。シリーズはこの巻で打ち切りのようだが、それにしてはかなり面白かったと思う。ラストシーンでおめおめと逃げおおせたキャラがいるのも、後の伏線になるはずだったのに……と悲しい気分になった。

AOJ-ICPCからまた1問解いた。

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2690

簡単。各頂点から一番遠い頂点にデータを送信して、次にそのキャッシュが残っている状態で一番遠い頂点にデータを送信して……ということをやりたい。このとき、一番遠い頂点を求めるdfsの最中に候補から抜け落ちた頂点については、抜け落ちた時点でのパスの長さが後々のキャッシュも含めた最短距離となるので、それを保存しておけばよい。これを各頂点から行って、最後に全部まとめてソートして貪欲。

布団に入ってしばらくラノベを読み、午前11時に就寝。

08/13(金)

午後7時半起床。今日は何もないのでのんびり起きた。最近予定が多く、そのくせ朝方まで起きているのが常になってしまい、睡眠が足りない。

起きたら部屋がかなり寒く、薄いブランケットに必死にくるまっていた。夜寝る前、この天気だとエアコンは必要ないなと思って消し、念のための暑さ対策に部屋とキッチンを隔てる戸を開いて寝たが、これがよくなかったらしい。キッチンのほうから冷気が部屋に入ってきたのはいいが、今はむしろ寒い。

食事をしてyukicoderのコンテストに出た。滑り込み全完。

yukicoder contest 309 - yukicoder

ABCはよい。Dはありうる和とそれに対する場合の数をdpで計算すればよい。Eは後ろ2文字を持つdp。'?'の場合の遷移については総和を取り、適切に引くことで262回の演算で計算できる。Fは各行各列に対応する超頂点を作り、辺を張った上で閉路を探したら通った。僕は観光名所も頂点として持ったが、超頂点同士を直接結ぶ辺だと思ったほうが解法の正当性がわかりやすい。

solvedが多いのでHに行った。適当に分解すると、x座標とy座標が両方絡む項が問題になる。自分の左下または右上にある点に対しては大小関係が定まるので簡単に求まるが、ここですべての点のy座標を符号反転することを考えると、もう一度同様の計算を繰り返すことで全点対に対して計算できることがわかる。y座標が同じだと2回計算されるが、値が0になるため問題なし。

Gに挑戦する。まずB=0の場合はA^N=PかつA^{N-1}=Qとなるため、BSGSで求まる。それ以外の場合が問題だが、制約より答えが1010以下であることがわかるので、こちらもBSGSと同様のことができそうだ。modintには大小比較が定義されないのでいちいちint型に戻し、それの2つ組をテーブルに持ったり掛ける数を行列に直したりしつつBSGSのコードを写す。最後答えを合わせるのに手間取ったが、定数を足してサンプル1を無理やり合わせて提出したら全ケース通ってびっくりした。後でちゃんと計算したところ、答えより2小さい値が出るはずが思い違いで出た値から2を引いていたということをちゃんと確認できた。

Gは非常に面白かったが、「1010以下に答えが必ず存在する」というような謎の制約が必須になってしまうところが難点か。例えば法を取る素数を100003とかにすると、2つ組にしても周期の最大値が1010ちょっとになるので、同様のことができるかもしれない。これくらいの制約だとdpもできない中、BSGSが使えるというのはかなり目新しく感じた。

ラノベを1冊読んだ。「前世は剣帝。今生クズ王子」。面白くなかった。クズ王子と呼ばれる王子が、実は前世では最強の剣士だった……という設定に惹かれて買った。実力を隠す系の話だと思ったのだ。読んでみると、主人公がグータラしているのは、前世での苦い経験からそれが一番幸福だと信じていたかららしい。それならそれでよくて、最強たる実力を遺憾なく発揮しているシーンもあったのだが、合間合間で執拗なまでに主人公の自分語りが入って、冷めた目で見てしまった。

「慫慂」という語彙が話題になっていた。鉄道関連ではよく使われる言葉、というツイートも目にしたような気がするが、調べた感じそれほど用例が多いわけでもなさそう。自分にとっては記憶に新しい語彙だ。なんとなれば、火曜日に読んだ幼女戦記8巻で出てきたからだ。履歴からどの時間にGoogle検索で単語を調べたか割り出し、その周辺で調べた単語が出現したシーンを探して具体的なページを見つけた。

C++の演算子優先順位は?:（三項演算子）が代入演算子より上だと思っていたのだが、それはC言語における話で、C++では同じらしい。自分がこれまで見ていた資料が違っていることを知った。コードゴルフに使えるかと思ったが、パッと探した限りはなさそう。

もう1冊ラノベを読んだ。「鳩子さんとラブコメ」。主人公が財閥の跡継ぎ候補という設定に惹かれていたが、読んでみるとタイトルに偽りなく、主にラブコメだった。9年以上前のラノベで、今では全然見ないような、主人公が語り手の立場でひたすら一人語りしている文体が逆に目新しい。シリーズは4巻まであるので、とりあえず読みはするが、興味はかなり薄れている。

ABC210-Fを人に説明する機会があった。グラフの圧縮については公式解説を読んでほしいと言ってぶん投げたが、実は自分も解説のやり方はよくわかっていない。向こうもさすがに無理があったようなので、グラフ圧縮に絞って一目で説明しているtatyamさんのツイートを教えたが、そちらもうまく伝わらなかった。最後に自分で図を描いてみたところ、一発で伝わったらしく、感動。苦労した甲斐があったものだ。

開いた問題の制約のところに「グラフは平面的とは限らない」と書いてあり、なぜ当たり前のことを注釈しているのか……と思ったが、どうやらストーリーで街と道を使ったかららしい。面白い着眼点だ。そのようなclarが飛んだことがあるのだろうか。

布団に移動してラノベを読んだりなろうを読んだりしていたら、午前10時を回ってしまった。明日は午後1時半から院試ゼミの予定だ。非常にまずい。祈りながら就寝。

08/14(土)

午後1時半の目覚ましで起床。無理やり布団から這い出してZoomに接続する。ちょっとだけ待たせてしまったようだ。今日はこれから時間を計って院試の過去問を解く。制限時間は2時間だ。

選ばれた年の問題は難しく感じた。数学基礎論の問題が解けそうだったので真っ先に手を付けたが、最後の小問の反例構築はすぐ思いつけたのに、その前の証明の記述に時間を取られ、1時間半もかかってしまった。あんまり直感的でないことを証明させられたので、簡単な方針がないかしばらく探していたり、丁寧に確認しながら場合分けしていたら時間を食ったらしい。残り時間でもう1つ大問を選び、そちらは位数が9の群に対して何かを計算する問題だったので、愚直に全通り計算して求めた。

本来は3問解かなければならない。残り時間、小問を少しだけ解き進められる問題が2つ見つかって、解答を書かずに詰まっている小問を考えながらシャワーを浴びたりしていたら、試験時間が終了してしまった。

みんなの解答を互いに見ながら質問を飛ばしたりする。全通り計算した問題は、計算こそ合っていたものの、勘違いで答えが少し違ってしまった。数学基礎論の問題について、最後の小問の構築は、今日はすんなり思いつけたが、普段は結構時間を使って考えているので、本番でこの分野に特攻するのは少し危険だなと思った。

他の年の問題を見つつ、しばらくみんなで話す。「実数全体に通常の大小関係を入れた全順序集合」から「有理数全体のべき集合に包含関係を入れた半順序集合」への順序埋め込みがあることを示せという問題があった。実数を2進数展開する方針で構築しようとしたが、できない。しばらく別の問題を見ていて、ふとデデキント切断を用いる方法を思いついた。つまり、実数rに対して\{q\in\mathbb{Q}\mid q\lt r\}\in\mathfrak{P}(\mathbb{Q})を対応させると、実は順序埋め込みになっている。しかしこの直感との合わなさと言ったら！そもそも2つの濃度が等しいことすら素直には頷かれない。後から知ったことだが、この構成はWikipediaに載っていた。

連続体濃度 - Wikipedia

次回は8/17(火)で、これが院試前最後のゼミとなる予定だ。事前に担当を決めず、各自好きな問題を解いてくる形式。最後までやり切りたい。

ゼミが終わってから、食事したり、洗濯物を干したりした。睡眠時間が明らかに足りておらず、非常に眠い。なろうを読んだりして何とか寝ないようにし、ABC214の時間を待って、出た。

AtCoder Beginner Contest 214 - AtCoder

6完遅解き。Eでめちゃくちゃに詰まって何もかもが崩壊した。

AはとりあえずAWK。BもAWKで書こうとしたが、何となくTLEを気にしてRuby。Cはdijkstra。Dはパスの重みの総和だと思って一回コードを書き、全部消して逆から見るUFを書き直した。問題文をちゃんと読んでいなかった。

Eは非常に迷走した。区間スケジューリングのような貪欲がうまくいかないケースはすぐに作れたので、判定問題を解くことを意識する。区間の掃き出し法みたいなことをすればよいのでは？と思ったが、これは区間の微妙なずれを認識できないため、必死に実装したもののWAだった。次に、ある区間であって、その中に入れるべきボールの個数が区間の幅より多いものを探す。このようなものが存在することと答えがNoであることは同値に見える（実際にはHallの結婚定理から言える）。実装については、探す区間の左端を固定して、右端を動かして行ったときに「含む区間の個数」引く「区間の幅」の累積最大値を求め、これが正になるような点が存在するかを二分探索した（実は一番右端を見ればよい）。ACできたが、すでに54分が経過しており、絶望。

Fは焦って5WAも出した。同じ文字が出現する直前の位置から今までの総和でdpを更新すればよいが、その直前の位置の1つ手前の値も足さなければならないことにずっと気づいていなかった。ずっと同じ文字が2連続する場合だけ処理していた。ACして残り20分、Gを読んで書こうとしたが、3乗のdpに見えてしまい詰め切れず終了。

コードゴルフをする。Aは40引いて86で割るのがよい。テストケースハックで縮みそうな気もするが、ちゃんとギリギリのケースが全部入っていて、単純な四則演算を誤魔化すのは難しい。BはAWKで3重ループ圧縮を頑張る。結局1重まで詰め込めた。CはとりあえずPerl。DもPerlで、連結成分を全部管理してuniteをマージテクでやるやつ。Eは手つかず、Fはちゃんと詰めると各文字に対する値を保存する配列と変数2個で書けて、Rubyならmodを取らずに計算できるが配列を記述するのが長く、その隙をついてPerlが現在最短。

Gを解く。コンテスト中に考えたことは、p_iとq_iを結んだグラフを作り、各連結成分（ループになる）ごとに違反するインデックスの個数を決めたときの場合の数を求めるもの。これが求まったら、全部畳み込んでから包除原理すればよい。連続した違反するインデックスを一気に遷移しないと遷移の係数が計算できないと思っていたが、実はループを切り開いた時の最初の値を使ったか・直前の値を使ったかの4通りを持っておけばインデックスを1つずつ処理することができて、2乗のdpになる。結構面倒だが結構すんなり答えが合って通った。ちゃんと落ち着いていたら20分でもチャンスがあったかもしれないものを……。

Hを解こうとしたが気力が切れ、少しTLを見てしまった。すると、うっかりフローの文字列が目に入ってしまう。ここでHがフローで解けることに気づいてしまった。このようなことがないようにTLを見ないようにしていたのに……。実際には、まずSCCしてループを消し、次に負辺ありの最小費用流を解くためのポテンシャル前計算をベルマン・フォードからDAG上のdpに書き直す必要があったのでちょっと面倒だが、一番難しいのはフローであると気づくところだろう。そこをスキップしてしまい、残念。

AはFAだったらしい。Hは今回も辺の重みをいじって負辺を消す方法があるらしく、なるほどなあという気持ちになった。

朝方、ラノベを1冊読了した。「鳩子さんとラブコメ」2巻。適当に読んでしまったため話の内容をあんまり覚えておらず、特に感想はない。

午前6時就寝。

08/15(日)

午後1時くらいに少し起きていた記憶もあるが、またすぐ寝たのだった。午後8時起床。しばらく布団でうだうだして、1時間くらいかけて布団から出た。

院試の過去問を解いていたが、夜中のCF #738 div.2に出た。

Dashboard - Codeforces Round #738 (Div. 2) - Codeforces

D2が解けなかった。

Aは全要素を全部のbitwise andにできて、これが最小。Bは'B'と'R'の交互で間をつなぐ。'?'が端にある場合や、そもそも全部'?'である場合に注意するべきだが、そのようなケースはすべてサンプルにある。Cは適切に場合分けすると必ず構築可能だとわかる。基本的にiからi+1への辺を順に通っていく。N+1から1に向かって辺が出ている場合は、最初にその辺を通ればよい。そうでない場合はどこかで一旦N+1を挟むか、あるいは最後にN+1に行けばよい。D1は、張れる辺を貪欲に張ってもよさそう（反例を構築できなかった）なため、全探索。Eはgcdが1\le g\le mの倍数となるような列の場合の数を全部計算してから包除原理（除原理？）を行う。計算は累積和dpを用いてO\left(\frac{Nm}{g}\right)くらいでできるため、全体でO(Nm\log m)となる。

D2のコーディングを頑張っていたが、間に合わなかった。後から出したら通った。それぞれのUFを見て最も大きな連結成分Uを取り、取ったほうのUFをA、他方をBとおく。v\not\in Uを見たとき、Bでvと非連結なu\in Uを探したいが、これはBにおける連結成分の代表点とその連結成分に含まれるw\in Uをmapで持っておけば可能。繋げることに成功したらmapとU自体を更新してまた先に進み、これを何回も繰り返して更新がなくなったら、Uの頂点を以降無視することにしてまた最初から始める。計算量解析はできていないが、Uは毎回そこそこ大きくなってくれるだろうという読み。249msで通っている。

TLで似たような解法を目にしたが、実は上のループは1回でよかったらしい。ある連結成分とどのようにしても結べなかった連結成分は、他方の森で1つの連結成分となり、選ぶ連結成分を変えたところでどうしようもない。

D2は乱択で通した人が多いようだが、非乱択解で非常に頭が良いものがあった。天才すぎる。

シャワーを浴びて着替える。最近やたらと寒いので、長そでのパジャマを着てみることにした。

院試の問題を解き進める。やはり難しい。多様体の分野で曲率が出題されることもあるようだ。今のところ、簡単なヤコビ行列を計算したり正則値定理を用いたりする程度の能力しかないので、曲率という文字が見えた瞬間逃亡していたのだが、さすがにまずいだろうということで教科書を読んで何とか頑張る。2つ見つけてきた問題のうち一方は教科書と似たような導入だったため解けたが、もう一方は全然違うため、どうしたらいいかわからない。最初の小問から手が出なくて、絶望的。

少し年代をさかのぼると、数学基礎論の問題も解けなくてかなりつらい。願わくば、これが易化傾向を表していて、かつ今年も簡単になりますように。昼前まで院試の問題を解いていたが、週記の投稿のため溜めていたぶんの日記を書いた。投稿して1週間の区切りとするものの、今日は夕方くらいまで起きておいて、試験に向けて生活リズムを整えたい。整えるといっても1周回す方向で、だ。

週記（2021/08/02-2021/08/08）

08/02(月)

先週は週記を投稿した後、すぐに布団に入ってしばらくラノベを読んでから寝た。午前7時半だった。

午後5時半くらいにすこし目を覚まし、起きようか悩んだが、もうちょっと眠れそうだったのでそのまま横になっていた。再度起きたのは午後9時になってからだった。

起きて食事をする。今日はTCO21 Regionalの開会式で、聞くところによれば参加しないとTシャツがもらえないらしい？とりあえず入ってだけおくが、人の話を聞く気もあまりない。午後9時半からのはずだったのに、直前に15分前倒しされており、早速ワクワクという感じがする。

先週の週記で、HIKAKIN TVに投稿された「ウ”ィ”エ” ヒカキンVer.」について触れた。そのメイキング動画が公開されていた。すごい熱量だ……。ほとんど同じ動きをしている8人の映像はコピーして重ね合わせたのではなく、8人それぞれで撮影していたというのを知り、ヒカキンの本気を感じた。動画1本（+メイキング）を作るために撮影チームを動員するのもすごい。どういう伝手で人を集めたのだろう、ただ金に飽かせただけではない、まさにYouTuber界の王の面目躍如といった様相だ。

youtu.be

ラノベを1冊読んだ。「グッバイ現実世界」。作者がVTuberということが帯に書かれているが、購入の決め手は普段と変わらずあらすじや表紙イラストによるものだった。実際に読んでみた感想だが、あまり面白くなかった……。

プログラムを書くことで様々な現象を起こせるVR空間が舞台で、主人公はプログラミングにおける発想だったり単純な技術力が優れていることから強いとされていた。主人公が強い話は好みだったが、こういう設定でさらに実際のプログラムも文章中に現れると、プログラマの端くれとしてはそちらに気を取られてしまう。一方、作中のプログラミング言語は文法こそ既存のものと似ているが、予約語や変数名に英語以外の言語が使われており、読んでも意味が分からない。文法だけ見ればループ処理すらない普通のコードを書いていそうなのに、何をやっているかちっともわからないというのは結構ストレスだった。

と、まあここまで作中のプログラミング言語についてしか書いていないわけだが、ストーリーとしても特に印象に残る部分はなかった感じ。

数学基礎論特選のレポートを書く。これまで3回レポートを提出してきて、これが最後になる。前回TeXでレポートを作成した。今回もそのつもりだが、さらにOverleafというサイトを利用することにした。リアルタイムでコンパイル後の文書を見つつ書けるらしく、それは当然便利だろうという感じ。まずjsarticleを使うために少し設定する必要があって、あとは普段と全く同じ感じで書ける。TeX用エディタなのでオートインデントだったり、\beginに対応する\endが自動で挿入されたりとかなり便利。

5時間くらいかけて3回分の講義資料を確認し、いつものように途中の問題を5問選んで解いた。与えられた論理パズルについて「共有知識」の定義を参考にしつつ論じよという問題があった。何か適当なモデルを用意するのかと思ったがどういう感じになるかちっともわからないので、飛ばそうとしたものの、講義資料をよく見ると他に解ける問題があまりなさそうだったので、渋々これを選び、適当に日本語で書いておいた。

出題された論理パズルはこれだ：「3人の死刑囚がいる。3つの青い帽子と2つの赤い帽子が用意され、看守が3人にランダムにかぶせた。自分以外の死刑囚がかぶる帽子は見えている。自分の帽子が青いと確信したならば逃げてよいが、このとき実際にかぶっている帽子が赤かったら射殺される。しばらくして、3人の死刑囚は一斉に逃げ出した。なぜ3人は自分の帽子が青いと確信できたか？」……めちゃくちゃ見覚えがある。レポートを書いた後に調べたら普通に有名問題だった。ここに書いても著作権などの問題は発生しないだろう。

水曜日の院試ゼミのために問題を解く。今回はこれまでの共通科目とは違い、8問から3問選んで解く選択科目の過去問を取り扱う予定。相変わらず大問の最後の1つが難しいが、何とか解けた……と思う。無限集合Aについて、可算無限集合\mathcal{B}\in\mathfrak{P}(A)であって集合ブール演算（補集合、2つの合併・共通部分）で閉じているようなものが存在することを示せという問題だった。特にA=\mathbb{N}=\mathbb{Z}_{>0}の場合に示せばよい。[2^i,2^{i+1})（i\ge 0）の合併で表せる集合たちを考えると、その濃度は一見\mathfrak{P}(\mathbb{N})と同じように見えるが、実は\mathbb{N}への全単射が構成できる。イメージとしては2^{\log_2 \#\mathbb{N}}という感じか。

と考えたまではよかったのだが、実際に解答を作ってみると1時間以上かかってしまった。どのくらい記述を省いていいのだろうか。まあアイディアさえ見て取れればそうひどい扱いはされないだろうから、粗く書き上げてから余った時間で補題として証明を付け加えるのも一つの手だろう。

布団に行ってしばらくラノベを読み、午前9時半就寝。

08/03(火)

午後4時半起床。目覚ましによるもの。もう2日後にチュウニズムのアップデートが近づいてきているが、まだ削除されてしまうマップを走り切れていないので、今日は何が何でもゲーセンに行く。

ちょっとパソコンを触っていたら学食の夜の部が始まったので、夜ご飯をそちらで食べてから市街地に出る。適当に自転車を停めた後、すぐゲーセンに行くのではなく、まずラノベを購入することにした。メロンブックスでチェックしてあったラノベの新刊をあらかた購入。7月発売のラノベをまだ1冊手に入れられていないので、さらに2件ほど本屋を巡ったが、どこにも置いていなかった。「剣と魔法の税金対策」3巻。ガガガ文庫で、同じ月に発売されたラノベは置いてあるのにこれだけないとは、かなり謎である。それだけ売れているということだろうか。重版を待たねばならないかと思ったが、ネット書店では注文できそうだ。

いよいよゲーセンに入ってチュウニズムをプレイした。今日は13のAJが2つ増えたくらいで、目立った成果はない。狙っていた譜面のAJが出せなかったのが悔しい。

閉店までプレイして、立ち食い蕎麦屋でざるそばを食べて帰宅。ざるそばのつゆを蕎麦湯で割ろうとしたが、つゆが思ったより多くて全然薄まらなかった。でも結局全部飲むなら塩分量は一緒、例えばインスタント味噌汁にお湯を注ぐときも、そのまま食べたほうが効率的だよな……ということを考えている。

今日もHikakinTV（HIKAKIN TVじゃなかった！）に本気動画の1本が投稿されていた。今回はHIKAKINがVTuberになるらしい。いや～……すごい。前回の「ウ”ィ”エ” ヒカキンVer.」とは全く違った切り口の「本気」であることに驚き。普通の新人VTuberとは違い、生身のYouTuberとしての膨大なバックグラウンドがあるわけで、配信のスタイルにも編集にも慣れからくる貫禄があるのだろう。また、動画の序盤でHIKAKINの声の収録風景がちょっと挟まるのは、普通はできない表現なので、非常に面白かった。

youtu.be

ところで、この3Dモデルは今後どれくらい使われるんだろう？何回か使って忘れ去るというのは、もちろん3Dモデルを作ってもらうのにも金銭と契約があるだろうしその上では問題はないが、心象的にはよくないだろう。HikakinGamesのゲーム実況で常用されることを期待したい。

ECR112-Fのupsolveをした。07/30の解き残し。

Submission #124796890 - Codeforces

ループを作らないような辺だけ先に処理して、後から出来上がった森を使って頑張るということは知っていた。森になったらあとはどうとでもなると思ったが、その部分も結構難しい・あるいは面倒くさくて大変だった。ループを作るのに使った辺にマークしたいが、これは遅延セグメント木の区間更新ではできないようだ。仕方なく、各辺が高々1回しかマークされないことを利用して、毎回1本ずつマークしていく形になった。公式解説もそうしていたので、もはやどうしようもなさそう。

布団に移動し、ラノベを一冊読んだ。「大罪ダンジョン教習所の反面教師」。面白かった。主人公が実力を隠している設定はやはり良い。さらに教官物も最近の自分の嗜好に合っているようだ。総じて好みの設定だった。ダンジョンで手に入るアイテムにはデメリットが設定されているが、それがどれも絶妙に嫌らしかった。使ってバフをかけたらその後の人生のどこかで同じだけのデバフがかかるだとか、使用回数に制限があるのはわかっているのにいつ使えなくなるかわからないとか。

別のラノベを開いたが、少し読んですぐに寝ることにした。午前8時半就寝。

08/04(水)

午後1時半くらいに目覚ましをかけていたが、止めた後も起き上がれず、1時間程度布団でクネクネしていた。今日は院試ゼミで、1人の家に集まって対面で行う予定なので、起きなければならない。

何とか身を起こしたものの、午後3時の集合時間にはかなり頑張らないと間に合わなそうだったので、遅刻すると連絡を入れて大学生協に寄り、昼ご飯のパンを買って食べていた。のうのうとしていたら事前に伝えていた時間よりさらに遅れてしまい、かなり申し訳ない気持ちになった。

院試ゼミ。今日もかなり勉強になった。選択科目の話で、これまたすっかり忘れてしまったことを問われている。適宜ググったりしながら話を聞き、自分も作ってきた答案を発表した。自分の担当した問題は基礎論の範囲で、特別な知識は特に必要ない答案になったが、これを試験時間中に書けるかと言われると……かなりつらい。

午後7時過ぎ、僕がTCOのRegionalに出るという話をしたら解散する感じの流れになったが、なあなあのうちにコンテスト直前になってしまったため、そのままノーパソで参加した。

TopCoder Statistics - Match Overview

EM2完86位。Appretも拡張も何も入れていないため、Web Arenaで問題を見て自分でクラスと関数を定義することになった。それはそれでよいのだが、EasyもMedも解くのにかなり時間をかけてしまった挙句、Medでリサブしてしまい、このような順位になった。レートは2535→2451(-84)。何とか次のRoundへ進めるようだが、通行料としても高すぎるだろう。

Easyは微妙に難読。競技結果によるタイブレークのアルゴリズムが延々書かれているが、そもそも結果のスコアが異なったらそれで順位が決まるということをよく理解していなかった。サンプルを合わせるのに非常に手間取った。Medはいかにも普通の問題で、解法も簡単だったはずだが、指数ではなく実際にべき乗した値を持ちながら計算しようとして大小関係が崩れることに気づいていなかったりと大変なことに。さらに、提出後しばらくして、高さ2以上の部分木を2つ以上持つような頂点で壊れていることに気づき、リサブ。かなり絶望した。

Medは結局2の各頂点の深さ乗を足し合わせる感じになるらしい。頭が良すぎる。またEasyでSTLのsortと指定された関数名sortが被るため、前者をstd::sortとしなければならないことも話題になっていた。僕も1度CEを食らったが、運よくすぐにこの対処法を思いつくことができた。

コンテストが終わって、みんなで近場の定食屋に行ったが、僕がコンテストに出ている間に閉まってしまったらしく、非常に申し訳ない気持ちになった。終電があるということで1人帰宅し、3人で何を食べるか悩んだ。これからどこか別の店に行くのも面倒だということで出前のピザを注文した。久しぶりに食べるとかなりおいしい。

その後、結局朝方まで3人でずっと院試の問題を解いていた。昔の共通問題はやってみるとかなりスラスラ解けるものもあり、そうやって瞬殺できると非常に楽しい。また初手から発想を必要とする問題が紛れていて、それをシュッと解けたのは本当に快感だった。このときチャレンジした問題はすべて解けたが、1人でやっていてはかなり詰まった問題も多かっただろう。まさに3人寄れば文殊の知恵といったところか。

午前7時前に解散。コンビニで少し朝食を買って食べ、帰宅した。結局朝までやっているのだったら、途中で帰ってしまった人も引き止めればよかったなあと後悔している。

帰宅してシャワーを浴び、TCのレート変動を確認して絶望したり以下の動画を見てエモくなったりした後、午前10時半に就寝。

www.youtube.com

08/05(木)

午後6時半くらいに起床。TLでチュウニズムのアップデート情報が流れてくる。チケットが大量に廃止されるらしく、今貯めこんでいる分はアップデートまでに使ってしまわなければならないらしい。レベルが5の倍数になるたびに1枚もらえる「もう1曲遊べるチケット」は、なんとなくもったいない気がして上限ギリギリまで貯めているので、非常にまずい。

論理学の最終課題に取り組む。これが今セメスター最後の課題になるはずだ。まず溜めていた5回分の講義動画を視聴。といっても、大胆に飛ばしつつ黒板に書かれている内容を読むだけ。あとは講義資料も適当に読んで、いよいよ課題に取り掛かる。

中間課題では、対話形式で証明を進めてくれるプログラムを作ったのだった。これは、それまでの講義で扱っていた命題論理にしか対応していないので、それを述語論理にも対応させ、最終課題とすることにした。

テーマはこれまでの講義に関係していればなんでもよいという自由度の高さなので、対話形式で証明を進めてくれるプログラムを作ろうと思い立った。

週記（2021/06/21-2021/06/27） - kotatsugameの日記

しかしどのように実装したものか。そもそも、今さっき講義動画を見たばっかりで、述語論理の証明については何もわかっていない。実装方針を迷ったり、そもそも別のことを最終課題にしようか迷っているうちに、TCO RegionalのRound 2が始まったので、出た。

TopCoder Statistics - Match Overview

またEMの2完。Hardを通した人も大量にいたが、一方でMedを落とした人も大量にいたので、結局21位になった。レートは2451→2480(+29)。日曜日のトーナメントに進出したらしい。

Easyは自明。あまりに自明すぎて怖くなり、かなり慎重にチェックした。Medは全然わからなかったが、「最後の要素が小さければ小さいほど良い」という性質をエスパーして解いた。証明はできなかった。エスパーした後もしばらく、最後の要素としてどこまで和を取るか二分探索することを考えていたが、普通に前からdpできることに気づいた。Hardは4次元dpを書いたが、最後のサンプルだけ合わずにコンテスト終了。

touristと同じルームだったが、チャレンジフェーズに入ってすぐtouristがどんどんMedを落としていて、非常に怖い思いをした。TCでエスパーするのは度胸試しという感じがある。しかし結果としては落とされることなく終われてハッピー。落ちた提出を見ても何が違うのかあまりよくわかっていない。後ろから貪欲に取っているのかとも思ったが、案外そうでもなさそうだ。

課題に戻る。実装したりラノベを読んだりを繰り返し、午前8時くらいに一応の完成を見た。正直まだまだという感じではあるが、講義資料に載っていた証明のいくつかを再現できたので、もういいだろうという感じ。\lnot\forall x.\lnot Fx\vdash\exists x.Fxが紹介された導出規則で示せず悩み、\forallの定義だと思うことにして左から右へ変換してくれる命令も用意したが、結局それを使わずにできた証明しかチェックしていない。以前までの命題論理のみの挙動を保つように実装したので、述語論理に対しても中間課題の時に実装した機能がそのまま動いてちょっと感動した。

github.com

あとはちょっと文章を書いて提出するだけ。ミニットペーパーも最後の分だけは提出しなければならない。ミニットペーパーの文章を作成して提出しようとしたところ、ログインセッション切れで書いた文章が吹き飛び、思わず声を出した。今度は手元のテキストエディタで書くことにする。頑張って再現して、いざ提出しようと思ったら、入力欄に吹き飛んでしまったはずの文章が復活しており、また非常な徒労感を得た。

次いで、作ったプログラムに関する文章を書き、最終課題として提出した。しかし、これで終わったと解放感に包まれながら最終課題をもう一度チェックすると、「小論文」を作成せよと書いてあるではないか。かなり困ったが、ここまで作ってしまったものはどうしようもないため、このままにしておくことにした。これで落ちるならそれでもいいやという開き直り。

布団に入ってラノベを読み、午前11時半就寝。

08/06(金)

午後6時半起床。前日は何となく寒い気がしてエアコンを切ってから寝たのだが、起きたら部屋が暑くて参ってしまった。ちょっと間違えば命の危険性があるのでは？もはやエアコンは生命維持装置の1つであるようにも感じられる。

サークル解説会の準備をする。今日はG問題とH問題にすでに解説役が立候補してくれており、非常にうれしい。僕もF問題の解説スライドを生やしておくことにする。午後8時から1時間くらい解説会を行った。今日はかなり濃い3問で、普段より大幅に長くなった。来週から9月末までは夏休みの予定だが、9月に入ったらICPC関連の連絡をするかもしれないので、Slackはチェックしておいてほしい、ということも話しておいた。相変わらず次代のサークル代表が見つからない。

2021/08/06 定例会 | puzzleknot 公式サイト

ICPC練習で部室を使いたいという話が合ったので、活動計画書を教務課に提出する必要がある。去年のものを参考に書くことにしたが、まずはyukicoder 308から。

yukicoder contest 308 - yukicoder

全完。タイムはそこそこ速いものの、前から順番に解いているため点数は低い。結果、後から全完した人にかなり抜かされてしまい、悲しい。

ABはよい。Cはdijkstra。Dはちょっとびっくりするが、赤字の制約を読むと、読み込んだ順に辺を張っていけばよいとわかる。Eは判定問題を解くのは一瞬だが、構築をどうするか悩んだ。結局、連結成分ごとに全域木とそれに含まれない辺を1本用意し、木上でdfsした後根に向かって辺を追加することにした。Fはオイラーツアーやるだけ。

Eにevilケースが入っており、自分の提出ではREを出してしまっていた。表示上はACだが、提出欄にACではないケースが紛れているのは目立つ。しかしREとは何だろう。適当にTLEを出したりして、問題文に記載されている制約を違反していることを確信し、clarを投げた。しかし回答は「evilケースなので制約違反していてもよい」とのこと。これは納得できないが、ほかの問題のevilケースがどんな感じだったかをよく覚えておらず、制約違反しているケースがあったような気がしないでもないので、結局「evilケース用の制約を表示してはどうか」と言うにとどめた。そのような変更はされなかったようだが。

入力される値がどんなものかわからないままだが、適当にvectorで確保することにすればACはできた。ほかの問題では200msを超えていないのにevilケースでは700msくらいかかっているので、相当大きいケースだったらしい。実際後から確認したらN=3\times 10^5だった。

明日の院試ゼミの準備をする。今回も選択科目の問題を解く予定で、僕は多様体の問題を担当している。講義も演習もかなり頑張った（課題が多かったので頑張らざるを得なかった）科目なので、何とかなるんじゃないか？という感じ。

今回は射影空間の問題だった。射影空間の計算は演習で何度も何度もやっていたはずが、すっかり忘れてしまった。提出したレポートを見返しても問題がないので何をやっているのかわからず、問題も見つからなかった（後から調べたらちゃんとClassroomにあった）ので、当時の講義資料をClassroomから掘り返して記憶を補いつつ、定義と計算方法だけ何とか飲み込み、解いた。やることさえわかってしまえばあとは愚直に計算するだけだった。

溜めていた日記を書き、午前7時就寝。明日のゼミは、生活リズムを整えようとのことで午前10時から予定されている。

08/07(土)

午前10時の目覚ましで起きる。信じられないくらい眠いが、人を待たせるのはまずいのでパソコンの前に向かってZoomに接続。すると他に1人しかいなかった。どうやら2人がまだ来ていないらしい。ゼミが始まらないのをよいことに、自分もうつらうつらとして少しでも眠気を取っておく。

1人は時間の勘違い、もう1人は徹夜に失敗していたらしく、午前11時を過ぎてからゼミが開始した。が、大変まずい。1度など人の発表を聞きながら意識を飛ばしてしまったらしく、気づいたら自分の番になっていた。申し訳なくなりながら自分の解答を発表。ついでに自分の理解していることを確認したりして、今回もかなり有意義だった。最後に、過去問を見つつその場で少し議論したりしながら、次回の日程と問題の担当を決めて終了。

午後2時だった。AHC005まで2時間あるので、少し寝ることにした。……午後4時の目覚ましに起こされるまで、その30分前の目覚ましにも気づかず爆睡。しかもこういう日に限って生協の弁当配達が午後3時台に来ていたらしく、もう1年以上注文し続けているのに初めて受け取り損ねてしまった。土曜日であることを完全に忘れていたのも悪かった。電話が来ていたので、折り返して再配達をお願いする。

AHCの問題を確認する。スコア的に、全マスを視界に入れるのは前提らしい。ただ、全マスをちゃんと回るような解を書くのがまず難しそう……。眠気も相変わらずひどいので、しばらくボーっとしていた。

シャワーを浴びたりして考えをまとめ、実装に移る。まず愚直に全マス周回する解を出して様子を見ようと思っていたが、そのあと使わなそうなコードを書く気力はないので、初めから思いつく限りの改善を実装する。まず考慮するマスを絞る。例えば行き止まりにわざわざ入っていく必要はないし、縦または横に通るだけの道の上のマスを特別扱いする必要はない。条件を詰めると、周囲に3マス以上の空きマスがあるか、2マスの空きマスがあって、それが縦横に分かれているようなマスだけを抜き出してもよさそう。サンプルが270個くらいなので、だいたい300個で抑えられそうな気がする。このマスたちの間の距離は全部前計算できる。

あとは適当にTSPを解けばよいだろう。TSPは普通どう解くのか知らないが、適当に2点swapして山登りしてみた。最初、抜き出したマスの個数を300個で抑えていて困ったことになった。手元で試してみると、普通に300個を超えるケースがあった。ところで、手元で試すときにinというサンプル入力のファイルを作っていたら、ジェネレータを動かす際inディレクトリが存在すると判定されてしまい、結果入力を書き込むパスが有効にならずエラーを出してしまっていた。

結局、500個で抑えなおしたら通った。しかしスコアはあまりよくない様子、6601725。次に、山登りを区間reverseにしてみた。11699590で、かなりの改善になった。最初の巡回順はマスを上から順に見ていった時のものだったが、このとき大体同じ行のマスが連続しているので、行の間のつなぎ方を変えるのがスコアに良い影響を与えるのだろう。

次に、初期解を実際に動かしながら作ることにした。貪欲に未訪問の頂点に向かい、隣接する頂点を全部訪れたら一番近い未訪問の頂点を目指す。11810404、これも多少の改善。続いて山登りを焼きなましに変えた。 12320530と先ほどよりは大きな改善。焼きなましの温度はコピペ元と全く同じにしていたので、手元で適当にずらしてみたところ、最初の温度をもっと高くするとスコアが上がるようだった。スコアの増減の度合いをよく確認していなかったのかもしれない。この改善で13213242と大きく上がった。

あとは、実際に解を文字列に直す前に、順番に見ていて明らかに余計な頂点（4方向の先にあるマスをすでに訪れているようなマス）を通らないことにしたら13282173、順番に見るのではなくランダムに消していくようにしたら13969535。ここでコンテスト終了、結果は170位でパフォーマンス1790、レートは1941→1969(+28)だった。

日記を書いていて気付いたが、余計な頂点として「4方向の先にあるマスをすでに訪れているようなマス」を考えるとき、壁マスのことを完全に忘れていた。その方向を考慮する必要はない。この改善を入れたら14720756になってしょんぼり。でも10位も上がらないらしいので、まあいいか。

TLを見た感じ、どうやら通るべきマスをさらに絞り込み（ここでも焼きなます）、何度もTSPを解くのが強いらしい。僕の解法に適用するなら、後半部分だろう。焼きなましを何度も行うべきだった。確かに、焼きなましの時間を延ばすことによるスコアの改善は小さかった覚えがある。それでも微妙に増加したので、結局2.9sec焼きなましてしまったのだが、それより通るマスをもうちょっと考えたほうがよかった。また、通るマスを計算するために二部グラフの辺カバーを計算するという解法もあるらしくて、アルゴリズムの力に震えた。

しばらくTLを眺めてから布団に倒れこむ。本でも読もうかと思っていたが、耐え難い眠気が訪れ、午後9時から午前0時まで寝ていた。

起きたら窓ガラスからゴンゴンと音が鳴っていてびっくりした。注意深く聞いていると、羽を持つ虫がぶつかってきているようだ。閉め切ってあるので害はないとはいえ、時折音が響くのは非常に恐ろしい。

GCJの順位表を見ながらラノベを読んでいた。GCJはtouristの連覇が止まってびっくり。YesNoを見ながら心臓が消し飛びそうになっていた。

「最強魔法師の隠遁計画」13巻を読んだ。Web版の記憶と書籍版の記憶がまぜこぜになって、前の話をあまり覚えていない。元首シセルニアは好きなキャラなので、今巻はアルスとの絡みが結構描かれていて良かった。しかしWeb版から加筆されまくっていて、全然話が進んでいる気がしない……。

別のラノベを手に取り、少し読んだ後今度こそ就寝。午前8時だった。

08/08(日)

午後6時半起床。食事し、午後7時15分からTCO21 Regionalのトーナメント1回戦に出た。

TopCoder Statistics - Match Overview

両方提出したが、両方落としてしまった。対戦相手も落としていたが、Round 2の順位差で負け。どちらも面倒くさくてコーナーケースが大変そうな問題だった。2問目は適当に出したので何とも言えないが、1問目については述べておこう。

文字列が2つ入力されるので、辞書順比較でその間にある文字列を1つ構築せよという問題。ただし文字列の長さはL文字以下と制限されている。最初にA\lt Bであることを確認した後、後ろに'a'を付け足せるなら1個だけ付け足し、付け足せないなら末尾の文字をインクリメントすることで候補を作り、実際にB未満であるかをチェックすればよかった。

僕は後ろに'a'を目いっぱいつけるという謎の操作をしていた。そこがあっていても、末尾の文字をインクリメントするときは'z'を'a'に直すのではなく削除しなければならないというのもできていなかったので、全然ダメ。

しばらく院試ゼミの準備をして、午後9時からABC213に出た。6完。完全にヤバい。

AtCoder Beginner Contest 213 - AtCoder

ABはよい。Cは縦横それぞれ座圧。Dはdfs。Eは01BFS。FはSA+LCPで累積minの総和みたいな操作に言い換えられ、これを遅延セグメント木で殴りつけたら2000msちょっとで通った。

ここまでは順調だったが、GもHも解けずに終了。しばらくGを考えて、何の成果も出なかったのでHに移動。ワーシャルフロイドみたいな感じで経路数をカウントしてみて、最後に1から1へのループをたくさん重ねてサンプルを合わせたが、他の頂点で何回もループする場合が全然カバーできていない。Gに戻って、連結成分を決め打つことを思いついたが、慌てて実装を初めて詰め切れず終了。

Fはstackでマージしつつシミュレーションすることで全体で線形時間が達成できる。priority_queueで同様のことを行うのは考えていたが、データをマージするのを考慮に入れ忘れており、計算量が抑えられないと思って捨てたのだった。

コードゴルフ。Aは最初にRakuで提出したものが最短だが、AWKでも同じコード長が達成できるようだ。gawkにxorという関数が存在することをかなり忘れがち。BはVimで書いたが、さらに縮められた。factorコマンドで空白区切りの数値を1行に1つに直すテクが使われており、同じことをして縮むコードを一通り縮めたりもした。Cは座圧なのでOctave。DはPerlで書いたが、負けた。EFはコンテスト後にC++で書き直したものが最短になっている。

Gに取り組む。1を含む連結成分を決め打つと、1を含むそれより小さい連結成分がある場合に適当に係数をかけて引くことでちゃんと求められる。この係数のせいで○○変換みたいな形にするのは難しいらしい。317なので惑わされていた。落ち着いて考えたらすぐサンプルが合ってそのまま通ってしまい、なぜHに行ってしまったのかと後悔。

Hは全然わからないので、kyopro_friendsさんのツイートにリンクがあったオフライン・オンライン変換を読む。それでもよくわからなかったのでいよいよ解説を開いたら、自分の間違った思い込みに気づいた。いくつかまとめて遷移しようとしているように見えていて、それなら今ある辺たちもいくつか繋げておく必要があると思ったが、そんな必要はないのだ。

qiita.com

実装したらサンプルが合って感動、勝ちを確信しつつ投げたらTLE。しばらく悩んでいたが、ループ中にT要素のvectorをコピーしていたのが重かったらしい。コピーもちゃんと必要な分だけにすると通った。GHともに、これまた僕のC++コードが現状の最短になっている。

院試ゼミの準備の続きをする。今回の問題は群に関するもので、見た目のシンプルさに違わずちょっとがんばったらすぐ解けた。特に忘れていた語彙などもないはずで、あとは自分が勘違いしていないかだけが心配だが、とにかく解答は完成した。さらにもう1問くらい解いておこうかと思ったものの、途中で詰まってしまい、ラノベを読み始めた。

「継母の連れ子が元カノだった」7巻を読んだ。非常に良い。最近こういう両片思いのラノベをよく読んでいるが、良いものは非常に良い。しかしこのシリーズ、7巻も両片思いしているのか。1巻からちょっとずつ近づいてきた感があり、かなり丁寧。この巻もラストシーンが非常に健康に良く、大変ありがたかった。あとがきで1巻の表紙に関する話が出て、改めて確認して変な声を出したりもした。

日記を書きながら月曜日に提出したレポートがどうなったか見に行くと、採点がすでに終了しており、なんと解いた5問すべてが満点の評価だった。有終の美。勝ったな、ガハハ！

週記（2021/07/26-2021/08/01）

07/26(月)

先週は週記を投稿してから午前9時半くらいに寝た。

午後1時半起床。今日はコロナウイルスのワクチン接種、1回目の予定だ。

朝方メールが届いていた東北大学のワクチンを予約した。

週記（2021/07/12-2021/07/18） - kotatsugameの日記

予約した後すぐ、富山の実家のほうにワクチン接種券が届いたので、郵送してもらっていた。ワクチンを接種するにあたり、「予診票」と「接種記録書」に記入して持っていかなければならない。このうち「予診票」はワクチン接種券の封筒に2枚同梱されていたので、そちらに記入。「接種記録書」はプリントアウトして持っていく。家に体温計がないので体温がわからなかったが、それ以外の記入は済ませた。そのような準備をしていたらけっこういい時間になったので、接種場所である仙台駅前のヨドバシカメラに行くことにした。

本当は学食で昼食を摂り、購買で買い物していったん家に荷物を置きに帰るような予定を立てていたが、そのような時間はなさそう。体温計などの買い物だけして、荷物を持ったまま地下鉄で仙台駅に行った。駅前につくと予定時間の10分くらい前だったので、丸亀製麺で急いで昼食を摂った。

ワクチン接種の時間は結構あいまいらしい。僕が行ったときは、確か午前9時から午後3時45分までの予約の人が受け入れられていた。東北大学が用意した摂取会場というような話を聞いていたが、実際は市民の方に紛れる形で受け付けから摂取までが進む。受付のところがボトルネックになっているのか、それ以外で作業を待つような時間はなかった。

朝家で書いた「予診票」について、実は東北大生専用の書式があったらしい。一見すると同じだが、上の余白に記入欄が増えているのと、下の項目がいくつか埋まっている。受付で知らされた。予診票を書かずに来る人も多いのか、そのために用意された場所があり、そこに座って書き写す作業が発生した。それ以外はスムーズに進み、15分の待機時間も何事もなく終了。最後に、受付で渡された接種手続きのスタンプラリーのような用紙を回収されるコーナーがあり、そこだけは東北大生専用の窓口があった。

富山県から送られてきたワクチン接種の書類には、県外で摂取するときは「住所地外接種届」だのが必要と書かれていた。これ以上ほかに何かするべきことがあるのかと質問してみたが、これは「仙台市に対して」提出すべき書類で、しかも東北大生は全員必要ないとのこと。心配していたのでスッキリした。

仙台駅前には謎のアンパンマンの石像がある。

せっかく駅前まで出てきたので、ゲーセンで遊ぶ。ちょっと手元動画を撮ったりしたが、あまり良いものは取れなかった。せっかく1発AJが出たのになぜか録画データが壊れてしまったり、緊張でアタックを出すのを何回かやったら癖がついて下手くそになったり。そのうちに微妙にワクチンを打った腕が痛くなってきたので、13をプレイするのを控え、12+最後の未AJ譜面と向き合うことにした。

まだSSSすら3回くらいしか出していない気がする。特に前触れなくシュッと出た。意識していたのは、フリックと小粒が絡むところは全押し端フリックで処理すること、52小節の右手3鍵左手16分は右手を少し早めて3鍵の終わりと16分の2ノーツ目、4ノーツ目の終わりを一緒にすること、くらいか。後者は昔は全押しで通していた気もするが、今やってみたら全然通らなかった。

午後9時くらいにゲーセンを出ると、周り中の飲食店がちょうど閉店したところだった。サイゼすらも閉まっていて、この先どうすればいいんだという感じ。仙台駅をふらふらしていたら、営業している本屋さんを見つけたので、うっかり吸い込まれて5000円使ってしまった。この本屋は午後9時半閉店だったらしい。手持ちのお金が心もとないので、夕食は立ち食いそばになった。

帰宅して購入した本を撮り、ツイート。

撮影した手元動画もいくつかツイートした。HalcyonもAJ時の運指を撮ろうとしたが、1か所どのように擦っていたか忘れた個所があり、事故った。そこ以外はAJだったので、自分としてはいい感じだと思う。

買ってきた本を読みたいが、目がシバシバして眠い。午前1時半くらいに就寝。

07/27(火)

午後2時前に目を覚ます。ワクチンを打った左腕がめちゃくちゃ痛む。どのような大勢で寝ていても痛いので、本当につらい。そのまま眠れずに午後4時になってしまったので、泣く泣く身を起こすことにした。

富山県出身の大関・朝乃山が新型コロナウイルスに感染してしまったらしい。地元に帰るたびに朝乃山のニュースが流れているので、四股名に見覚えがあった。

Nキチさんから赤達成お祝いのお酒が届いた。これは先週木曜日（07/22）の酒盛りのときに購入するか迷っていたお酒だったので、ギリギリ被らなくてよかった。購入しようと思っていただけあり、かなり気になっていたので、送られてきたのは非常にタイムリー。

学食に行って夕食を摂り、帰宅。人の週記を読み漁る。よこの週記には、よこが先週のABC・ARCに出た様子が綴られていた。そこに書かれていたARC124-Bの解法は、実は嘘解法のように思われるが、それで通ったのならコードゴルフとしてかなり革命的。いそいそと実装して投げたらWAだったが、テストケースの内訳を見るといつの間にか追加されていたafter_contestでしか落ちていなかった。いつ追加されたのか調べると、なんと今日の昼間らしい。昨日のうちによこの週記を読んでおけばよかったとひとしきり後悔していた。

aとbのxorテーブルがあるとすると全ての列に登場する数字が「よい数」である

よこ週記 2021/7/19-25 - よこのブログ

atcoder.jp

昨日買ってきたラノベを読んだり、院試ゼミの担当の問題の解答を作成したり、YouTubeを見ていたりしたら午後9時になった。左腕が痛いと、そこをかばうように変な姿勢になるため、結局全身が痛くなる。全身の痛みというのは風邪の症状なので、頭も痛いしなんとなく熱がある気がしてくる……実際に熱があるのではないか？昨日買ってきた体温計で測ってみると、37度3分だった。立派な微熱であった。

どうしようもないので、さっきまでやっていたことを同様に続けていた。真夜中になって、明日の院試ゼミで担当する問題の解答に（今回もホスフィンの助けを貰いながら）一段落つけられたので、Nキチさんから送られてきたお酒を飲むことにした。アルコール度7%だし割るものもないのでロックで飲む。飲み比べセットということだったので、3種類を順に飲んでみた。僕は梨が一番好きかな。

yukicoderの問題を解く。先週木曜日のコンテストの問題は全然解いていなかった。Bは場合分けで、空文字列が回文ではないというのはかなりよくわからない定義であった。C問題は累積輪の累積和っぽい感じで、引き算する部分は適当にサンプルを合わせる。

問題文一行コンテスト - yukicoder

Bを解いた段階ですでに酔っぱらっており、かなり気持ち悪くなったので、体調が悪い時に飲酒するものではないなという気持ちになった。しばらく横になっていたら収まったのでCを解き、Dは面倒だったので諦め、日記を書いて布団に移動。ちょっとだけなろうを読もうと思ったら、スマホを握りしめて寝落ちしてしまった。午前4時過ぎだった。

07/28(水)

午前11時、目覚ましで起床。ちょうどこの時間から院試ゼミの予定だったが、かなり眠いのでもうちょっと寝ようかな……という気持ちが芽生えてくる。

布団の上でコロコロしていたら、ゼミのメンバーからLINE通話がかかってきた。どうやら、僕がちょっと前にSlackで「起床頑張ります」という内容の投稿をしていたのを見て、気を使ってくれたのだろう。人に気にかけてもらえると、かなり嬉しい。起き上がらないわけにはいくまい。顔を洗ってトイレを済ませ、Zoomに接続した。

今日のゼミもかなり有意義だった。毎回、一度覚えていたけれど忘れてしまったものを拾い集めるような気持ちで参加している。有理数の稠密性とかもウッとなってしまったのでWikipediaで定義を再確認しておいた。ある位相空間上で定義された関数が「全点で不連続であること」を示す問題があった。位相の文脈で1つの点における連続性というのはほとんど扱った覚えのない話なので、定義が出てこない。休憩時間などを利用してチマチマ調べていたところ、どうにもネット上の資料や教科書に書かれたことが一致していないように思える。この話を少し振ってみたところ、僕が「近傍」の定義を間違えていたことが分かった。勝手に開であると思っていたが、そのような注釈はない。

そういえば、ゼミの最中に体温を測っていたが、もう熱は下がってしまったようだった。左腕も痛みはだいぶ取れている。喉元過ぎれば熱さを忘れると言うが、昨日辛かったことは現実なので、2回目はもうちょっと準備を整えてから望みたい。冷えピタはあったほうがよいだろう。

午後2時半くらいにゼミが終了。院試ゼミの面々で金曜日の昼間に街で食事をすることになった。楽しみ～。

僕は東北大学競プロサークルの代表をすでに2年務めているが、実は任期が1年なので、更新のタイミングでメンバーの同意を得なければならなかったようだ。ほかにもサークルの規約はいろいろ策定されているが、あまり守れていない。面倒さは感じるものの、おろそかにするとすぐサークルが崩壊するはずなので、気を付けたい。今は僕の方針で全ての活動を参加自由としており、幽霊部員がかなり多いため、すでに崩壊しているのかもしれない。

ともかく、代表を2年やってしまったわけだが、さすがにそろそろ引継ぎをしなければならない。多分もうしばらく僕ができないことはないが、それは健全ではないだろう。いまだに碧黴さんが契約しているサービスもいくつかあり、碧黴さんが大学にいる間に何とかしておく必要がある。ということで、とりあえず次のサークル代表の立候補を募ることにした。自薦で決まってくれればいいが……。

Slackに投稿してから布団に転がり、ラノベを読んだ。午後5時から午後8時半くらいまで寝落ちしていた。起きてからまたラノベを読み続け、この日は3冊を読了した。

「公女殿下の家庭教師」9巻。面白かった。主人公が認知されてきてそうで、目立つのは好みの展開なので好き。しかし文章について、毎巻のように読みにくいということを言っている。今巻はセリフからキャラを判別するのが難しかった。ヒロイン全員に1言ずつ喋らせるのは無茶だろうと思う。

「嘘と詐欺と異能学園」。買ってしばらく寝かせてあったが、Twitterでお勧めされていたのを見て読むことにした。かなり面白かった。中盤、ヒロインが主人公のことを考えて勝手な行動を取り始めたあたりがかなり辛く、相棒なら報連相をちゃんとしてほしい……！という気持ちになったが、それらもすべて終盤で回収されてスッキリ終わった。ラストで衝撃の事実が発覚したけど、シリーズ1巻でもうそれをオープンにして大丈夫なのだろうか、という気持ちになる。

イラストはkakaoさんが担当している。最近ラノベでよく見るイラストレーターだが、だいたいお色気シーンが挟まっていて、「そういう」印象があった。しかしこのラノベではそういうシーンがなく、びっくり。正直微妙なお色気シーンならばないほうが好みだ。「新妹魔王の契約者」くらい吹っ切れてくれるといい（？）んだけど。

「推しが俺を好きかもしれない」。よかった。中盤の特定のシーンから目に見えてヒロインの態度が変わるのが非常にわかりやすくて安心する。微妙な描かれ方をするとわからないからね。ひと悶着あった後、とりあえず友人関係となるのもいい感じ。

列車の窓から黒い羊が見えたとき、その羊の少なくともこちら側半分が黒いことしか保証されず、他の羊に関しては何も言えないのと同様に、作中で明言されない限り、ヒロインは主人公が好きなのではなく、今でもただ主人公とお友達になりたいだけである、という可能性を否定しきれない。

週記（2021/03/29-2021/04/04） - kotatsugameの日記

夜にこういう投稿を見かけたのだった。レビュー自体は読んでいて気分が悪くなる類のものだったが、noteのほうはかなり気持ちの良い書き方というか、むしろ楽しむための前向きさを感じて、非常に感触が良かった。自分がどういう考えを抱いているのかわからない。飲食店としては失格だろうと思うが、最後に掲載されていたDMのスクショ（すでに削除されている）を読んで、店にも事情があることは考慮する必要があると感じた。特に関係ない自分が何を言っているんだとも思う。とにかく、いくつか考え事をしたということを記録しておきたかった。

何かに悪感情を抱くのは自由だが、それを外に出すにはそれなりの覚悟と理由が必要であるということも考えていた。これは、レビューを読んで悪印象を抱いたのに、次にnoteを読んですぐその印象がぼやけた自分に対する戒め。

朝方、コップ半分くらいのお酒を飲んで寝ようとするが、TLに流れてきた問題が気になる。しばらく考えていたが、もうN+O\left(\sqrt N\right)解でお腹一杯という気持ちになった。最終的にN+O(1)で解けるということだけツイートされたのを見届け、何もかも諦めて就寝。午前9時半だった。

07/29(木)

午後1時、目覚ましで起床。ゼミが始まる。パソコンを起動してZoomに繋いだら、午後1時1分ですでに僕以外勢ぞろいしていて正直怖かった。ちょっと待たせてしまったようで申し訳ない。

今日のゼミはアルゴリズムの話が持ち上がったが、そもそも言葉の定義をよく知らなかったため、特に何も言及できずに終わった。正直アルゴリズム自体もそこそこ難しい（というか、文字列の頭いいアルゴリズムの1種）気がする。結局、発表者の説明を聞いてもよくわからず、ネットで調べたものを読んでいた。与えられた文字列を適切なLyndon wordに分解する問題で、そもそもLyndon wordの定義からあやふやだったが、以下の資料にある定義ならばアルゴリズムが動作することはわかる。これが講義で扱っているものと同じかは……知らない。

Lyndon factorization - Competitive Programming Algorithms

あとは生協の弁当を注文したり、前回の内容を再確認したりしていた。午後4時半くらいに終了。眠すぎて購買や学食に行く気力もないし、YouTubeを見ながらうだうだしているうちに雨も降ってきてしまった。

サボったCF div.3を解いた。

Dashboard - Codeforces Round #734 (Div. 3) - Codeforces

Abはよい。Bは、queueを使うのが面倒だからとvectorをstackのように使って解いたが、これはミス。FIFOである必要があった。Cもよい。

dは難しかった。適当に投げて4WAしてしまった。しかもテストケースも見ているので、本番で通せたかどうかは定かではない。場合分けなのにあまり真剣に考えていなかったのも問題だろう。Dはカス。こんな構築させるwriterは二度と作問しないでほしい……と思いつつTutorialを見たら、idea：Mikeとあって絶望した。ナマ言ってすいません……。EFは明らか（と言って、Eでサンプルが合っていないことに気づかず提出してしまったが）。

昨日、明日の昼間に食事する予定だ……と書いた。天気予報によれば明日は昼だけピンポイントで雨らしく、夜にしないか？という話が持ち上がっていた。冷静になると金曜日の夜はサークルがある。AtCoderのコンテストに気を取られて、その時間も予定があることを伝え忘れていた！結局、昼に雨が降っていたら延期ということになってしまい、かなり申し訳なさがある。

布団に移動し、昔読んでいたなろうを少し読み返した後、今日もラノベの積読を減らした。

「きみは本当に僕の天使なのか」。よかった。特に主人公の言動がずっと一貫していて、非常に好ましい。ヒロインは主人公の推しのアイドルであり、アイドルを応援することを常に念頭に置いていたという感じ。しかしそのように一線を引いた状態ではこの先どう仲が深まるのだろう、と思っていたが、ラストではオフのヒロインを別枠として捉えることで次巻以降の進展を予感させる形になった。このラノベは「ひげを剃る。そして女子高生を拾う。」の作者さんの新作で、僕はそちらは読んでいないのだが、最近TLでよくおすすめされている。

「日本語が話せないロシア人美少女転入生が頼れるのは、多言語マスターの俺1人」。なろう書籍化。ロシア語要素に反応したふぁぼん氏が言及していたが、「時々ボソッとロシア語でデレる隣のアーリャさん」とは異なり、こちらはテンプレートなざまぁ系で受け入れられなかった様子。ロシア語要素もあってないようなもの（とにかく言葉が通じなければなんでもよい様子）だった。しかし僕としては、ざまぁの前振りが重かったりしたものの、主人公無双と同じ感じでかなり面白く読めた。

日記を書いてから院試ゼミの担当の問題を読む。今回はかなり簡単な問題にあたっているようで、1問を残しすぐ方針は浮かんだ。午前5時に就寝。

07/30(金)

午前11時前に起床。いい感じに晴れているようなので、予定通り昼に集まることにする。

地下鉄で行こうとしたが、僕の家も集合場所も地下鉄の駅から微妙に離れているため、実は歩いたほうが早いのでは？と考え、今日は歩いてみた。結果としては、地下鉄のダイヤによっては歩いたほうが早くなることも十分ありうると感じた。歩いている間は昨日解き残した院試の問題を考えていた。

集合時間になると天気予報の通りに雨が降り出してしまったが、アーケード街なので集まってしまえばこちらのもの。北京餃子という店で昼食を摂ることになった。僕も行くのは久しぶりな気がする。食事を終えた後もしばらくテーブルで喋っていた。マスクはつけていたものの、声が大きくなってしまっていたらしく、途中で別のお客さんに注意されるということがあった。

店を出ると、すでに雨は止み、日差しが強くなっていた。2時間かそこらで雨が止むというのも天気予報通りであった。本屋を2件ほどめぐった後、話の流れで僕の部屋に行くことになった。溜めに溜めた積読を見せたり、パソコンの環境を紹介したりした後は、みんなで院試ゼミの問題に取り組んでいた。僕の担当の問題で最後に残ったものについて、実は昼食の後喋っている間に着想が得られており、それを紹介していくらか検証してもらったが、どうやら合っていそうで一安心。最後の詰めの部分はぼんやり考えていたものより良い方法を紹介してもらい、非常に参考になった。

僕は途中でサークル解説会の準備・ホストのため少しパソコンに向かっていた。ゼミの友人と喋るのが楽しすぎて解説会の準備が少しおろそかになってしまった感じがある。解説会の最後で、次のABCからは8問体制だが特に変わりなく行うと宣言したものの、よく考えると来週から8月なので普通は夏休みなのかもしれない。さらに言えば僕は院試2週間前なのかもしれない。とりあえず次々週からしばらくはお休みにしよう。

さらにサークル解説会から間を置かずyukicoderがあったので、それにも参加した。みんなにも1問紹介して一緒に考えたり（ちゃんと考察を言わないようにお願いしていた）したが、そろそろいい時間だということで、みんなは午後9時過ぎに帰っていった。このご時世にこういうことをするのは何となく危ない感じもするが、みんなずっとマスクをつけっぱなしでいてくれたこともあり、楽しい思いのほうが強い。

さて、yukicoder 307の話に戻る。結局7完だった。面白かった。作問者はサークルメンバー。東北大学の次世代が順調に育っており未来は明るい。

yukicoder contest 307 - yukicoder

Aはソート。Bは数字ごとの寄与に分解する。複数ある同じ数字もすべて区別することにしておくと考えやすかった。Cは上の桁から再帰関数で決めていく。Dはmodと使った数字を持つdp。Eがみんなで考えた問題だが、実のところかなり見覚えがある。2つの数字のswapをいくらか実験してみると、9掛ける何かという形になっていそう。ということで、（すべて同じ数字である場合を除き）最大公約数の候補は少なく、すべてチェックできる。チェックの際は適当に1つ整数を構築して割り切れるか調べれば十分で、これはmodを持つ行列累乗で可能。

ここで詰まったが、何とかさらに2問解けた。Fは下の桁から決めていくと枝刈りできて、かなり高速になった。Gは無理やり半分全列挙し、定数倍高速化を頑張ったら通ったものの、想定解も半分全列挙だったので、どこで定数倍的に差がついたのかわからない。Hはあまり考えていない。

ちょっと時間をおいて、ECR112に出た。5完。

Dashboard - Educational Codeforces Round 112 (Rated for Div. 2) - Codeforces

Aは、どのようにピザを買っても1切れ当たりの値段が同じなので、結局6と8と10を組み合わせてちょうどの値を作れるかという話になる。2で割れば3と4と5になって、3以上は常に作れるとわかる。Bは見るからに嫌だが、縦と横を独立に考えてよくて、高さを足して収まるならば並べる順序2通りを考える、横についても同様、ということで4通りしか考えなくてよい。CはAliceの行動を全探索する。Dは3文字しかないのでabcabc...というふうに長さ3の周期になるしかない。6通りについてどれだけコストがかかるか累積和で計算しておく。Eは尺取り法+遅延セグメント木。

Fが解けない。木である間はよくて、初めてループを作る時も重み付きUFと同じ感じでXORを管理しておけるので判定可能。2回目以降のループが曲者で、すでにループに使った辺を含むようなループは作ってはいけない。この判定ができず、結局解けないままコンテストが終了した。

コンテスト後のTLでFがHLDというような話を聞き、非常にEducationalであることだなあと思っていたが、それがなくてもオイラーツアーで解けるらしい。というのも、ループを作らないような辺の追加についてはループと関係がないため、先にすべて処理できる。これで最終的なグラフの形が木として得られるので、オイラーツアーをしてから改めてループを作るような辺の追加について考えればよかったらしい。非常に頭がいい。

解法に感動したものの、異常に眠いため、upsolveを諦めて布団に入る。布団に入ったらすぐ眠れるはずだったが、何となく眠れなくなり、ラノベを読んでいた。午前6時半就寝。

07/31(土)

午後7時起床。食事したりシャワーを浴びたりした後、ABC212に出た。今回から8問体制。

AtCoder Beginner Contest 212 - AtCoder

7完。今回は速度重視で、コードゴルフをせずに駆け抜けたつもりだったが、純粋にHが解けなかった。

AはAWK。Bは言語選定から非常に迷い、Rubyを使った。CからはC++。ソートして要素ごとに二分探索。Dはpriority_queue。Eは最初包除原理のつもりで書いていたが、普通に遷移が計算できることに気づき、書き直しの手間が発生した。Fは非常に面倒。あるバスに乗っている状態からスタートし、2k本先に乗るバスをダブリングで計算しておく。クエリに答えるときは、まず最初に乗るバスを計算し、次にダブリング配列を見ながらBIT上のような二分探索を行う。ダブリング配列の計算で余計なことをしており1WA。

Gは位数の総和を求めたくなる。P=7で表を作ってしばらく眺めていると、原始根というものの存在を思い出した。原始根で言い換えると、指数とP-1との最大公約数が気になるということになり、指数は1\dots P-1のすべてを渡るため、結局1+\sum_{r=1}^{P-1}\frac{P-1}{\gcd(r,P-1)}が答え。\gcdが同じ数をまとめたくなってLCM Rushの解説を見たりしていたが、結局1012以下の高度合成数が約数を高々7000個弱しか持たないということから、2乗かけて計算することにした。

Hはアダマール変換までたどり着いたが、f+f^2+\dots+f^Nを求める方法がわからず解けなかった。普通の畳み込みと同じ感じで乗法逆元が計算できるのではないかと思ったが、そんなことはないどころかXOR畳み込みは一般には乗法逆元を持たないらしい。

Cは要素を混ぜてソートし、隣接する2要素が別の列から来ているか確認する方法がある。Fは乗るバスが時間が進むにしたがって合流していって、最終的に根付き木になるので、UFなりマージテクなりで答える方法もあるらしい。

コードゴルフ。Aはdcだが、0=などするより割り算して0割りで場合分けするほうが短くなる。Bは、最初AWKで1234567890123~$1をチェックする方針で書いたが、テストケースに入っているのが0123、3456、7890、8901、9012だけのようなので、うまいことまとめてsedで判定すると短くなった。CはOctaveのlookup関数が強い。DはPythonで、場合分けがインデントありのif-else→三項演算子→orによる短絡評価、と短くなってきている。EはCrystalでないと通らないらしい。Fは手つかず。

Gは、まずコンテスト中の解法で縮めていた。約数列挙はこれまで\sqrt Nまで見てから重複を削除していたが、i\rightarrow\left\lfloor\frac{N}{\lfloor \frac N i\rfloor+1}\right\rfloorとすることで約数の候補を降順に列挙できる。あとは実際に約数かを確かめれば、簡単に降順・重複なしの約数リストが得られる。リストを作らずにその場で計算をするとさらに短くなる。が、今回の問題では素因数分解と数論的関数を利用したさらに短い解法があるようだ。これを実装し、さらにVimに移植するとかなり縮んだ。

Hのupsolveをする前にTCO21 R4に出た。

TopCoder Statistics - Match Overview

Easyの1完で52位、レートは2575→2535(-40)。

Easyの問題文がTCO21 R2Aと同じ感じでカスだった。これ本当にオンサイト前最後の予選に出す問題か？

Easyはカス。問題文が5400文字くらいある英文で、題意を把握するのにかなり苦労した。

週記（2021/05/17-2021/-5/23） - kotatsugameの日記

問題文を自分なりに要約してみた。

52枚のトランプがあり、最初はすべて裏向きになっている。大まかに3等分し、真ん中の山の上からX番目を確認してもらった。真ん中の山の上下をひっくり返し、そのまま3つの山をもとの順に積み上げる。

リフルシャッフル（大まかに2等分し、両手に持ってだいたい同じペースでテーブルに落としておおよそ交互に積み上げる）し、全体をひっくり返し、上から任意の枚数選んでそのままの順序で下に重ねる操作を1回行う。

トランプをテーブルに広げる。このときの裏表入り混じった状態と値Xが与えられるので、確認してもらったカードがどれかを90%以上の確率で当てよ。

ここで、「大まか」とか「だいたい」という言葉を使った部分は、テストケースを作るときに正規分布に従う乱数を発生させてシミュレートされる。このことは問題文にあるリンク先に飛ばないとよくわからなかった、というのも辛いポイント。Xがかなり小さいことに注意すれば解法は簡単で、表向きのカードがたくさん連続している部分を検出すればうまく判別できる。乱数は正規分布に従うので、そうひどいことにはならない。

Medは「Nの倍数であってB進数として見たときに同じ数字が表れないような数」のうち2番目に大きいものを答える問題。B\le 10くらいまでは全探索できるが、B=11,12が困った。昨日のyukicoder Gみたいな半分全列挙だと思ったが、計算量がよくわからないし、実装する時間もなかったため、結局解けず。

ABC212-Hのupsolveをした。アダマール変換に限らず、フーリエ変換でも数論変換でも、和や積に線形性があるらしい。なので、f+f^2+\dots+f^Nが知りたいなら、アダマール変換した後に各点でa+a^2+\dots a^Nを計算し、逆変換すればよいらしい。ここで変換には係数がつく。この扱いに納得いかずしばらく考えていた。係数を逆変換に全部押し付けることで、変換後の世界で線形性が成り立つようにできるという仕組みとして理解した。コードゴルフとしてすでにRubyコードがあったので、縮めておいた。

過去のRubyコードに適用できる更新がいくつか見つかっていたので、探して縮めたりしていたら、朝になってしまった。布団に移動して眠気が来るまでラノベでも読んでいよう、と思ったら、面白すぎて最後まで読んでしまった。

「時々ボソッとロシア語でデレる隣のアーリャさん」2巻。非常に良かった。最初のほうはこのシリーズ1巻がどういう文章のノリだったかを忘れており、ちょっとついていけない部分もあったが、読むうちにストーリーに引き込まれた。最後のシーンに向けての流れが生まれたあたりで、あまりに気になりすぎるため寝る前に読み切ることを決意。実際、期待以上に盛り上がってとても面白かった。主人公の妹は、今巻でも1人深く関係するキャラクターが出たものの、特に掘り下げられていない感じなので、次巻以降が楽しみ。

このラノベ、1巻が売れに売れたらしい。確かに最近ラノベの何らかのランキングを見るといつも名前が挙がっていた気がする。ロシア語要素はともかく、素直に面白いラノベであることは文句なく認められる。

午後1時半就寝。

08/01(日)

午後3時半起床。院試ゼミが午後3時から予定されていて、1時間半なのでいい感じに1周期で起きられないかと思ったものの、あまりの眠さにしばらく布団に突っ伏して動けなかった。しかし自分から参加したゼミを自分で休んでいては世話がないため、気合で布団から這い出した。

ゼミ自体は特に何事もなく終了。土曜日にワクチン2回目を接種した人が2人いて、ちょっとばかり辛そうな感じもあったが、思ったより元気らしい。まあ本人の自己申告であるため、実際のところはわからない。

昨日のコードゴルフに更新があった。DはPythonの場合分けをどのように行うかで縮んでいったが、比較演算子のチェインを短絡評価目的で使うのがさらに短いらしい。それと、1行目もクエリとして処理してしまうことで結構縮んでいた。

EのCrystalはまた知らないメソッドが出てきて縮んでいた。単項-が.-でできるらしい、というのはともかくとして、.uptoや.downtoをまとめた.toというメソッドがあるらしい。しかも、そういうメソッドの引数として括弧をつけなくても動く場合があるようだ。

atcoder.jp

HIKAKIN TVに「ウ”ィ”エ”」を再現した動画が投稿されていた。7月でHIKAKIN TVが10周年なので8月はすごい動画をたくさん予定しています、ということが告知されていて、これはその1本目らしい。HIKAKINが何を思ってこれを投稿したのか知らないが、おふざけ一切なしの異常なまでの完成度で感動した。確かに信じられないくらい力が入っている。

7月の読書記録をツイートした。ちょっとは本を読んだが、それ以上に買っていて積読はかなり増えた月だった。

信じられないくらい眠いが、寝る気にもなれないので、YouTubeを見たりしながら頑張って日記を書いた。そういえば先週ホスフィンに「日記のうちコンテストの感想だけ隠しておけばどうだ」という提案をされており、一理あると考えていたのだが、改めて文章を見返すとコンテストの感想とそうでない部分とがちょっとばかりあいまいなように思えたので、うまく区切ることができなかった。

AtCoderをクロールして最短コードを一覧にして保存している。気が向いたらクローラを起動して、3000問以上の問題をクロールし終わるまで見守っていたものだが、前回のクロールから1か月くらい経ってしまうと情報が古く感じられてしまうため、以前から定期的に実行するようセットアップしたいと考えていた。今日はその一歩として、atgolferを動かしているサーバでクロールできるように環境を整えた。

クローラはRubyで書いたので、Rubyの環境を構築する。yumで入れると2.0.0という信じられないくらい古いバージョンが入るどころか、必要なライブラリも入れられなかったので、rbenvを使って再チャレンジ。無事2.7.4とNokogiriを入れることができた。NokogiriはPythonでいうBeautifulSoupで、つまりHTMLパーサ。なぜそんな感じの名前がついているのだろう……。ともかく、これで実行できるようになった。

次にクローラを手直しする。atgolferと同じサーバからAtCoderにアクセスする以上、連続したアクセスは避けたい。そのような場合、リクエストを送るためのメソッドを定義して、そこで適当にsleepさせるのが簡単だと思われる。これはatgolferのコードを読んで学んだこと。timeoutも設定しておいてコードは完成。さらにシェルスクリプトを書いて、ファイルのバックアップを取ったり自動でGitHubのほうに上げたりするところまで一発で済ませられるようにしておいた。

あとは相対パスを絶対パスに直すかcdを挟むかしてcronに登録しておけばよさそう。ただ、今は1回クロールが完了できるかチェックするという意味で、素のまま動かしてみている。実行ログをteeでファイルに取りつつ眺めるつもりだったが、なかなか表示されずにやきもきしていた。出力バッファをflushすることで解消され、今のところちゃんと動いているように見える。ネットワークの遅延のほかにも、以前Zlib圧縮されたコードを読もうとしてエラー落ちしたことがあって、再発しないか不安。

atcoder.jp

自作の最短コードクローラがこのコードをcsvファイルに書き込もうとして、落ちた。

週記（2020/08/10-2020/08/16） - kotatsugameの日記

週記（2021/07/19-2021/07/25）

07/19(月)

午後3時くらいに目を覚ます。TLにチュウニズムのアップデート情報が流れてきた。8/5の更新で、CRYSTALのマップ全部とイロドリミドリのマップが1つ消えるらしい。CRYSTALはラスボスのマップが残っていて、イロドリミドリのマップは手つかずなので、都合1500マスくらい走る必要がありそうだ。非常にまずい。

先週のARC123Cについて、実は操作回数は最大でも5回らしい。かなりびっくり。僕は60回で見積もって、これだとちょうどlong longに詰め込めるから簡単で、うまい問題だな～と思っていたのだが……。

TLを眺めたりYouTubeアプリで動画を見たりした後、また寝た。次に起きたのは午後9時だった。

昨日投稿した色変記事にかなりアクセスされているようで、今日だけですでに700回くらいアクセスされている。これで週記も投稿できていれば、合わせて1日で1000回アクセスくらい達成できたのかもしれないが、書きあがっていないものはしょうがない。しばらくTwitterでエゴサーチなどした後、溜めていた分を書き始めた。

AtCoderのコンテストについて書く段になり、本当は当時の順位表など参照したかったのだが、ちょうどAtCoderのメンテナンスが始まっており、見られなかった。仕方なくTwitterや録画していた画面キャプチャから情報を補完して書いた。

午前4時くらいになってようやく書きあがり、投稿。先週も20000文字を超えてしまった。確か初期の週記は10000文字に満たないくらいだったから、1年で文章量が2倍になってしまったということ。一応人に見てもらうことを前提に書いているのだから、無理なく見てもらえるような分量にしなければならないのだが、解いた問題のコメントだったり、こういうその時考えていたことをネチネチ書いていたらどうしても増えてしまう。

午前5時を待たず、AtCoderのメンテナンスが終了した。ACLのアップデートが本題だったようだ。このアップデートによって使えなくなったゴルフテクが存在する。

ACLのデータ構造の宣言について、コンストラクタ呼び出しがあたかもint型かのように代入で行えることを知った。

週記（2021/07/05-2021/07/11） - kotatsugameの日記

以前のバージョンでは、ACLで定義される構造体のコンストラクタにはexplict指定がなかった。それで、int型を代入することで暗黙的な型変換のためにコンストラクタが呼び出されていた。バージョンアップでexplict指定がなされたため、そのようなコンストラクタ呼び出しをするコードはCEになるようになった。つい最近知ったゴルフテクだし、実際に使われたものとしても、探した中では以下の5月初めに提出されたコードが最古だから、かなり寿命が短かったテクである。

atcoder.jp

朝方、色変記事に追記する作業をしていた。ありがたくも寝ている間にまた質問がたくさん寄せられたので、それらへの回答を追加した。

実は7/20が提出期限の期末レポートがある。僕の感覚としては月曜日だから7/19なのに、実際はあと14時間もないというバグ。数理統計学のレポートで、自分の関心と数理統計学との関連で自由に論じよ、という課題。書くことは一応ぼんやりと考えていた。コンピュータで正規分布に従う乱数を生成する方法だ。僕が知っている疑似乱数生成の方法は、どれもある区間の整数を一様分布に従って生成することしかできない。よく考えると、浮動小数点数もbit列なのだから、整数を生成するのとfloatやdoubleを生成するのに大した違いはないかもしれないが、どちらも一様分布であることに変わりはない。

GCCのヘッダファイルを覗いたところ、std::normal_distributionの実際の実装は、手元のGCCでもGitHubのミラーでもbits/random.tccにあった。実際のところ、そんなことしなくてもcpprefjpに「マルサグリア法を使う」と書いてあったのだが、念のため確認した。

gcc/random.tcc at 16e2427f50c208dfe07d07f18009969502c25dc8 · gcc-mirror/gcc · GitHub

std::generate_canonicalという、整数を生成する乱数生成器を受け取って[0,1)の浮動小数点数を返す関数が使用されている。これも興味深い。実装を読んだところ、2進数の桁数を指定すると、それを下位桁から埋めるように整数を生成してはめ込んでいくようなアルゴリズムらしいが、ここまで行くともはや数理統計学とは何の関係もないし、割愛した。

マルサグリア法の細かい話を書こうとしたが、眠くて頭が働いていないのか、理論的な話が全然分からない。いったん寝て、また明日レポートを仕上げることにした。午前2時就寝。

07/20(火)

午後8時起床。レポートの続きをする。

マルサグリア法は、0\lt x^2+y^2\lt 1を満たすような-1\lt x,y\lt 1を生成したとき、X=x\sqrt{\frac{-2\log(x^2+y^2)}{x^2+y^2}}とY=y\sqrt{\frac{-2\log(x^2+y^2)}{x^2+y^2}}がそれぞれ標準正規分布に従うというアルゴリズムである。これを理論的に示すには、講義ではやっていないはずだが、この記事にある感じの計算をすればよさそう。

2次元確率分布の変数変換（計算してPythonで確認）

x=\frac{X{\rm exp}\left(-\frac{X^2+Y^2}4\right)}{\sqrt{X^2+Y^2}}、y=\frac{Y{\rm exp}\left(-\frac{X^2+Y^2}4\right)}{\sqrt{X^2+Y^2}}となる。かなりゴツい形をしているが、実際にこれでヤコビアンを計算してみると、いい感じに\sqrt{X^2+Y^2}が消えてくれて-\frac 1 2 e^{-\frac{X^2+Y^2}2}となった。

絶対値を取ってXとYに分離すると、Xに対しては\frac 1{\sqrt 2}e^{-\frac{X^2}2}というような形になる。これはかなり標準正規分布に近いが、微妙に違う。\frac 1{\sqrt\pi}の違いは、おそらく0\lt x^2+y^2\lt 1という条件を考慮していないことによるものだろう。では実際はどのように計算すればよいのか、とWikipediaを読んだところ、実はボックス=ミュラー法という別のアルゴリズムを高速化したものだったということを知った。そちらを経由して示すべきだったということか。

しかしもうレポートを書くのが面倒になってきたので、計算したら合わなかったということを書いて終わらせることにした。最後に、疑似乱数の話ばかりしていたので、真の乱数である/dev/randomにちょっと触れて終わった。環境ノイズを収集して真の乱数を得るという話は面白くて好きであるが、中身は全然知らない。

しばらくコードゴルフをした後、日付が変わってからTCB38に出た。ちょうどこの時間からだった。いつものように、この週記が公開される前にイベントが終了しているため、結果を書いておく。

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

今回も理論値を達成することができたが、序盤かなり失速してしまった。数え上げというテーマからもわかる（？）ように、どうせmodintをしこたま使うので、最初から貼りっぱなしでやっておけばよかった。1問、modpowを自前で実装してしまったのもかなりのタイムロスだろう。

4問目まではよい。5問目がmodpowを実装してしまった問題。制約が109と思ったより大きくてびっくりした。N=Kというコーナーケースもある。6問目はlong longで管理すれば十分収まる制約だが、そのことを確認するのに慎重になってしまい、結構時間を使った。19!\approx 10^{17}のようだ。7問目は余事象。8問目はちょっと面白かった。先頭からの累積和として出現した値を管理するbitDPになる。数列の長さは高々10。9問目はケイリーの公式を知っていれば一瞬だが、知らずに解けるものなのだろうか。10問目は木DP。畳み込みが出てくるが、2乗の木DPなので愚直に計算しても間に合う。というか、そこで畳み込みを使ったところで計算量的には良くならなそう。

今日も色変記事に質問と回答を追記した。もう新しく来る質問の数が少なくなったので、そろそろGoogleフォームを閉じるつもりだ。

朝方、院試ゼミの準備としてまた問題を解いていた。今回も2問担当するので、まずこれを解く。1問目は位相の問題で、嬉しいことに瞬殺できた。逆に2問目が全然わからない。しょうがないので頭の中で寝かせておくことにした。

日記を書いて寝ようとしたら、第7回PAST-Mのコードゴルフで更新が流れてきた。解いていない問題だったが、微妙にコードが目に入ってしまい、なんとなく使うアルゴリズムがわかってしまった。考えてみたら、案の定フローに帰着できた。コードゴルフについては、もうどこも縮まないかと思われたが、ふとnetworkxでNoneを頂点に使うことを思いつく。

networkxの頂点にはたいがい何でも使える、というのは知っていた。これまでは別の関数を使ったり、あるいはグラフそのものを使ったりしていたが、これらはどれも1Bかかってしまう。一方Noneは4Bだが、グラフにadd_edgeしたりadd_nodeしたりするとその返り値がNoneになるので、そのまま使うことで-1Bどころか、セミコロンを省けるのでさらに-1Bできる。これを利用して縮め、ほかに適用できる問題がいくつかあったので、それらも縮めておいた。

atcoder.jp

MultiDiGraphを使う問題では、add_edgeするとNoneではなく辺に割り振られたkeyが返ってくるようで、そこだけちょっと変える必要があった。結局これもadd_nodeが必要なNoneの個数分用意できたので、それらを使って思った通りに縮めることができた。

午前9時就寝。

07/21(水)

午後4時起床。昨日寝る前にゴルフした問題から1問縮められていたので、縮め返した。

夜、ホスフィンからリプライが来て、一緒に夕食を食べてゲーセンに行くことになった。午後7時くらいに外出。僕の自転車を止める場所を見繕いながらどこで食事するか相談していたところ、ホスフィンはイオン近くの道路の下にある駐輪場の話をしているのに、僕はイオンの地下にある食事処の話をしていると勘違いするというすれ違いが起きた。イオンの地下にも食べ物屋さんはあるということなので行ってみたらフードコートだったが、かまわずそこで夕食を食べた。

はなまるうどんの大を注文。実ははなまるうどんを食べるのは初めて。信じられないくらい多くてびっくりしていたが、実は丸亀製麺の大よりはなまるうどんの中のほうが多いらしい。なんとなく聞いたことがあるかもしれない。後悔しつつうどんだけはなんとか完食したが、取ってきたいなり寿司はホスフィンに食べてもらった。

午後8時過ぎからゲーセン。今日も閉店までプレイしていたが、入店時間が遅かったのでプレイ時間としては3時間くらい。ずっとマッチングしていたのであまり進捗はないが、チュウニズムのアップデートで削除される曲関係の、8/5から新規取得ができなくなってしまう称号を集めていた。

ラスト3クレくらい使ってMIRACLE RASHの1速フルコンに粘着、見事達成できた。ギリギリまで下げたフィールドウォールがかなり便利で、格段に見切りやすくなった。フルコン目的なので適当に擦っていれば取れるだろうと思っていたが、全然そんなことはない。エアーのタイミングも怖いし、そうでなくてもいたるところでミスが出る。結局普通にプレイした。

マックに寄ってポテトを食べる。明日はホスフィンとたいぺーと3人で家飲みをするつもりなので、ドンキでお酒を買って帰宅した。

あーだこーだーで重大な発表があったらしいということはゲーセンにいる間から気付いていたが、公式のツイートを見て詳しい内容を知った。ABCが8問体制とはびっくりである。

TLに小林賢太郎さんの過去のコントについての記事が流れてきたので、読んだ。これヤバいやつじゃないか？僕の抱いているラーメンズ・小林賢太郎さんのイメージとはそぐわないが、公演メインの活動に移る前、テレビでコントを披露していた時代のラーメンズのことはよく知らないので、実際そういうコントがあったのだろう。燃えそう。

今日開かれていたyukicoder 305を解く。

yukicoder contest 305 - yukicoder

Aはよくわからないが、貪欲に操作してよさそう。投げたら通った。Bは、存在しない素因数を掛けるか、どこかの素因数を1つ選んでいくつか掛け、約数の個数がちょうど2倍になるようにするかしかないと思っていたが、違った。素因数をいくつか選ぶ場合がある。しかし、存在しない素因数を掛けることで必ず条件を満たせるので、探す範囲は50倍くらいまでで十分。約数の個数を数えるのが難しそうだが、新たに掛けた数に含まれる素因数のぶんしか関係しないので、十分速く計算できる。

Cは疲れた頭には非常に辛い。頂点1と頂点Nから同じ回数だけ辺を辿り、最後に辿った辺のラベルを記録しておく。このラベルが異なるような辿り方を見つけたら、その間を適当に繋げば回分ではなくなる。3回くらいbfs→親を辿ってパスを復元、をする必要があって、変数名など気を使う必要があった。

今日ホスフィンと相談してきたので、それを参考に院試の問題に再挑戦する。小問が2つあって、1つ目は別の定理の証明を参考にすれば解けるんじゃないかという話だったのだが、それを調べようとしたら今解いている問題と全く同じ命題の証明が目に入ってしまった。背理法というワードが見えて、ちょっと考えてみると一瞬で解けた。

2つ目は解けない。1つ目を参考にするのだと思って、久しぶりに「点列による連続性の定義」とか「点列コンパクト」などを調べてみて、ちょっとばかり進んだかなと思ったが、ある所からパッタリ先が見えなくなった。問題を整理してみると、良さそうな定義などいろいろ生えてきていたものの、本質が一切変わっていないことに気づいて絶望。今日は諦めることにした。

寝る前に恐る恐るTwitterのトレンドを見ると、小林賢太郎さんが炎上していた。小学生のころからずっと好きだった人が批判されているのを見るのは本当につらい。問題のコントでは、ホロコーストは否定的な文脈で出ているが、コントによる「いじり」であるかと言われると、該当しないとは言えないだろう。もはや何を言っても炎上は収まらないように思われる。これからどうなってしまうのだろうか。YouTubeに公式で上がっているコント動画たちも消えてしまったりするのだろうか。

かなり落ち込みながら午前7時半就寝。

07/22(木)

午後1時起床。即座にゼミのZoomに入る。

Twitterのトレンドを確認すると、僕が寝ている間に小林賢太郎さんがオリンピック開会式のディレクターを解任されていた。昨日の今日であるから、信じられないほどの速さである。小林賢太郎さんのコメントも出ていたので、読んだ。オリンピックに携わる以上このような問題があってはならないだろうと、考えればわかるが、感情としては非常に悲しい……。

昨日のyukicoder Dを解いた。小さい盤面で実験すると、2進数表現と見て3で割ったあまりがGrundy数になるようだったので、実装してみたら通った。解説はbitの引き算で考えていてなるほどという感じ。

院試の受験票が速達で届いた。出願に成功したようだ。オンラインで試験することになった場合のため、家の環境に関するアンケートに答える必要があるようだったので、答えておいた。アンケート回答の締め切りが結構早くて焦る。

ゼミが終わってからホスフィンとたいぺーが家に来た。大学病院のほうまで出向いて食事をする。最初は焼き鳥屋さんに行くつもりだったが、2店見つかったうち片方は満員、もう片方は休みだったので、ラーメン屋に行くことになった。学生は麺増し無料だったのでお願いしたのがちょっと多かったが、おいしかった。

午後7時くらいに帰宅して飲み始める。

最初はホスフィンがハマっているという大喜利を3人で行っていた。ホスフィンがお題を考えてきてくれたので、小分けにしてGoogleフォームを作り、匿名で回答を投稿、みんなで確認するという形。大喜利はほとんど考えたことがないのでなかなか難しかったが、そこそこ良さげな回答が出てきて面白かった。自分と違う着眼点で答えているものは興味深い。

途中参考資料として動画を再生しようとしていたが、ノーパソから音が出ない（スピーカーがダミー出力しか選択できない）ことが発覚。ちょっと格闘してみたが直らなかったので、結局スマホで再生した。

途中、最近の睡眠不足が祟って少しだけ眠ってしまった。その間にノーパソのTwitterから勝手にツイートされており、涙。yukicoderが開催されていたので問題を見たが、全然頭が働かない。1問目は入力をそのまま出力すればよいように感じられるが、証明が付けられない。最短コードを見るとbashだったので、おそらくddだろうなと思い、それ以上はさすがに縮まないのでわざわざ提出する必要もない。

日付が変わったあたりで大喜利を終え、回答をTLに流した。

相変わらずノーパソから音が出ないのでもうちょっと格闘してみたものの、諦めてスピーカーをつないだ。以降、YouTubeやニコニコ動画でお互いの好きな動画を紹介しあっていた。午前1時半くらいにお酒がなくなってしまったが、その後もお茶などを飲みながら延々と動画を再生していた。感電MADとか、カロリーメイトのCMに使われたorangestarの新曲とか、ゆっくり実況とか。

僕はラーメンズのコントを1本再生した。公式チャンネルは最初から動画のコメント機能がオフになっているので、今の状況下でも安心して見ることができる。でも相変わらず初見の人にどれをおすすめするべきかがわからない。今の動画を紹介しあう流れなら短めのものがよいだろうと思って、今日も「受験」を選んだ。大体1年くらい前も同様の悩みを得て、この日は「受験」以外にもいくつか見せている。

あとは動画投稿サイトで各々の好きな動画を布教しあっていた。僕はラーメンズが好きなので、コントをいくつか見せようと思ったのだけれど、これといって心に決めていたものがなかったので、かなり迷ってしまった。

週記（2020/09/21-2020/09/27） - kotatsugameの日記

www.youtube.com

朝方、今度はたいぺーが布団で寝てしまったので、ホスフィンと喋っていた。大学生協で弁当を注文するのを忘れていたので注文し、その時にautocompleteが暴発するのを見せたり、相変わらず解けない院試の問題について相談したり。

午前5時半くらいにホスフィンが帰り、床で寝る体勢だったはずのたいぺーも復活して帰った。少し部屋を整えた後、布団に入ってラノベを読み、午前8時半に就寝。

07/23(金)

午後3時起床。即座に院試ゼミのzoomに入る。昨日まで考えていない問題が結局解けていないし、考えたことだけ発表するにしても解答を書いていない。ほかの問題の解答もスキャンしていないので、人の発表を聞きつつ済ませた。

オリンピック開会式についての続報が流れてきた。内容を精査した結果、問題がないものとしてこのまま行うそうだ。これはつまり、小林賢太郎さんの手になる演出が見られるということだろう。クレジット表記から彼の名前が消えてしまうことは悲しいが、彼の作品が世に出るのは嬉しい。しかしどちらにせよ、すでに引退し、さらにこのような事態になった以上、もう彼は表舞台には出ないのだろう……。

ゼミは良かった。僕が解けなかった問題は特別難しいらしく、大体みんな解けておらず黒い安心感を得た。一人の昔の解答を共有してもらい、みんなで読んだ。かなりうまい。僕は収束先の具体的な形が得られず困っていたが、背理法を使うことにすると収束先をそのまま文字で扱って矛盾を導けている。

ゼミが終わってからサークルの解説会の準備をした。ABC210。最初はF問題を扱おうとしていたが、準備時間が1時間しかなかったのでE問題に変更。今日はほかにD問題を解説してくれる人と2人で発表した。先週書いたGoogle Meetのリンクを固定する話は、今日からやってみた。リンクの生成自体はいつもと同じで、それをSlackのチャンネルにピン留めしておいた。

来週の解説会からは固定されたリンクで活動できるように準備しておきたい。

週記（2021/07/12-2021/07/18） - kotatsugameの日記

yukicoder 306に出た。3完。

yukicoder contest 306 - yukicoder

Aは正三角形を作ればよい。2等辺三角形3個に分解して面積を求めると簡単。Bはちょっと難しい。長さについてのヒストグラムで各色の棒を管理する。赤色の棒の長さを決め打つと、他2色で使ってよい棒の本数がわかり、前計算によって2色の棒の組であって使っていけないもの（長さの和が赤色の棒以下になる）の数もわかる。青色や緑色で赤色の棒より長い棒を使おうとすると、2色の棒の長さの和が赤色の棒より大きくなるため、この前計算は最初に全部やっておいても問題ない。コンテスト当時の僕は赤色の棒の長さを決め打つループの中でインクリメンタルに計算する必要があると思い込み、実装がちょっと面倒になっていた。

Cはたくさんの三角形で平面を敷き詰め、反射を直進に読み替えるテク。僕がこのテクを初めて知ったのは、確か高2の時に出た数学甲子園2016だったはずだ。数学甲子園の本選では毎年、与えられたお題に沿って各チームが数学の問題を作り、出来の良いものは前に出て発表することになる。この年に作られた問題の中に、反射を直進に読み替えるテクを使う問題があった。YouTubeで当時の動画を探してみたら、写っていた。以下のリンクを踏むと該当の箇所に飛ぶ。スクリーンにそれらしき図が映っているのが見える。

数学甲子園2016 ダイジェスト - YouTube

探している途中、動画の中に僕の後ろ姿が映りこんでいるのを発見し、懐かしい気持ちになった。のちに競プロ関係で知り合ったり認識した人も数人出場しており、こんなところでニアミスしていたんだなあと思った。

4問目は難しい。考えながら椅子で寝てしまったため、布団に移動。すぐさま寝ようと思ったが、なぜか微妙に目が冴えてきたので、ラノベを2冊読んだ。

1冊目は「サベージファングお嬢様」。数日かけて少しずつ読んだ。面白かった。いい感じの無双系。赤石赫々さんのラノベは読んだ限りどれも主人公の1人称視点で、特に主人公の設定上言葉遣いが普通とはちょっと異なる場合、地の文もそれに合わせた口調になるので、結構特徴的。このラノベでも、主人公は前世が傭兵ということで粗暴な男っぽい口調で、それが地の文に反映されていた。

2冊目は「ブラックな騎士団の奴隷がホワイトな冒険者ギルドに引き抜かれてSランクになりました」4巻。相変わらずキャラクターの名前をほとんど覚えていない。今回も無双してハーレム作っていたなあという感じ。

さらになろうを読んで、午前5時半就寝。

07/24(土)

午後3時くらいに目覚ましで起きる。生協の弁当を待つ。チャイムが鳴ったので出たら、母から送られてきた荷物だった。夏用のシーツ。

布団に戻って弁当を待ちながら寝ていたが、午後6時半くらいにハッと目覚めた。すわ寝過ごしたかと思ってインターホンを確認するも、宅配便以降の来客はなさそう。そこでふと思い当たった。今日は休日なので、生協の弁当配達は休みであった。もうちょっとぐっすり眠れたのに、と後悔。

色変記事の更新をする。数日ぶりで、いくらか質問が溜まっていた。じっくり悩んで回答していたら、ABCの時間になってしまったので、記事の更新ページをそのままにして出た。

AtCoder Beginner Contest 211 - AtCoder

全完8位。BCでWAを出していてやる気あるのかという感じ。

A問題は\frac{A+2B}3。dcで書く。Bは入力を全部読み、Perlの正規表現で4つそれぞれ含んでいるかチェックした。単語の末尾を/$/としていたが、文字列はまだ続く可能性があるので、/\n/である必要があった。1WA。Cは典型90問008でほぼ既出なので、そこから最短コードをコピペしてきて提出。典型90問のほうは微妙なテストケースハック（'r'が出現しない文字列は入力されない）がなされており、これで1WA。

Dはやるだけ。Eは結構考え込んだが、最終的にはBFSをした。サンプル3を見ると状態数が十分少ないことがわかる。Fは面倒そうに見えたが、よく考えると区間add・点取得で多角形の内部にいるか外部にいるかが判別できる。これはすべての多角形について同時に行えるので、解けた。多角形の点がどちら周りで与えられるか固定されていなかったので、x座標最小の点とその次の点を見て適当に反転したりした。

C問題が典型90問とほとんど被っていたのが話題になっていた。僕は、これはあまりよくないことだと思っている。典型90問を解いた人が得するというのは、典型的なテクニックを学べるという意味であるべきで、まったく同じ問題が出るという意味ではないはず。これに関し、Twitterでこういう↓意見を見た。このことで解けなかった人が不利益を被っているかというとあまりそうでもなく、典型90問がなくてももともと同じくらい解かれただろう、という感じか？これも納得はできる。が、やはり被った問題が最近過ぎるのも問題だろう。

コードゴルフをする。Aはこれでよい。Bは制約をよく読んでいなかったが、入力される文字列は4つで固定らしい。ソートして全体をマッチさせる正規表現を作り、両端を削るテストケースハックを行っていたが、入力に被りがあるかどうかを見るほうが短い。Vimの:sor uに取られて終わりかと思ったが、実はテストケースには4つ全部違う文字列の場合と2つが同じ文字列の場合しか含まれていないらしく、*をうまいこと使うと縮んでくれた。*dd*dd*で2行消し、残り2行の状態になるが、3つの*のどれかでマッチした場合は下の行、マッチしなかった場合は上の行にカーソルがあるので、それで場合分けできる。

atcoder.jp

Cも典型90問そのままのコードが現状最短。Dは適当にRubyで縮めた。EFは手つかず。

午前1時からSRM810に出た。コンテスト開始直前に次のような内容のメッセージが表示され、かなり不穏だった。

TopCoder Statistics - Match Overview

EMの2完と2Chalで14位、レートは2535→2575(+40)でhighest。これで今現在、AC、CF、TCの3サイトでレートの最高値を記録している。

Easyは難しい。{\rm clamp}\left(2\left\lfloor \frac{raceTime-1}{observationTime}\right\rfloor,1,observerCount\right)\times observationDistanceになる。最初は全部同じくらいずらすことを考えていたが、反例を見つけたので考え直した。2人の観測者をペアにして扱うと、observationTime+epsで2\times observationDistance進むことができる。

Easyに40分くらいかけたので真っ青になりながらMedを開いたら、既出でびっくりした。これ↓のメイン部分の問題になる。当時は計算量的によくわからない解法で通したが、その後改めて解説を読んで通してあったので、それを引っ張ってきた。ACLの遅延セグメント木はTopCoderではコンパイルエラーになるだろうと思ったので、自分の遅延セグメント木を持ち出し、ラムダ式をfunctionで受け取っている部分を関数に直したりしていたが、この作業は結構時間がかかった。幸いバグなく動いた。

atcoder.jp

Easyはサンプルがめちゃくちゃ弱いので、沢山落ちるだろうと思ってチャレンジフェーズもきちんと参加した。最初にノールック爆撃が行われていたようだが、幸い僕が開いた提出にはチャレンジされず、じっくり考えた結果落とすことができた。他に同じケースで落とせる提出を2つ見つけたが、片方は入念にチェックしている間に取られてしまった。合計で2Chal。部屋のEasyの提出13件の提出のうち、生き残ったのは5件だけだった。いろいろな解法があったが、上に書いた解以外はすべて落ちてしまったようだ。

色変記事の続きを書き上げて投稿。質問を受け付けるのは日曜日いっぱいにするつもりだ。

IOLの結果が出たらしい。今年は金賞が2人同時に出たということで、日本の言語学オリンピックもレベルが高くなったなあという感想。僕が出場したころは競技人口が少なかったため、なんとなくで国際大会に進めることになり現実感が湧かず、まともに努力できなかったどころか大会中も結構不真面目だった。今になっても後悔している。

小林賢太郎さんはオリンピック開会式の公式プログラムに寄稿していたらしいが、ディレクター解任を受けてプログラムの発売が中止になってしまった。その内容がTwitterにアップされていた。以下のツイートの文面はどうあれ、またこのような形であっても小林賢太郎さんが書いた文章を読めるのはうれしい。まあ、僕は結局開会式を見なかったわけだが……。

https://twitter.com/matsukaze1978/status/1418775167048687617

https://pbs.twimg.com/media/E7CAfV8VgAMSQ57?format=jpg&name=large

溜めていた日記をある程度書き、午前10時就寝。

07/25(日)

午後6時くらいに目を覚ました。

いい加減に冬用の布団を片付ける。布団カバーをはがし、シーツを昨日届いた夏用のものに交換し、洗濯機を回した。布団はクリーニングに出すべきらしいが、とりあえずクローゼットにしまっておく。布団を入れる袋に押し込んで、さらに天井に押し付けて無理やり棚に乗せた。毛布などがあるせいで幅が狭く、かなり苦労した。

ARC124に出た。人生初のUnrated ARC。結果は4完遅解きで、かなりひどい。

AtCoder Regular Contest 124 - AtCoder

Aはよい。制約のk_i\ne k_jが優しい。Bは上の桁から再帰するいつものやつだろうと思って実装。適当に投げたらTLEしたが、全部同じ要素になったらすぐreturnする枝刈りを入れたら通った。Cは1番目の要素の約数のペアを全探索すればよい。

Dを読んでわからなかったので順位表を見たら、かなり悪い順位でびっくり。B問題が明らかに遅い。考え直してみれば、作れる数の候補となるのはa_1とb_iのXORだけなので、全部試しても十分間に合うようだ。なぜ気づかなかったのだろう。悔しいので適当にRubyで縮めていた。

D問題に戻る。適当によさげなswapをすると1\dots NとN+1\dots Mの置換に分割されるので、お互いを使ってうまいこと当てはめてみた。サンプルがあったので提出するも、当然のようにWA。これをさらに2回行った。もう全然わからないまま残り15分くらいになったあたりで、急にもともとの列をFunctional Graphとして見るアイディアが浮かんだ。とりあえずループを検出してそれぞれ1\dots NとN+1\dots Mに含まれる要素を数えるコードを書く。片方しか含んでいないようなループの個数が重要なことはすでに分かっていたので、両方含むようなループの操作回数として手で試したループをもとにそれっぽい式をいくつか当てはめてみる。サンプルが合うものが見つかったので提出、AC。

BもDも初手が悪すぎた。特にBはそのまま突き進めてしまったのもまずかった。コードゴルフはBのRubyコードをもう少し縮めたあと、AをPerlで通したくらい。

Codeforces Global Round 15に出た。7完45位、レートは2850→2885(+35)でhighest。

Dashboard - Codeforces Global Round 15 - Codeforces

Aからちょっと悩んだが、冷静になるとソート後の文字列がわかるので、異なるインデックスを抜き出せばよい。Bもしばらく悩んでいた。勝ち抜き戦を行い、それが本当に全部に勝てるか確かめることで解ける。以下の問題と同じ。1度考えたが、求める選手の条件をよくわかっておらず棄却してしまい、再度正気に戻ってようやく解けた。

atcoder.jp

Cは円を適当に切り開き、空いている点をN-K個飛ばしで繋げばよい。これの最適性は、そのように繋いだ時すでにある辺と目いっぱい交差でき、また新たに繋いだ辺同士もすべて交差していることからわかる。交点の個数の計算はBITを用いた。Dは未証明だが、a_iの絶対値を取った後2つの異なる部分集合で和が等しいものがあればYES、なければNOとした。Eは難しい。k-1個のブロックに分割するとか考えていたが、ブロックの幅が問題。最終的には左から貪欲に\left\lceil\frac{n}{k-1}\right\rceil個ずつペアを作り、作れた段階でブロックを区切っていった。何を示せば正当性が言えるかよくわからなかったため、\left\lfloor\frac{n-1}{\left\lceil\frac{n}{k-1}\right\rceil}\right\rfloor個のブロックを作った後にまだペアになっていない要素が2個以上残っていることをプログラムで全通り確かめた。

Fは簡単。あるポータルにたどり着いたとき、それより前のポータルはすべてactiveになっているため、その状態でワープした後戻ってくるまでの時間は常に等しい。これは累積和やBITを用いて前から計算できる。

Gはそこそこ面白かった。2^N通りの01列がソートされることを確かめればよい。当然2^N通りあるが、各回の操作で新しく触れることになるインデックスの個数を計算し、そこに何個0を配置するかさえ全探索すれば、すべての状態をカバーできる。これは最大でも5^{10}\approx 10^7通りとなる。普通にシミュレートしていると通らないが、再帰関数で全探索しながらシミュレートを進めたり、情報を40bitに詰め込むことで1回の操作のシミュレートをO(1)で行えるようにしたところ、爆速になった。

Dの証明とEの証明をTLで見た。Dは、a_iを数直線の点の間に張られた辺だと思うと、必ず閉路が存在することからわかる。Eは、実は上のようにブロックを区切ると、全部でk-1ブロックになっているらしい。しかも作り方から、i（1-indexed）番目のブロックまででまだペアになっていない要素は高々i回しか出現していないため、残りk-1-iブロックにk-i個以上出現することになって、必ず最後までにはペアになれる。

TCB38が終わっていた。理論値は7人で、僕は合計32分19秒、2位と11秒差で優勝した。危ない……。

色変記事の最後の更新をし、Googleフォームを閉じた。最終的には109件の質問が集まった。非常にありがたい。

kotatsugame.hatenablog.com