2024-03-04

週記（2024/02/26-2024/03/03）

02/26(月)

午後3時過ぎ起床。半からインターン先定例会に出席した。

先週は修論修正を口実に稼働していないので、今週はタスクを進めますと宣言しておいた。勉強会はAHC030の話。ベイズ推定による特定方法はビジュアライズすると魔法のような挙動をしているが、この理論が聞けて良かった。最上位層はそこからさらに焼きなましで配置パターンを探索していたらしい。奥が深すぎる。

解散後はずっと先週の週記を書いていた。日曜日の時点である程度書いてあったので、午後10時くらいにはUniversal Cupを残して完成。そこが穴あきなのは毎週のことだからもう投稿してしまおうかとも思ったが、気合いを入れて埋めることにした。結局コンテスト後にD問題を通した部分が書ききれず、日付が変わってから追記した。

グダグダしながら食事したりシャワーを浴びたりゴミを出したりした。もうちょっとテキパキ行動したかった。ただ無為に時間をかけたおかげでゴミ出しが日の出少し前のタイミングになり、夜明けの空気を楽しむことができた。

セミナー発表の準備でしばらく論文を読みながら資料を作っていた。午前8時就寝。

02/27(火)

午後3時起床。昨日の続きに少し取り組んで眠気を覚ましてからゲーセンにでも行こうと思ったのだが、線形代数に手こずっているうちに3時間経過してしまった。これ以上遅くならないうちにと外出。

夕食は油そば。普段の行動範囲から微妙に外れたところにあってこれまで行ったことのなかった店に入ってみた。よく行く一二三よりタレの量が多く、その分薄めになっている。麺の量は大盛り・320gを選択。かなり空腹だったので難なく食べきれたが、そうでない場合は厳しいくらいのサイズ感だった。今後のために記録。

食事 pic.twitter.com/K4wFfrrFpe
— こたつがめ (@kotatsugame_t) 2024年2月27日

ゲーセンに行く途中にあるたいやき屋がさくらみこさんとコラボしていたので、商品を買うわけではないが写真を1枚。いつも歩く道にいきなり巨大なイラストパネルが現れるので目に付く。第二弾とあるように昨年も見かけた記憶があったので、当時のツイートを探しリプライに繋げておいた。

第二弾 pic.twitter.com/dy9vo7VI8z
— こたつがめ (@kotatsugame_t) 2024年2月27日

ゲーセンには午後7時から午後10時半くらいまでいて20クレプレイ。今日も未プレイの譜面を埋めていた。「ASH」は「My First Phone」の再来と聞いて身構えていたが、そんなに難しくはなかった。似ているのは前半だけで、後半はまた違ったトリッキーさ。新要素である高さの違うエアーが乱れ飛んでいた。譜面が見にくいだけで手をぶんぶん振り回していれば何とかなる。それにしても4落ちはかなり上手くいった。

ASH AJ！ pic.twitter.com/gs7MmqQUcF
— こたつがめ (@kotatsugame_t) 2024年2月27日

帰りにトイレで手を洗おうと思ったら、いつの間にか午後9時以降使用不可となっていた。びっくり。GiGO仙台も確か午後9時半だったか、ともかく夜になるとトイレを使えなくしてしまう。結構不便。

ドンキに寄ったら安くバナナが売っていたので20本ほど買った。皮の色がくすんでいる気もしたが、食べてみるとなかなか甘い。ドンキが熟した頃合いを見計らって売るわけがないと見くびっているため、店で売れ残っているうちに食べごろになったのではと考えている。まあ自分にとってはいい買い物だった。

毎日バナナ健康生活 pic.twitter.com/ZjWzsFcNPr
— こたつがめ (@kotatsugame_t) 2024年2月27日

午後11時帰宅。半からCF #929 div.3に出た。

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

Aは絶対値の総和。Bは場合分け。Cは $x,y$ を全探索。Dは最初 $1$ に注目して考えていたが、その議論は最小値に対して一般化できる。最小値が一つなら可能、二つ以上のときも最小値の倍数でない数があれば可能。それ以外は不可能であることも示せる。Eはパフォーマンスの増分が負になるセクションを含むトラックを探し、その周辺で実際に計算してみる。

Fは岩を動かす代わりに自分が下に1マスずれるものと思う。岩に対する相対位置が同じならできるだけ早く到着すべきなので、BFSが正当となる。上への移動はその場に留まる遷移となるため、右端に到達してゴールと重なるのを待つときだけ行う。ここで、岩だけ動かしているのでゴールマスは下に1マスずつずれていくのだが、岩と一緒に上にずれると勘違いしてかなり手間取ってしまった。

Gはサンプルが最初から8パターンしかないと言っているので全部チェックする方針が立つ。手で試していたらそれらのパターンを特定できた。 $n,m\ge 5$ という制約がそれらのパターン以外を排除するのに十分大きいと信じて提出。

全完7位。Gは $5\times 5$ を全探索して8パターン見つけるのが安全だろうか。手での実験だと、自分は左上マスから適当に埋めていたが、十分に広いグリッドの中央から始めて $2\times 2$ に3マス同じ形があったとき矛盾することを確かめるのが良いらしい。

www.youtube.com

その後はずっとカクヨムを読んでいたが、寒くて布団に移動したところそのまま寝落ちした。午前8時前。

02/28(水)

午後3時から3時間ほどカクヨムを読んでいたらしいが、本格的な起床は午後8時。

昨日からは最近追えていなかった作品を最新話までと、同じ作者の新作を読んでいた。後者の「神ゲーに転生したけど人生はクソゲーだった」も起きて少しで読了。この作者が描く主人公の態度が好み。何事に対してもどこか適当な感じで、しかし圧倒的に強い。

kakuyomu.jp

布団から脱出し、セミナー準備を開始。興が乗って翌日までずっと続けていた。今読んでいる論文はself-containedなのにたった7ページ。その分行間は自分が経験したことのない広さだが、本当に重要な式はちゃんと書いてあるし、間違いもほとんどない。読んでいてワクワクするようなものである。

午後1時過ぎに学食で昼食を摂り、ラノベを受け取ってきた。セミナー準備の今できているところまで先生に送り、午後3時就寝。

02/29(木)

午後11時起床。今日は4年（正確には4年強）に一度のうるう日だが生活リズムの関係からもう終わりかけ。半からCF #930 div.1に出た。

Dashboard - Codeforces Round 930 (Div. 1) - Codeforces

書く：CF

www.youtube.com

朝までセミナー準備を続けていた。これまで用意した分で内容の量としては十分だろうが、論文自体はまだ読み切れていない。昨日送ったメールに対する先生の返信では最初に全体の流れを聞きたいと書いてあったので、それに答えられるようにしていた。

午前7時過ぎにシャワーを浴びて布団へ。明日のセミナーは正午開始。しかし寝る前になぜか2時間近くスマホを眺めてしまった。

03/01(金)

午前11時半起床。本当は30分前に起きるつもりだった。セミナー開始まで時間がなく、地下鉄で登校すると間に合わないだろう。外がよく晴れていたので久しぶりに原付で山登りすることにした。路面が濡れていたのでスピードは控えめだったが、山道を走りながら昨年以来の景色を眺めているうち2月＝冬を越えて3月＝春がやってきたことが実感され、清々しい気持ちになった。

余裕を持って教室に到着。予定通り正午から2時間ほどセミナーを行った。全体の流れについてはおそらくそれなりの感じで喋ることができたものと思うが、今週頑張って準備してきた細かい内容についてはほとんど触れられなかった。ただせっかく準備したので、これから数週間かけてじっくり話していく予定。

午後4時から論理学セミナーに参加するよう言われていた。それまでの時間は今日そこで話す先生が来て詳しいことを語ってくれるはずだったらしいのだが、トラブルで来られなくなったとのこと。それで空いた時間は図書室から借りていた本を返しに行ったり先生と話したりしていた。

時間が来たので建物を移動してセミナーへ。この内容は……ほとんど何もわからなかった。専門でないものを英語で発表されると聞き取るのすらおぼつかない。さらに板書の文字も汚かったため手も足も出ず。ただ、つい先日の日本数学会東北支部会で聞いた発表とほんの少し重なっていたところがあったようで、奇遇だなと思った。

学食で食事して午後7時に帰宅。学位記授与式のため実家に置いてあったスーツ一式を送ってもらったのだが、荷物の底にチョコとうなぎパイが入っていた。この年になっても貰えるというのはありがたいものだ。

母からバレンタインのチョコが届いた pic.twitter.com/Nm98Ee8oNq
— こたつがめ (@kotatsugame_t) 2024年3月1日

2月の読書記録をツイート。先月もなろうにすべてを捧げてしまった。おそらく今月もそうなるだろう……。

2月の集計
買った：30冊
読んだ：3冊
積読：+27冊
積読（累積）：+63冊
— こたつがめ (@kotatsugame_t) 2024年3月1日

しばらく日記を書き、午後9時20分からyukicoder 419に出た。

yukicoder contest 419 - yukicoder

Aは二つの軸に分けた後どうすればいいのか分からない。大きな値から貪欲に使って半々に分割しようとしてみたところWAだったので、何か条件を考えることにした。奇数のほうは奇数個あると無理、偶数個あるとできる。偶数のほうは2で割ると連番になるから、その総和が偶数なら必ず可能。これで通った。

Bは $a+b\ge a\oplus b$ よりスライムの移動が交差するならマージしてしまったほうが得であるため、dpで解ける。

Cは下の行から順に答えを求めていった。各マスについて、同じ行で障害物に阻まれず移動できる区間を尺取り法で求め、それに応じてセグ木に値を乗せておき、二分探索でボタンを押す回数を求める。セグ木上の二分探索が使えなさそうだったので毎回 $O((\log W)^2)$ かけたが、400msとかなり速い。

Dは微妙に制約が小さかったので $O(N^2)$ を出したら6600msで通った。prefixとsuffixのXORをカウントすることにして、調べる位置をずらしながら差分更新していく。テストケースが多いのでいつTLEするかとハラハラドキドキしながら見守っていた。

この後はずっとEを考えていたが本当に何もわからない。途中で寝そうになったのでシャワーを浴びて眠気を覚まし、午後11時半からのCF #931 div.2へと逃亡した。

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

Aは式をぐっと睨むと最大値二つと最小値二つの差の2倍だとわかる。Bは適当なところまでdpして残りは15円連打でよさそう。真面目に見積もろうとしてよく分からなくなったため、10⁵までdpしておいた。Cは左上・右上・左下を聞くことでmineの乗る線分が3本得られ、その2交点のどちらかには必ず存在する。正確には1本に退化するケースもあるが同じ。

D1は立っていなかったbitを立てるのに、そのさらに上に「1→1」と「1→0」の2パターンのbitを用意しておく必要がある。もともと $m\subseteq n$ ならよし、そうでないなら「0→1」のbitのうち一番上を探し、その上に2パターン用意できるかチェックする。「1→1→0」と「1→0→0」を使い2手かけて遷移させるケースもあることに注意。

D2は問題も解き方もD1と似ているとはあまり思わなかった。実験すると $p$ のpopcountが偶数なら先手勝ち、奇数なら後手勝ちだと分かる。ところがそこから自分の手を実装するのに大苦戦。popcountを等分しても奇数になるとは限らないことを忘れ、63回より多く操作できないことを忘れ……。全部サンプル1で落ちたのでペナルティにならなかったのだけは助かった。最上位bitとそれ以外を分けるのが正解。

Eは後半 $n/2$ 個を3個ずつ組にして操作し、LCM二つのGCDで元の数が得られるようにするのだろうと思ったが、肝心の組を作る戦略がわからず。D2までで27位。

www.youtube.com

日記を書いて午前6時就寝。

03/02(土)

ICPC プレーオフのミラーに出るため午前11時少し前に起床。ところが30分延期されてしまった。二度寝すると寝坊しそうだったので日記を書いて待った。

Dashboard - 2024 ICPC Asia Pacific Championship - Online Mirror (Unrated, Online Mirror, ICPC Rules, Teams Preferred) - Codeforces

ソロ参加でコピペなし。結果的には検索もしなかった。HCJGEFKをこの順で解いて33位。

Aを読んでしばらく唸っていたが、難易度順ではなかったらしい。しばらくしてHが解かれ始め、そこからは自分もsolved数の順に取り組んでいった。

Hは人数が少ないほうをどこかに移動させる。ただしすべてのテーブルで人数が少ないほうが同じメニューだった場合はそのために一つテーブルを確保する必要がある。さらに全員が同じメニューを頼んだ場合はその処理を行ってはならない。なんだか2段階のコーナーケースがある感じだった。

Cは生成される数列の階差を観察した。それ自体特徴的な形をしているが、解法に繋がったのは階差が $b$ であるのと直後の数の下 $1-b$ bitだけが0になっているのが同値だという事実。つまり階差が最小値を取るところを探せば、上のほうのbitは他で変化しないため、そこの数が1...10...0のような形になるのが最小とわかる。あとは実際に復元してチェックした。 $n=1$ は別処理。

Jは行きを最短経路としても損しない。帰りに寄る辺を全探索した。Gは $b$ を固定し、各問題に対し同じ文字を回答した人をリストアップしても間に合う。鳩ノ巣原理からここで $(k-1)n$ 個より多く見ることになった場合その時点で答えが確定する。

Eは順列を壊す。順列である行と列のうち多いほうの数が答え。基本的にはインクリメントでずらし、ダメだった場合1マスだけ追加でもう一回インクリメントすれば、 $n\ge 3$ よりうまくいく。

Fは難しい。約数 $k$ を全探索し、 $a_1$ を入れる場所をずらしながらグループのスキルレベルをセグ木に乗せようとした。これは $O(d(n)n\log n)$ であり間に合わないようだ。何とか $\log$ を落とそうと考えた結果、左右からの累積を求めることにした。挿入箇所がどんどんずれていくだけなので、右か左の値はずれる度に一つずつ修正していける。もう片方は $k$ 回に1回 $O(k)$ で修正すればよい。

Kはまず $x$ が確定する。次いで $x$ の祖先とそれがLCAとなる $y$ の個数を持ち、二分探索することでLCAが決まる。最後に $y$ だが、これはオイラーツアーにおける高々二つの区間のうちから選ぶことになる。rangefreqで個数カウントすることで二分探索が可能。 $\log$ 三つだがエイヤと書いたら通った。二分探索付きBITとrangefreqの写経も含め26分でかなり順調だった。

次にLに取り組んだ。後ろのほうから次元を求めればよいかと思ったものの通らず。立て続けに4WAくらいしたところで午後2時になったため一旦DDCC予選に移った。このために焦っていてよく考えずに提出してしまった。まあ結局ここのペナは何も関係なかったのだが。

ディスカバリーチャンネルコードコンテスト2024 | Discovery Japan ディスカバリージャパン

こちらはあまり言うことがない。1問目はやるだけ、2問目は多少面倒なパース、3問目はちょっとした幾何、4問目は少し捻ろうとした感じのナップザック。26分弱で全完した。3問目でライブラリの写経ではなくコピペを行えばもう少し速くできたかなと思う。ネットに公開済みのコードをそのまま使うのが少し怖かった。

後からTLを見ていた感じ、入力を受け取るところで苦労した人が多かったようだ。自分はトップページの注意書きを熟読していたためソースコードに直接コピペできることを知っていた。D問題は文字列と数値が同時に出現して少し面倒そうだったが、適切な構造体を定義しておくとそのまま使えることに気づいた。ここは少し気持ちがよかった。

ICPCミラーに戻ってLとの格闘を続けたが全然わからない。なんとそのまま2時間椅子を温め続けて終わった。Fは $k$ として素因数だけ見ればよかったらしい。

Lに向き合っているうち眠気が耐え難くなってきていたので、午後5時から午後8時半まで仮眠。起きて午後9時からABC343に出た。

AtCoder Beginner Contest 343 - AtCoder

