週記(2023/05/15-2023/05/21)

05/15(月)

午前11時半起床。正午から指導教員の先生と学振について打ち合わせをする予定だった。

それに関して今朝方メールが来ていた。内容は「評価書作成の材料とするため何か本や論文について今日説明してみてほしい」というもの。普段読んでいるDiestel以上の知識を何も持ち合わせておらず不可能である。顔面蒼白になった。

出発までのわずかな時間で昨日申請書と格闘した後開きっぱなしにしていたページを漁り、何か話せる話題がないか探した。一つ面白そうな定理が目に付くも今から読めるサイズの論文ではない。諦めモードで家を出たが、大学までの移動中になんと自力で示せてしまった。

打ち合わせは3時間に及んだ。自分に関する話、競プロに関する話、あとは先ほどの定理の証明。その場で考え考え喋っていたのでかなりボロボロな説明になり、実は先生には伝わらなかったようだが、自分でやっていて変な部分がなかったため証明の正しさには確信が持てた。後から論文を確認しても同じ方針だった。

先生から紹介された本を借りに数学科の資料室……は休みだったので情報科学研究科の図書室まで遠征した後、帰宅。しばらく調べ物をした後午後4時半からインターン先定例会に出席した。

先週の進捗はしょうもないものしかないので、画像を貼って発表スライドを飾り付けておいた。しかしこれについて少し議論が発生したため、無意味ではなかったようだ。

勉強会はオセロAIの話だった。角の周辺マスの良し悪しといった知識でちゃんと盤面を評価すれば、定石の具体的な手順を埋め込むとか泥臭い作業をしなくても十分強いAIが作れたらしい。ハイパラ調整のため、実際に打たれた手が(オセロに強い)人間から見て自然な手になっているか確認していたというのは面白かった。

先週の週記をほどほどに埋めて午後10時過ぎに投稿した。3コンテストが空欄のままになっているが、それよりも学振の申請書の進捗がまずい。明日も先生と打ち合わせする予定で、その時に今書けているものを見せてほしいと言われている。しかしほとんど何も書けていないのである!

朝までずっと、なろうに気を取られつつも申請書を書いていた。自己分析の欄は研究実績がない自分にとっては競プロの話をするしかなく、逆に競プロ関連なら自信があるため特に苦労せず話題を出せる。問題になるのは研究計画だった。そこを大して埋められないまま就寝。午前7時過ぎだった。

05/16(火)

今週からサークル活動が毎週火曜日になる。新歓時期は毎週月曜日に行われており、インターン先定例会とダダ被りして一度も参加できなかった。今週からはできるだけ顔を出したいと考えている。

早めに起きてサークル前に購買でラノベを受け取ったり散髪したりするつもりだったが、起きたら午後3時半だった。登校してみたら4限終わりとちょうどかち合ってしまい、購買周辺は大混雑。何もできないまま教室に向かった。

午後5時半から先生と打ち合わせのため、それまで1時間弱サークルバチャに参加した。後ろから解いた。9問目はいったん飛ばし最後に戻ってきて取り組んだが、8ケースWAから合わせられなかった。後から確認したところ、二分探索で求める境界が等号付きか否かを間違えていたと判明した。

https://kenkoooo.com/atcoder/#/contest/show/855f03d9-577a-4c20-9528-ce3120939a42

9問目に粘着してしまい10分ほど遅刻して待ち合わせ場所へ。申請書へのコメント・アドバイス自体はすでにメールで頂いており、対面では研究計画についての話し合いを行った。論文を眺めて未解決問題をチェックしていた。

午後7時に別れてサークルの教室に戻ったら、ちょうど解説が終わったところだった。コロナ禍前のICPC事情などしばらく駄弁って解散した。

帰宅してからはずっと申請書と格闘していた。言及しようと思っていた未解決問題が、先生から送ってもらった2012年の論文で解決されていることに気づいてひっくり返ってしまった。別の問題を探して載せることに。一通り書き上げたものを先生に送ったのが午前9時だった。

