04/15(月)

午後3時半前に起床。インターン先定例会に出た。

先週はセミナー準備に追われて進捗がなかった。セミナーが2回あったからなので、毎週こんなことになるわけではないはず……と言っておいたが、実際のところ今後どうなるのだろうか。まあどうなるというか、自分がどうするかの問題。

勉強会はコーディング時に使える便利ツールの紹介だった。VSCodeの拡張機能がメインだったので自分には関係ないなと思いながら聞いていたが、「GitLens」はかなり良さそうだった。GitHubのGUIからBlameを使うよりよほど高機能らしい。

解散後はずっと先週の週記を書いていた。日付が変わる前に一旦投稿し、その後さらに1時間ほど追記してUniversal Cup以外は埋まった状態になった。

その後朝方までかけてラノベ「凶乱令嬢ニア・リストン」5巻を読了。面白かった。前の巻を読んでいても感じたことだが、学院でのシーンがもうほとんど存在しない。さらには普段の生活範囲でのイベントすら粗方描かれ切ったのか、長期休暇で遠出した先での話が多く、そのため休みのシーンだけつまみ食いしているような感覚を覚える。このようにどんどん時間を飛ばしてもらえると主人公を幼少期から描くにあたっての中だるみを感じずに読める。「幼年期」「少年期」「青年期」など章ごとに時間が大幅に飛ぶのはこれの極北だと思っていて、見かけると興奮する。

今季の履修を決めた。博士課程では20単位取る必要があるが、そのうち16単位は研究と博論で自動的に埋まる。つまり残りの4単位だけ考えればよい。専門と近い話題の集中講義を見つけたので、今季はそれだけにすることにした。

またしばらくラノベを読んで、午前9時就寝。

04/16(火)

午後3時起床。ラノベを読んでいたら午後5時を回っており、慌てて大学に向かった。今日は午後6時過ぎから競プロサークルの新歓に顔を出すつもりで、その前に夕食を摂っておきたい。学食に着いたのが5限が終わる直前だったようでギリギリ混雑に巻き込まれず、急いで腹に詰め込んだらなんとか間に合った。

新歓の内容は非常に良かったと思う。まず新サークル長のnononさんによる競プロ、弊サークル、AtCoderの説明があり、続いてブラウザ上で動くアルゴリズムゲームをプレイし解説を聞いた。この解説パートは競プロ経験者でも満足できるものだったし、未経験者も雰囲気を知る手がかりとして参考になったのではないか。未経験者の本当の気持ちはわからないが……。

プレイしたゲームは前サークル長のsotanishyさんが作ったもの。長さ8の列を比較回数20回以下でソートする問題は、マージソート想定のところ、自分は挿入ソートで挿入先を二分探索して解いた。実用上は挿入操作が重くて使えないが比較だけなら簡単。比較回数も、天井関数を無視すれば $\sum_{i=1}^{N-1}\log_2(i+1)=\log_2 N!$ となり、 $N!$ 通りの並び方を区別するための理論的下界と一致する。

終了後、サークルメンバーや入部希望者たちとしばらく喋って午後8時過ぎに解散。山に登って先週金曜日に置き去りにしてきた原付を回収し、帰宅してからはラノベを読んでいた。

「S級冒険者が歩む道」2巻を読了。非常に面白かった。このシリーズは導入こそ追放モノで、1巻で決定的な決裂が描かれていたが、そこからじわじわと関係が改善された上での2巻だったし、自分も1巻を読んだ時の記憶をある程度失っていたので、ギスギスした感じが一切なく読みやすかった。主人公が自分の実力に自覚的だったり、正体を特に隠していなかったりと真っ当に最強の座にあるのも嬉しい点。

今週末が期限となっている博士研究支援プロジェクトへの応募のため、申請書を書こうとした。しかしまず必要となる研究計画書と向き合った瞬間、学振のときの辛さがぶり返してきて、手が動かない。修論の英訳修正に逃げ出した。

午前8時半就寝。

04/17(水)

午後2時半起床。外出して、クリーニング屋で先週預けたスーツを回収し、大学生協でいくつか用事を済ませた。用事というのは新幹線の切符購入、メガネのメンテナンス、学食で食事、ラノベの受け取り。

