11/11(月)

午後3時起床。半からインターン先の定例会に出た。今週末に国際会議の締め切りがあり、また来週その内容について学内で発表する機会があるため、それまで稼働は難しいと報告した。

勉強会は業プロにおける設計の話。自分がこれまでインターンで書いたコードだと、肥大化した部分を都度切り出して関数化しながら進めていたように思う。それで、最後の最後になって情報が足りないことに気づき、かなり奥のほうまで手戻りが発生することが多かった。つまり、そもそも入出力の定義をせず書き始めていたのが良くない。そこをちゃんと考えれば切り出し方についてもより良いものが見つかったりするのだろうか。

解散後は先週の週記を書いていたが、コンテストをいくつか穴あきにしたまま午後10時過ぎに早々と投稿して、preprintへの加筆修正に取り組んだ。国際会議に出すのだから、正確にはpreprintではなくextended abstractである。長いので日記では論文と言及することにしたい。

非常に眠かったので、ほとんど進まないうち午後11時過ぎには寝てしまった。

11/12(火)

午前4時半に目を覚ました。二度寝しようとしばらく横たわっていたが、このままでは無駄に時間を浪費するだけだと判断し、起きて論文の作業を開始した。昼過ぎに学食で食事する以外はぶっ続けで取り組み、午後5時にひとまず加筆部分が完成。メールで送った後、文章の校正を始めた。

眠くなってきたので午後7時半に就寝。ところが4時間くらいでまた起きてしまった。仕方ないので校正を再開した。

数値計算にSageMathを用いたので、適切に引用する必要がある。公式ドキュメントだと「このように表示せよ」というサンプルが置いてあるだけだったが、調べていくとBibTeXにおけるサンプルを提供しているページを発見。さらにDOIも載っていて至れり尽くせりだった。

https://doc.sagemath.org/html/en/tutorial/afterword.html#how-do-i-reference-sage

Publications_using_SageMath - Sagemath Wiki

自分が行った計算に関してしばらく考え事をして、午前6時過ぎ就寝。

11/13(水)

午前10時半起床。昨日寝る前に考えたことを反映して少し計算を行ったが、実行が遅すぎて使い物にならなかった。

昼前に学食の「bush clover café」に行った。コロナ前は朝食セットとしてパンケーキやフレンチトーストにコーヒーが提供されており、朝から大学に来たときはよく使ったものだった。コロナ禍の長い閉店期間ののち、飲み物とデザートのみで再開していたはず。食事まで戻ってきたとは知らなかった。……とここまで書いたが、食事の提供が再開したのはここ最近ではなさそう。単に忘れているだけかもしれない。

食事 pic.twitter.com/YEZRag6t0n
— こたつがめ (@kotatsugame_t) 2024年11月13日

購買に寄ったら森見登美彦「恋文の技術」の新版文庫本が出ていた。初版限定小冊子もついてくるため購入。この作品を最初に読んだときは意味不明で全く面白く思えなかったが、かなり経ってから再びチャレンジしたらいくらか機微を感じ取れるようになっており自分の成長を実感した、という思い出がある。

www.poplar.co.jp

帰宅してメールで届いたコメントを論文に反映。その後、来週使う発表スライドの準備を始めた。実は明日のセミナーで発表練習をする予定なのだが、まだ何一つできていなくて大変まずい。思ったより論文の加筆に時間がかかってしまった。

午後9時くらいに一旦できている分を先生方に送信。その後もスライド作成を続けたが、日付が変わるくらいに椅子の上でちょっと寝てしまったので、諦めて布団に入って就寝した。

11/14(木)

午前4時起床。スライド作成の続きに取り組んだ。午前11時過ぎに何とか完成。この午前中はTLに興味深い話題が二つほどあって、スライドと格闘している間チラチラ確認していた。

一つ目。AGC070のコンテストページが公開された。当初は開催日が12/22となっており、ICPC横浜大会と被っていた。帰るのは間に合わなそうなので後泊することを検討していたが、幸いすぐ一週間ずれて12/29になった。ただし今度は中学の同窓会と被っており、悩みものである。