布団に入ってしばらくなろうを読み、午前10時半就寝。

05/17(水)

午後3時半起床。今日が数学科における学振の締切日である。しばらく布団に転がったまま過ごした後、大学に行ってラノベ受け取り、夕食、散髪を済ませた。

帰宅してから送られていた先生のメールに従い申請書を手直しした。これでいったん完成。先生に送った後ホスフィンにも見せて助言を乞うた。文字サイズを少し大きくするとか、英字フォントにTimes New Romanを使うとか言われるままに調整したところ一気に見栄えが良くなって感動。内容については今更変えるような気力がないため、何も言わないでくれと頼んだ。

午後10時に完成。改めて先生に送り、1時間ほど待機して何も返信がないのを確認し提出した。

解放感に包まれてハーメルンから「完璧な三角関係」を読了。全体的に淫靡で良かった。三角関係を構成する前後のみで完結した物語だったが、その後の話を是非とも読んでみたかった。

syosetu.org

午前6時半就寝。

05/18(木)

午後4時頃に目を覚まして布団でゴロゴロしていた。明日のセミナーでは前回準備した分の残りを発表する予定なので、今から新たに教科書を読み進めなくともよい。今日は何もしなくていい日だな~と思って二度寝に入ろうとした。しかしギリギリで1on1があることに気づいた。目覚ましもかけていなかったし本当に危ないところだった。

身を起こし、少しだけ作業して午後5時から1on1。相変わらず進捗がほぼない。さすがにこれはまずいと思い、今やっていることは1週間後までに必ず終わらせますと宣言した。その後はデバッグを眺めたりするだけで終了。一応これまで1on1の時間として2時間確保されていたが、最近内容が薄いので1時間半に縮めることとなった。今日もそのくらいの時間で終わっている。

解散後にも少しだけ作業した。今のタスクは本腰を入れたら、というか入れなくても1時間程度確保すればすぐ終わるようなものであることが発覚。このために一体何週間かけてしまったのだろう。

ABC301でピッタリ学生10位だったらしく、アマギフ5000円分が届いていた。

ハーメルンから「どう考えても、俺が三股疑惑かけられるのはまちがっている。」を読了。昨日読んだものと作者が同じ。こちらもかなり淫靡だったし、話がメインキャラだけで完結しておらず外部の反応もかなり描写されていたという点でより良かった。比企谷八幡が眼鏡をかけるとイケメンになるという設定はよく二次創作で見るもので、非常に好みである。

syosetu.org

午後9時過ぎに布団に入り、すぐ寝落ちしたらしい。

05/19(金)

午前1時半くらいに目を覚まし、朝方までずっとハーメルンの既読作品を読み返していた。具体的には「【完結】閃光と隼と風神の駆ける夢」。クライマックスのドバイ編はやはり最高であった。

syosetu.org

少し教科書を読んだりシャワーを浴びたりした後、午前7時半からまた寝た。

午後4時に起床し、セミナーのため大学に向かった。雨が降っていたため原付ではなく地下鉄を使用。思ったより時間がかかって、かなり余裕を持って家を出たのに到着は結構ギリギリになった。

今日は同級生が休み。まず1時間程度Diestel 1章の演習問題の発表を聞いて、その後2時間弱自分が発表するというタイムテーブルだった。演習問題は当然先週やったものと異なるから目新しくて楽しい。自分の発表は、先週準備したものをあまり復習せず黒板の前に立ったので、少し下手くそだったなと感じた。6.4章の最後まで行かなかったので残りはまた来週である。

午後8時過ぎに終了して帰宅。午後9時20分からのyukicoder 389には余裕を持って参加できた。

yukicoder contest 389 (Until that day when "Cherry Month" is over.) - yukicoder

Aは星5なのでいったん飛ばす。Bは「嘘をつく」という語彙に引きずられて問題文が読みにくかったが、単に色を変えているだけらしい。差分更新。CはABの両方に現れる数を列挙して適当に並べる。