大学生協でも切符が買えることを知らなかった。当然学割の適用も可能なので、みどりの窓口に行くより近いし人も少ないしよっぽど良い。ただし店員が少し不慣れなので要望があれば自分でリードする必要がある。祖母の一周忌に向けた今週末の帰省の切符を買ったのだが、北陸新幹線に関する確認で少し手間取った。

メガネはレンズの留具の調整。リムレスなので着脱の際つるを開いたり閉じたりする力がすべてブリッジにかかり、外れやすくなってしまった。レンズも少し傷ついたし度も合っていないしそろそろ買い換えようかな……と考えていたら、新年度のキャンペーンで1割引だと聞かされたので、その場で新調することに決めた。帰省から帰ってきたら受け取る。

帰宅後は研究計画書と向き合っていた。あまり進まないまま午後9時くらいまで耐えたが、どうしても今日ゲーセンに行きたかったので、気分転換という理由をつけて出かけることにした。歩きながら作文していたら椅子でうずくまっているより進みは良かった。

今日は閉店まで13クレプレイ。捨てゲー込みなのでプレイしていた時間に比べるとクレ数は多くなっている。新曲を埋めた。「INTERNET YAMERO」EXPが、MVのぴょんぴょんしたダンスをエアー付きタップで再現していて非常に楽しかった。MASはノーツ数が多くて満足感があるが、かなり難しかった。

油そばを食べ、ドンキに寄って、日付が変わったくらいに帰宅。シャワーを浴びた後改めて申請書執筆に取り組んだ。

午前6時までかけてなんとか研究計画書と自己分析をでっち上げた。読み返すのは辛いためChatGPTに添削を頼んだが、かなり便利。ただし聞き方を間違えると要約されてしまう。必死に水増しした部分が一瞬で判別されてしまうと目の前が真っ暗になるため、注意が必要。自己分析については去年の学振で書いたものを一部流用した。振り返ってみると、研究らしいことを一つもしていなかった当時によくぞ1ページも埋められたものだと感動してしまう。

書類を先生に送り、1時間ほどラノベを読んで就寝。

04/18(木)

午前10時半起床。30分かけて布団から這い出し、原付で登校した。着いたときは空いていた学食だが、図書館で教科書を借りる一瞬の間に長蛇の列が形成されていて唖然。まだ2限が終わる時間ではなかったはずなのに……。仕方ないので購買でパンを買って食べた。

論文を読んで過ごし、午後1時からセミナー開始。今日は後輩の発表だった。用意してきた分量で足りるか心配していたので、どうせ途中で具体例を計算するよう言われるから足りるよとアドバイスを送ったが、今日はその計算が大変で時間を大幅にオーバーし3時間かかった。先生による発表はなし。

その後先生と一対一で修論の英訳修正に取り組んだ。途中学食に行きつつ6時間コースでかなり完成に近づいた。その場で確認しながら直していくと手っ取り早くて良い。英語での言い回しが全然身についていないことを実感した。そこを先生にカバーしてもらいながら書いたので、もう自分が最初に書いた文章は残っていないレベル。

その後研究計画書についてしばらく話し、日付が変わる直前に帰宅。

Yandex Cupの賞金振り込みが遅いなと思っていたら、ゆうちょ銀行への送金に失敗していたらしい。とりあえず、以前ダメと言われたPayPalが使えないか改めて聞いてみることにした。

Yandex Cup Payment
I'm texting you about the payment: we have sent the money to your bank account but last week we received this payment back. The reason is an internal policy of the bank. So now we need your another bank account details.

助けて～
— こたつがめ (@kotatsugame_t) 2024年4月18日

銀行口座よりPayPalに送金してもらったほうがお互い簡単かと思ったものの、そういう選択肢はないらしい。
週記（2023/12/11-2023/12/17） - kotatsugameの日記

少し日記を書いたあと申請書と向き合った。研究計画書を少し書き直してエッセイを2本生成。既存の研究領域を超えた発展のビジョンについて書かされ、完全無欠のポエムになった。ChatGPTに評価してもらったら明確なビジョン・論理的な展開・詳細が不足していると言われ横転。ポエムであることを見抜かれている。