Aを見てちょっとギョッとした。 $A+B+1\bmod 10$ を出力。Bは $A_{i,j}=1$ なる $j$ を順に改行区切りで出力してもジャッジがよしなにしてくれる、と思ったらWAが出てしまった。今回はちゃんと空白で区切る必要があったらしい。まあ理解はできる。Cは10⁶まで全探索。Dはmapで頻度配列を持ち、0になった要素を逐一消す。

Eは大変。立方体たちをギチギチに詰めてもよいので、 $21\times 21\times 21$ にどう配置するかという問題になる。ここで立方体を一つ中央に固定しても良いことに気づいた。すると全探索ができるようになる。体積については包除原理で求まる。

Fはセグ木に乗る。Gは文字列たちに包含関係がないよう前処理をすると、直前に置いた文字列とどれだけ重ねられるかという話になる。前計算しておいてbitDP。前処理も前計算もZ-algorithmでできる。

1ペナ全完、3位。Bのつまらないミスさえなければ……。普段はそういうところも丁寧にやっているのだが、今回ばかりはB問題でわざわざ手間暇かけるのが馬鹿らしくなってしまった。Eで立方体を固定する位置が中央ではなく角だとWAになるらしい。どのようにずらしても角に立方体を寄せられない位置関係が存在するようだ。正直何も考えていなかったので運がよかった。