DはまずBIT上の二分探索でSがもともとどの位置にあった演算子か計算し、その後最後の演算子から順に分割する再帰関数で値を評価した。演算子の順番とそのインデックスをセグ木に乗せ、区間MAXを取ることで最後の演算子を取得できる。

Eは大変苦労した。X,Y,Z,W円の組み合わせをそれぞれa,b,c,dセット売るとする。a+c+d\le Aなど三つの条件を満たしながらaX+bY+cZ+dWを最大化したい。a,dを固定したと考えてみると、c\le A-a-db\le B-a-db+c\le C-dが条件になる。

(A-a-d)+(B-a-d)\le C-dのとき、b,cは最大値を取ってよい。このとき売り上げはadの一次関数になり、dを動かしたときの最大値が簡単に求まる。そうでないときはb+c=C-dとするべきである。ここから例えばb=C-d-cと表すと、三つの条件がcの範囲として書けてしまう。売り上げは相変わらず一次関数だからcとしては最小と最大だけ試せばよい。これでadだけの式になり、後は先ほどと同様。

結局dの値を固定する必要はなかったということで、1ケース当たりO(A)で解けた。小さいケースで愚直と比較してから提出したら一発AC。

Fは最初にO(N^3)で任意の頂点間の経路を数え上げておき、クエリごとに関係する頂点だけ抜き出してO(K^2)でdpした。ただしクエリごとのdpで元々あった経路を分割して辿らないよう、最後に通った辺がクエリ特有のものかそうでないか状態に持つ必要がある。

残りAとGはどちらも星5。まずAを読んだがちっともわからなかったのでGに進んだ。こちらは実装が面倒なだけ。クエリ3もクエリ4も有名問題で、前者は辺に向きを付けて頂点の次数を抑えるやつ、後者はマージテク。一応クエリ3とクエリ1の順序には注意する必要がある。自分は頂点ごとにBITを持ち辺ができてから散った花びらのみ数えられるようにした。辺ができた瞬間に値を調整するだけでも良かったらしい。

Aは何もわからなかったのでCFに備え撤退。最終順位は6完トップで6位だった。

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

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

Aは問題文が読めない。サンプルによれば隣接する2文字を取り出して種類数を出力すればよいらしい。Bはそういう並び替えが存在するなら値の昇順にペアにしてもvalidである。

Cは\min(a)のparityを変化させられないことに注意。\min(a)が偶数ならparityを揃えるため奇数からは奇数を引く必要があって、もしaに奇数が存在する場合そのうちの最小値がどうにもならず不可能。\min(a)が奇数なら何でもOK。

Dはまず先頭の要素を最大化する。p_i=nとすると、i\ge 2ならr=i-1とすることでnを先頭に持ってこれる。またi=nならr=nでもよい。それ以外、つまりn\ge 2p_1=nの場合はnを先頭に持ってこれないので、n-1を探して同様のことをする。こうして答えとなる(l,r)の候補が列挙できたが、これはO(n)通りしかないから最大のものを全探索可能できる。

Eはia_iに辺を張ったグラフの連結成分を見る。これはfunctional graphなので必ずループを一つ含む。そのループの長さが3以上だったらそこでround danceは完結している。この場合さらに連結成分がちょうどループと一致することも言えるが、必要ない。長さが2の場合はround danceの切れ端であるから、切れ端を全部繋いで一つのround danceを作った場合が最小値、それぞれバラバラにした場合が最大値となる。

Fは条件から選ぶlevelの集合が連番になっている必要がある。aをソートしてランレングス圧縮し、連続m項が連番であることをチェックしたら人数の区間積を答えに足す、という方法で求まる。うっかりmodintを使わず実装してしまい、mod取り忘れで1WA。

Gは木dp。頂点数をカウントすればどんな形に切り分けなければならないかわかる。

50分ちょっとで全完し23位。動画を投稿した。

www.youtube.com

シャワーを浴びた後午前2時くらいからTCB58を解いていた。日曜日終了だからここに感想を書く。

https://techful-programming.com/user/event/4215