ホスフィンにも見せたらコメントが返ってきた。彼も忙しいのにありがたい話。やはりエッセイがポエムすぎるとのことで、説得力を増すアドバイスをいくつかもらい、それに従って可能な限り修正した……つもり。サーベイが足りないのはどうしようもなかった。

先生に送って午前10時就寝。

04/19(金)

午後2時半起床。今日帰省する。新幹線の時間まではまだかなり余裕があるが、その前にゲーセンに行っておきたいため無理して起きた。

準備して出発。駅近くの丸亀製麺で食事して、ゲーセンで9クレ遊んだ。眠くて集中力がないしドライアイがひどくて目を開けていられず、成果はない。ただし今日はチュウニズムクエストを進めることが目的だったため、プレイさえできればそれで良かった。

アンパンマン像を撮り、午後6時半の列車に乗車。車内ではラノベを読んだりスマホを触ったりして眠気に耐えていた。

仙台駅を庇い石にされてしまったアンパンマン pic.twitter.com/tOaT2lMgv5
— こたつがめ (@kotatsugame_t) 2024年4月19日

長野駅で各駅停車の新幹線に乗り換え、ふと隣を見たら姉がいてびっくり。駅まで迎えに来る親の手間を減らすため列車は合わせたが、まさか指定席で同じ車両・同じ列になるとは思わなかった。

午後10時過ぎに帰宅し、申請書の提出作業を行った。その後食事と入浴を済ませ、少しだけラノベを読んで午前0時半就寝。

04/20(土)

正午起床。

昼食を摂ったあとは、実家に置いてある「お隣の天使様にいつの間にか駄目人間にされてしまった件」の4巻ラストと5巻冒頭を読み返していた。体育祭のシーンとその後でストーリーが大盛り上がりする箇所だが、主人公とヒロインのやり取りも面白いということを再確認した。最近の巻はそこが少し苦手、ということはつまり食傷気味なのではなく高すぎる糖度に拒否反応を起こしているらしい。

礼服に着替えて祖母の一周忌へ。祖母宅はこの1年でかなり片付けが進んでいた。古新聞が必要になったので引っ張り出してきたら、祖母が特別に保管していたものだった。自分の名前が載ったときのものもちゃんと残されていてしんみりとした気持ちになった。

一周忌 pic.twitter.com/687emBJU3D
— こたつがめ (@kotatsugame_t) 2024年4月20日

一周忌を終えて実家に引き上げたら、そのままの格好で会食へ向かった。と言っても出席者は我が家のみ。料理は写真にまとめてある。感想としては、品数が多すぎるの一言。自分以外に完食できた人はいなかった。特にローストビーフは冷たすぎて味もよくわからないし、余計だったかなと思う。

食事 pic.twitter.com/IwccoZu4Ud
— こたつがめ (@kotatsugame_t) 2024年4月20日

食事 pic.twitter.com/fmxzzEYQsJ
— こたつがめ (@kotatsugame_t) 2024年4月20日

帰宅してシャワーを浴び、午後9時からABC350に出た。

AtCoder Beginner Contest 350 - AtCoder

Aは……カス。ただでさえ面倒だしABC000というコーナーケースもある。特に制約の書き方も気づきにくさに拍車をかけていると思う。まあ他の簡潔な書き方は存在しないわけだが。Bはストーリーを読むと意味不明になるので歯医者とか治療とかはとっとと忘れるのがコツ。

Cは逆順列を管理するのが面倒なので、 $i$ の昇順に $i\ne A_i$ の間 $A_i$ と $A_{A_i}$ を交換することを繰り返した。出力の制約 $i\lt j$ には気づいていなかったが、このアルゴリズムだと自動的に満たされる。ラッキー。Dは連結成分ごとに頂点数と辺の数を数えて算数。Eはメモ化再帰すると $\left\lfloor\frac{N}{2^a3^b5^c}\right\rfloor$ しか出てこないやつ。

Fは括弧列を一旦パースすることで括弧の中身を右からも舐められるようにし、もう一回進む方向を持ちながら見る。Gは適当に根を固定したときの親が分かれば質問クエリに答えるのは簡単で、辺を追加する際小さい方の連結成分の親を愚直に再計算してもマージテクの逆で高速。