二つ目。チュウニズムのアップデートがあった。隠し曲でついにLv.15+が出たのは実力的に縁遠い話で、自分は同時に追加された「What's up? Pop!」がniconicoジャンル初のLv.15になったことに驚いた。せっかく少し前に「マシンガンポエムドール」のAJを捻り出したところだが、ジャンルAJフィルはこれで剥奪だろう。それはそれとして、好きな曲なので来てくれて嬉しい。

正午、登校。昼休み中の学食は信じられないくらい混んでいた。友達と話しながらゆっくり食べた後、時間があったので院生室に寄って立体四目ならべで対戦した。お互い何度かの待ったを発動し、最終的には自分が詰んで終了。終盤は自発的な勝ち筋がなくなってしまい、置いても負けないマスがいくつあるかという問題になるらしい。

午後1時半からセミナーで発表練習。スライド完成がギリギリだったので当然原稿など何も用意していない中、英語で発表する必要があり、大変なことになった。単語や表現が全然出てこなかったので、そういうものを準備する意味でも来週までにはちゃんと原稿を書いておく。できたら留学生が校正してくれるらしい。

スライド中の文章についていくらか改善してもらい、午後3時半くらいに解散。1時間ほど院生室で時間を潰して今度は5限に参加した。予定されていた発表に入る前の雑談から発展して、今日は学部4年生が多様体、微分形式、テンソル積について話してくれた。資料もなしによくぞあれだけ説明できるものだ。これが午後7時まで続き、本来の発表は次回にずれた。

学食で食事して院生室へ行ったが、今日は麻雀をする面子が足りない。すぐ帰宅することもなく、知恵の輪を解いたり立体四目ならべで対戦したりして午後10時過ぎまでダラダラしていた。知恵の輪はガチャガチャしていたら一つ解けたのに今度は戻せなくて、片手落ち。

帰宅後、論文をちょっと直して国際会議に投稿した。日付が変わる前に就寝。

11/15(金)

午前6時に目を覚まし、カクヨムを読んでいた。午前10時から3時間ほど二度寝。起きたら論文に関してちょっとしたコメントが届いていたので、修正して再投稿した。

久しぶりにゲーセンに行くか迷ったが、まだ寝足りないこと、論文の修正があったら即対応する必要があることを理由に今日はやめておくこととした。代わりに明日行くつもり。

布団に戻ってカクヨム。「【悲報】お嬢様系底辺ダンジョン配信者、配信切り忘れに気づかず同業者をボコってしまう～けど相手が若手最強の迷惑系配信者だったらしく動画がアホほどバズって伝説になってますわ!?」を読了した。

これは先週読んだラノベのWeb版で、正確には書籍化していない部分だけ読んだが、やはり面白かった。高すぎる主人公の実力にイベントが徐々に追いついてきて、ちょうど今ギリギリソロで活動できる範囲の話が一段落ついたところ。すると次はコラボでの活動が始まるらしい。話の転がし方が上手いと思った。

kakuyomu.jp

午後7時から2時間ほど、三度寝。午後9時半からCF #987 div.2に出た。

Dashboard - Codeforces Round 987 (Div. 2) - Codeforces

書く

www.youtube.com

ハーメルンを読んだりYouTubeを見たりしてダラダラ過ごし、午前5時過ぎ就寝。

11/16(土)

午前10時半に目を覚まし、二度寝できなかった。正午を過ぎたくらいに外出。昨日言っていた通り、今日は夜までゲーセンに行く。Universal Cupは日付が変わってから走る予定である。

昼食は以前見かけた蕎麦屋「味玄十割そば」に入った。鴨南蛮そばにミニ天丼を付けたら思ったより多かった。そばを大盛りにしなくてよかった。

食事 pic.twitter.com/3CvWTbLAgG
— こたつがめ (@kotatsugame_t) 2024年11月16日

そのあと午後7時前までゲーセンで25クレプレイした。成果は上々。まず「What's up? Pop!」のSSSが出た。鍵盤を雰囲気で押したらかなりいい感じに通り、SSS+間近のスコア。しかしこのプレイ以外SSSすら出なかった。ラストを押そうとすればするほど押せなくなってしまった。

What's up? Pop! SSS pic.twitter.com/7iQe4uZ57K
— こたつがめ (@kotatsugame_t) 2024年11月16日