1問目はよい。2問目は最大値とそれ以外に分けてみる。3問目はiを全探索し、その連続部分文字列を全列挙した。4問目もよい。5問目はいかつい見た目をしているがP^{N+1}で通分しつつ愚直でOK。

6問目はKの約数を全列挙してそれをキーにdp。K=0はちゃんと場合分けしていたのにA=0を見逃してゼロ除算で1ペナ、負の約数を列挙し忘れていてさらに1ペナ。-18pt。

7問目はGrundy数。各頂点に対しその頂点の親までが根になったときのことを考えるとうまく定義・計算ができる。木を降りながらXOR和を累積的に求めていくことで遷移先の列挙が頂点ごとにO(N)となる。

8問目は、lを昇順に見ながら左右に共通して現れる要素のインデックスを管理するなどで、lに対する最大のr=r_lが計算できる。全体を反転すればrに対する最小のl=l_rも計算できる。この二つを用意すれば、r\le r_lなるlに対しBITで1を足して[l_r,r]区間和を取ることで、rに対する(l,r)の個数が求まる。これの高速化はrを降順に全探索するだけでよい。

9問目は何桁の整数がどの値からどの値までかという情報を列挙して頑張る。d桁の整数が[L,R]であるとすると、fの右半分には\sum_{i=L}^R 10^{d(R-i)}iのような形で現れる。これをWolfram|Alphaに投げると閉じた式にしてくれたので頑張って写した。

指数にd,L,Rが現れるので、これらは\bmod{(998244353-1)}で計算しておく必要がある。LR\bmod 998244353でも持っておく必要がある。2種類のmodintを使うと、変な計算をしたときにコンパイルエラーになってくれるので便利だった。制限時間21分のところ23分半かかって-3pt。

10問目は難しかった。難しいというより自分が苦手なのかもしれない。操作を逆に見て順列をN-1箇所で分割していくと思い、その順番を数え上げることにした。P_iP_{i+1}の間を分割できるタイミングは、j=\max\{j\le i\mid P_j\gt P_{i+1}\}としたときにP_jからP_iのうちどこかを切り離すよりも前である。

これは明らかに必要条件である。十分性については、分割する直前に列の先頭要素がP_jまたはそれより大きな値となっていることからわかる。言わばjより前に関する条件はP_jのためにすでに満たされているのだ。またP_1=Nは自明な必要条件なのでjは必ず存在する。

以上より「P_jからP_{i+1}にあるi+1-j個の分割のうち初めに行われるものはP_iP_{i+1}の間の分割である」という条件になった。実はこのi+1-jの総積で(N-1)!を割れば答えになる。条件は自分より前の分割についてしか述べていないので独立になっているらしい。後ろの分割から順に見て適する操作列だけ残していこうと考えたら納得できた。この問題には80分弱かけて-55pt。

布団に入ってしばらくスマホを触っていた。午前6時就寝。

05/20(土)

午前11時起床。外出して、午後0時半からホスフィンとたいぺーと3人で昼食会を行った。自分のこの予定に加えチームメイトが別コンテストに参加するため、今日のUniversal Cupは午後8時から5時間で参加することになっている。午前3時からでない理由は、明日のAGCに響きそうだから。

今日は自分の提案で懐石料理。高くて特別なものを食べたいと思っていて、その点では大満足だった。しかし食事を摂るなら満腹になりたいという男子高校生みたいな考え方が抜けず、物足りなさも感じてしまう。身の丈に合わないというのはこういうことかもしれない。

二人とも忙しい中たまたま会えたのが今日この時間であるというだけで、食べ終えた後は青葉まつりをしばらく眺め歩いた後解散となった。

帰宅して動画を見たり日記を書いたりし、午後8時からUniversal Cupに参加した。この話をする前に、コンテスト時間に完全に含まれていたABC302について書く。Universal Cupを途中抜けしてそちらにもちゃっかり参加していた。

TOYOTA MOTOR CORPORATION Programming Contest 2023#2 (AtCoder Beginner Contest 302) - AtCoder

