週記(2024/02/12-2024/02/18)

02/12(月)

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

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

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

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

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

02/13(火)

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

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

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

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

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

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

ミスドで食事して午後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の問題の話をしていた。

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

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

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

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

02/17(土)

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

会場の宮城教育大学は初めて行く場所なので念のため早めに家を出たのだが、開会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は余計な情報もたくさん表示してくるから……。

午後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と互いに素なnn^n\bmod{10^k}と一対一対応するらしい。そこでXからスタートしてn\rightarrow n^nという変換を繰り返し、ループしてXに戻ってくる直前の値を答えるという解法を考えたが、ループのサイズがそこそこ大きくなるようで無理だった。

もう少しまともに解こうと思い、\bmod{2^9}\bmod{5^9}に分解した。nの候補を\bmod{5^9}側で絞り込み、29回探索したい。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それぞれについてXm^{5^9}の逆数をかけていき、前計算しておいた1\le n\lt 5^9に対するn^nと一致しないかチェックする。次に、そこで見つかったnに対しn,n+5^9,n+2\times 5^9,\dotsを答えの候補として、それぞれ計算して判定する。この方法で答えが求まる……はず。

とりあえず答えは求まるようになったので提出したら、TLE。調べたところ答えのチェックを217回ほど行ってようやく見つかる数があるらしい。どうにもならずそのままコンテストが終了した。そのまま考えていたら、m^{5^9}の逆数をかけていく部分に無駄があることに気づいた。定数回のループを回していたが、最初の数に戻ってきた時点でbreakしてよい。これで試すと最大211回で見つかるようになり、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 2n^{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/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時間かかった。ただ感触は非常に良いし、何より楽しかった。そういえば最後に博士課程卒業後の進路を聞かれたことを記録しておく。自分はプログラマーと答えた。まあ定番の質問という話だし、これで落とされたりはしないだろう。

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

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

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

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

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

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

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

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

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

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

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

午後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 yy\rightarrow zx\rightarrow zy\rightarrow yにしていき、すべて自己ループになったら終了。辺がm本ある連結成分なら必ずm-1回操作できるかというとそうでもないようで、サンプル5で落ちる。長さ2のループばかりあるのが問題。

相異なる3頂点x,y,wについてx\rightarrow yy\rightarrow xx\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が全部作れるらしいと分かった。よってaa\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は10100秒では足りないのでは?と思って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}=0B_{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/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月に続き先月もひどかった。修論関係のタスクに追われていたときも結構な時間を布団の上で過ごしていたから、読もうと思えば読む時間はあった。しかしラノベよりスマホを持つほうが楽で、キリもなく延々なろうを読み進めてしまう。ただ電子書籍を買うつもりは相変わらずない……。

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

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

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

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

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

午前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/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時過ぎに寝た。

01/25(木)

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

しばらくなろうを読みながら寝たり起きたりしていたはず。特に午前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時出発。

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

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

大切なものなのだから面倒がらずちゃんとリアル本屋で注文・受け取りを行うべきだった。

週記(2023/10/23-2023/10/29) - kotatsugameの日記

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

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

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

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

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

「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/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時間ほど話しながら最後の修正を行った。その後院生室で印刷し、提出。

さらに今後について先生と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が選ばれるまでにijの間のインデックスが選ばれないという条件から\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。

合計回答時間は4時間ちょっとで、失点は123ptだった。

食事したりなろうを読んだりして午前10時半就寝。

01/21(日)

午後8時半起床。お菓子で食事を済ませて午後9時からARC170に出た。

AtCoder Regular Contest 170 - AtCoder

書く:ARC

www.youtube.com

新春TCB2024が終了していた。7位。速度も点数もボロ負け。

食事した後は年末年始の帰省でもらってきたお酒を飲みながら日記を書いていた。

朝方、眠気に負けて机で2時間ほど寝てしまったらしい。慌てて布団に移動し寝なおす……つもりがまたなろうを読み始めてしまった。寝落ちもせずのうのうと正午まで読み続け、さすがにまずいなと思い就寝。

今週を破壊しつくしたなろうは「影の勇者の再冒険 ~~Re-Tale of the Brave~~」。年末、読み返し始めたと言っていたものである。何とか800話ちょっとで止められたはずだったのに再開してしまった。

https://ncode.syosetu.com/n5534co/

週記(2024/01/08-2024/01/14)

01/08(月)

午前10時少し前に何とか起きてセミナーに臨んだ。

これ面白そうだな~くらいの軽い気持ちでピックアップしておいた論文について言及したら、まともに読めていないところに「あなたの修論とどんな関係がありますか?」「この論文について何か研究テーマになりそうなところがありますか?」など突っ込んだところを聞かれ、正直にない・わからないと言ったらやる気がないとボロクソにけなされて本当に最悪の気分になった。

無理やり話を打ち切り、今度はちゃんと関連する文献も含めて目を通しておいた論文の話をしたところ、そちらはそこそこ丁寧に準備されていて印象が良いという評価を受けた。終わりよければすべてよしということで……。ところで、今日のセミナーは終わりでも今後の研究計画がまだ決まっていない。明日の深夜にもセミナーをすることにして正午前に解散。

cybercatsのぬいぐるみをついに受け取った。思ったよりしっかりした作りで、手で揉むと確かな弾力を感じる固さが好ましい。

自分が寝ている間にcybercatsから賞品のぬいぐるみが届いていたらしい。今から再配達を頼むわけにもいかないため、来年帰ってきてから受け取ることになる。

週記(2023/12/25-2023/12/31) - kotatsugameの日記

その後夕方まで先週の週記を書いていたが、眠気の限界が来たため午後5時半から午後9時くらいまで仮眠を取った。さらに書き続けて日付が変わる直前に投稿。今週もコンテストは穴だらけである。

ハーメルンで「【ポケ釣り】知らないポケモン釣ったんだが【知識求む】」を読んだ。まだ3話しかない。各話タイトルを見て今のところ掲示板回だけかと思っていたのだが、後半部分に別視点があって嬉しかった。

syosetu.org

夜明けまでかけて週記のOUPCの部分だけ完成させた後は、ずっとTLやYouTubeを眺めていた。リゼ・ヘルエスタさんの投稿された動画が非常に良かった。配信でも配信の切り抜きでもなく、動画スタイルが一番好み。

www.youtube.com

シャワーを浴びて寝ようとしたがうっかりABC331Gに取り組み始めてしまい、かなり時間を溶かした。ABC331はYandex Cupの閉会式中に開催されたコンテストで、結局Gが解けなくて懇親会中に他の参加者に解法を教えてもらった思い出がある。今はその出来事だけ覚えていて、肝心の解法をすっかり忘れ去っていた。

コンプガチャだからと確率pなら期待値1/pという話を使おうとしてかなり迷走していた。当時もずっとそんな感じの解法を考えていた気がする。この方針、取り出したカードの種類の集合を考えているとどうしようもない。その状態に至る確率がカードを取り出した順番にどっぷり依存していてどうにもまとめられないのだ。公式解説の解法2のようにカード自体の集合を考えるとうまくいくというのは驚き。

諦めて解説をチラ見したところ、太字で「包除原理」と書いてあるのが目に入り、その瞬間すべてを理解した。また当時教えてもらった計算方法の記憶も蘇ってきた。あとは公式解説の解法1と同じものを再現して終わり。

Submission #49173357 - Daiwa Securities Co. Ltd. Programming Contest 2023(AtCoder Beginner Contest 331)

午前10時就寝。

01/09(火)

午後5時半起床。予約したラノベが年末年始の間に18冊溜まっているため、今日はそれを受け取りに行く。本当はもっと人の少ない昼下がりの時間帯に行くつもりだったのだが起きられなかった。

一応レジ待ちの人がいなくなったタイミングを見計らったのに、本を確認してレジに通してもらっている間にどんどん行列ができていった。5限が終わる時間になってしまったというのが一つ、もう一つは別の有人レジのレジ締めが行われてしまったから。やはり来るのが遅かった。結局自分の会計が終わるころには10人以上並んでいたと記憶している。

学食でカレー中を2皿頼んでフードファイトし、帰宅。

TUPC2023の情報が出ていた。自分は昨年同様にテスター作業をすることになっているが、運営側にはノータッチだったためTLに流れてきてびっくりした。肝心のそのテスター作業にはまだ手が回っていない。忘れているわけではないので、関係者の方々はもうしばらく待ってほしい。

深夜のセミナーに向け論文サーベイを行った。複数の論文で「この文献にある手法は一般の場合に応用できる」とあったが、その参照先を読むとそういう話は影も形もなかったし、自分で考えてみても手掛かりすらちっとも掴めない。この辺りに時間をかけすぎて思うほどの量を調べられなかった。

午後11時からセミナー開始。大したことが話せずこのまま進展なしかと覚悟していたが、先生がどこからともなく見つけ出してきた海外の大学の講義録が修論との関連もあるし興味深いワードも含まれていたので、当面の研究計画としてはそれを進めていくということにした。取り組みたい問題も明確になっていないのに何が研究計画かという感じはある。読んでいるうちに何か見つかることを願う。

ところでこの講義録だが、どうやら先生から今日の昼過ぎにメールで送られてきていたらしい。先生が普段と違うメールアドレスを使っていたため東北大メールのほうで迷惑メールフォルダに振り分けられてしまい、メインのメールアドレスに転送されて来ず、結果セミナーで直接言われるまで気づけなかったようだ。そういうこともあるのか。ちょっとこれは対策のしようがない。

如何にも時間に追われて捻り出しましたという感じになってしまったが、とりあえずこの先しばらく何をするかが決まったということで、先生から博士課程進学の承認が出た。承認してもらわないと進学願書が出せず、その締め切りが明日、というか日付が変わってもう今日に迫っている。それで昨日から立て続けにセミナーしてもらっていたわけだ。

正直なことを言うと博士課程進学は意志さえあればOKなんだと舐めていた。実際はこうやって指導教員から承認を貰うところで躓いてしまったし、この後修論審査も控えている。進学後の研究計画もあいまいでまさにお先真っ暗。……なんてことを書いてみたが、1年後2年後のスパンで物事を考えたことがないので、心の中ではなるようになるさとしか思っていない。

気が抜けてうっかりカクヨムに没頭。昔読んだ部分の読み返しをしてしまった。何とか切り上げた後はネットサーフィンを始めてしまい、午前7時。シャワーを浴びて布団に入り、1時間ほどハーメルンを読んで寝た。

01/10(水)

今日は午後3時からホスフィンと、彼の所属する研究室の小部屋に集まって修論執筆合宿をする予定である。午後1時という微妙に早い時間に目を覚ましてしまい、二度寝もできず布団でYouTubeを見ていたら午後2時半になってしまった。先生から博士課程進学の承認を示すメールが届いていたので、それを添付して進学願書を提出してから出発。学食で食事もしたため30分ほど遅刻して到着した。

PCの電源ケーブルを忘れたことに気付いた。バッテリーは10時間以上持つし終電までには帰るから大丈夫だろうと考えていたが、二人であれこれ話しながら書き進めるのが思いのほか楽しく、結局午前2時半にバッテリーが切れるまでずっとその部屋にいた。夕食は午後9時前くらいにコンビニでカップ麺を買って食べた。

11時間PCと向き合っていたわけだが、文章量的にはそれほど進んでいない。ホスフィンの修論をチラ見したり書き方Tipsを聞いたりしているうちに、放置していたイントロをまず書かなければならないことに気づいて、そこを書いているうちに話の流れを修正したくなって……という感じでこれまで書いたものを並べ替えている時間が長かった。あとは息抜きとか称してお互いの研究の話をしている時間もあった。

終電はとっくの昔になくなっているため徒歩で帰宅。途中神社に寄ったりコンビニでパンを買って食べたりしていたら1時間くらいかかった。深夜にウロウロすると気分が高揚する。石段を下りるのはスリリングだった。ただ写真では上から見た時の怖さと下りきった後の達成感をうまく表現できない。

亀岡八幡宮石段 - 仙台市の指定・登録文化財

エアコンを切って出たため部屋が寒く、耐えかねて布団に潜り込んだらすぐさま寝落ちした。午前4時。

01/11(木)

午前10時半に目を覚ました。今日は午後3時半から修論執筆合宿の予定である。二度寝するか起きて家でも書き進めるか迷っていたらうっかりハーメルンYouTubeを開いてしまい、4時間くらい消し飛んだ。シャワーを浴びて学食に寄り、また30分遅刻して到着。

今日はホスフィンのほうに予定があって午後6時半までだった。昨日のことから構成をいじる作業はずっと続けられてしまうと分かっていたので今日は文章を書き進めることに注力。結果短い時間の割にはそこそこ進んだのではないかと思う。

解散後地下鉄に乗って直接ゲーセンに向かい、閉店まで22クレプレイした。今日のメインは01/24までのイベントを走りきること。大型アップデートで通常解禁された譜面にもまだ全然手を付けられていないのにさらに今日アプデがあったので、またずっと新曲埋めをしていた。

今日のアプデではプロジェクトセカイとのコラボイベントが開始した。そのためかそもそも人が多いし、初めてプレイする人もちらほらいたような気がする。仙台駅前は人口のわりにゲーセン、というよりはチュウニズム筐体が多いようで、ここで待ちが発生した記憶がほとんどないのだが、今日はちょっと並ぶことになった。

油そばを食べてドンキに寄り帰宅。今日も部屋が寒い。寝落ちしないようにだけ頑張りつつ、何かする元気もなくしばらくYouTubeを見ていた。シャワーを浴びたら暖かくなって復活。日記を書き進めて午前6時に寝た。

01/12(金)

午後1時半起床。ドンキで買ってきたパンを食べて大学に向かった。

午後3時から2時間半は留学生のセミナー。自分が今週頭に漁っていた論文との関連で、計算複雑性理論に関する話をやってもらうことになっていたのだが、難しかった。これまでチューリングマシンの話なんて影も形もなかったのに、急にそれを使って#Pの定義を正確に行えと言われてもまあ不可能。留学生自身の発表も控えている中時間を割いてもらって申し訳ないなと思う。舵取り役はあくまで先生なので口出しもしにくい。

ただ先生の話を聞くうちに自分としては分かった気になった。そもそもNP問題の定義に決定性チューリングマシンとwitnessを用いるものがあるらしく、このwitnessを数え上げる問題が#Pになるようだ。さらにwitnessとは非決定性チューリングマシンが遷移先を選ぶ際に1bitずつ消費される神託であるという認識をしている。

午後5時半からは自分だけ教室を移動し、確率論セミナーにお邪魔した。今日は同期4人が修論の内容について発表する。何か参考になればと思ったのだが分野が違ってそもそも話についていけない発表が多かった。無念。ただ発表の構成くらいは分かって、以前ホスフィンに教えてもらったものと大体同じだった。みんな先行研究からの流れをちゃんと説明できてすごいな。自分は自分の結果を周辺の論文とうまく関連付けられなかったから……。

終わってTLを開いたら米澤穂信さんの小市民シリーズの新刊発売とアニメ化決定の報が流れてきて声が出そうになった。新刊はもちろん楽しみだし、普段は興味を持たないようにしているアニメもさすがにこれくらいは見たいという気持ちが強い。ネット配信されたらホスフィンに頼み込んで視聴会を開きたいな。

帰宅し、冬のLAシンポジウムの旅費に関していくつかメールを送ったら午後9時を回っていた。20分からyukicoder 414。Advent Calendar Contestに結局一切参加しなかったりで2か月振りらしい。

yukicoder contest 414 - yukicoder

書く:yukicoder

日記を書いて午前6時くらいに布団に入り、久しぶりにラノベを読んだ。「推しにささげるダンジョングルメ」を読了。カクヨムからの書籍化でかなり好きな作品で、改めて読んでも面白かった。最強探索者の主人公がVTuberとなり、ダンジョン由来の物品・スキル・ズレた常識で同僚と視聴者の度肝を抜き続ける感じの話。ダンジョングルメはその一側面に過ぎないと認識している。

1巻では一章が本になった。2巻が出るなら二章だろう。ここまでは文句なく面白かったと言えるが、次に第二部が始まってからはダンジョン要素が薄れてVTuberの話が続いたため、正直そこの印象は薄い。週1回更新で毎週少しずつ読んだからかもしれないので、本になったらまた違った感想があるだろう。シリーズ続刊を願う。

午後1時前に就寝。

01/13(土)

午後4時くらいに起きて一瞬だけAHC028に参加した。申し訳程度にほぼ愚直を書いて提出し、再度就寝。

ALGO ARTIS Programming Contest 2023 Winter(AtCoder Heuristic Contest 028) - AtCoder

午後8時半起床。食事して午後10時からUniversal Cup 18回目、Dolgoprudnyセットに出た。risujirohさんが夜まで用事があるとのことでこの時間になった。CF div.2はお休み。

The 2nd Universal Cup. Stage 18: Dolgoprudny - Dashboard - Contest - QOJ.ac

書く:UC

食事した後は日記を書いたり年末年始で溜めていた他の人のブログ記事を読み漁ったりしていた。午前10時就寝。

01/14(日)

午後3時に親から仕送りが届いて目を覚ました。猛烈な頭の痒みがあったので慌ててシャワーを浴び、再度就寝。

午後8時半起床。慌てて食事し、手元撮影の準備を整え、午後9時からABC336に出た。

AtCoder Beginner Contest 336 - AtCoder

書く:ABC+コードゴルフ

www.youtube.com

年が明けてここ2回のABCは辰年由来だったり2024年由来だったりする問題が多い。wikipediaに記載のある2024の性質がいろいろ出題されたとのツイートが興味深かった。

また辰年由来だと問題名に「loong」が入る。これの意味は「中国の竜」らしい。動画ではずっと「ローング」と読んでしまっているが、最後の「ng」は「ん」だった。確かに龍と書いてロンと読ませるのは見たことがある気がしないでもない。

Chinese dragon - Wikipedia

日記を書いていたがうっかりラノベに手を伸ばしてしまい、「性別不詳VTuberたちがオフ会したら俺以外全員女子だった」を読了。主人公はヒロインを親友だと思い、ヒロインは主人公を彼氏だと思い……というタイプの勘違いがずっと続いていて、お互いすれ違ってドツボにはまっていく様子が結構苦しかった。

午前9時くらいに就寝。

週記(2024/01/01-2024/01/07)

01/01(月)

午前10時に親に起こされた。家族はみんなすでに朝食を終えたらしく、一人でお雑煮とおせちを食べた。すぐ着替えて初詣に出発。

今年の神社は雪がまったく積もっておらず新年という感じがしない。普段は駐車場の端に雪が山盛りになっていて車は2列で駐められているのだが、今年はなんと3列形成されていた。また出店が1店しか出ておらず寂しい感じ。

昼食を摂って午後3時頃帰宅。両親は買い物に出かけ、自分含む残った3人はこたつで昼寝の体勢に入った。

午後4時過ぎ、地震発生。前震からそこそこ大きかった。TLに流れてきたNERVのツイートで能登のほうが震源と知り、そりゃこれくらい揺れるわと思いながら再度横になりつつとりあえずツイート。送信ボタンを押すと同時に本震が来た。

本震の揺れは自分が過去経験した中で最大だったように思う。震度だけで見れば2022年福島県地震が記憶に新しいし、富山県でも2007年能登半島地震があったが、今回は揺れている時間が非常に長かった。

最初はこたつの中で固まっていたが、次第に家具もグラグラしてきたためリビングのほうぼうに散ってテレビを押さえたりしていた。リビングの高い位置には物がないため多少は安全。ただキッチンの方まで行くのは、戸棚に地震を検知してロックがかかるシステムが導入されていたとはいえ危険行為だった。

揺れのピークが過ぎた後、まだ多少揺れている中を暖房器具の電源を落としたり、他の部屋を確認したり、玄関扉を開け放ったりして回った。幸い何も壊れていないようだし、棚から落ちたものもほとんどなくて一安心。上の14分のツイートは確かこのタイミングで行ったはず。

テレビを付けると富山県津波警報が出ていた。実家はそこそこ海の近くなのでまずい。アナウンサーの緊迫した声に焦燥感を煽られ、3人で避難しようと決め荷物を持ったが、ここで問題発生。どこに逃げれば良いかがわからない。市のハザードマップを確認すると徒歩圏内にいくつか避難場所が定められているものの、どれも家より海側にあるのだ。

まごついているうちに外出していた両親と通話が繋がった。あと10分ほどで帰宅するので待つように、とのこと。津波+車+避難といえば渋滞なのでそれを心配したが、家の方向に向かう分には大丈夫だったらしい。4時半くらいに合流した。

町内会長などまとめ役を務めているから家にいなければならない、という父だけ置いて、母と4人で山の方にある春に亡くなった祖母の家に向かった。そちらに向かう人はやはり多いようで途中から道が渋滞していたが、そこはこのあたりで生まれ育った母のこと、裏道からスイスイ行ってなんの問題もなく到着。積雪がなくて良かったねという話をした。道中見えた被害は石灯篭の上の部分が道路に落ちていただけだった。

残念ながらここまで来ても標高は実家とあまり変わっていない気がする。富山平野は進んでも進んでも真っ平ら。高いところに逃げろという指示には従いようがなかった。途中立体交差している道路に人が鈴なりになっているのを見て、そこに逃げるのは頭がいいなと思った。

祖母宅は、無人となって8ヶ月経つとはいえ電気・水道がまだ維持されており、過ごせる環境にある。ここで1時間ほど待機した。古い様式の家なのでふすまが多く、余震のたびにガタガタ言ってなかなか怖い。また土壁の端が剥がれて粉が落ちてきていた。もしかしてヤバかったか?

午後6時くらいに一段落ついたと判断して実家に戻った。山道はまだ車だらけのようで、ライトが列をなしていてなかなかきれいだった。以上が自分の避難行動の一部始終である。

振り返りを少ししておきたい。今日の行動は……最悪もいいところだった。立山信仰というのは根深くて、自分も東日本大震災の頃小学校で友人たちと「富山は揺れない」と囁き交わしていた記憶がある。アナウンサーの声がなければ一時的な避難すらしなかったと思う。後で確認したら自宅は海岸線から1kmも離れていなかったから、津波警報通り3mの津波が来たとしたらひとたまりもなかったのではないか。

ツイッターでも避難しようとしない親と揉めた人が散見されたが、これはどうしようもない気がする。津波で酷い目に遭った歴史が富山県にはほとんど、あるいはいっそ一切、存在しないからだ。「ここに津波は来ない」という考え方が前提になってしまっている。それでも、自分が祖母宅から戻ってきたとき車がなくなっている家が数軒あったから、避難する人もちゃんといるらしい。

午後6時過ぎに家にたどり着いてから1時間ほど寝て、夕食。今日はしゃぶしゃぶだった。わざわざ今日やらなくても……という気もしたが、早く肉を消費する必要があったらしい。

午後9時くらいまではこたつでゴロゴロしていた。見ていたチャンネルでは午後9時に緊急放送が終わって通常のテレビ番組が再開した。自分もそのあたりから先週の週記を書き始め、日付が変わる前になんとか投稿。相変わらず穴開きがいっぱいある。

入浴してからまた日記執筆。記憶が薄れないうちに、と先週の穴埋めより先に今日の日記を書くことにした。午前4時半就寝。

01/02(火)

午後5時半に起こされ、すぐに家族揃って夕食を摂った。今日はすき焼き。先週金曜日もすき焼きだったが、それから帰省してきた姉がいるとかそういう理由だろう。その姉は食後、新幹線に乗って帰っていった。つい数時間前に運行を再開した北陸新幹線の座席がなんとか取れたらしい。もともとは今日の、もう少し早い時間に帰るつもりだったと聞いた。

自分は、食後は紅白の録画を飛ばし飛ばし見ていた。気になっていたのはTLでも話題だったAdoの「唱」とYOASOBIの「アイドル」。どちらも圧巻だった。「アイドル」で他のアイドルが全員出てきて踊ったことについてはなんだか否定的なツイートも見かけたが、単純にそれぞれが主役級の人たちが大人数で踊っている事実が壮大で、自分としてはなんだかワクワクした。ただしそれに合わせて引き伸ばされた間奏に間延びした感じは抱いた。

その後うっかりこたつで寝落ちして、起きたら日付が変わっていた。入浴してから本日の活動開始。まずはラノベ新刊を予約した。いつも毎月下旬にやっていることだがちょっと遅れてしまい、すでに発売されてしまった本があったりする。今回は34冊となった。ピックアップしたいものがいくつかあるので以下に記す。

「非科学的な犯罪事件を解決するために必要なものは何ですか?」は夏に書籍化の情報を聞いていたが、ついに発売間近となった。楽しみである。

何気なく活動報告に目を通したら、つい最近書籍化の情報が出ていてびっくりした。非常に嬉しい。

週記(2023/08/14-2023/08/20) - kotatsugameの日記

famitsubunko.jp

現代社会で乙女ゲームの悪役令嬢をするのはちょっと大変」の5巻。4巻が出てから丸一年経過しており、3巻から4巻も1年以上空いていたため続刊を心配していたが、無事出てくれて嬉しい。この巻からイラストレーターが変更になっているからその周りで何かあったのかもしれない。

over-lap.co.jp

「やさぐれ執事Vtuberとネガティブポンコツ令嬢Vtuberの虚実混在な配信生活」。一年半前になろうで読んだがその後の更新は追えていない。そのため書籍化も今初めて知ってびっくりした。

tobooks.shop-pro.jp

その後ついに修論の執筆を開始し、朝まで取り組んでいた。思ったより難しい。とりあえず絶対に書くべきことを大まかに書いてしまって、肉付けしたり順序を入れ替えたりするという形で進められればと思う。

午前8時半くらいに両親が起床したため朝食を用意してもらった。今日もお雑煮とおせちの残り。

そのうち携帯ショップに行きたいなと思っていたが、今日はあんまり眠くなかったのでいい機会だと思って父に連れて行ってもらった。スマホに入れているmicroSDカードの容量が一杯になってしまったため新しいものに換えるというのが主目的。ただスマホ自体、4年近く使ってきてちょっと動作が不安定だったりケースやガラスフィルムが割れてしまっているため、あわよくば機種変更もしたいと考えていた。

父にお伺いを立てるとOKが貰えたがまだこの時点では迷っていた。ただ単純なもので、店員さんに新機種の説明を受けたり実際に手に取って見たりしているうちにその気になった。父も一緒に変えると言い出してびっくり。そこから二人分の契約の説明なりデータ移行なりで3時間ほどかかったので、あんまり混んでいなかったのは幸いだった。

あとは、急にSIMカードを認識しなくなって再起動する事象が頻発していたので、新しいものを発行してもらった。店員さんが機械で新しいSIMカードを読み込むとほぼ同時に古いスマホの携帯回線が途絶して、その反応の良さが面白かった。

microSDカードは最初に適当に選んだが、会計のときやたら高いのを不思議に思って聞くと2万円くらいしていてひっくり返った。結局機種変更もしたのでデータ移行には大して苦労しなかったし、ここで買う意味は一切なかったようだ。父に無駄遣いをさせてしまい申し訳ない。

二要素認証アプリの設定やチャットアプリの引継ぎなど古いスマホを使いたい用事はまだまだあったので持ち帰ってきた。以下の写真は仙台に戻ってから撮ったものである。古いスマホの色が赤なのはちょっとした冒険心だが、思ったより馴染んだ……というかどうせ画面しか見ないので気にならない。新しいスマホも奇抜な色にしようと思っていたのにプラチナシルバー・ブラック・ブルーしかなかったので、泣く泣くブルーを選択した。

駅で仙台に帰る新幹線の指定席券を買った。帰るのは金曜日の昼過ぎの予定。そこそこ混んでいたらしいが大宮までは3人掛け通路側の席を、そこからは3人掛け窓側の席を取れた。午後1時半に帰宅して昼食を摂り、午後2時半就寝。

01/03(水)

午後10時起床。夕食はすでに終わっているため夜食になるのだろうか、とにかく別メニューを用意してもらった。昨日のすき焼きで余った牛肉を使った牛丼。高い肉だけあって柔らかくて美味しい。

入浴して午後11時半からCodechef Starters 115に出た。コンテスト初め。このコンテストはRated for Allで、2週間前の113もそうだった。こんな短いスパンでRatedがあるのはかなり久しぶりに感じる。

https://www.codechef.com/START115A

書く:CC

修論に取り組む気になれず新しいスマホの設定をしていた。この時気づいたのだがやはり古いスマホは電池がかなり消耗していたらしい。そちらの感覚で見れば新しいスマホの充電の減りはほとんどないようなものとすら感じられた。

午前4時くらいからようやく執筆を開始。今日も午前8時半くらいに両親が起床したため、切り上げて朝食を摂った。今日は最後のお雑煮。少し残った分は納めるという話だったので、2.5人前くらいを全部食べつくした。

昨日変な時間に寝てしまったので、金曜日昼過ぎの新幹線に乗るために今日夜まで起きて生活リズムを一周させるつもりだった。しかし思ったより眠い。諦めて午前10時半ごろ寝た。

01/04(木)

午後9時半起床。寝すぎ。本当はもっと早く起きて一緒に夕食を摂るつもりだったので自分の分も用意されており、それを食べた。

食後に読売新聞を開いたら「賢くなるパズル」というのが目に入り、軽い気持ちで取り組んだら1時間以上かかってしまった。9\times 9の盤面が数マスずつ連結な領域に分割されているので、1\dots 9の数字を各行各列被りのないように埋めて、各領域の数字の総和または総積、2マスの場合なら差・商も可能、が領域で指定された数と一致させるというもの。

演算が指定されているパターンもあるようだが今回はなかった。これが厄介。例えば3マスで105と書かれていたら3\times 5\times 7と埋める数字は一意に決まるが、24だと2\times 3\times 4,1\times 4\times 6,1\times 3\times 8の他に7+8+9もあって大変。

どの数字もすべての行・列に出現する、という条件と領域の条件の合わせ技でしか先に進めなかったタイミングが2回ほどあって、苦しんだ分わかると快感だった。5マスで42と書かれているところに7+8+9+9+9を埋めたのだが、これはそのあたりに9をたくさん置く必要があったから分かったことである。こんな約数の多い数なのに総積ではなく総和が適用されるあたり作問が上手すぎる。

01/13追記:この問題は懸賞問題だったので締め切りが過ぎるまで回答の公開を待っていた。新聞紙に手書きした写真を張ろうとしたが、検索したら専門のブログの記事を見つけたため代わりにそのリンクを置いておく。それにしても、この難易度で「そんなに大変ではなかった」のか……。

読売新聞 夕刊 賢くなるパズル 1月4日 練習・挑戦問題 - なぜだかパズルが好きすぎる

入浴後は日記を書いたり来年度のミールカードの申し込みをしたりしていた。申し込みについて、たしか昨年までは書類を郵送していたと思うのだが、今年はWebから。コロナ禍での冷凍弁当の注文システムを流用しているらしく懐かしい気持ちになった。

午前5時くらいにようやく布団に入ったがなかなか眠れず、1時間ほどハーメルンを読んでから就寝。

01/05(金)

午前9時に目が覚め、布団の中でスマホを触っているうちに1時間くらい経過して予定していた起床時刻になった。

食事して荷物をまとめ昼前に家を出発。母に黒部宇奈月温泉駅に送ってもらった。12月の体調不良で大家さんにお世話になったという話をしたら駅でお土産を買って持たされた。まだ時間が余っていたのでお土産屋をうろうろしたり、天気が良かったので山の写真を撮ろうとしたりしていた。

改札前で母と別れホームへ上がった。途中の階段の一部がずれていてびっくり。写真はうっかり全体像を撮ってしまったのでわかりにくいが、壁際を見ると一目瞭然である。

せっかくなのでここで元日の地震からしばらく経っての所感を書いておきたい。余震は相変わらず続いており、今朝起きて布団の中にいるときも揺れていた。まあ富山だから揺れても震度1くらいなのだが、逆にここでそれだけ揺れるということは、震源に近い能登では同じ頻度で震度3や4を観測しているということになる。これはちょっと凄まじい話じゃないか。

元日の時点の報道であまり大きな被害が報告されなかったのを見て、正直に告白すると自分は呑気に「日本は地震に強い国だな~」などと考えていた。まあ富山県氷見市では断水が続いていたのだが。その考えを改めたのは以下のツイートが話題になってから。書いてあることをよく読むと音信不通の町がある。これで、被害が少ないのではなく集計できていないのだと理解した。事実、それから日を追うごとにじわじわと、しかし着実に死者数は増えていっている。気が滅入る話。

新幹線の車内ではずっとハーメルンを読んでいた。午後4時前に仙台に到着。その足でゲーセンに向かい、3時間半で19クレ投入して01/10まで開催のイベントを走り切った。慣れない素手だったので成果は特にない。どんなにスライダーを乾拭きしてもプレイしているうちにすぐ指がべたついてしまうので、おしぼりが用意されている店舗じゃないと無理だなと感じた。

イオン地下のフードコートでラーメンを食べて帰宅。大家さんに連絡を取って持たされたお土産をお渡しした。

シャワーを浴びて午後10時。今からUniversal Cup 17回目・Jinanセットに参加する。土曜日はOUPC・ABC・Hello 2024とコンテストが盛りだくさんで、フルで参加できるタイミングがなく運営に連絡を取ってこの時間にずらしてもらった。後から知ったことだがUSA1チームはUCを土曜日午前9時から開始し、4時間で全完してそのままOUPCになだれ込んだらしい。

The 2nd Universal Cup. Stage 17: Jinan - Dashboard - Contest - QOJ.ac

書く:UC

感想戦を終え、少し日記を書いて午前4時半就寝。

01/06(土)

午後1時5分前に起床。OUPC2023 Day 1にはソロで参加するのでどうせなら動画を撮ろうと思い立ち、急いで準備を済ませた。何とか間に合って録画開始から十数秒後にコンテストが始まった。

OUPC 2023 Day1 : 大阪大学セット - AtCoder

ABCLJKDHIQMGNFをこの順で解いて14完、3ペナしかつけなかったので速度差で5位に入った。最初3問が難易度順であることは知らされていたので、まずそれを解き、あとは順位表で多く通されているものを見ていった。

A、Bはよい。Cは先頭の文字との差分で判定。Lは実験するとX=0Y=\frac{1+3+\dots+3^{T-1}}{3^{T-1}}が得られた。Jは\sum_x k^xが等比級数の和で求まり、\sum_x x^kFPS典型。Kは現在時刻をループ変数で表現し、そのタイミングである空港にいるためにはいつまでに空港1を出発しなければいけないかという情報を管理した。

Dは括弧列と同じ要領でスタックを使えばバーガー文字列が判定できる。知りたいのは全バーガーだけなのでSの先頭1文字を抜いておくことに注意。またS自体が全バーガーである場合にも注意。通してすぐに問題設定を共有しているというE問題をしばらく考えてみたが、こちらは何もわからなかった。Hは答えを二分探索し、bool値のdpをbitsetで高速化するM^2 X\log K/\mathrm{wordsize}が1secで通った。

IはAN-Aを用意しておけばB\ge 0だと思ってよい。つまり重複を許して選び出した要素の和\bmod Nを考えていることになるので、g(t):=1+\sum(t^A+t^{N-A})という多項式に対しg(t)^kの係数を見れば\sum B\le kとなるような解があるか判定できる。指数の\bmod Nを取ったり係数が大きくなりすぎないよう01に置き換えたりしつつ二分探索。

Qは変換がセグ木に乗り、(i,j)\mapsto(Ai+B,Cj+D)あるいはその転置として表せる。そこでc\le((Ai+B)\bmod N)\le dを満たすようなiの総和が求められればよい。\gcd(A,N)=1よりAの逆元を取ったりして計算すると、結局ある範囲のxに対しA^{-1}x\bmod Nの和を求める問題に帰着できた。これは(X\bmod N)=X-\lfloor X/N\rfloor\times Nを用いてfloor_sumで解ける。

Mはユークリッド最小全域木を取ってその辺だけ見ればよい。kactlから高速なドロネー三角形分割を拝借して通した。全点が1直線上にあるときで1WAしたので、右上・右下・左上・左下の十分遠くに4点追加した。

kactl/content/geometry/FastDelaunay.h at main · kth-competitive-programming/kactl · GitHub

Gは駒がある頂点のペアで状態を表現できる。このままだと遷移がO(NM)になり、提出したら1ケースだけTLEした。結局自分が駒を動かせる頂点に勝ち状態があるかチェックしているだけなので、頂点のペアを決めてから行ける頂点を舐めるのではなく頂点の片方を決めたタイミングで行ける頂点を舐めることにしたら、bitset高速化が効いてO(M+N^3/\mathrm{wordsize})で通った。

Nは、k-1番目のグループまで座るのに成功したとき、k番目のグループが座るのに失敗する必要十分条件\sum_{i=1}^{k-1}A_i+k(A_k-1)\ge Lとなる。この式を見ながら今座っている人数を持ってdp。状態数O(NL)で遷移O(L)に見えるが、kが大きいとk(A_k-1)\lt Lを満たすA_kが少ないため、調和級数で2乗logになっている。おそらくO(L^2\log N)。座らせないグループの人数を弄って得できる場合があることに注意。サンプルが優しい。

Fはa\gt bに対し(a\mod m)\lt(b\mod m)となる条件を考えると(b\mod m)+((a-b)\mod m)\ge mに等しく、ba-bの商列挙を同時に行うことでmの範囲が出せた。これをa=\max Aのもとほかのbに対してすべて計算すれば、mとして考えられない正整数の区間が求まり、クエリに答えられる。O(N\sqrt A)個の区間が現れるためvectorで管理するとTLEで、左端が小さい区間を配列に持ったら間に合った。よく考えれば(a\mod m)\lt(b\mod m)から直接商列挙に持ち込める。

残り15分でPの部分点を全探索で通そうとしたが、ギリギリで投げたコードは実装ミスにより落ちた。ただし1401点がおらず、自分は1400点の中では最速だったため順位に影響なし。

撮った動画には昨日のUniversal Cupのコードが映り込んでしまったので、そちらの終了を待って日曜日に公開した。やたら音割れしているが、もしかしたら年末年始で人とたくさん会話したためデフォルトの声量が一時的に大きくなっているのかもしれない。以降の動画ではマイク音量を少し下げている。

www.youtube.com

TLを見ながら呆けているうちに時間が過ぎた。食事して午後9時からABC335。今日は企業スポンサードに見えて賞品もないし、個人情報の入力も求められない不思議な回。

AtCoder Beginner Contest 335 (Sponsored by Mynavi) - AtCoder

書く:ABC

www.youtube.com

OUPCの動画公開が遅れるため、この動画が新年一発目となる。冒頭に年始の挨拶を入れておいた。

午後11時半からはCF Hello 2024に出た。

Dashboard - Hello 2024 - Codeforces

書く:CF

www.youtube.com

明日も朝早くからOUPCがある。午前5時前に布団に入ったがうっかりカクヨムを読み始めてしまい、寝たのは午前7時くらいだった。

01/07(日)

午後1時10分前に起床。カメラなどは昨日セットしたままにしておいたので、今日は撮影準備に慌てることもない。午後1時からOUPC2023 Day 2、今日もソロ。

https://onlinejudge.u-aizu.ac.jp/beta/room.html#OUPC2023Day2

ABICDKEGJFHをこの順に解き、全完3位。Aが最も簡単ということだけ知らされており、また今日は同時コーディングが禁止なので、順位表情報が得られないタイミングもあるかもな~と心配していたが、結局2問目で詰まったせいでその後そのような場面はなかった。

Aはよい。後から解説を見たら場合分けO(1)解法があってびっくりした。次にとりあえずBに進んで、手でちょっとやってみたら解けそうだったのでそのまま取り組んだ。Nが奇数のときは行をrotateしていく感じでよい。偶数のときも同様にできるらしいが、気づかずちょっと面倒な構築をしてしまった。ここでタイムロス。

順位表を確認したらすでにいろんな問題にACが出ていてひっくり返った。あとはsolved数順に。Iは行列累乗。Cは入力を(\sin\theta,1-\cos\theta)として1-\cos t\thetaが答え。二分累乗法っぽく加法定理を適用していく。

Dはかなり悩んでしまった。閉路において頂点数と辺の数は等しいから、なもりグラフに対し閉路の辺を1本選ぶと考えてもよい。よって答えは1辺と全域木の組でdisjointなものの数。最初に1辺固定すると全域木をM回数え上げる必要があって、グラフのラプラシアン行列があまり変化しないことを用いた解法がないか探しに行ったが見つからなかった。実は最初に全域木を固定するとM-N+1を掛けるだけになる。

Kはオイラーツアーとセグ木でlrの範囲を求め、掛け合わせる。Eはどちらかの数列を使い切ると確率計算が素直に行かないので、整数Kまたは-Bを置く直前の状態で場合分けした。Gは操作を逆から見る典型。今回頂点に重みがついているが「任意の点に対し最遠点は直径の端点のどちらかである」という性質は辺重みの場合から変わらないようで、それを使って直径を更新していける。Jはマージテク。

Fはとりあえずリールごとに考える。1回殴ると期待値はE_1=\frac{\sum a}Mになり、以降殴れる回数が増えるごとにE_{i+1}=\frac{\sum\max(a,E_i)}Mと変化していく。あとは頑丈さをどのように割り振るかだが、Xが大きいため愚直な計算は不可能。しかし実は列Eが上に凸なので畳み込みが線形時間で計算できてしまう。1回も殴らない場合を加えると凸性が壊れるため別で遷移させなければならないことに注意。

Concave Max Plus Convolution | Library

Eが上に凸であることはコンテスト中は実験で確かめただけだが、証明も難しくない。M\times(E_{i+1}-E_i)=\sum\max(a-E_i,0)より差分が非負だとわかり、ここからまずEが単調増加であると言える。E_iが大きくなるにつれ差分の式は明らかに減少するため上に凸だったというわけ。

Hは1列の状態をあらかじめ列挙して遷移させてみた。1列だけ切り出すと長方形は区間になる。H=7a:=28通りあるため全部持とうとすると228になり到底間に合わないが、ここからいろいろ枝刈りを考えた結果b:=4140通りまで減らせた。高速ゼータ変換の要領で区間を一つずつ潰したり増やしたりすれば遷移はO(ab)回の計算で行え、W回繰り返しても十分高速。

枝刈りは「左端または右端を共有する区間は同時に存在しない」というもの。実は当初考えていたのは「左端または右端を共有する区間があるとき、大きいほうを後から追加することはない」という程度のことだったのだが、実装ミスにより前者を書いていたようだ。後者は大きいほうから追加されると無力なので枝刈りになっていない。

www.youtube.com

Dで辺を固定した後毎回全域木を数える解法はO(N^4)になるらしい。グラフGの全域木の個数をT(G)と書くと、辺uvについてT(G-uv)=T(G)-T(G/uv)となる。ここでT(G/uv)を行列木定理で求める際、縮約で生じた頂点を取り除いて考えることにすれば、使用する行列はGラプラシアン行列Lから頂点u,vを削除したものL^{(u,v)}と一致する。

その行列式L^{(u)}(v,v)における余因子として現れるが、今L^{(u)}は正則なので、逆行列行列式を求めてしまえば余因子行列が計算できて手に入る、ということらしい。余因子行列から逆行列を手に入れる話は線形代数典型であるものの、逆もできることを意識したことがなかった。感動。

食事した後、明日のセミナー準備を始めた。このセミナーは自分の今後の研究計画を考えるのが目的。先生に眺めておいてと言われた教科書を定理に絞って読み、めぼしいものを書き出していた。

途中で飽きてカクヨムに手を出してしまった。最近読んでいた「面倒くさいからって試験をサボったら序列最下位で学園生活が始まったんですけど、ここからでも巻き返すことってできますか?」を読了。同じ作者は他作品で現代ダンジョンものを2本書いており、どちらも非常に好みなので新作のこれにも手を出してみた。相変わらず誤字が多いが面白い。

kakuyomu.jp

教科書を読み終えた後は論文のサーベイを行った。最近の研究の動向を見ようと思ったのだが、そういう探し方は何分初めてなものでよくわからない。まあ目ぼしいものはいくつか見つかったからよしとしよう。シャワーを浴びて午前6時前に布団に入り、1時間ほどハーメルンを読んで就寝。