さらに14+のAJを四譜面増やした。今、98譜面あるようだ。出そうな譜面は他にいくつかあるから、3桁の大台にはすぐにでも到達できるだろう。

今日は25クレ pic.twitter.com/mggUemqNgi
— こたつがめ (@kotatsugame_t) 2024年11月16日

本屋で本を買い、スムージーを飲んで帰宅。寝過ごさないよう机に突っ伏して1時間弱仮眠し、午後9時からABC380に出た。

AtCoder Beginner Contest 380 - AtCoder

Aは頻度配列を作った。Bは適当にループ。Cはランレングス圧縮して要素をswap。Dは $\lfloor(K-1)/|S|\rfloor$ を見て大文字・小文字のflipが起こるか判定。実際に操作を巻き戻す感じで実装したが、後から見返すと単にpopcountのパリティだった。Eは区間をsetで管理するテク。Fはメモ化再帰。Gはシャッフルする区間内の転倒数を引いてシャッフル後の転倒数の期待値 $K(K+1)/2\times 1/2$ を足せばよく、区間をずらしながら差分更新していく。

32分半で全完して5位。DはThue-Morse sequenceという。名前を聞いたことはあったが、調べるより自分で計算したほうが早いだろう。そもそも列を見てpopcountのパリティだと気づけない時点で遅いという話でもある。

コードゴルフとしてAとBをNibblesで解いた。Aはよくわからない。Bは文字'|'でsplitしてそれぞれ長さを数えればよく、非常にシンプルな7Bが得られ、さらにImplicit Opsでmapの1Bが削れる。

www.youtube.com

シャワーを浴びて午前0時からUniversal Cup。今日は17回目、Jinanセット。

書く

DMOJで開催されていたunratedのコンテストに参加してみた。実はタイトルの「Arcadia」を音ゲー「Arcaea」と読み間違えていて、関係のある問題文が読めるものと楽しみにしていたのだが、ただの勘違いなので全然そんなことはなかった。期間は来週木曜日まで。

Arcadia Computing Contest 1 - DMOJ: Modern Online Judge

カクヨムで「【本物】オカルトVtuber【現る？】」を読了。画面越しに視聴者に対して直接影響力を行使できる、主人公の能力の設定がかなり好きだった。それを用いたアンチへの対処が爽快。ブロックとか開示請求とか、仕方ないけど迂遠な手段だなあと常々思っていた。

kakuyomu.jp

午前10時半就寝。

11/17(日)

午後8時起床。午後9時からARC187に出た。

AtCoder Regular Contest 187 - AtCoder

Aは大変。とりあえず前から適当に操作を繰り返すことで $A_1\le\dots\le A_{N-2}$ とできる。さらに $A_{N-1}\le A_N$ が成立すれば、 $i=N-1$ での操作を2回ずつ繰り返すことで、ほかの大小関係を崩さず $A_{N-2}\le A_{N-1}$ とできる。ここで $A_N\lt A_{N-1}\lt A_N+K$ であるケースが問題となる。 $N=2$ なら不可能。そうでないなら、 $i=N-2$ で2回操作すればよい。

Bは $\min(A_1,\dots,A_{i-1})\gt\max(A_i,\dots,A_N)$ という位置で連結成分が切れるから、逆に各 $i$ に対しそこで切れる $A$ の数を数え上げればよい。 $\min$ と $\max$ のどちらかを $O(M)$ かけて全探索すれば、後は簡単な組み合わせの問題になる。

Cは、 $P$ から $P'$ を作る際、 $P$ の累積maxの更新点を後ろに動かすということをする。動かした要素は $P'$ でも累積maxの更新点となるから、逆にそこからいくつか選んで前に動かせば $P$ が復元できる。更新点の選び方と $P$ は一対一に対応するため、更新点の数を $k$ 個とすれば $P$ は $2^{k-1}$ 通り。ここで $1$ 引いているのは、必ず選ばれる $P_N=N$ の分である。

あとは適当にdp。 $k$ を具体的に持つ代わり、遷移の度に値を2倍すればよい。自分は大きな値から順に $Q$ に埋めつつ、これまで埋めた要素のうち最も前にあるものの位置を状態として持った。