Aは負の数がないのでdcで書ける。現時点での最短が7Bで、丸ごと覚えていたのでそのまま書いた。後から確認したらやっぱり最短だった。

Bは頑張る。Cは全探索。DはBをsetで持ってA_i+D以下の最大値を求めた。Eは隣接リストをsetで持って愚直に辺を張ったり消したりしても間に合う。

Fは集合が共通の要素によって鎖のように繋がるというイメージが浮かんだ。これによれば、集合のマージを「整数x\in X\cap Yを経由して集合XからYに行く」と言い直すことができる。あとは適切に辺を張って1からMまでの最短距離を求めればよい。

Gはソート後の列が確定し、どの要素をどの要素に置き換えなければならないかわかる。この情報で4頂点の有向グラフを作る。長さlの有向サイクルをl-1回のswapで解消する、という操作を繰り返してグラフの辺をすべて使い切りたい。サイクルへの分解自体はグラフの構成からすべての頂点で入次数と出次数が一致するため必ず可能。あとはできるだけ多くのサイクルに分解せよという問題になる。

まず長さ2のサイクルは貪欲に使ってよい。あとは長さ3と4のサイクルのみだが、ここで長さ3のサイクルも貪欲に使ってよいのではないかと考えた。特にヤバそうなケースも思いつかないし、何より焦っていたのでとりあえずで書いて出したらそのまま通った。証明はしていない。

Exはパスではなく列の場合が既出なので、まずその解説を見に行った。すると書いてあることが全部Undo可能UFで再現可能だったので、後はひたすら実装。ほぼ一発でサンプルが合いそのまま通った。

K - 種類数 β

31分50秒でノーペナ全完、優勝。賞品としてアマギフ20万円がもらえるようだ。1回のコンテストでもらった最高額を記録した。時給換算(するのが正しいかはともかくとして)でほぼ40万円というのもこれまでの最高値のほぼ倍である。

ただ、今日録画していなかったのが残念でならない。Universal Cupの最中だから前後バタバタしてそうだし今日はいいかなどと考えていた。ABC直前は考察が行き詰っていたから録画セットを準備できたはずだし、多少見苦しくてもとにかく撮っておくことに意味がある、と常々思っていたのに。何ならShadowPlayを起動しておくだけでも良かった。

気を取り直してUniversal Cupについて。今日は17回目で、Guangzhouセットだった。

第八届中国大学生程序设计竞赛总决赛(CCPC Final 2022) - Dashboard - Contest - QOJ.ac

書く

朝まで日記を書いたりなろうを読んだりしていた。午前6時半就寝。

05/21(日)

午後1時起床。外出し、昨日と同じ3人でラーメンを食べた。食後は本屋に寄ってから解散。

帰る前にゲーセンで少し遊んでいこうとして、うっかり午後7時までプレイしていた。バージョンアップ後初プレイだったため今日は新曲を埋めてばかりで特筆すべき成果はない。

帰宅してシャワーを浴び、ラノベの新刊チェックをした。本当は昼食後すぐ帰ってきて一眠りするつもりだったし、実際に微妙な眠気がある。不安感を抱きながら午後9時からAGC062に参加した。

AtCoder Grand Contest 062 - AtCoder

Aは難しかった。最初ランレングス圧縮した状態でfを記述しようとしたが、あまり綺麗にならないようだし末尾の取り扱いが難しい。統一的には扱えなさそうだから場合分けしてみよう、という経緯で末尾の文字に着目する解法に至った。末尾がAの文字列はfを作用させても末尾がAのままであり、答えもAとなる。

末尾がBの場合の挙動を調べるのはなかなか苦労した。文字列が/BA+B+$/にマッチする場合fを作用させると/BA+B*$/になるようだ。もうちょっと具体的には、末尾に連続するBが1文字減っていることも言える。従っていずれ末尾がAとなり、あとは先ほどと同様。そうでない場合、つまり文字列が/^A*B+$/のケースは答えがBであるとすぐ確かめられる。