ノーペナ全完、3位。NibblesでAとBを縮めた。Aは $1\dots 349$ から $316$ と $N$ を取り除いた残りの個数の偶奇をチェック。Bは $1\dots N$ からリストのXORを使って更新していった。 $O(NQ)$ が通る制約で助かる。

しばらく日記を書いた後、午前2時くらいからは布団でラノベを読んでいた。「無能と言われ続けた魔導師、実は世界最強なのに幽閉されていたので自覚なし」4巻を読了。

あらすじに「アルスの実力はついに多くの民が知るところとなる」とあったからワクワクしながら読んでいたものの、思ったより多くなかった……。そのくせ主人公が持つ能力を知って求め暗躍するキャラばかり増えていくのだから大変。また主人公によるマッサージという謎の行動が頻繁に登場してかなりノイズになっている。お色気シーンのつもりなのだろうと思っていたが、それにしては中途半端だし、もしかして重要な伏線だったりするのか？

もう一冊手を出し、午前6時になってようやく寝た。

04/21(日)

午後3時起床。夕方までラノベを読んでいた。

夜は外食。帰りに本屋に寄ってもらい新刊を眺めていたら、宮内悠介さんの新しい短編集を見つけた。ラノベ専門サイトで新刊チェックをしていると、こうやって一般書を見落としてしまう。反射的に買ったが、単行本サイズなので帰省中に読み切ってしまいたい。

食事 pic.twitter.com/G8aZVhjThe
— こたつがめ (@kotatsugame_t) 2024年4月21日

帰宅して入浴を済ませ、午後9時からARC176。

AtCoder Regular Contest 176 - AtCoder

Aにかなり時間をかけてしまった。 $i$ 行目は $(i,i),(i,i+1),\dots,(i,i+M-1)$ に1を書き込めばよいな、という観察から一般化する方向性を間違えたらしい。長さ $N$ の順列 $P,Q$ を用意して、 $(i,j)\mapsto(P_i,Q_j)$ と見なすことを考えてしまった。一応これでも解ける。 $P_1\dots P_M$ と $Q_1\dots Q_M$ を適切に選べば必ず構成できる。 $k=0\dots M$ について、 $A$ のうち出現頻度上位 $k$ を取り除くと高々 $M-k$ 個しか残らないため、それに対応する $B$ を貪欲に詰めてもはみ出ない。

Bは簡単。まず $2^M\equiv 2^K$ を使って $N\lt M$ のケースに帰着する。この時点で $2^N\lt 2^M-2^K$ ならよい。そうでない場合 $M-1=K$ なので、最初から $\bmod{2^K}$ で考えればOK。

Cもすんなり解けた。重み $C$ の辺 $(A,B)$ があると思って条件を考えると、2本の辺が頂点を共有した瞬間1点確実に決まる。よって連結成分ごとに値がほとんど決定するようだ。さらに、残りは独立に考えられる。辺が残ると $P_A=C$ と $P_B=C$ のどちらかを選ぶ必要があるが、これはどちらを選んでも対称なので決め打って2を掛ければよい。あとは上限だけ気にする数え上げで、上限の小さい頂点から埋めていけば求まる。

Dはいい感じの考察ステップを踏めたと思う。まず求める値を $P_1\rightarrow P_2\rightarrow\dots\rightarrow P_N$ と移動したときの距離の総和と見なし、点 $i$ と $i+1$ の間を何回通るか数え上げる方針を考えた。これは $P\le i$ と $P\gt i$ が切り替わるタイミングを数えればよい。しかし法則性がわからなかった。

考察を簡単にするため $P_0=P_{N+1}=0$ を加えてみたのだが、そのキャンセル方法を考えているときに、端の値の数え上げならそこそこ簡単にできることに気づいた。これを2箇所同時に行うと $(P_j,P_{j+1})$ 自体が直接求まる。ただし遷移がシンプルでも状態数が $O(N^2)$ あるためまだ厳しい。ここで先ほどの2値化を適用すると4状態になり、さらに線型性から $j=1\dots N-1$ で同時に計算できる。