Dは雰囲気が全然違う問題。 $X$ の最小値 $m$ を固定すると、 $C_i=C_i(m)$ の値は高々一意に定まる。答えは $\min_m\max_i C_i(m)-m$ 。ここで $C_i(m)$ は $m$ について広義単調増加だから、 $\max_i C_i(m)$ もそうなっている。よって $C_k(m)$ を追加する際は、chmaxなんて高等なものは必要なく、二分探索して求めた区間への代入さえできればよい。答えも含めてすべて遅延セグ木に乗る。

この時点で順位表を見たら3位だった。時間も1時間ほど残っており、全完チャンス。ドキドキしながらE問題に臨んだ。

Eは操作の逆を考えるとよい。長さ3の区間を選び、三つのうちどれかの要素で残りの二つを置き換えるというものになる。一度消えた要素は復活しないから、操作しない（できない）という自明なケースを除けば、作れる順列には $A$ に出現しない要素が二つ、距離0か1で存在する必要がある。

さらに、操作の逆は数の連結成分を大きくしていると見なせる。つまり $A$ においてある数が非連結に出現している場合は0通り。さらに、 $A$ に出現する数の順番が順列においても保たれていないといけない。ただしcyclic shiftはできるようだ。例えばサンプル3だと四つの数の順番が固定されているから、円順列 $(4-1)!$ で $10!$ を割ったものが答えになっていると解釈できる。

あとは数え上げ。 $A$ に出現する要素の集合を $X$ 、出現しない要素の集合を $Y$ とし、まず具体的な値は忘れて $X$ と $Y$ の2タイプの並べ方を考えた。cyclic shiftができるなら、ひとまず先頭は $Y$ としてよく、 $\binom{N-1}{|X|}$ 通り。ここから、 $Y$ の間に常に $X$ が二つ以上挟まるケースを除く。 $|Y|$ 個の隙間に $|X|-2|Y|$ を挿入する場合の数であるから、重複組み合わせで求まる。

具体的な値については $X$ と $Y$ で独立に数えられる。 $X$ のほうは順序が決まっているため、 $|X|$ 通り。 $Y$ についてはいったん先頭要素を固定して $(|Y|-1)!$ 通りとする。最後にcyclic shiftを考えて $N$ 倍すると答えが求まる。

ところが7ケース落ちてしまった。cyclic shiftができるという部分はまともに議論していないが、よく考えてみると幅2ずつずらせるだけの気がする。操作にほぼ自由度がない $|X|=N-2$ のとき、かつ $N$ が偶数だとまずそう。実験コードを書いて確かめると、確かに倍の値を出力してしまっていた。2で割るコードを提出すると、今度は4ケース落ち。

もう一度試していたら、 $N=4$ のときもともと正しい答えを出力していたのに、半分にしてしまっていたのを発見した。それだけで4ケースも落ちるかと首を傾げつつ、残り時間もないのでとりあえず提出してみると、なんとAC。意地の悪いコーナーケースが四つも入っていたらしい。

何はともあれ全完。3位だった。ARCでは初めての全完である。難易度改定で簡単になったからという理由もあるかもしれないが、それでもEは本番7ACだったから、そこまで極端に簡単というわけではなさそう。

Eには結局50分ほどかけた。それだけの時間で合わせきれたというのはかなり運が良かったと思うが、それでも最後の1問にコンテスト時間の半分を残せた点で、Dまでの出来は会心。AはともかくBCDでほぼ詰まらなかったのが効いた。

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

Dashboard - Codeforces Round 988 (Div. 3) - Codeforces

Aはよい。Bはソートして尺取り。 $a_i^2=k-2$ となるケースに注意する必要があるが、自然に実装するとそれより先に正しい解が見つかった。Cは $[2,4,5,1,3]$ の左右に偶数と奇数を並べた。Dは優先度付きキューで貪欲。

Eは、 $f(1,n)=0$ なら特定不可能で、それ以外は必ず可能。 $f(1,r)\gt 0$ なら $f(1,r)-f(1,r-1)$ を見ることで $s_r$ の値と $s_1\dots s_{r-1}$ に含まれる0の個数が分かる。後者の情報を使うと $f(1,r)=0$ となったところで $s_1\dots s_r$ も確定させられる。