念のため愚直と比較し正しいことを確認してから提出した。20分ちょっとかかって難しかったな~と思いながら順位表を確認したら、もう300人以上に解かれていて目の玉が飛び出た。実験エスパーをした人が多かったらしい。確かにこの条件は非常に見えやすそう。一度実験を始めたらまともな考察はできないだろうと考えて控えていたのが裏目に出た。

Bはすぐ解けた。挿入の操作がかなり強力だから、N-k項とk項に分割した後まとめるのを後回しにしてみる。1回目の操作でA=L+Rと分割された場合に、2回目の操作でどういうことが可能か考えた。すると、L=L_1+L_2R=R_1+R_2と分割して、L_1,L_2,R_1,R_2を(それぞれで順番を保ったまま)好きにマージできることが分かった。

この時k_2=|L_2|+|R_2|であり、コストはk_2C_2=|L_2|C_2+|R_2|C_2と書ける。このようにコスト計算を独立に行えるのが嬉しい。また分割後の列たちをマージしてPを作れるかの判定は、それぞれの列がPの部分列として現れるか見るだけでよい。この点でも独立になっている。

3回目の操作以降は今の話から類推できる。分割が再帰的に行えるので、それをそのままメモ化再帰にした。Aの連続部分列aと次に行う操作が与えられたとき、もしaPの部分列として現れるならコスト0を返し、そうでない場合0\le k\lt|a|を選んでaを分割しそれぞれ再帰的に解く。状態数がO(KN^2)で遷移にO(N)かかるので計算量は4乗。問題なく間に合った。

Cは細部を詰め切れずに何となくで通してしまった。Aをソートしておく。A_1\dots A_{k-1}で「作れない」数の集合Sが分かっているとして、A_kを追加して更新するのをkの昇順に行う。

r=\sum_{i=1}^{k-1}A_iとおく。Sには[0,r]のうち作れない数が入っているものとする。A_k\le rのとき、更新後の集合にx\in[0,r+A_k]が含まれるのは、x\lt A_kならx\in SA_k\le x\le rならx,x-A_k\in Sr\lt xならx-A_k\in Sの場合である。よってSを舐めることでxを列挙できる。r\lt A_kのときは単にS\cup(r,A_k)\cup S+A_kが作れない数の集合になる。

Sを更新した後、A_k未満の数はすべて条件を満たすXであるから、これがK個以上になったら即座に答えを出力できる。特に区間(r,A_k)は非常に大きくなり得るが、小さいほうから高々K個しか答えに関係しないため全部愚直にSに入れる必要はない。

ただしSの要素がすべてXとして適切なわけではないので、計算が続いているなら|S|\lt Kであるとかは言えない。しかし|S|が指数関数的に爆発するようなケースはなさそうに思えた。ジャッジに聞いてみるくらいの気持ちで出したら通った。

この時点で1時間しか経っておらず6位とかなり良い順位にいたが、その後2時間使ってもDが解けなかった。どこかのiに対する\max(D_i,\max(D)/2)が答えになると思って判定を頑張っていたものの全然合わない。距離だけチェックして途中で|x|+|y|がはみ出ないか考えていないから、そこに問題があるのだろう。

終盤になってDがどんどん通っていき、最終的には28位となった。パフォーマンス3199でレートは2842→2883(+41)。highestを1だけ更新した。大成功ではあるが、Cのエスパーを交えて崖まで速解きしただけなので、満足感がない。

動画を投稿した。これが初めてのAGC実況となる。

www.youtube.com

Aだけコードゴルフした。sed/^A*B+$/を調べるより条件を反転させて/A$|BA/としたほうが短くなるらしい。ここまではすでに提出があったが、TNの読み飛ばしを3~2!dと書くと縮んだ。このコマンドは「3行目、5行目、7行目……『以外』を削除」である。

TCB58の結果が出ていた。優勝。そもそも全完者が少なかった。

かなり長い時間AGCの余韻に浸ってTLを眺めていた。AGC前にチェックしておいた新刊27冊を注文した後、日記を書いたりラノベを読んだりして、午前7時に就寝。