コードゴルフはABCD。Aはdcで $B^A\bmod 10$ としてみた。テストケースハックで5B。しかし $9-A-B$ でも同じく5Bが出る上、Nibblesにはさらに $0^{A+B}$ という4B解もあった。Bは`?_1で一発。各行ごとに1のインデックスを全部探してくれる。こうなると $N\ge 2$ で1行目を読み飛ばさなくて良くなっているのがありがたい。CはNibbles、DはAWK。

www.youtube.com

少し日記を書いた後、TUPCのテスター作業をした。午前10時くらいに一段落ついてなろうへ。今週はほとんど読み進めていなかったが、このタイミングでついに以前読んだことのある最前線に到達した。

午前11時就寝。

03/03(日)

午後8時半起床。しばらくなろうを読んでから布団を脱出し、UTPCへの参加登録をした。いずれUniversal Cupに収録されるらしいからrisujirohさんと現地でチームを組む。たまにはこういうのもいいだろう。Nyaanさんは残念ながら来られないらしいのでオンラインで。

UTPC2023 - connpass

PCを眺めていたがまた眠くなってきた。布団に戻って午前1時前には就寝。本当は今日、インターンの作業を進めたかったのだが……。

今週はなろうを2608話まで読み進めた。実はちょっと興味が離れたタイミングがあって、その時ちょうど面白い論文を読み始めたためそちらに掛かり切りになっていた。

そういえば、先週も今週も火曜日・水曜日あたりに布団の上で一日を終える日がないよう意識して行動できていた。しかしその反動か知らないが代わりに日曜日が消えてしまっている。たまたま2週連続コンテストがなかったこともあるだろう。平日は気合いで耐え、土日はコンテストに没頭することで何とか週七日きちんと活動したいところだ。

2024-02-26

週記（2024/02/19-2024/02/25）

02/19(月)

午後2時半起床。購買に行ってパン類とラノベを買ってきた。

午後3時半からインターン先定例会に出席。用事で欠席・寝坊・休日とここ3週間進捗報告を行っていないようだ。まあ先々週までは報告するような進捗もなかった。先週は少し稼働したので、今日はそれについてと、博士課程合格を報告した。今週から頑張れるかというとそうでもなく、木曜日に修論修正・再提出の締め切りがある。

勉強会は母関数を使った数え上げの話で、特に指数型母関数を使ったり、簡単な関数との間の等式から式変形したりするテクニックを扱っていた。前者はcombinationから自然に見出せると思っていて、それで解けたこともあるが、後者は残念ながら成功体験がない。dpで扱おうとすると複雑でよくわからない遷移になって手に負えなくなるだろうし、難しい話だ。

解散後は週記を書いていた。今日はyukicoderがあるのでそれまでに先週の週記を投稿しよう、と思っていたのだが全く捗らない。そうこうしているうちに午後9時20分になったので、問題だけ読んでおくかとページを開き、流れでうっかり2時間近く参加してしまった。

traP 作問ハッカソンコンテスト 002(day2) - yukicoder

まともな取り組み方はしていない。Hを解いた後Iの非想定解と格闘し、最後にGを考えていた。

Hは3次元ということで一瞬嫌な気持ちになったが、操作後も必ず $[0,100]$ に収まるというかなり優しい制約に気づいた。これなら細かいことを気にせず $101\times 101\times 101$ の1次元に潰してもよい。ならば、と犯罪のつもりで畳み込みを書いたらFAだった。しかもこれが想定解だったらしい。

Iは $d(k)/k$ が乗法的関数であることを利用するものと考え、以下のライブラリを自力で再現しようと試みた。素数の逆数和が必要だが、それは途中で打ち切っても何とかなるだろうと思った。しかしそもそも、まともな速度が出ない。諦めてライブラリを拝借した。

乗法的関数のprefix sum | Nyaan’s Library

設計が特殊なので使い方のメモをしておきたい。コンストラクタには和を取る範囲、今回なら $N$ を渡す。答えを求める関数はrunだが、これの引数fprimeは $1\le k\le\sqrt{N}$ に対する $S_p(k),S_p(N/k)$ の列を期待しているらしい。ここで $S_p$ はドキュメントの上のほうで定義されている。

そんなのどうやって求めるんだと思ったら、 $f(p)=1,p$ の場合のコードがpi_tableやprime_sum_tableとして用意されていた。今回は逆数和だが後者を弄れば作れそう。問題となるのはその関数の初期化部分で、 $1+1/2+\dots+1/x$ が必要。小さい $x$ については前計算し、大きな $x$ はググって出てきた $\log(x)+\gamma+\frac{1}{2x}$ で近似した。

調和数 (発散列) - Wikipedia

TLEしたので、long doubleをdoubleに変えたり、dfsの引数を増やして $f(p^c)$ を徐々に計算するようにしたりと高速化を試みたところ、1982msで通った。想定解を見て横転。

Gはうっかり牛ゲーに帰着して何もできなくなった。

いつの間にか午後11時を回っていた。週記の体裁だけ慌てて整えて投稿。半からCF #928 div.4に出た。

Dashboard - Codeforces Round 928 (Div. 4) - Codeforces

Aはよい。Bはややこしそうだが、行ごとの1の個数を見ると特定できる。Cは前計算。TLが謎。Dはmultisetを使い $a$ と $(2^{31}-1)\oplus a$ を貪欲にペアにしていった。Eは $2^0\times\text{奇数},2^1\times\text{奇数},2^2\times\text{奇数},\dots$ と並ぶ。

Fは簡単な方法がわからなかったので、Xの出現パターン2²⁵通りすべてに対して答えを前計算した。正確にはもう少し減るだろうが気にしない。下位集合へのゼータ変換が必要になって3000msを超えた。日記のこの部分を書いているとき、それがいらない遷移を思いついて、試したところ826msで通った。Gは木dp。

全完7位。Fは市松に塗り分けてみると完全に独立になるため、操作の候補も半分になって全探索できるらしい。

www.youtube.com

先週の週記にコンテストを三つばかり書き足したら朝になった。午前6時半就寝。

02/20(火)

正午くらいに腹を壊して目を覚ました。

槻影さんのなろう発ラノベ「嘆きの亡霊は引退したい」のアニメ化情報が流れてきた。好きな作家さんだ。めでたい。

◤￣￣￣￣￣￣￣￣￣￣￣￣￣
　＼㊗アニメ化決定㊗／　　
『嘆きの亡霊は引退したい』
　　　2024　ON AIR
＿＿＿＿＿＿＿＿＿＿＿＿＿◢

特報映像を公開しました！https://t.co/yVOsE3Exr6

🎙キャスト🎙
クライ・アンドリヒ： #小野賢章
ティノ・シェイド： #久保田未夢

▼公式サイト… pic.twitter.com/w7eHw1GDqp
— 『嘆きの亡霊は引退したい』公式｜アニメ化決定 (@nageki_official) 2024年2月20日

1時間くらい二度寝するか迷っていたが、ここで寝てしまうと今日はずっと布団で過ごすことになりそうということで、気合いを入れて起床。学食で食事し、ラノベを受け取ってきた。

先週の週記にARCとその後取り組んだDMOJのことを書いていたら夜になった。DMOJと言えば先週一つコンテストに参加したのだった。そのコンテストは今日の午後2時終了で、TLでも言及が流れてきていた。自分もここで書いておこう。

The Contest Contest 1 - DMOJ: Modern Online Judge

P1はまあ、できる。P2は消える区間を管理してみた。各 $i$ に対し $d=a_i$ についてだけ更新すれば十分であるようなデータの持ち方をすればよい。

P3は天啓一発。情報に間違いがないなら $a+b$ や $c+d$ の頻度配列を見ることで要素の大小関係がわかる。それを満たすように小さい値から埋めていけばよい。ところで今間違いは高々一つだから、 $a+b$ と $c+d$ のどちらかは正しい。よって両方試してチェックすることで候補が求まる。気づくまでは不可能に見えており、閃いたときはかなり気持ちよかった。

P4はかなり大変。操作が耳dpの元となった問題に似ていたので、まずその解説を読みに行ったが、今回は頂点を訪れた回数だし、始点に戻ってくるし、結局あまり関係なかった。1点、辺を通った回数のほうが扱いやすいというのはポイントかもしれない。

D - Ears

始点を決め打ち、そこだけ $f$ をデクリメントすることで、経路一周分が表現された状態になる。この状態で左から考えると、辺 $i\leftrightarrow i+1$ を通った回数が $2(f_i-f_{i-1}+\dots+(-1)^{i-1}f_1)$ として表せる。これが0以下だったり、辺 $N\leftrightarrow N+1$ を通った回数が0でなかったりすると実現不可能。そうでない場合は $K$ を無視すると可能。部分点1は愚直、部分点2は $f$ のデクリメント分を差分更新すると通る。

問題は $K$ について。経路を辿る際、一瞬だけ往復することで制限を回避することを考えると、基本的には辺 $K-2$ 本置きに往復する必要がある。ただし辺 $1\leftrightarrow 2,N-1\leftrightarrow N$ では往復したと見なしてもよい。そこで、経路一周を2回の $1\rightarrow N$ だと見なせば、辺を通った回数を見ながら貪欲に往復することで判定ができそう。

できそうなだけで残念ながら微妙に違う。今決め打っている始点が $s$ だとすると、「片方の $1\rightarrow N$ において」辺 $s-1\leftrightarrow s,s\leftrightarrow s+1$ で往復したと見なせる、という条件が付いてくる。そこで2回の $1\rightarrow N$ を2回ずつの $1\rightarrow s,N\rightarrow s$ とさらに分割すると、往復しなかった辺の連続回数を記録しておけばマージができて、先ほどの貪欲が効く形になる。

これを毎回愚直にやると部分点3、左右で分けて前計算すると満点。先ほどの辺を通った回数の計算によれば、 $f$ のデクリメントはより右に、かつ決まった形でしか影響しないから、左からは元の $f$ で、右からはデクリメント後の $f$ で前計算しておける。

P5は1列持つdp。といっても状態は...、.##、##.、###の4種類しか考えなくてよい。 $b$ として出現する列だけ遷移を全探索で行い、その間はいったん...に揃えてから一気に遷移した。この遷移の際、途中に $1\times 1$ の家3軒からなる列がある場合や、遷移先が###になるなら $1\times 1$ を取り除いて.##や##.にしなければならない点は注意。また $2\times 2$ を縦に並べる際は2列分の条件を判定する必要があることにも注意。時間は結構かかったが、ほぼ一発で合ってそのまま通ったので助かった。

P6は部分点1のみ。頂点 $1$ の次数が1で、そこから頂点 $N$ に至るまでのパスが1本道だと答えがYESになる。この場合Aliceは辿る辺を選べないので、辺の重みは何を出力してもよい。逆にそれ以外のケースではAliceが辺を選べるタイミングが存在して、頂点 $N$ に向かわない辺を選ばれると戻って来ない。

以上510点。P4に1時間半くらいかけたので解いている途中はヤバいかもという気持ちになっていたが、満点をちゃんと出せたしP5も間に合ったので結果オーライ。P6の部分点でまくられることもなくずっと順位表のトップにいた。しかし最終日に自分より6分早く同じ510点に到達した人が出て、2位。レートは3091→3209(+118)と、前回優勝した3000以下Ratedより上がり幅が大きかった。

夜は修論の修正作業として先生から頂いたコメントを反映していた。眠気が来たのですぐ布団に入り、午後11時就寝。

02/21(水)

午前9時に一度目を覚ました。この時点で久しぶりに長時間連続して眠ることができていたが、そこからさらに二度寝まで成功。午後1時に起床した。

外を見たら雪が積もっていて学食に行く気がかなり失せたが、理由があって頑張って登校した。食事し今日もラノベを受け取って帰宅。

理由というのは、ミールの適用範囲拡大措置についてのもの。コロナ禍が始まってから何度かの期間延長を経て続いてきたこの措置だが、今のところ今日までということになっている。これまでの延長は数か月前の時点で告知されていたから、春休み突入に合わせて終わるのだと思う。いつもこの制度を利用してお菓子だったりパンだったりを買っていたので、残念。

コロナ禍が始まって以来続いてきたミールカード適用範囲拡大措置も今日で終わりっぽいな pic.twitter.com/esOOSoEnH1
— こたつがめ (@kotatsugame_t) 2024年2月21日

帰宅して久しぶりにラノベを開いた。2冊読了。特に1冊目だが読むのに非常に時間がかかって、なろうばかり、しかも同じ作品をずっと読んでいた影響を感じた。

1冊目、「一生働きたくない俺が、クラスメイトの大人気アイドルに懐かれたら」5巻。4巻に引き続きこの巻でも厄介事が持ち上がり、シュッと解決して終わった。話が長引かないのは読みやすくて良いこと。合間合間でヒロインたちとのイベントもこなし、どんどん距離が近づいている。そのゴールはどうやら作中で3か月後の武道館ライブになるようだ。と、順調な展開を見せるストーリーだが、あとがきを読むと6巻の刊行が確定していないような書き方で、4巻と5巻の間もちょっと長かったし心配。5巻まで出ていてそんなことあるか？続きが読めることを願う。

2冊目、「双子まとめて『カノジョ』にしない？」2巻。1巻の最後のほうでも垣間見えていたが、主人公の才覚・手腕によって校内のトラブルを解決へと導いていくのがラブコメと並ぶもう一つの軸という感じがする。確かに一歩引いたところからあれこれ糸を引いていた様子はあった。ただラブコメに紛れたあっさりした描写からは有能さがあまり実感できなかったというのが正直な感想。

日付も変わり、そろそろ修論の修正作業と向き合わなければならない。シャワーを浴びて気合いを入れ朝まで取り組んだ。いろいろ加筆していた部分が何とか形になったので、先生にメールを送信。今から寝て、起きたら見直しをし、午後5時までに教務課に行って提出を行う。

外を見たら雪がかなり積もっていた。明日は時間に余裕を持って登校しなければならない。午前9時就寝。

02/22(木)

午後1時起床。もう少し眠れるかなと思いつつ1時間ほどなろうを読んで、起き上がった。

昨日送ったメールへの返信では指摘は特になかった。では後は見直しということでしばらく修論を読み直して文章を弄っていたが、かなり時間がかかりそうだったので先に大学に登校することにした。到着した大学構内には入試に向け掲示物がいろいろ張り出されていて新鮮。まず教務課で締め切りと提出方法を確認し、院生室に移動して修正を続行した。

TeX打ちをする際、自分はかなり空行を入れるのだが、別行立て数式の前後に空行があると微妙にスペースが開いてしまうことに気づいた。どうせ別行になるならそのあたり無視されるだろうと勝手に思っていた。これを慌てて削除する作業に追われ、後半の文章をしっかり読み直す時間は残らなかった。

午後5時直前に慌てて印刷し、提出。その後院生室にいた同期・後輩とひとしきり喋り、一緒に学食で食事して解散した。自分の研究テーマの周辺に相手がやっていることと近い話題があったので、それについていろいろ話したのだが、知らないことが多くて雰囲気だけのコミュニケーションになってしまった気がする。

あとは、この先必要になりそうな分野について院生室に置いてある教科書をいくつか紹介してもらった。そういう教科書は皆自分で読み進めているらしい。偉すぎる……。正確にはそれが普通で、自分が怠惰すぎるという話なのだろう。セミナー発表に合わせてDiestelを読んでいるだけではお話にならなかった。

午後7時帰宅。夜中のSRMにレジってからYouTubeを見たりなろうを読んだりして、午後10時半から2時間ほど仮眠を取った。午前1時からSRM853。

https://community.topcoder.com/stat?c=round_overview&er=5&rd=19722

Easyは二分探索。入力の生成が面倒。

Medは最初 $a$ 文字ずらしと $b$ 文字ずらしが可能なら $|a-b|$ 文字ずらしも可能だと思ってしまったが、サンプルのabracadabraで落ちる。ありがたい。ずらせる文字数の候補が $d_1,\dots,d_k$ だったとすると、十分遠くでは $\gcd(d_1,\dots,d_k)$ 倍が全部作れる。しかしそれがどのくらい遠くになるのかわからない。ここでかなり長い間詰まってしまった。

最終的には考え方を変え、作れる文字列の長さを $q\times|\mathrm{needle}|+r$ と書いたときに $r$ に対し $q$ の最小値を求めることにした。 $d$ を全部求めておけば01BFSになるが、気づかなくて各 $d_i$ ごとに $|\mathrm{needle}|$ 頂点の遷移を行った。多始点dijkstraだとTLEするので、頑張って始点のソートと01BFSで処理した。ここにも結構時間をかけてしまった。

残り時間がもう少ないのにまだ提出がないHardは、よくわからない構築。サンプルと同じ方法ではカバーできないパターンを一つだけ考えて実装を開始したが間に合わなかった。チャレンジフェーズは何もせず。結果は8位で2967→2910(-57)となった。思ったより下がらなくて助かった。

Hardの解説を読むと、サンプルにあるパターンと四畳半みたいなパターンの二つで全部作れると書いてある。四畳半については自分も思いついていたが、ちょっと一般化が足りていなかったようだ。

しばらくなろうを読んで午前4時半就寝。

02/23(金)

夢を見た。一瞬起きたタイミングでツイート。また正午から3時間ほどなろうを読んでいた記録がある。

夢：海外オンサイトに行く。靴に1kgの鉄の棒を4本刺して安全性を高め、自転車に乗る。病院で検査を受けるとスヌークという流行病にかかったと言われた。幸い特効薬が昨日来たらしい。2日分につき1000現地通貨≈2USDの賄賂を要求されたが、それくらいならいいかと財布のシンガポールドルを適当に渡した
— こたつがめ (@kotatsugame_t) 2024年2月22日

午後6時起床。2時間ほどなろうを読んで布団から脱出し、シャワーを浴びて午後9時20分からyukicoder 418に出た。今日のコンテストは2時間半で直後のECRと少し被っているため、そちらが始まる前に全完するのが目標。

yukicoder contest 418 (Re: start!) - yukicoder

Aはよい。Bは $X_i\lt X_{i+1}$ となる条件が笛を鳴らす回数の下限として書けるので、それらの最大値が答え。Cは $N(N+1)\bmod{2M}$ を計算する。Dはいろいろな方法がありそうだが、自分は人の座標をsetに入れ、音を逆順に見ながらどんどん取り出して確定させていった。Eはよくわからないので必死に手計算して $x_i,y_i,x_j,y_j$ による表示を具体的に求めた。

Fは一般的なパターンを構築しようとして失敗。Mo's Algorithmのことを考えたらうまくいった。手計算によると、ブロックサイズは $L/\sqrt N$ くらいがよいらしい。怖かったので、 $k=500$ からデクリメントしながら答えが見つかるまで $L/k$ を試した。

Gは解が基本 $N-1$ で、そこからprefixが $M$ の倍数になるたびに1減っていく。そこで各prefixについてそこが $M$ の倍数になれる回数を数え上げればよく、左右から前計算すれば求まる。右からも計算する必要があるのは、prefixが $M$ の倍数になるなら同時にsuffixも $M$ の倍数になるというのが $A$ に関する三つ目の条件だから。

Hは大変。操作回数は $C$ の最大値または最小値を取り除いてから $\sum|C-x|$ の最小値を求めることで計算できる。ただし $x$ が取り除いた最大値あるいは最小値に一致する場合は少しずらす必要があるのと、そもそも $C$ の値が一種類しかないケースがコーナーとなる。 $C$ を値の大小で半々に分け管理することで、追加クエリ・削除クエリを処理しながら $\sum|C-x|$ の最小値を求めることができるが、これを頑張って拡張すると今回の問題も解ける。

1時間半で全完し目標達成、3位。たまたまノーペナだったがこれはかなり偉いようだ。まあyukicoderではペナルティは関係ない。少しの間日記を書いて過ごし、午後11時半からECR162に参加した。

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

Aは右端のチップを操作し続けるのがよい。1回操作する度左端のチップと右端のチップが近づくので、初期状態でその間にあったフリーのセルの数が答え。Bは適当にシミュレーションしていれば $n$ 秒以内に決着がつく。Cは1でない値をできるだけ減らし、1をインクリメントしたい。よって1の個数を $k$ 個とすると $\sum(a_i-1)\ge k$ が必要条件。 $m\ge 2$ なら十分でもある。 $m=1$ の場合は不可能。

Dは $i$ 番目に隣接する適当な区間をマージして $a_i$ より大きくするのが目標。区間の条件としては、まずマージのために長さが1であるか2種類以上の値が登場していて、さらに総和が $a_i$ を超えている必要がある。これを満たす端点を二分探索で求めた。Eはマージテクで木dp。

Fは最初二つ目の操作を誤読していた。shrinkで左の0が消え、reverseで右の0が消える。その後に行うswap操作はその前に持ってくることができるので、結局swapを繰り返した後二つ目の操作を高々1回行うとしてよい。0回行う場合は簡単なので1回行う場合を考える。

swapは難しいので1を $k-1$ 個選んで一斉に動かすと考える。全部の1を選べるならよい。そうでないときは両端から合わせて $k-1$ 個を選んで、その間にある0を埋めることになる。その結果として得られる文字列に二つ目の操作を行うと、 $\mathrm{rev}(s)$ の連続部分文字列の後ろに1がいくらか連続した形となる。SA+LCPによって $\mathrm{rev}(s)$ の連続部分文字列の大小比較を行うと数値としての最小も求められる。

全完6位。自分と全く同じ解法だったtouristのCがHackされて戦々恐々としていたが、何かミスがあったようでいつの間にか復活していた。

www.youtube.com

日記を書いて午前9時就寝。

02/24(土)

午後2時半起床。Universal Cupは今日の夜中に走る予定。ゆっくり二度寝……するわけでもなくずっと布団でなろうを読んでいた。

午後8時起床。食事して午後9時からABC342に出た。

HUAWEI Programming Contest 2024（AtCoder Beginner Contest 342） - AtCoder

Aはちょっと手間がかかる。150点がつけられただけはあった。Bは逆順列。愚直でもよい。Cはaからzに対しそれぞれどの文字に置き換えられたか持った。Dはsquare-freeにしたとき同じ値となるペアを数える。ここまでなら見たことがあるが、今回は $A=0$ に注意しなければならない。サンプルにあって助かった。Eは駅 $N$ からdijkstra。

Fはまずディーラーの戦略をシミュレートして最終的な $y$ の確率分布を求める。それによって $x=x'$ で操作を終えたときの勝率が計算できるため、 $x$ の降順に勝率が高くなるよう操作するかしないか決めていくことができる。これで解けることはすぐわかったが、 $y$ の確率分布を求める際imos法の遷移と累積和を同時に行おうとしてバグらせ、かなり手間取ってしまった。素直に遅延セグ木でぶん殴ればよかった。

Gはクエリ番号をセグ木のインデックスと見て数列のインデックスを舐めながら操作を乗せたり下ろしたりし、取得の度に一時的にキャンセルすればよいと考えた。しかし冷静になるとキャンセル回数が毎回 $Q$ 回くらいになる可能性があって間に合わない。そこでクエリ平方分割を行い、毎回 $\sqrt Q$ 個に抑えることにした。あとは実装を頑張る。

ランダムケースで試すと思ったより遅かったが、バケットサイズを調整して一度に処理するクエリを多くすると速くなった。どういうケースに弱いかわからないのでそこまで多くはせず、最終的には1500クエリごとで提出。ところが同時に行っていた定数倍高速化にミスがあって、サンプルすら通らないコードを投げてしまったらしい。修正してAC。3secだったのでまあまあ余裕があった。

56分1ペナで全完。Fに手間取ったと思っていたが、それよりGを瞬殺できなかったのがダメだったらしい。37位だった。Gはクエリを点 $(l,r)$ に乗せて $[1,i]\times[i,N]$ を取得するという典型的な言い換えをすれば終わりだったらしい。そういうテクニックがあることを見知ってはいても、実は使えたことがない気がする。

コードゴルフはAのみ。ソートした $S$ の2文字目「でない」文字を探す。Nibblesにはfind indexとfind indicesがあって、今回は一か所見つけるだけなのでどちらでも同じに見えるが、後者でだけ使えるnotによってわざわざ2文字目「でない」文字を探す必要がなくなり縮んだ。

www.youtube.com

動画の投稿まで済ませ、午前0時からUniversal Cup 24回目、Chongqingセットに出た。

https://qoj.ac/contest/1530

チームでCFILAGKの7完、12位。自分はLとGを解いた。

最初にLを読み、解けそうだと感じて手で実験を始めた。risujirohさんのC、NyaanさんのFが通ったところで考察がまとまったので実装へ。しかし念のため愚直コードも書いて比較したところ落ちてしまった。一旦PCを空けて考察をチェックし、間違いを発見。NyaanさんのIが通ったところで再度実装に入り通した。

左端がR、右端がLの場合が非自明で、この場合文字列は/(R+L+)+/と分解できる。ランレングス圧縮した状態でRL、RLRL、RLRLRLのケースを手計算し条件を眺めたところ、一般の形がエスパーできたのでそれを実装したという感じ。詳しい条件は省略するが交代和が出てきた。実は文字列が開き括弧Rと閉じ括弧Lによって正しい括弧列になる場合後手勝ちらしい。

その後risujirohさんがAを通した。ここまでが簡単枠のようだ。

Gは、 $L$ が固定されているなら、 $|L-h_i|$ が狭義単調減少したのち狭義単調増加するという条件になる。減少と増加が切り替わるインデックスを $b$ と書くと、 $i\lt b$ か否かで $|L-h_i|$ と $|L-h_{i+1}|$ の大小関係が決まる。そしてこれは $\frac{h_i+h_{i+1}}2$ と $L$ の大小関係で表現できる。

ここで $L$ を昇順に試すことにする。すると、しきい値 $\frac{h_i+h_{i+1}}2$ より大きくなるタイミングで $i$ と $b$ の大小関係が切り替わる。これを差分更新すればよさそう。 $i\lt b$ なる $i$ が続く区間と $i\ge b$ なる $i$ が続く区間をそれぞれ管理しておくと、更新された点が関わるペア $(u,v)$ を「 $l\le u\lt b\le r$ なる $(u,v)$ 」という形で記録できる。

ところで今触れなかったコーナーケースがある。それが $h_i=h_{i+1}$ 。実は $|L-h_i|$ の最小値だけ同じ値が2回連続することが可能なのだ。逆に言えばそこでしか出現できないので、先ほどの $l$ と $r$ を求める際に注意深く扱えば対処は可能。

自分がGを実装する前からNyaanさんはKに取り組んでおり、MLEに苦しまされていたようだが無事通っていた。その間自分とrisujirohさんはDを考えていて、自分が解けたと主張。実装に移るも微妙な考察ミスがあったりして、30ケースから先に進めなかった。risujirohさんはNyaanさんと共にJを考えていたらしい。そちらは進捗なしとのこと。

感想戦。CFIは自明らしい。この3問は公式Discordによれば昔の中国ICPC地区大会から持ってきた問題とのことで、セットの中でもとりわけ簡単に見える。Aは概要を聞いてすぐ寄与を考える解法が思いついた。まあコンテスト中はノータッチだったのだし、感想戦で冴えを発揮してもしょうがない。

Kは永続平衡二分木と双対セグ木を使って通したそうだ。永続だから $O(1)$ でコピーできて、平衡二分木だから $O(\log)$ でマージができるのだろう。それならできそうな雰囲気はある。詳しい話は一切わからず。またクエリ3に対応できるよう平衡二分木を書き換えるのも大変そう。永続重み平衡木に書き換えたらMLEを回避できたと聞いた。

Persistent-Weight-Balanced-Tree(永続重み平衡木) | Luzhiled’s Library

感想戦後に追加で1時間ちょっと格闘し、Dが通った。基本的なアイディアはコンテスト中に出せていて、細かいところが詰め切れていなかった。

区間の端点 $0\dots N$ を頂点だと思うことで、ノード $[l,r)$ と辺 $l\leftrightarrow r$ を対応させ、 $L_i$ と $R_i$ を連結にする問題と読み替える。まず最初に $0\dots N$ をすべて連結にしなければならないケースを考える。葉のほうから辺を使うか使わないか決めていったとき、ノード $[l,m)$ と $[m,r)$ を見た後はもう $m$ と繋がる辺は存在しない。

この性質を用いて、ノード $[l,r)$ 以下の辺を見たとき $l\dots r$ が連結になる場合の数 $a$ 、ある $l\le i\lt r$ について $l\dots i$ と $i+1\dots r$ が連結かつ $i$ と $i+1$ が非連結になる場合の数 $b$ を持ち、下から決めていく。 $[l,m)$ に対し $(a_x,b_x)$ 、 $[m,r)$ に対し $(a_y,b_y)$ があるとき、 $[l,r)$ に対しては辺 $l\leftrightarrow r$ も考慮して $(a_z,b_z):=(2a_xa_y+a_xb_y+b_x a_y,a_xb_y+b_x a_y)$ となる。

さて、一般のケースでは $l\le i\lt m$ と $m\le j\lt r$ について $i+1\dots j$ が孤立してもよいことがある。具体的にはその内と外にまたがる連結成分がない場合。これに対応するため、先ほど $b$ を「ある $l\le i\lt r$ について」と定義したが、各 $l\le i\lt r$ について個別に持っておくことにする。そして、今のように $b_{x,i}$ と $b_{y,j}$ をマージできる場合、その積を $b_{z,i}$ と $b_{z,j}$ のどちらか一方に足す。

$i+1\dots j$ が孤立してもよいことさえ分かっていれば、 $i\leftrightarrow i+1$ と $j\leftrightarrow j+1$ のどちらかは繋がっていたと見なしても問題ないのだ。これで切れ目が増えていく問題は解消できる。愚直を書いたらWAは出なかった。コンテスト中は高速化も一緒にやろうとして、マージ可能条件を正しく扱えていなかった。

高速化については詳しく説明するのが困難。まずマージテクで $i$ または $j$ を全探索する。例えば $i$ を全探索したとき、 $i$ や $r$ をまたぐ連結成分が存在しない $j$ の最大値はセグ木上の二分探索で求めることができる。また $i$ を降順に見ると、実は使用不可能な $j$ がどんどん増えていくので、それを適宜キャンセルしていける。

以上、 $O(N(\log N)^2)$ で解けた。問題文にはTL 1secと書いてあるが1759msで通っている。最初のACは1467msで、それからちょっと整理してみたら伸びてしまった。

Submission #339235 - QOJ.ac

朝になった。大学入試2次試験初日の朝。TLに京大のタテカンの写真が流れてきた。以下のツイートの写真2枚目にある「タテカンの元ネタ全部分かるやつガチで危機感持ったほうがいい」が大好き。確かに、ちゃんとネット断ちできていれば流行りのネタはわからないのか。

京大２次試験会場のタテカン２ pic.twitter.com/9szQeAB7mW
— 京大職員同好会 (@kusyokuin) 2024年2月24日

午前9時就寝。

02/25(日)

午後6時前には目を覚ましていた。今日は珍しくコンテストのない週末。腹も減ったし外食しに行こうかなと考えていたのだが、昨日シャワーを浴びずに寝てしまったので、外出するならその分をこなす必要がある。これが面倒で面倒で仕方なく、空きっ腹を抱えて寝転がりながらずっとなろうを読んだりKoP 5thの生配信を見たりしていた。

www.youtube.com

日付が変わる前にようやく布団を脱出。外出は諦めたからシャワーも寝る前でいいだろう。パスタを食べて日記を書き始めた。しばしばなろうに吸い寄せられつつもそこそこ書き進めて、午前10時前就寝。

今週は2555話まで進んだ。以前読んだことのあるのは2600話弱までだから、あと少しで知らない話が始まると思うと非常に楽しみ。と同時に、これだけ長大な話でしかも読んでから3年近く経ったにも拘わらず、要所要所で話を覚えているという点に、自分のことながら驚いていた。それだけ好みだということ。

2024-02-19

週記（2024/02/12-2024/02/18）

02/12(月)

午前4時に一瞬目を覚ましたらしいが、早々に二度寝に入ることができた。午前7時起床。布団に横たわったまま昼までずっとなろうを読んでいた。

午後1時頃に布団を脱出。今日は建国記念の日の振り替え休日だからインターン先定例会は行われないし、生協も営業していない。なので夜中までずっと先週の週記を書いていたが、案の定なろうに気を取られたりしており、あんまり捗った感じはしなかった。

日付が変わる前に投稿した。久しぶりにコンテストの感想をいくつか書けたが、週末のコンテストまではたどり着けなかった。週末は基本コンテストに出る以外の行動をしていないため、そこが埋まっていないと本当にスカスカになり、残念。最近の週記はいつもそう。完全に手が回っていない。

明日の午前中は、留学生が仙台を離れるにあたっての諸手続きに付き合う予定がある。せっかく外出するので、ついでに郵送して来ようと部屋の賃貸借契約の更新用書類を準備した。

その後TLを眺めているうちにうっかり椅子で寝てしまった。少しして目を覚まし、慌てて布団に移動して就寝。午前3時だった。

02/13(火)

午前8時起床。準備して外に出ると雲が一つもない、途轍もなく良い天気だった。待ち合わせは区役所前に午前10時。早めに到着したので近くの県庁で自分の用事をすべて済ませたうえ、施設の位置も確認しておいた。

無事合流してまずは転出の手続き。転出届を記入した後は窓口で渡された紙に従って区役所をウロウロしていたら自動的に終了した。やはり留学生が多いのか、寮の住所を一発で記入できるスタンプが区役所に用意されていて面白かった。そういえば彼は明日仙台を去るらしいが、帰国はその3週間後とのこと。それまで日本国内を旅行して回るそうで、ホテル代が高かったとぼやいていた。

1時間くらいで予定が完了。お互い朝まともに食べていなかったので、昼には少し早いがつけ麺屋で昼食を摂った。開店直後だったため並ばず入れてラッキー。その後仙台土産を探すということで駅横のビルや駅ナカの店舗をウロウロした。

最初はポケモンセンタートウホクに連れて行ったが、ここ限定の商品はずっと品切れらしい。東京にメインの店舗があるなら今ここで買う必要はないので、同じビルのジャンプショップやガンダムベースもただ練り歩いただけになってしまった。結局駅ナカでずんだ饅頭を購入。メジャーな商品は日本にいる間に賞味期限が切れてしまうようだ。

駅のステンドグラス前で記念撮影し、午後1時に解散。これで留学生チューターとしての活動は終わりになる。

その後ゲーセンに行って20クレほど遊んだ。相変わらず残っている未プレイの譜面をいくつか触り、理論値を狙っていた。あまりドブらなかったので調子は良かったのではないか。

バグ理論値等 pic.twitter.com/mOd5qSjjNU
— こたつがめ (@kotatsugame_t) 2024年2月13日

ミスドで食事して午後7時過ぎ帰宅。夜中のコンテストまで仮眠するつもりだったが、外出中にインターン先からタスクが降ってきていたので対応した。自分の管理しているツールについて使い方の説明をするというもの。昔書いたドキュメントを引っ張り出して追記していた。

思ったより時間がかかって、布団に入ったのは午後10時。1時間半後のコンテスト直前にギリギリ起床に成功し、慌てて録画の準備を整えてCF #925 div.3に参加した。

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

Aはまあ何でもできる。最初に $n$ から3引いておくと少し楽だったかもしれない。Bは左から順に、一つ右に押し付ける。Cは右端を残す場合・左端を残す場合・両端を残す場合でそれぞれ操作すべき区間が決まる。Dは $x,y$ で割ったあまりをペアにしてmapで持つ。二つの条件のうちどちらかが成立するペアを数えるものと誤読してしまい余計なコードを書いていた。

Eは桁数だけが問題。先手が操作すると下の0が消えるのは分かりやすい。後手の操作は、上位にくっつけた数の下の0を消せなくすると思うと見通しが良い。結局お互いは下の0が多い数から順に消したり保護したりすることになる。最初の問題文では $n=1$ のとき先手も操作できないという解釈が可能だが、サンプルで落ちるのでギリギリセーフか。後から修正が入った。

Fはすべての条件を有向辺で表現してトポロジカルソート。Gはタイプ3と4をいったん無視するとタイプ1と2が交互に並ぶ。どちらが先頭か二通り試すとタイプ3の入る隙間とタイプ4の入る隙間が数えられるので、重複組み合わせで入れ方が求まる。ピースが存在しないケースで壊れてしまったがサンプルにあって助かった。

40分で全完し25位。Eに10分かけたのは遅かったらしい。

www.youtube.com

またしばらくインターンの作業を行った。シャワーを浴びて午前5時半就寝。

02/14(水)

午後2時～午後9時半、午前2時半～午前4時半になろうを読んでいた記録がある。今日は布団から出ず。

02/15(木)

午前8時に目を覚ましてなろう。ふとTLを見たら新刊情報として予約していない本が流れてきた。見落としがあったらしい。それを注文するついでに3月の新刊チェックも行い、計23冊注文した。

インターン先の業務開始と合わせてメッセージを送信したところすぐにレスポンスがあって、その後3時間ほど追加で作業を行った。

学食が閉店しそうになったので急いで出発。家を出た瞬間ムワッとした暖気が押し寄せてびっくりした。後から調べたところ今日の仙台市の最高気温は21.1度で、2月の気温としては観測史上最高を記録したらしい。冬の終わりを感じてしみじみとしていたが、そんなレベルではなかったようだ。

学食の営業時間には問題なく間に合った。食後は購買でラノベを受け取って帰宅。すぐ布団に入って午後5時まで昼寝し、起きてからも4時間くらい横たわったままなろうを読んでいた。

実は明後日土曜日に日本数学会の東北支部会で発表することになっている。準備時間はたくさんあったはずなのに今日まで特に何もせず過ごしてしまった。発表時間が修論発表会と同じ15分だから基本的にはスライドを使いまわせるはず……と思ってしまい全く気が向かなかった。

実際にはゆっくりしゃべることを考えると分量は減らすべきだし、聴衆には自分の修論発表を聞いた人もいるだろうから、ある程度の書き直しは必要。ということで布団を脱出してスライドと向き合った。

向き合って構成を考え直しているだけですぐに時間は過ぎていき、午後11時半からCF #926 div.2へ。

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

Aはよい。Bはサンプルの説明がほとんど答えで、 $k\le 4n-4$ までは1マス塗るごとに2本の対角線をカバーでき、最後の2本だけ1マスずつ必要。

Cは難しい。各ターン同じ金額を賭けるかと思ったがサンプル3で勝てない。手で試そうとしたところ、閃いた。1,2,4,8と賭けていけば良い。これそのものを閃いたというよりは、負けたら倍にして賭けなおす戦略を思い出したというのが近いか。ともかくこの戦略がわかってしまえばあとは簡単で、負けた分を取り返せるギリギリの額を賭け続ければよい。

Dは木dp。部分木の根から始まるパスに危険な交差点が最大いくつ乗るかを持つ。

Eはまず、辺ごとにそれがカバーできるペアの集合を求めた。しかしそこからbitDPしようとして間に合わないことに気づく。OR convolutionもよくわからない。考えているうち、カバーできるペアの集合の種類数がそれほど大きくならないことに感づいた。証明はできなかったが出してみたら通った。

Fは簡単。通りがけ順に頂点を並べるとソートされた列が得られる、というのが条件なので、その列から値の範囲が求まる。あとは適当に重複組み合わせ。 $\binom{n}{k}$ のうち $n$ は非常に大きな値となるが、 $k$ の総和が $n$ 以下なので、ループを回して計算する。

全完24位。Eについて、集合の種類数が少ないことの証明は、ペアに登場する頂点だけ集めた圧縮木を考えれば一瞬だった。圧縮木の辺数は高々 $4k-2$ 本で、これに空集合を足したものより種類数が多くなることはあり得ない。録画中、振り返りをしているときにプログラムで適当にメモ化再帰して求めた値と一致した。正しく計算できていたことに感動。

www.youtube.com

以前draw.ioで作った図についてホスフィンに意見を求めたところ、全体を一気に見せるのではなくアニメーション表示で少しずつ出すとよいと助言を貰った。少しずつ変えた図をたくさん用意すれば実現はできるが、TikZで頑張るほうが後々楽だろうと思い、挑戦することにした。3時間くらい格闘して何とか綺麗なものが完成。

beamerでのアニメーション表示について一つ。スライドの上部に文章Aを表示したまま下を文章BとCで切り替えたいとする。BとCで量に差があると、A+Bを表示するときとA+Cを表示するときで占有する高さが異なるわけだが、ここでデフォルトの中央揃えを使うとAの位置が上下にずれて、ページ遷移のときに少し見栄えが悪い。

これを解決するのに、自分は\phantomみたいな感じで領域だけ確保する命令があるものと思い、ずっと探していた。しかし見つからない。諦めてホスフィンに聞いたところ、中央揃えではなく上揃えにするとよいのではと指摘された。この方法は目から鱗。確かにAの位置が綺麗に揃ってくれた。

こういった調整で力尽き、机で寝落ちしていたらしい。午前6時半くらいに布団に移動して再度就寝。

02/16(金)

午前11時半起床。今日頑張ればスライド作成も発表練習も問題なく終わるだろうと思っていたが、予定を確認すると夜に競プロサークルの追い出しコンパが入っていた。ちょっとまずいかもしれない。

とりあえず学食で腹ごしらえ。昨日の異常な陽気は早くも過ぎ去ったようで非常に寒い。寒暖差を原因とする錯覚かと思っていたが、単純に2月の平均的な気温を下回っていたようだ。

帰宅してスライド作成。やっぱりTikZで作った図は非常に綺麗に見える。幸い昨日の頑張りで身についた技術を使えば他の図も置き換えられそうだったので、もっぱらその作業をしていた。してしまった、のほうが近いか。丁寧に作りこみすぎて時間切れになり、未完成のまま午後6時半くらいに家を出た。

待ち合わせて午後7時から2時間、昨年と同じ武屋食堂のコース。料理と飲み物は以下のツイートのリプライにまとめた。会の間は大学院の話とTUPCの問題の話をしていた。

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

店を出て記念撮影を行った後、1時間くらい路上で立ち話をしていた。その後解散。昨年は二次会でカラオケ屋に行ったが今年はなし。

帰宅してスライド作成を再開し、午前3時くらいに何とか完成した。構成を練っていたら修論発表で使ったスライドはほとんど残らなかったし、何なら自分の結果の説明もほとんど残っていない。専門が離れた人が多いと予想されるから、最初に自分の結果を見せた後は前提となる部分の説明で終えることにした。

次に発表練習。pdfにして40ページを超えるスライドだが、ページ数が多いのはアニメーションのせいで、図もたくさん入っているため最初の練習は14分くらいで終わった。ちょっと足りないかな、という感覚で何度かやり直したら15分前後に収束。しかし今から考えると15分の発表でギリギリの時間になってしまうのは良くなかった。最初の14分くらいが一番良い。

スライドと発表練習の録画を先生に送り、シャワーを浴びて午前7時半就寝。

02/17(土)

午前11時半起床。先生からスライドに関するコメントが返ってきていたので、それに沿って1時間くらいスライド修正を行っていた。その後出発。いい天気である。今日は日本数学会東北支部会。

pic.twitter.com/wa23CBlZAb
— こたつがめ (@kotatsugame_t) 2024年2月17日

会場の宮城教育大学は初めて行く場所なので念のため早めに家を出たのだが、開会30分前に到着してしまい、一人ぽつねんと座って待ちぼうけしていた。同期が一人来ており、声をかけてもらえて嬉しかった。

自分の発表について。まず何よりも、つつがなく終了できてよかった。2件来た質問にはどちらもまともな返答ができたと思う。修論発表会の時とは傾向が違い、純粋に内容に関する質問が来たので答えやすかった。

四つくらい飛んできたうち三つは「〇〇のケースではどうですか」「〇〇を知っていますか」というもの
週記（2024/01/29-2024/02/04） - kotatsugameの日記

時間は15分を少しオーバーしてしまった。10分のベルが鳴った時点で発表練習の時より2ページほど前にいてかなり焦った。また、質問対応用のページも含めてページ番号を振ってしまっており、終わった後同期から「スライドが大量に残っているのに終わってびっくりした」と言われてしまった。なのでもしかしたら発表内容を全部話せていないと思われているのかもしれない。

休憩時間に4年ゼミでお世話になった先生と話した。自分の研究について「面白いことをやっているね」とお褒めの言葉を頂戴し、非常に嬉しい。その後特別講演でその先生の発表を聞いたのだが、扱う対象こそ異なれど「双対」と名付けられた関係に着目している点は共通しているから、その点で興味を持っていただけたのかもしれない。

閉会後すぐ帰宅。午後5時過ぎに家に帰りつき、即座にUniversal Cupに途中参加した。23回目・Shanghaiセット。今日は夜中にCF combinedがあるので、無理やり3人揃おうとすると午前3時からのウィンドウになる。それよりは、ということでいつもの午後2時から二人で走ってもらっていた。実は自分も学会中に問題だけ読んでいたりする。

https://qoj.ac/contest/1516

書く：UC

シャワーを浴びて午後9時からABC341。

Toyota Programming Contest 2024#2（AtCoder Beginner Contest 341） - AtCoder

Aはよい。サンプル1の出力は341の2進数表示のようだ。Bは昇順に。Cは始点を全探索してシミュレート。数えるべきものが終点であることに気づいていなかったので、考察を1ステップ飛ばしたらしい。Dは二分探索。上限がどこかわからなかったのでunsigned long longにして9e18を使った。後から丁寧に評価したところ、 $2NK$ で抑えられるらしい。

Eは同じ文字が隣接する箇所をsetで持った。Fは $W$ の昇順に、その頂点にコマが1個あるとき何回操作できるか求めた。計算にはナップザック的なdpを用いる。

Gにかなり時間をかけてしまった。 $k$ の降順に問題を解くことで過去の答えを利用する。区間 $[k,r)$ の平均が暫定的に最大となるとき、次に追加すべきなのは $k=r$ のときの答えとなった区間である。そこの平均値が今の平均値を上回れば採用。そうでなければ今の区間が最大となる。これは式変形でも言えるし、平均値 $a,b$ をマージして得られる平均値が $\min(a,b)$ 以上 $\max(a,b)$ 以下という直感からもわかる。

このマージ操作は、 $[k+1,N)$ をいくつかに分割した区間が並んでいるときに先頭に $[k,k+1)$ を追加し、平均値が単調減少になるまでまとめていくという風に見ることができる。つまり愚直にやっても線形時間。考察の途中、必要な区間が $[k+1,N)$ の分割であることに気づかず、中途半端なところの答えも全部考慮する必要があると思っていた時間があった。

全完23位。Fまでの速度では決して負けていないので、やはりGに20分かけたのが敗因らしい。コードゴルフはAをNibblesで、DをRubyでパッと書いておいただけ。

www.youtube.com

コンテスト前、自分がシャワーを浴びている間に母から電話がかかってきていた。以下のような事情らしい。改めて電話がかかってきたのでしばらく通話し、3月末に仙台に行く予定だと伝えられた。またTwitterに関して、アカウントを作ろうとしたら姉に止められたということも聞いた。まあ陰謀論に染められた話も聞くし、危険性は確かにありそう。自分のツイートだけ見るなら全く問題はないと思うが、今のTwitterは余計な情報もたくさん表示してくるから……。

ｶｰﾁｬﾝと電話した。Twitter閲覧がログイン必須になったせいで僕のリアルタイムの動向が確認できず困っているらしい。イーロン許せへん
— こたつがめ (@kotatsugame_t) 2024年2月17日

午後11時半からはCF combined、think-cell Round 1に出た。

Dashboard - think-cell Round 1 - Codeforces

書く：CF

www.youtube.com

日記を書いて午前6時就寝。

02/18(日)

昼頃3時間ほどなろうを読んでいた記録がある。

午後5時に目覚ましで起床。ARC前にDMOJに参加した。来週火曜日までのコンテスト。

The Contest Contest 1 - DMOJ: Modern Online Judge

コンテストとコンテストの間に何かできるほどの気力は残らなかった。午後9時からARC172。

AtCoder Regular Contest 172 - AtCoder

Aは大きなピースから適当に詰めていってよい。また $H\times W$ のピース（の左上）から $A\times A$ を切り取ったとき、残りの階段状の領域をさらに切り分けて $A\times(W-A),(H-A)\times A,(H-A)\times(W-A)$ の三つに分けてもよい。一回操作するたびにピースが二つ増えるだけなので、十分大きなピースを愚直に探して切り出す、という操作を $N$ 回繰り返しても間に合う。

Bの条件は、同じ文字が出現できる最短の間隔として表現できる。具体的には $N-K$ 文字離れていなければならない。これを言い換えると、すべての文字はその直前 $N-K$ 文字と異なるということになる。当然その $N-K$ 文字もdistinctであるから、候補は $L-(N-K)$ 通り。先頭 $N-K$ 文字は微妙にずれるが同じ感じで候補を数えることができ、掛け合わせることで答えになる。

Cは投票者 $2$ から $N$ までで作った得票数の差の列に投票者 $1$ を挿入することを考えた。それによって値がどう変化するか調べ、挿入した結果が等しい2か所を見出そうとしたところ、一人ずらすパターンだけ調べればよいことに気づいた。実際のチェックは簡単。

Dは1点追加するごとに1次元ずつ増やす方針を考えていたがまともな計算量にはなりそうにない。30分くらい経って順位表を見たらEのほうが少し多く解かれていたので、自分もそちらに移った。

Eはまずより小さい10べきで実験した。どうやら10と互いに素な $n$ が $n^n\bmod{10^k}$ と一対一対応するらしい。そこで $X$ からスタートして $n\rightarrow n^n$ という変換を繰り返し、ループして $X$ に戻ってくる直前の値を答えるという解法を考えたが、ループのサイズがそこそこ大きくなるようで無理だった。

もう少しまともに解こうと思い、 $\bmod{2^9}$ と $\bmod{5^9}$ に分解した。 $n$ の候補を $\bmod{5^9}$ 側で絞り込み、2⁹回探索したい。 $n^n\equiv (n+5^9)^{n+5^9}\pmod{5^9}$ だったりしないかと思ったが、残念ながら $n^{5^9}\equiv 1$ でないためずれてしまうようだ。しかしこの値は $n\bmod 5$ に依存することが実験から分かったので、1から4まで全部試すことが可能。

まとめると、まず $m=1,2,3,4$ それぞれについて $X$ に $m^{5^9}$ の逆数をかけていき、前計算しておいた $1\le n\lt 5^9$ に対する $n^n$ と一致しないかチェックする。次に、そこで見つかった $n$ に対し $n,n+5^9,n+2\times 5^9,\dots$ を答えの候補として、それぞれ計算して判定する。この方法で答えが求まる……はず。

とりあえず答えは求まるようになったので提出したら、TLE。調べたところ答えのチェックを2¹⁷回ほど行ってようやく見つかる数があるらしい。どうにもならずそのままコンテストが終了した。そのまま考えていたら、 $m^{5^9}$ の逆数をかけていく部分に無駄があることに気づいた。定数回のループを回していたが、最初の数に戻ってきた時点でbreakしてよい。これで試すと最大2¹¹回で見つかるようになり、1234msで通った。

3完227位。Cまではかなり順調だったのだがその後がダメダメ。久しぶりにひどい順位を取った。Eは最終的に219人に解かれたようだ。いろんな解法をTLで見てから自分の考察を振り返ると、解ける方向に進むチャンスをことごとく逃していることがわかる。

まず答えの候補を $\bmod{5^9}$ で求めるところ。ちゃんとオイラーの定理を使えば、 $\varphi(5^9)=4\times 5^8$ から $\mathrm{lcm}(4\times 5^8,5^9)$ まで全探索することで確実に見つかることがわかり、変な探索を行う必要がなくなる。次に $n^{5^9}\not\equiv 1\pmod{5^9}$ に気づいたところ。なんと $k\ge 2$ で $n^{10^k}\equiv 1\pmod{10^k}$ となるらしい。まさか分解しないほうがうまくいくとは……。

www.youtube.com

$(\mathbb{Z}/p^k\mathbb{Z})^\times$ に対する苦手意識をツイートしたらWikipediaの記事を教えてもらった。

Multiplicative group of integers modulo n - Wikipedia

そこで、せっかくなので先週のDMOJの最終問題と3時間ばかり格闘し、通した。三つの答えのうち二つ目まではコンテスト中に正答できていたので、最後の数え上げに取り組んだ。

Yet Another Contest 8 P6 - Into the Woods - DMOJ: Modern Online Judge

問題文の集合 $S$ は、群論の言葉を使えば「巡回群かつ $(\mathbb{Z}/N\mathbb{Z})^\times$ の部分群」ということになる。これを $|S|$ ごとに数え上げればよい。先ほどのWikipediaによれば $(\mathbb{Z}/N\mathbb{Z})^\times$ はいくつかの巡回群に分解できるので、分解後を1個ずつ見ながらdpで求めてみる。

今 $C_a$ ができているところに新しく $C_b\subseteq C_n$ を追加する。 $b\mid n$ なら $C_b$ の選び方は一意。また出来上がる巡回群は $C_{\mathrm{lcm}(a,b)}$ となる。問題はその個数で、うまく巡回するような $C_b$ の「並べ方」は一意ではない。愚直と比較していろいろ試した結果 $\varphi(\gcd(a,b))$ 通りと分かった。

https://dmoj.ca/submission/6211453

式変形でも求まる。巡回群の「並べ方」はその生成元の個数 $\varphi$ と一致するから、生成元を固定して数え、改めて割ることで $\frac{\varphi(a)\varphi(b)}{\varphi(\mathrm{lcm}(a,b))}$ を得る。計算すると $\varphi(\gcd(a,b))$ に一致する。 $\varphi$ は完全乗法的ではないのだが、この変形はうまくいく。

ところで、この考え方ができるなら最初に生成元として $(\mathbb{Z}/N\mathbb{Z})^\times$ の要素をすべて試せば一発で出る。作れる巡回群のサイズが $(\mathbb{Z}/N\mathbb{Z})^\times$ における位数と一致するため、カウントしておき、最後に $\varphi$ で割ればよい。maspyさんのコードはこれを用いている。実はそこから上の証明をつけられたという流れ。

日記を書いて午前8時半就寝。

なろうは現在2354話。週の後半はほとんど読み進めていなかった。このままフェードアウトできれば一番良いのだろう、という思いと、せっかく以前読んだ近辺まで戻ってきたのだからあと少し進んでまだ読んだことのない箇所に突入したいという思いがある。

2024-02-12

週記（2024/02/05-2024/02/11）

02/05(月)

午後4時過ぎにふと目を覚ました。起き抜けは謎の喪失感だけがあり、何が何だか分かっていなかったが、少し考えてインターン先の定例会に寝坊したことに気づいた。どうやら昨日寝る前に目覚ましをかけ忘れたらしい。慌ててPCに向かうも進捗報告のフェーズは終了しており、勉強会から参加した。

今日のテーマは汎用ビジュアライザについて。来月開催されるマスターズ選手権の予選で使おうとしているそうだ。このコンテストは決勝が社会人対象ということで話題になっていたが、他にもチーム戦だったり、ビジュアライザが提供されなかったりと特殊な点が多い。特にそのチーム戦向け機能として、サーバーを立てることでリアルタイム共有・同時操作を可能にしたとのこと。何がどうなっているかわからないものの、かなり便利そうなことはわかる。

解散は午後6時。先週までならこの時間から大学生協に行けたのだが、今週から春休み期間で学食は昼の部2時間のみ、購買も午後5時までですでに閉店してしまっている。しょうがないのでずっと先週の週記を書いていた。

週記は体裁だけ整えて午後9時くらいに投稿してしまった。博士課程進学試験が明日に迫り、それに向けて修論発表会のスライドを更新しなければならないので、あまり時間をかけていられない。ところがそのスライド更新もどうにもやる気が出ず、食事したりなろうを読んだりで2時間ほど溶かしてしまった。

何とか気持ちを奮い立たせて取り組み、午前8時くらいまでかけて24ページから39ページに増やした。もちろん重要なのはページ数ではないが、内容についても書きたかったことは盛り込めたのではないか。発表会で話した内容を深掘りしたり、飛ばした部分の説明を加えたり。さらに、当時来た質問に対してちょっとした回答を用意した。

外を見ると雪が積もっていた。明日は早めに起きる必要がありそうだ。シャワーを浴びて午前9時就寝。

02/06(火)

正午、起床。なんとか布団から出て地下鉄で登校し、午後1時過ぎに大学に着いた。30分ほど時間に余裕が持てたので学食で腹ごしらえ。まともなメニューがないと勘違いして「ガリたま唐揚げ丼」というこれから人前で話すとは思えないメニューを選択してしまったが、注文してからカツカレーの存在に気付いた。

午後1時半から進学試験開始。この試験は数人の先生の前で40分ほど修論の内容について説明し、その後10分質疑応答に答えるという形式。普段のセミナーのように、と声をかけていただいいて、緩めの雰囲気で行われた。こうなるとスライドを用意してきた分、むしろいつもより話しやすいとさえ言えるかもしれない。

冒頭で早口すぎることを指摘されたのでゆっくり喋ることを意識したほか、途中途中で質問が来たり少し議論が行われたりした結果、全体で1時間かかった。ただ感触は非常に良いし、何より楽しかった。そういえば最後に博士課程卒業後の進路を聞かれたことを記録しておく。自分はプログラマーと答えた。まあ定番の質問という話だし、これで落とされたりはしないだろう。

自分だけ退室した後、先生方が相談して合否を決める時間がある。暇なので誰かいないかウロウロしていたら、同じ教室で次に試験する人が教室の前で待っていて、それが知り合いだった。スーツを着てきていてびっくり。自分は今日も私服だった。

しばらくすると指導教員の先生が教室から出てきて、合格を伝えられた。ツイートは数時間後のもの。

東北大学大学院理学研究科数学専攻博士課程に合格しました
— こたつがめ (@kotatsugame_t) 2024年2月6日

同時にコメントとして「修論の結果があまり苦労せず出たもののようだから、博士課程で頑張っていけるか心配」といった感じのことを言われていたらしい。まことにその通りでございます……。結果についても複雑なことをしていないのはそうだし、関連を調べるうちにどんどん自明になってしまった。正直、自分に近い分野を専門にしている先生がいないから審査をすり抜けただけなのではないかと疑っている。

指導教員の先生に自分の博士課程進学を承認していただけた決め手もよくわからない。修士2年間ずっとD進したいと駄々をこねていたら折れただけか？それとも何かを評価してもらえているのか？こればかりは人と比較できることでもないし、面と向かって聞く勇気もないので、不安だけが付きまとう。

とまあネガティブなことばかり書いてみたが、合格自体はもちろんおめでたいことだ。とりあえず3年の期間を追加で与えられた。修士課程、特に前半は正直何もわからないまま終わってしまったので、そのあたりの反省を活かしていきたい。

数学棟の談話室に移動して、春休みの予定について2時間ほど先生と話した。修論の修正、学会発表、投稿論文準備。毎週のセミナー発表準備とは異なり、重くて締め切りの少し遠いタスクが積みあがる。一番苦手なタイプだ。何とかなってほしい。

その後留学生と合流し先生含め3人で街に繰り出した。自分の試験合格記念に加え、留学生がもうすぐ母国に帰るのでそのお別れ会で食事に行く。彼の留学プログラムは秋学期のみで、その集大成として今日、同じキャンパスの別会場でポスター発表をしていた。本当は見に行こうとしていたのだが思ったより会場が遠くて足が向かなかった。

約束の30分前に最寄り駅に到着したため、駅直結の藤崎をしばらく練り歩いて時間を過ごした。午後5時半に集合して入店。メンバーは3人に加え、我々のセミナーに参加していた競プロサークルのメンバーのうち二人が来てくれた。店はそのサークルでもよく使う武屋食堂。

食事 pic.twitter.com/qhg7f8tJ1R
— こたつがめ (@kotatsugame_t) 2024年2月6日

生成拡張botみたいな写真を撮ってしまったなと思っていたが、実際にTLでそういう言及を見かけた。よく見ていますね。

話題はもっぱら競プロの話になってしまった。日本語だったこともあり留学生には申し訳ない。午後7時に解散し、他の人が帰宅するのを尻目に自分はゲーセンに行った。

夜中にCFがあるので今日は10クレのみ。今日は手元動画を撮っていた。素手でのプレイだったがゲーセンにおしぼりが用意してあって、毎回手を拭くことを心掛けたところかなり快適にプレイできた。新しいゲーセンで台が綺麗ということもあるかもしれない。スライダーをおしぼりで拭くと誤反応が生じて面倒なことになる。

SUPER AMBULANCE 9-0-0 手元 pic.twitter.com/YOuBkZIuxr
— こたつがめ (@kotatsugame_t) 2024年2月6日

午後10時くらいに帰宅し、撮ってきた手元動画を3本ツイートした。上のツイートとそのツリーにまとめてある。その後急いでシャワーを浴び午後11時半からのCFに備えていたが、10分こどふぉった。今日はCF #923 div.3。

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

Aはよい。必ずBがあるのがありがたい。Bは $s_i=s_j$ なるインデックス $j$ を記録しているものと誤読してしまった。毎回 $O(\sigma)$ かけて条件に合う文字を探す。ここで $\sigma=26$ 。Cは $a$ にしかない数と $b$ にしかない数をカウントする。

Dは各インデックス $i$ について $a_i\ne a_j$ なる $j\gt i$ のうち最小のものを前計算。右から見て要素を2種類管理していくと求まるがかなり面倒だった。クエリへの回答は $i=l$ に対する値を調べるだけでよい。Eは $p_{i+k}-p_i=\pm 1$ が条件。値が被らないよう丁寧に埋める。Fは辺を重みの降順に並べてクラスカル法をすることで、閉路に含まれる最も軽い辺がわかる。閉路の復元は適当に。

Gは左から順に見るdp。塗られたマスは基本的に連結となりそうなので境界を持てばよい……かというと、まだ不十分。連結成分が二つになることがあるらしい。まあ二つだろうが二つ以上だろうが区別する必要はなく、区間を一斉に塗ることから塗られたマスの最右と塗られていないマスの最左のみ持てばよい。 $O(n^3)$ のdp。

全完12位。

www.youtube.com

しばらくボーっとTLを眺めていた。午前4時就寝。

02/07(水)

午後4時半起床。購買はもう閉まりかけなので、外出を諦めた。布団に横たわったままなろうを読みふけり、午後9時くらいに寝落ち。

02/08(木)

午前2時に目を覚ましてずっとなろうを読んでいた。途中午前9時から正午までは寝ていたらしい。午後3時前に布団を脱出して、久しぶりのインターン先1on1に臨んだ。

今日の議題は自分が稼働を再開するにあたってのタスク確認。昨年末、取り組んでいた機械学習プロジェクトがうまくいっていないという話をしていたが、結論から言うと引き続きこれを進めることになった。本当は「進めてよいことになった」のほうが近かったりするのだろうか。半年かけて成果が出ていないため何とかすべしと言われていたはず。

このことに関して、自分の稼働時間が長いほうに勘違いされていたらしいという話を聞いた。正社員が半年取り組んでダメなら方針転換の必要があるが、自分はその数十分の一しか働いていないのだからまだ判断は早い、とかそういう感じだろうか。インターン生という立場に甘え切っている点で申し訳なさは感じつつ、今のタスクを継続できるのは嬉しい。

また、3月中旬に勉強会の発表をさせてもらうようお願いした。その前に修論関係の話が一段落してくれている予定なので、久しぶりに何かやりたい。テーマは未定。

1時間弱喋って解散。ひどい空腹に襲われ購買に行ったが菓子パンやおにぎりはほぼ売り切れていた。仕方がないのでとりあえずラノベを受け取り、帰りにコンビニに寄っていろいろ買ってきて、その一部を食べた。

今日の夜中に開催されるConstructor Open Cupに参加登録した。4時間のコンテストということで、Open Cupという名前もあり歯ごたえありそうな雰囲気。TLで少し言及を見たので出る人はちらほらいるのだろうと思った。賞品には興味なし。

Constructor Open Cup 2024 - Codeforces

コンテストサイトはCFを間借りするようだ。Muscatキャンプと同じ。ただ、念のため練習問題を2問ばかり解いておいた。solved数が一番少ない問題を開いたらすんなり解けてしまったが、本番の難易度や如何に。

まだしばらく時間があるのでこの間にDMOJに出ようかと思っていたが、微妙に眠い。諦めて午後7時半くらいから3時間仮眠し、午後11時からConstructor Open Cupへ。コンテストサイトのURLは参加者のみに配布されたようだ。解法の議論は告知ブログのコメント欄で行われていたので、ここにも書いてよいだろう。

AからGまではよいものとして飛ばす。正直説明が面倒なだけ。Hはちょうど $k$ 回操作するというのが難しいので、「 $k$ 回以下の操作で作れる」かつ「和が $k$ 以上」と言い換えておく。すると前者が $O(nk^3)$ のdpで計算できて、そのうち後者を満たさないものはまあどうにでもなる。Iは人 $1\dots i$ のうち $i-1$ ラウンドまで生き残る人の集合を管理した。Jはdpやるだけ。

Kは $x$ として $n-k$ の約数を全探索し、判定を $O(n\log n)$ で行った。 $(n-k)/x$ 文字の同じ連続部分文字列を重ならない・隣り合わないように $x$ 個取り出せればよいので、まずsuffix arrayとLCP arrayで同じ連続部分文字列のインデックスを集めソートし、 $(n-k)/x+1$ 文字以上間隔を開けるように貪欲に取り出してカウントした。

Lは $a$ をソートした列を $b$ として辺 $a_i\rightarrow b_i$ を考えるのがよい。1回の操作で $x\rightarrow y$ と $y\rightarrow z$ を $x\rightarrow z$ と $y\rightarrow y$ にしていき、すべて自己ループになったら終了。辺が $m$ 本ある連結成分なら必ず $m-1$ 回操作できるかというとそうでもないようで、サンプル5で落ちる。長さ2のループばかりあるのが問題。

相異なる3頂点 $x,y,w$ について $x\rightarrow y$ 、 $y\rightarrow x$ 、 $x\rightarrow w$ が存在すれば、2回の操作で前2本の辺を自己ループに組み替えることができるので、これを使って長さ2のループを消せばよい。連結成分に頂点が三つ以上あるケースなら必ず可能で、 $m-1$ 回を達成できる。二つしかない場合は $m/2$ 回になる。

2時間13分で全完し、5位。歯ごたえがありそうと言っていたがそれほどでもなく、日本人も別に多いわけではなかった。

しばらくTLを眺めてダラダラしていたが、シャワーを浴びて気合いを入れ、午前3時半からDMOJに出た。今開催中のコンテストは3000以下Rated。明日には終わるため、ここに感想を書ける。

Yet Another Contest 8 - DMOJ: Modern Online Judge

P1は操作する区間をdisjointにするべき。移動元と移動先を見て、区間をできる限り分割していった。P2は実験すると2要素のXORが全部作れるらしいと分かった。よって $a$ と $a\oplus X$ に共通部分があるか見て判定する。ただし $X=0$ のケースだけは同じバケツを2回使ってしまいかねないので別で処理。

P3は、ノード $u$ 以下にある鉱石の頻度配列を $\{c_i\}$ と書けば、 $k\times\#\{c_i\ge k\}$ の最大値が $u$ に対する答えとなる。まず $\{c_i\}$ はマージテクで管理することができる。またその更新は $c_i\leftarrow c_i+1$ とインクリメントの繰り返しで表現することができ、このとき答えの候補としては $k=c_i+1$ についての値しか変化しない。

以上により、 $\{c_i\}$ のほかに $\{\#\{c_i\ge k\}\}_k$ も持っておくことでマージテクと答えの更新が可能となる。このとき $\sum c_i$ が小さいほうを大きいほうにマージしなければ計算量が壊れることに注意。頂点 $1$ からdfsしたらWAが出てしばらく首を傾げていたが、 $i=1$ 以外でも $P_i=0$ となることが許されているため頂点 $0$ から始めなければならなかった。

P4はまず $N=1$ で先手が勝てるか考えた。距離2以下の2マスが黒く塗られた状態で回ってくればよい。3マス以上離れていた場合、その間のマスを選んで黒く塗ると、後手はそのマスに対して操作できないから、どのようにしてもより距離の縮まった2マスを残して返さなければならない。半々にしていけば $2\log_2 M$ ターンくらいで終わるのでOK。

ここから $N$ が一般のケースに拡張するのは簡単。最初2ターンで2マスの黒マスが得られるが、これが行と列ともに異なる場合、1マス目の行と2マス目の列を選ぶなどすることで4ターン目終了時に必ず同じ行、あるいは同じ列の2マスが黒く塗られた状態となる。あとは先ほどと同じ。

このテクニックは $N=2$ または $M=2$ のとき使えず、後手必勝となる。例えば $N=2$ なら、後手は必ず1行目と2行目に1マスずつ黒マスを残した状態で返せばよい。以上を丁寧に実装したら通った。操作回数については深く考えていない。

P5は適当に根付き木にして、頂点の深さと親の頂点番号を持てば良い。また制約から2頂点の深さが1だけ異なるときはどちらの親を答えてもよいため、深さとしては2で割った値を保存するだけで十分。これで73点を取った。

P6は $\left(\mathbb{Z}/N\mathbb{Z}\right)^\times$ の話。要素の位数を計算し集計することで $|S|$ の候補が求まる。必ず $S$ の頂点のどれかに $1$ が割り当てられているため、 $1$ を根に置くことで0個が達成可能。また $|S|$ の候補は少ないため適当に木dpすることで最大値も計算できる。ただしそのままだとMLEしてしまったので、以下のテクを適用した。かなり効いて感動。

[Idea] Using HLD to reduce memory - Codeforces

場合の数は難しい。 $N$ が素数ならある $|S|$ の候補に対しそれを達成する $S$ が1通りしかないため、部分点3は解ける。部分点2は $|S|=1,N$ しか考えなくてよいため同様に解ける。部分点1は、調べると $N=8$ だけ変なふるまいをしているらしい。それっぽい計算をしたら何とか通った。しかし一般化できず残りは誤答、合計76点となった。

以上で549点。なんとtouristをも超え初優勝となった。レートは2978→3091(+113)で、初の3000オーバー。

人のブログを読んだり日記を書いたりしていたらいつの間にか昼になっていた。せっかくなので学食の開店を待ち、正午くらいに昼食。購買でこの時間はまだたくさん残っている菓子パンを買い込み、ラノベを受け取って帰宅した。

帰宅後はすぐ布団に入り、しばらくスマホを弄っていた。午後2時半就寝。

02/09(金)

午後5時から1時間起きていた記録がある。無事二度寝に成功し、次の起床は午後9時。20分後からyukicoder 417に参加した。

yukicoder contest 417 - yukicoder

Aはよい。Bは10¹⁰⁰秒では足りないのでは？と思ってRubyで真面目に計算してしまった。ここで大幅なタイムロス。Cは客の番号を $\bmod{(X+Y)}$ で集計してよい。あとは有名な貪欲。

Dは受験者数 $k$ 、点数の総和を $s$ としたとき $\lfloor 1000s/k\rfloor=S$ が条件。式変形すると $kS\le 1000s\lt kS+k$ が得られる。 $s$ は必要になる範囲ならどんな整数にもなれると思ってよいから、 $[kS,kS+k)$ に1000の倍数があることが条件となる。 $k\ge 1000$ なら必ずOKなので、それ未満を愚直に調べればよい。

Eは $A_0=B_0=A_{N+1}=0$ 、 $B_{N+1}=10^5$ と置いて考えるとすべての条件が $B_{i+1}-B_i$ たちの下限と総和で書ける。よって必要な分を割り振った後重複組み合わせで一発。Fは、一致判定はZ-algorithm、大文字・小文字の異なる箇所のカウントは畳み込み。

Gは $A$ に一律でオフセット $t$ を加えた後、操作3と4を使って値の範囲を $[0,U-L]$ に収めるものと見た。すると不自然さは、ある区間の $t$ に対して $\lfloor(\pm t+\bigcirc)/K\rfloor$ 、のような情報の組み合わせで書ける。

$t$ の代わりに $\lfloor t/K\rfloor$ で考えると、 $\lfloor t/K\rfloor$ が1増えたときの差分で不自然さがだいたい求まる。 $t\bmod K$ に由来する微妙な $\pm 1$ は遅延セグ木を使った区間ADD・区間MINで扱える。よって区間の端点を座圧して端から舐めていけばすべての $t$ を試したことにできる。

1時間ちょっとで全完して4位。Bで手間取ったせいでyukicoderスコア形式だと後からどんどん抜かされる……と思ったら一人にしか抜かされなかった。上下どちらとも点数に結構な差がある。

一瞬だけAHC030に取り組んだ。

THIRD PROGRAMMING CONTEST 2023（AtCoder Heuristic Contest 030） - AtCoder

あとは朝方まで日記を書いたりなろうを読んだりしていた。午前7時就寝。

02/10(土)

正午過ぎに目を覚ましてしまい、案の定なろうを読むのに夢中になって二度寝ができなかった。午後2時からUniversal Cup 22回目、Hangzhouセット。

The 2nd Universal Cup. Stage 22: Hangzhou - Dashboard - Contest - QOJ.ac

書く：UC

シャワーを浴びて午後9時からABC340。

KAJIMA CORPORATION CONTEST 2024（AtCoder Beginner Contest 340） - AtCoder

書く：ABC

www.youtube.com

動画投稿作業を後回しにしてTLを眺めているうち眠気がやってきて、午前1時くらいに寝てしまった。よってこの動画は次の日投稿されたものである。

02/11(日)

午前5時に目を覚ましてなろうを読み始め、午前8時半から3時間寝ていたのを除いてずっと読み続けていた。布団から脱出したのは午後6時。

昨日のABCの動画投稿作業を行い、半からCF #924 div.2に出た。

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

書く：CF

www.youtube.com

なろうを読んでいたらすぐ眠気が来て、今日は日付が変わる直前くらいにはもう寝てしまった。

ただいま2113話。今週は270話ちょっと読み進めたということで、先週までに比べ少ない。ところで最近「ねね」「ぽきた」ツイートができていないのだが、これは毎日布団に入った後、スマホでなろうを読んでいるうちに寝落ちしているからである。これも自分の睡眠の質を下げる要因の一つ。今週の日記で「就寝」という言葉を使っているのは、実はほとんど嘘であった。

2024-02-05

週記（2024/01/29-2024/02/04）

01/29(月)

午前6時起床。修論発表の練習をしなければならないのに布団から出るのすら1時間以上かかった。食事してPCの前に座ってもやる気が出ず、しばらくなろうを読んでいた。

ようやく少し気が向いてきたときには午前9時、修論発表会午前の部が始まっていた。オンラインで発表を見つつ練習できないかやってみたが、ミュート事故が怖いし、発表の雰囲気だけなら最初の数人で掴めたので途中でZoomを抜けた。雰囲気以上の内容は真面目に聞いても理解できない……。

午後1時くらいまで発表練習とスライド修正を交互に繰り返していた。話していて詰まった部分を見つけ、どういう説明をするか自分の中で決めて、それが再現できるよう暗記したりスライドに情報を盛り込んだりする。原稿というにはほど遠いが、それでも途中で詰まらなくなるくらいの効果はあった。

適当に喋っていたら毎回15分弱になったので時間調整はあんまり考えていない。一応練習は録画してあって、ベルが鳴る10分の時点でスライドのどのページにいるかだけは確認しておいた。

地下鉄で登校して午後の部のほぼ最初から出席した。自分は5人目で、前の4人は以前発表を聞いた確率論セミナーの人々。ただし彼らの発表については緊張していたためほぼ覚えていない。

確率論セミナーにお邪魔した。今日は同期4人が修論の内容について発表する。
週記（2024/01/08-2024/01/14） - kotatsugameの日記

午後3時過ぎ、ついに自分の発表の番。発表自体はまあまあ上手くいったと自分では思っている。ほぼずっとスライドのほうを向いていたのは当然よくないが、とにかく大きな声で喋ることを心掛けたため聞こえないということはなかったはず。また途中で詰まったりもしなかったし、ちゃんと時間内に終えられた。

発表時間については、緊張した頭ではベルが鳴ったときのスライドを見ても自分が速すぎるのか遅すぎるのかパッと判断できないという点を今後注意しておきたい。後から確認したが多分スライド1ページ分くらい遅かったのではないだろうか。誤差。

発表に対して質疑応答はカス。四つくらい飛んできたうち三つは「〇〇のケースではどうですか」「〇〇を知っていますか」というもので、それぞれ考えたことがない、名前だけは聞いたことがある、と答えるしかなかった。特に後者については有名だから絶対来ると思っていたのに、回答を用意するのを忘れていた。最後の一つは扱った対象の性質についての質問だったがパッと出てこなくて断言できなかった。

まあとにかく終わったので気は楽になった。自分の次の発表者は板書スタイルで、メモなど見ていないのに手も口も流暢に動くし、適宜体を聴衆のほうに向けるし、式を書いている時間がそこそこあったのにちゃんと15分に収めてくるという完璧な発表。ただただ感心していた。

最後の人まで聞いて一日目終了。なんと午後の部の発表者は自分以外全員スーツだった。解析系の先生に厳しい人がいるという話で、院試の面接のときもこの分野の人はスーツで揃えてきていた記憶がある。一応、午前の部にはちゃんと私服の人もいたことを明記しておく。

学食に移動して2時間ほど先生と話した。発表への質問について、進学試験について、博士課程について。留学するなりしてもっとテーマの近い先生に師事することを強烈に勧められている。大きな声では言えないが、今の環境を変えるのが怖い。また仙台の地の住みよさには離れがたいものがある。オンラインでどうにかならないだろうか。そもそも実績のない自分を受け入れてくれる先生がいるのだろうか。

先生と別れた後、近くに座っていた同期の友人二人に合流して食事。このメンバーは偶然、以下に引用した2年近く前の日と同じで、今日もまた数時間喋った。

講義を終えて、同級生数人と学食で食事。（中略）その後道端で3時間ほど喋っていた。
週記（2022/05/23-2022/05/29） - kotatsugameの日記

取り留めのない話から一つ記録しておく。東京23区とか47都道府県とかキリの悪い数が気になって $24n-1$ 型の素数を考えたところ、地球表面における海の割合71%もこの系列であることに気づいたらしい。自分はそれを聞いて、119が周期表における発見済み元素と未発見元素の境であることを指摘したが、そもそも119は素数ではなかった。

119はともかく、この $24n-1$ について指導教員の先生に話す機会がなぜかあって、先生はそれを聞くや否や、5以上の奇素数の2乗が必ず $24n+1$ であることを指摘したそうだ。素数と聞いて何かの定理かと思ったが何のことはない、 $m$ が2の倍数でなければ $m^2\equiv 1\pmod 8$ で、3の倍数でなければ $m^2\equiv 1\pmod 3$ であるというだけの話だった。ただしこれがパッと出てくるというのは意味不明。

午後9時過ぎに帰宅。先週の週記を書いて、相も変わらず穴あきだらけのまま日付が変わるギリギリに投稿した。それからすぐ眠気の限界が来て、布団に倒れこみ就寝。午前1時過ぎだった。

01/30(火)

午前7時に目を覚まし、しばらくなろうを読んでから起き上がった。今日の修論発表会はオンラインで聴く。昨日の時点では会場に行こうかななどと思っていたが、眠くて体が動かなかった。

今日の他の話をする前に、まず修論発表会について。今日は午前・午後ともにほとんどずっと聴いていた。が、やっぱり内容は理解できない。唯一ゼータ関数周りの話題は、4年ゼミで触れたこともあって多少ついていけた気がする。他はもう、そもそものモチベーションからちんぷんかんぷん。

内容以外の発表スタイルについては、やはりスライドではなく黒板を使っているとオッと思わされる。わざわざそれを選ぶだけあってみんな立て板に水のごとく喋り、板書していた。また手書きスライドを使っていた人も何人かいた。そのうち一人についてはむしろ弁舌が印象に残っている。ゆっくり、というよりじっくり語りかける感じの堂々とした話しぶりで、かつしっかり時間内に収まっていた。

話し方といえば、今言及した人がそれほど堅苦しい敬語を使わなかった一方で、ガチガチの敬語をずっと話していた人もいる。自分は前者寄り。私服とスーツの違いも含め、修論発表会をどう捉えているかが表れているように思う。博士に進学するなら単なる発表会だが、修士で終わる人にとってはこれが6年間の集大成となるのか。そういう重要さをあまり意識できていなかった。

発表会を聴きながらラノベの新刊をチェックしていた。今回は28冊で、うち発売日の近い4冊は予約できなかったためリアル書店で調達したい。と、そんなことをしていたら昼休みの時間を逃してしまった。

終了後に外出。まず郵便局に寄ってセミナーに参加している留学生宛てに寒中見舞いを出した。

実は正月の帰省から帰ってきたら彼からの年賀状が届いていたのだ。イラスト面にTUSTEMと書いてあったから、日本文化関連の講義で何か言われたのではないかと邪推している。自分は今回喪中なので、返礼はこの形で。喪中などの詳細な説明は彼にはしていない。

その後購買でラノベを受け取り、学食で食事し、散髪して帰ってきた。

朝から起きているせいかもう眠気が強まってきた。夜中にコンテストもあることだし、と午後7時過ぎに布団に入り仮眠。しかし中途半端に寝たら余計に眠気が強まったようで、何度目覚ましに起こされてもなかなか布団から離れられない。コンテスト15分前にようやく這い出ることに成功し、午後11時半からCF #922 div.2。

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

書く：CF

www.youtube.com

日記を書いたり先週の週記の穴埋めをしたりして、午前7時半就寝。

01/31(水)

午後1時半に起きて、午後5時までなろうを読んでいた。学食に行こうかなと思いつつ二度寝。

午後11時に目覚ましで再度起きて、月末が提出期限の書類を提出した。その後布団に戻ってなろうを読みふけり、午前6時就寝。

02/01(木)

午前10時起床。2時間ほどなろうを読んでから布団を脱出した。

2月になったので1月の読書記録をツイート。昨年12月に続き先月もひどかった。修論関係のタスクに追われていたときも結構な時間を布団の上で過ごしていたから、読もうと思えば読む時間はあった。しかしラノベよりスマホを持つほうが楽で、キリもなく延々なろうを読み進めてしまう。ただ電子書籍を買うつもりは相変わらずない……。

1月の集計
買った：38冊
読んだ：2冊
積読：+36冊
積読（累積）：+36冊
— こたつがめ (@kotatsugame_t) 2024年2月1日

学食に行って食事し、ラノベを購入して帰宅。それからついに、TUPCのテスター作業に手を付けた。

午後8時くらいに一区切りつけて外出。まず本屋を2件回って火曜日予約し損ねたラノベ新刊を探したが、なかった。今日が発売日のはずなのに。諦めて立ち食いそばを食べ、ゲーセンへ。

閉店まで15クレ遊んだ。来週水曜日までのイベントを消化するのがメインで、選曲としてはずっと未プレイの新曲を埋めていた。今のイベントはキャラクターレベルを上げるのに時間がかかる一方マップはすぐ終わるから、過去の走れていなかったマップもどんどん進んでいく。それで「Disruptor Array」を解禁した。自分と同じくらいのレートの人が初見で鳥出しているのを見て簡単なのかと思っていたが、追いつかない人間にとってはかなり絶望的な譜面だった。

油そばを食べ、ドンキに寄って飴の大袋を買って帰宅。

パインアメ pic.twitter.com/mWE69xv1U0
— こたつがめ (@kotatsugame_t) 2024年2月4日

本屋で見つからなかったラノベ新刊が大学生協のサイトで買えるようになっていたため、リアル書店で入手するのを諦めて注文した。初版が手に入るか気になっていたが、そもそもラノベとは発売数日で重版がかかるようなジャンルではないか。

午前3時就寝。

02/02(金)

昼前から寝たり起きたりしていた。

午後2時くらいにラノベ「放課後、ファミレスで、クラスのあの子と。」を読了。といってもほとんどの部分は2週間くらい前に読んでおり、今日は最後の数十ページだけだった。主人公とヒロインの関係性はいいなと思う。主人公の妹の言動が不穏。

その後はうっかり「謙虚、堅実をモットーに生きております！」の再読を始めてしまい、4時間ほど消し飛ばした。あのシーンが面白かったからもう一回読みたいな、というくらいの気持ちでも、各話タイトルがないため手当たり次第に読んで探す必要があり、そうしているうちに止まらなくなる。

https://ncode.syosetu.com/n4029bs

寒い中学食へ行って夕食。帰宅してから何か作業をするつもりだったが、外があまりに寒かったので即座に布団に戻ってしまった。そのまま午後7時半くらいに寝落ち。

02/03(土)

午前2時起床。TUPCのテスター作業を行い、午前10時前に寝た。

次は午後1時半起床。シャワーを浴びて午後2時からUniversal Cup 21回目に出た。今日はDelftセット。

The 2nd Universal Cup. Stage 21: Delft - Dashboard - Contest - QOJ.ac

書く：UC

午後9時からはABC339。

Japan Registry Services (JPRS) Programming Contest 2024 (AtCoder Beginner Contest 339) - AtCoder

書く：ABC

www.youtube.com

しばらくYouTubeを眺めていたが、いつの間にかうつらうつらしていた。慌てて布団に移動し就寝。午前2時だった。

02/04(日)

午前6時起床。記録によればそこから文字通り半日の間なろうを読んでいたようだ。確か昼前に二度寝していたと思うのだが、Chromeの閲覧履歴には1時間程度の空きしかなかった。その程度の睡眠だったらしい。夕方になって布団から脱出し食事した後もなろうを止められず、そうしているうちに眠くなってきたので布団に戻ってARCの前に仮眠を取ることにした。

寝る直前に知ったのだが、今日は富山県魚津市「新川文化ホール」で棋王戦が行われていたらしい。身近な施設でこういうイベントがあるとは驚き。対局に使える和室があるのも知らなかった。

www.shogi.or.jp

2時間ほど眠り、午後9時からARC171。

AtCoder Regular Contest 171 - AtCoder

書く：ARC

www.youtube.com

夜中はずっと日記を書いていたが、次第に集中力がなくなりなろうに手を出してしまった。午前10時過ぎ就寝。

このなろうは現在1840話くらいを読んでいる。ペースとしては週300話から350話といったところで、この調子ならあと5週間かかるらしい。多分、山積したやるべきことから目をそらし、このまま読み進めていってしまうのだろう。

何かに追われ、逃げている状態が精神に負荷をかけているのか、最近眠りが浅い気がする。6時間も経たず目を覚まし、すぐなろうを読み始めてしまい二度寝がスムーズにいかず、そうして十分な睡眠時間が取れないと夜また倒れこむように寝て、するとまともに寝た気がしなくて起きてもなお更なる睡眠を求め、しかしなろうがやめられず……と書いていて気付いたが、これメンタルの問題ではなくなろうのせいだな。ならしょうがないか……。

2024-01-29

週記（2024/01/22-2024/01/28）

01/22(月)

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

進捗報告では修論の提出に成功したことを伝え、また先週話したスケジュールに進学試験が追加されたためさらに1週間稼働できないことを宣言した。今後のタスクについて話し合う直前というよくないタイミングで休み始め、もう1か月稼働していないから、復帰してもやっていけるのか不安になってきた。

勉強会はフィギュアスケートの採点法について。かなりシステマチックでびっくりした。昔氷上をひょうきんな感じで歩くパフォーマンスを見て衝撃を受けたことを覚えているが、これは面白くても得点としては高くないらしい。まあ表現の採点を公平にやろうとしたら、構成要素などに分解してガッチガチに決めてしまうしかないのかもしれない。

解散後、学食に行こうとしたが、天気が微妙に悪いのを見て断念。家で食事して、それからずっと先週の週記を執筆していた。日付が変わる直前に投稿。今週も穴だらけ。

眠すぎて何もできず、すぐ布団に倒れこんで寝たらしい。午前1時頃。

01/23(火)

午前5時に目を覚まし、シャワーを浴びて昨日やるつもりだったゴミ出しを済ませた。それから布団に戻ってなろうを読み、午前11時過ぎに二度寝。

午後6時、再度起床。JOIG本選の問題が公開されていたのでAとBだけ解きコードゴルフした。

JOIG 2023/2024 本選過去問 - AtCoder

Aはsed。Bは制約を見て考え込みそうになったが、冷静になるとソートして終わり。Nibblesで縮めておいたものの、どう書いたらよいかいまいちピンと来ていないので、とりあえず実装しただけという感じになっている。

その後また布団でなろうを読んでいた。途中何度か寝たり起きたりした気がしないでもない。徹夜という感じでもないので、ここで日付を改めておく。

01/24(水)

昨日に引き続き布団に横たわってなろうを読んでいたが、空腹だしやるべきこともあるということで何とか起き上がり、とりあえず食事して机に向かった。

今やるべきことというのは、修論発表会のためのスライド作成。今日の午前中に発表練習の時間が設けられているのでそれまでに完成させておきたかった。昨年11/17に発表したときのスライドを使いまわせばすぐ出来上がるだろうと舐めてかかっていたため全くやる気が出ず、結局その後数時間はなろうを読む姿勢が横から縦になっただけであった。

実は来週金曜日に別のセミナーで自分の研究成果を発表する
週記（2023/11/06-2023/11/12） - kotatsugameの日記

午前6時くらいにようやく取り掛かったのだが、当時のスライドを見て仰天。導入が過剰にネットリしていて、修論では必要ないとカットした部分も懇切丁寧に説明している。そんなことをするくらいなら図の一つでも追加して視覚的な説明ができるよう努めたほうが良いはず。

ということで修論での説明に合わせてカットし、図をいくつか用意し、また分量が多すぎるので後半をばっさり消し飛ばし、話の流れの整合性を確認し……などが必要となって、作業量が想像の数倍だった。図についてはTikZと格闘している時間もないため手っ取り早くdraw.ioで作成。このツールを誰から聞いたか忘れたが、クオリティの高い図が簡単に、かつ素早く作れて非常に助かった。

何とかスライド作成が一段落したのが午前9時半。発表練習の開始時刻である。ヤバいヤバいと言いつつ急いでシャワーを浴びて家を飛び出した。雪が降っている。地下鉄がかなり混んでいてびっくりしたが、降雪時ということもあるし、そういえばこの時間帯はちょうど2限前だった。いつも昼過ぎから夕方という変な時間に乗るので新鮮。

結局1時間遅れで会場に到着したのだが、その時点ではなんと一人しかいなかった。あんまりかしこまった場ではなかったらしい。最終的には自分を含め5人しか来なかったし、そのうち実際に時間を計って発表してみたのは最初に来た人と自分だけ。他はPC操作やスライド映りをチェックするくらいだった。

このスライド映りについては、薄い色が全く映らなかったので愕然とした。そもそも拝借したBeamerのテンプレート自体薄めの色を使っていたのでどこがブロックになっているかすら判別できない。テーマから変えるなど抜本的な改善が必要。確認しに来て良かった。

終わり際に修論発表会の新しいプログラムがメールされてきたのだが、発表順が変わっている以外にもなんだか違和感がある。昨年末配られたものと見比べたところ二人いなくなっていることに気づき、みんなで震え上がった。

その後練習に来たうちの二人と食事。単位が足りているか心配だとぼやいたら、足りてないですよと教務課からメールが来て履修登録ミスに気づき対応してもらったという体験談を聞いた。そういう確認をしてくれるなら何も来ていない自分は安心か。

山を下り、川内キャンパスの購買でラノベを受け取って帰宅。修論をセミナー関係者に送ったり、先生に勧められた学会発表に申し込んだりなどのメールを計3本書き、午後4時過ぎに寝た。

└( ＾ω＾ )┘♪ 買った♪└( ＾ω＾ )┘♪ 買った♪ pic.twitter.com/xoW6clh5e1
— こたつがめ (@kotatsugame_t) 2024年1月24日

01/25(木)

01/24 午後10時くらいに起きた。すっかり雪が積もっており、光を照り返して外が薄っすら明るい。「明るい夜」というのはかなり好きな現象。満月の夜、雪が降る夜……。白夜や超新星爆発もいつか体験してみたいものだ。

起きて外見たら「積もった雪の照り返しで日が沈んでも明るいやつ」やっててクッソ興奮した
— こたつがめ (@kotatsugame_t) 2024年1月24日

しばらくなろうを読みながら寝たり起きたりしていたはず。特に午前4時半からはずっと起きていたことをChromeの履歴から確認している。午前11時になってようやく布団から脱出。昨日の反省を活かして、主に色を濃いものに変えるなどのスライド修正を行った。

シャワーを浴びて午後2時登校、午後3時からセミナー。今日は自分の発表練習のみという予定だったが、まずスライドを映すためのプロジェクターをPCと接続するのに30分くらいかかってしまった。結局は壁際に備え付けられているコントローラーの電源を入れていなかった点と、VGAでの接続以外うまく動かない点が問題だったという認識。アダプタでUSBに変換した。

自分のノートPCにはUbuntuを入れているのだが、そうするからにはこういう問題もドライバを自分でインストールして解決できなければなりませんよ、と先生にチクチク言われてかなり苦しかった。正論ではあるのだろうが、さすがに今時のUbuntuだと手作業はほぼないんじゃないかと思っている。HDMIケーブルが効かなかった時点でコントローラー側の問題だと思っていた。

その後はスライドを1ページ1ページじっくり見て先生からの手直しを受けた。結構自分の思想と違うところがあって、ところどころでバトルが発生。まあ結局全部受け入れることにした。登場させざるを得ないけれど性質に興味がない用語があったとき、自分は「そういうものがある」とだけ述べれば十分だと思っていたのだが、少しでも説明しておくべき、など。

午後6時終了。結局発表練習はしなかった。学食に移動して先生と話しつつ食事し、帰宅。

空を見上げて、今日が満月であることに気づいた。昨日の夜の明るさは満月＋積雪によるものだったらしい。外に躍り出て十分堪能しておけばよかったなと少し後悔した。もう雪は全然残っていない。

午後8時から午前0時半まで仮眠して、午前1時からSRM852に出た。

https://community.topcoder.com/stat?c=round_overview&er=5&rd=19721

Easyは冷静になるとbitDPでよい。ただし誤差の保証がどうなっているのかは知らない。Medは整数を先頭3桁から末尾3桁への辺と見て有向オイラー路を作る。ひたすら面倒だし、後述する通り気を付けるところが多い。Hardはなもりグラフの閉路でない部分に思いを馳せていやな気持ちになっていたが、冷静になると $f^K(f^K(x))=x$ なので閉路しか登場しない。適当にdp。

チャレンジフェーズでは部屋のMedのほとんどを落とした。凶悪なのは「leading zeroを許さない」という点。グラフの問題にした時点で数として見た時の話を忘れてしまう人もいるだろうと思ったが予想以上に多く、3人。あとは3桁未満の数があっても最初からサイズが1ならOKというケースで一人落とした。

自分はちゃんと全完できており、速度差をチャレンジフェーズで補って2位。レートは2919→2967(+48)。Room運がよかった。

日記を書いてシャワーを浴び午前8時就寝。

01/26(金)

午前11時半くらいに目を覚ました。TLを眺めていたらボイロ動画が流れてきて、1時間超の大長編だから適当なところで切り上げるか～と思いつつ視聴を開始したところ、うっかり最後まで等倍速で見てしまった。

www.youtube.com

高速道路を走っている時間が長いので画面としてはやや単調。しかしトークが途切れることなくずっと続いているので無理なく見ていられる。これだけでも偉業なのだが、どこを取り出しても話が面白いというのはもはや常軌を逸している。

スマホを眺めつつ二度寝をするかしないか1時間以上迷って、結局起きることにした。今日はゲーセンに行く。午後3時出発。

まず久しぶりのリアル本屋に行った。森見登美彦さんの新刊を無事初版でゲット。

pic.twitter.com/BLqimYzoTu
— こたつがめ (@kotatsugame_t) 2024年1月26日

さらに古典部シリーズ愛蔵版の第3弾を予約した。第2弾をAmazonで注文して痛い目を見たことが記憶に新しい。

大切なものなのだから面倒がらずちゃんとリアル本屋で注文・受け取りを行うべきだった。
週記（2023/10/23-2023/10/29） - kotatsugameの日記

大戸屋で食事しGiGO仙台に向かう。隣に新しくカードショップができていた。バズって流れてきたデュエルスペースの黒板アートに仙台クリスロード店とあったので、通りのどこにできたのか気になっていた店。せっかくなので写真を撮りに行ったのだが、部屋の端で二人黙々とデュエルしていたためかなり気まずかった。

GiGOの隣にできたのか pic.twitter.com/huESDkuBWp
— こたつがめ (@kotatsugame_t) 2024年1月26日

ゲーセン。今日は閉店間際まで30クレプレイした。相変わらず新曲埋めだが、ようやく高難度にも手を付け始めたのでまあまあ成果がある。理論値三つ、14+のAJ四つ。

Stellar Stellar 理論値 pic.twitter.com/up78zTEDgD
— こたつがめ (@kotatsugame_t) 2024年1月26日

「Stellar Stellar」理論値。何度か聴いたことがあるので譜面をガン見しなくてもリズムを掴むことができた。フリック抜けはどうしようもないのでお祈り。

†大闘士＝クライン・フォーゲル・シュピール＝えりか† 99AJ
Sage 初見AJ
2枚抜き pic.twitter.com/0NXJ9X1IY6
— こたつがめ (@kotatsugame_t) 2024年1月26日

「Sage」初見AJ。といっても譜面動画は何度か見たことがあって、初プレイという意味での初見である。右に寄ったトリルを片手で拾えたことなど、なぜ通ったのかわからない配置が多い。精度が悪いかなと思ってもう一度プレイしてみたところ、無事ボロボロになった。

うおうっま pic.twitter.com/OJnrhQN2uA
— こたつがめ (@kotatsugame_t) 2024年1月26日

AJではないが、「盟月」も初プレイでSSS+が出た。序盤で2-0出したのが痛い。後半の鍵盤に関しては先ほど同様なぜ通ったのかわからない。

理論的には出そう pic.twitter.com/D79Q9oINF6
— こたつがめ (@kotatsugame_t) 2024年1月26日

「sølips」は今のところ7kで、噛み合い待ち。こんなの無理だろと思っていたが案外擦れるところが多かった。終盤のホールドとフリックが入り混じるところは自然にフリックを取ると腕がクロスする。その状態で何かするのは思ったより無理だったので、ホールドを取った手を奥に伸ばして直後のフリックを取ることにしている。しかし忙しくて思った通りに手を動かせない。

油そばを食べて帰宅。眠気をこらえてシャワーを浴び、ぼんやりTLを眺めて時間を過ごし、午前3時半ぐらいになって寝た。

01/27(土)

正午くらいに微妙に起きてなろうを読んでいた。二度寝に成功。今日のUniversal Cupは大岡山セット、すなわちTTPC2023なので、すでに参加済みである。

Tokyo Tech Programming Contest 2023 - AtCoder

午後7時起床。1時間くらいなろうを読んでから布団を脱出し、食事した。午後9時からABC338に参加。

AtCoder Beginner Contest 338 - AtCoder

書く：ABC338

www.youtube.com

午後11時半からはCF #921 div.1。

Dashboard - Codeforces Round 921 (Div. 1) - Codeforces

書く：CF（+E）

www.youtube.com

その後はなろうを読みつつ、木曜日指摘された点について延々スライド修正を行っていた。01/28 午後6時くらいに何とか完成。発表練習は起きてからやる。シャワーを浴びて午後7時に寝た。

01/28(日)

消えた。

今週は発表スライド作成となろうの週。なろうは現在1500話を超えたところである。以前に読んだ記録があるのは2600話までで、現在は3300話弱ある。先は長い。ヤバい。

2024-01-22

週記（2024/01/15-2024/01/21）

01/15(月)

午後3時半前に起床。年が明けて初めてのインターン先定例会に参加した。

昨年末、修論に取り組むためしばらく進捗がないと宣言した通り、何もやっていない。ただ定例会に参加したのだから何か話しておこうと思い、修論に関する今後のスケジュールをお知らせした。01/29に修論発表会があるので、その日の定例会はお休みする予定だ。

勉強会はプリューファーコードの話だった。相変わらず難しい。ただ、数列を作るアルゴリズムが辺を1本残して停止する理由に新しい解釈ができた。他の辺を残った辺から出る方向に向き付けることを考えると、すべての頂点について出次数が次数引く1になる。1点だけになるところまで進めると、その残した1点だけ食い違ってしまう。

解散後購買に向かってラノベを受け取り、食事して帰ってきた。家を出るころにちょうど雪が降り始めた感じで、帰り道では薄っすら積もっていた。

帰宅後はまず先週の週記を書き進めた。相変わらずコンテスト関連で穴あきまみれなのには早々に見切りをつけ、午後10時過ぎに投稿。その後修論に取り組んだ。

午後11時半からCF #920 div.3に参加。

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

書く：CF

www.youtube.com

また修論に戻ったが、朝方には集中力を失いYouTubeを見てしまっていた。午前9時就寝。

01/16(火)

午後3時起床。

以前の週記で冬のLAシンポジウムに参加すると言っていたが、指導教員の先生に許可が取り消されたためキャンセルすることになった。旅費補助をもらうにあたり運営に補助あるいは自費での前泊ができないかを問い合わせていたところ、疑念を持たれるような行動はするなと怒られた。実際当日の午前7時くらいに出れば間に合うのでまあ無理だろうなとは思っていたものの、聞くことすら許されないとは……。営利企業と税金が使われるアカデミアの違いが分かっていなかった、というところだろう。

先週に引き続き今日も修論執筆合宿を行う。学食に寄りつつ、ほぼ予定通りの午後4時半過ぎにホスフィンが所属する研究室に到着し、それから午後11時半まで修論と取り組んでいた。今日は時間が長く取れたし会話の量も少なめだったため、結構進んだのではないかと思う。もうしばらく作業すればひとまず完成したと先生に伝えることができそう。

帰宅間際、ICPC プレーオフの準備でホスフィンとチームAobayama_doctorsのメンバーが話し合っていた。カザフスタンに行ったとき飛行機が全然苦にならなかったので同じくらいの時間ならLCCでいいんじゃないのと口出ししたのだが、実は自分が乗ったアシアナ航空はLCCではなくちゃんとした航空会社らしい。そりゃ機内食も出るし足元もゆったりしているわけだ。余計なことを言ってしまったなと後悔している。

終電で帰宅。しばらくPCの前に座っていたが修論に取り組んでいたわけではなく、TLを見たりYouTubeを見たりしていた。眠気から午前1時過ぎに布団に倒れこみ、就寝。

01/17(水)

午前6時に目を覚まし、しばらくラノベを読んでいた。午前10時に二度寝。

午後3時くらいにもう一度目を覚ました。今日は修論執筆合宿を行わない予定である。それでも資料室に行って昔の修論を読んだり参考文献とする教科書を確認しようかなと思っていたのだが、検索すると目星を付けていた教科書がちょうど貸し出し中だった。前者の目的だけで家を出るのも面倒。外出の予定が消えたのでもうひと眠りすることにした。

次に起きたのが午後7時半くらい。修論もあと少しと思うと、もうちょっと休んでいても読んでもいいかなという気持ちになってきた。朝方までに先生に送ることができれば寝て起きるころには添削が帰ってきているはず。ということで布団から出ず、スマホでなろうを読み始めた。

01/18(木)

気づいたら夜が明けていた。寝落ちしたわけではなく、ずっとなろうを読み続けていたのである。午前7時前後にようやく布団から脱出することに成功した。

修論執筆開始。朝はダメでも昼くらいには見せたいなと考えながら作業していたが、思っていたより時間がかかって全然間に合わなかった。午後4時になってようやく完成。昨日確認する予定だった教科書はネットにPDFが転がっていたため難を逃れた。

眠くて考えがまとまらないため自分で読み返すのは諦め、すぐ先生にメールを送って寝た。

01/19(金)

01/18 午後11時起床。ここから金曜日ということにする。今日の午後5時が修論提出締め切り。

修論はOverleafで書いており、リンクをあらかじめ先生に共有していた。それで自分が昨日格闘している最中にも文章を読んでいたのだろうか、寝てすぐ修正事項のメールが届いていたようだ。自分は夢の中であるから当然一向に修正されないのだが、それに業を煮やしてかどんどん語調の強まっていくメールが2本、2時間おきに届いており、肝を冷やした。

最後のメールには「明日の2時まで」と書いてあった。自分はこれを午前2時と解釈し、ECRを諦めて執筆に取り組み始めたのだが、後からよく確認すると午後2時のことだった。コンテストに出損ねて残念。ともかくそのまま格闘を続け、正午に再度送信した。修正点を直すのに加え、ページ数が少ないと言われたので新しい内容を追加して文章を増やしてある。

残るは要旨2ページのみ。イントロをコピペすればほぼ完成だろうと舐めており、シャワーを浴びたりなろうに少し手を出してから取り掛かったのだが、これが思ったより大変だった。何をどんな粒度で書けばよいのか、と迷っているうちにどんどん時間が過ぎていく。エイヤと書き始めたらぴったり2ページになってくれたので、これもすぐ先生に送った。午後2時半だった。

午後3時から大学で先生と打ち合わせをする予定。食事する暇もなく地下鉄で登校し、教室で待ち構えていた先生と1時間ほど話しながら最後の修正を行った。その後院生室で印刷し、提出。

pic.twitter.com/rmoczK7GSu
— こたつがめ (@kotatsugame_t) 2024年1月19日

さらに今後について先生と2時間ほど話し合いを行った。そこで出た話を一つ。修論というのは、修士2年間で自分が学んだことを書くものらしい。今日の午前中慌てて増やしていた部分は自分の主な結果とはそれほど関わりがなく、論文としてどうなんだ……と思っていたが、そういうことならまあ意味があったかなと納得できる。

結局自分の修論は表紙を除いて40ページだった。院生室にたむろしていた友人は皆そんなものと言っていたが、先生からすると博士課程に進学するなら少ないらしい。今の話を聞いた後だと確かに同意できるし、書く時間がそもそもなかったとは言え追加できる内容はまだあったので、残念。

あとは、修論発表会とは別に進学試験があることも知った。実は同じものだと思っていて、発表会20分で何が審査できるのだろうとか考えていた。ちゃんと別日に1時間確保されるようだ。ヤバいかもしれない。

学食で食事し帰宅。yukicoderのため待機していたが、眠気に耐え兼ねて午後8時過ぎに寝た。

01/20(土)

午前2時くらいに目を覚まし、なろうを読み始めた。当然のように止まらなくなって9時間熱中。何とかもう一度寝直し、午後2時直前に再度起床してUniversal Cupに出た。今日は19回目、Estoniaセット。

The 2nd Universal Cup. Stage 19: Estonia - Dashboard - Contest - QOJ.ac

書く：UC

感想戦後慌てて食事し、午後9時からABC337。

Toyota Programming Contest 2024#1（AtCoder Beginner Contest 337） - AtCoder

書く：ABC

www.youtube.com

実はTechFULの新春TCB2024が明日までである。うっかりなろうを読み始めたため今日はもう無理かと思ったが、何とか欲望を抑え込むことに成功。午前3時半から開始した。眠気で頭が回っていない感じがちょっとあったもののなんだかんだ全問解いた。

https://techful-programming.com/techful/event/5321

5問目は総和のチェックを忘れ1WA、6問目は桁合わせのための0をうっかり小数点の直後に追加してしまい1WA。どちらも-6pt。9問目は難しかった。 $P=(Q\oplus N)-N$ と見ると、 $Q$ で立っていないbitはどうでもよいことがわかる。また上のbitから貪欲に調整するしかないので、それでチェック。17分かかって-5pt。

11問目はややこしい。枝分かれ以降の頂点全部を番号順に並べ、どの枝分かれ先にいるかでラベルを付けることにすると、操作はこの列を一つ左にrotateするものとなる。これが分かれば後はZ-algorithmでOK。

12問目は謎の貪欲をずっと考えていてとんでもないことになった。?の個数が少ないのがよくわかっていなかったが、冷静になると個数の3乗でdp、あるいはメモ化再帰ができる。操作は必ず両端のどちらかに行うべきなので、左右からどれだけ行われたかに加え先手が何回左端を操作したかで状態を表現できる。77分かかって-49pt。

13問目はちょっと面白かった。 $S$ がソート済みであるとして、 $S_i$ をピボットに $S_j$ を並べることになる確率は、 $i$ が選ばれるまでに $i$ と $j$ の間のインデックスが選ばれないという条件から $\frac{1}{|i-j|+1}$ となる。あとはこれをLCPごとに足し合わせたいが、LCPは $O\left(\sqrt{\sum|S|}\right)$ 種類しかないので愚直に見てよい。

14問目は正規系を作って比較する方針。削除できる要素をできるだけ削除した後辞書順最小にするとランダムケースを通った。削除のほうは簡単に線形時間になる。辞書順最小は難しいが、大きな要素から順にできるだけ前に寄せていくと考えれば、双方向連結リストで数列を管理し、そこから今見ている要素より1大きな要素のみ抜き出して持っておくことで実装できる。うっかり2乗かかるコードのまま投げてしまい1TLE、さらに51分弱かかっていて-42pt。

15問目はわからないが、どうせまともなテストケースは入っていないだろうと速そうなコードを投げたら通った。suffix arrayで最も前にあるインデックスが答えの候補で、真の答えはそのprefixになる。短いprefixは一つ一つ確認し、長いprefixはLCP arrayで区間を調べて一気に見た。おそらく $O(N^2\log N)$ だがLCP arrayで見ることになる区間の数を多くしようとすると短いprefixのほうですぐ見つかってしまうのではないか。ランダムケースで試すなどしていたら実装に時間がかかり、42分弱で-15pt。