Eは $2^N$ 方針を考えていた。 $A_{\ast,j}$ の最大値となる更新を $X$ と $Y$ のどちらに適用するか決め打つ。そのとき、例えば $X$ に適用するなら、 $A_{\ast,j}$ を降順に並べたときどこまで同じく $X$ に適用するかを調整する問題だと思ってみる。するとその次の値が $Y$ に適用される最大値になるから、最終的な $X_j+Y_j$ がわかる。

さらに矛盾する調整も「列 $i$ のここと列 $j$ のここを選ぶとコスト $\infty$ 」と書けるから、燃やす埋めるで解けそう。実現のためには $Y$ のほうだけ真偽値を反転する必要があったものの、ともかく実際に書けた。頂点数 $O(NM)$ 、辺の数 $O(N^2 M)$ 、流量は $500N$ くらいになるだろうか。提出すると当然のようにTLEしたが、時間がなかったため最初に決め打つ $2^N$ 通りをシャッフルし枝刈りを加えて投げたら、1846msで通った。

5完13位。Eはそのまま燃やす埋めるになるらしい。してやられた。

午後11時半からはCF #940 div.2に出た。

Dashboard - Codeforces Round 940 (Div. 2) and CodeCraft-23 - Codeforces

Aは3本で1個作る。Bは $n=1$ のとき自明、 $n\ge 2$ のときは $x,k-x,0,\dots$ とし、 $x$ を $k$ 、または $k$ からあるbitを下ろしそれ未満のbitを立てた数とする。Cは $r=c$ とする回数を全探索。 $r\ne c$ についてはペアの作り方が2重階乗、白黒の置き方が2べきで求まる。Dは $y$ を決め打つ。 $y$ のMSBが $a_x\oplus\dots\oplus a_z$ で立っていなければよいが、累積XORに関する条件に書き換え、左右から累積カウントを求めれば計算できる。

Eはまず $C(i,j)=\binom{i}{j}\times(j-1)!=\frac{i\times(i-1)\times\dots\times(i-j+1)}{j}$ 。この値を $j$ で割ったあまりは、 $j$ が素数でなければ $(j-1)!$ のせいで0になりそう。素数ならウィルソンの定理から $(i-j,i]$ に存在する唯一の $j$ の倍数を $cj$ として $-c\bmod j$ になるので、 $i$ を固定したときの和をimos法で求め、その累積和を取ればよい。しかしサンプルが合わない。よく考えたら $j=4$ のときあまりが0にならない $i$ があった。それも追加したら通った。

Fはよくわからない。まず値に乱数を割り当て、総和 $\bmod{(10^9+993)}$ をmultiset hashとする。またオイラーツアーしたりLCAを求めたりして、パスのmultiset hashがBITにより $O(\log n)$ で求まるようにしておく。これが下準備。あとは値を半分に分け、片方だけBITに乗せてmultiset hashを比較することで、食い違う値の候補をどんどん絞っていった。計算量は知らない。F1は1500ms弱で通った。

$k$ 個見つかるまでもう半分も調べることにすればF2に拡張できる。しかし全然間に合わない。値の順番をシャッフルしたり、BITへの値の余計な積み下ろしを少し減らしたりして、pretestはなんとか4483msで許されたが、システスで落ちた。それもpretestに入っていたケースで落ちた。どうせHackされる暇なんてないんだからseedを固定しておくべきだったか。

6完7位。Fで2次元データ構造を使うと、値の積み下ろしなく特定の値だけ考慮するmultiset hashが計算できる。さらに、実は総和をそのままhashとして使っても良かった。色々高速化の余地はあったようだ。

ラノベ「家事代行のアルバイトを始めたら学園一の美少女の家族に気に入られちゃいました。」を読了。面白かった。主人公のスペックの高さから来る安心感がある。家事代行をバッチリこなすのは当然のことながら、家族からヒロインとの仲をからかわれてもそつなく返してかなりスマート。そのからかいも過剰なものではなかったりと、登場するキャラがみんな良い人柄で、読んでいて心地よかった。

日記を書いて午前5時半就寝。結局今週もインターンの稼働ができなかった。明日定例会の前になにかしたい。