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