12/12(月)

午後4時過ぎ起床。

古典部シリーズが愛蔵版で出版されるらしい。まだ本に収録されていない短編が二つ含まれるようなので、ぜひ買いたい。こういうコレクターズアイテムはさすがに本の扱いがド下手くそな大学生協で予約する気にはなれない。地元で買えるとそのまま実家に安置できるので嬉しいが、タイミングが合わなければ仙台の本屋で予約することになるだろう。限定生産とあるのでちゃんと予約を忘れないようにしたい。

【情報解禁】
米澤穂信さんの〈古典部〉シリーズが愛蔵版に！

第1弾は「氷菓」「愚者のエンドロール」に加えて
2つの物語が新規小説となって収録されます✨
豪華な函入り単行本で3/2発売予定。

限定生産につき書店やウェブストアでの予約をせひお願いします🙏https://t.co/z00XUc8W25 pic.twitter.com/G8bxfk7Wpl
— KADOKAWA文芸編集部 (@kadokawashoseki) 2022年12月12日

午後4時半からインターン先定例会。金曜日に少し進めたのが先週の進捗になり、今週はタスクがないし学業も忙しいので休むということを報告した。

勉強会はHTTPS通信の話。暗号化が絡むとかなり理解が苦しくなる。暗号化の方式を十分に知っているわけではないし、かといって完全にブラックボックスと見なすには挙動を知らなさすぎる。それ以外にもHTTPS通信には面倒なことがいろいろあるらしく、とにかく大変だということは分かった。

それらを終えたタイミングで先週の週記を投稿した。文章は昨日寝る前にほぼ完成している。校閲は……諦めた。いつかしたいが今はできない。というのも、明日のセミナー準備が何もできていないため。教科書の先週少し読み進めた部分については、定理の紹介と系だけで肝心の証明がなかったのでセミナーでは扱わないことにして、これからその続きを読む。

準備を進めながら月ノ美兎さんの登録者100万人耐久記念配信を見ていた。開始とほぼ同時に100万人に到達したようだ。むしろ配信開始までチャンネル登録を解除して待っていた人がいたらしい。僕は何も考えず直前にチャンネル登録してしまった。

www.youtube.com

怪しくて胡散臭い社員3人の事務所のオーディションに応募してほぼ5年、

いま、チャンネル登録を100万人もの方にしていただけました。

わたくしをそんな面白い人生にしてくれて、本当にありがとうございます！！！ pic.twitter.com/eOjqeLK3mn
— 月ノ美兎🐰 (@MitoTsukino) 2022年12月12日

午後11時くらいにセミナー準備が完了した。明日は補題を一つ紹介した後定理を一つ示す。この補題の証明は教科書のずっと先のほうにあるらしく、ここでは深く踏み入らないことにした。少し前の部分では証明がないから飛ばすと言っていたのでかなり基準がバラバラだが、大胆に飛ばしていかないといつまでたっても教科書を読み進められないこと、かといって読んだ端から飛ばしていてはセミナー準備ができないことからしょうがないものとする。

そこそこの疲労感を抱え明日のためにもう寝てしまおうと考えたところで午後11時半からECR139があることを思い出し、しばらく待って出た。

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

Aはよい。Bは長さ2の部分文字列で等しいものが二つとれるか調べる。ただし重なっている場合を除くことに注意。

Cは片方の端からもう片方の端へジグザグに進むしかない。両端の列にWが現れるようBだけの列を適切に切り落とすと、通るべき始点と終点がわかるので、その間を実際に辿ってみて解いた。最初に上下どちらの行にいるかを両方試せば切り落とす必要もなかったらしい。

Dは $\gcd(x+k,y+k)=\gcd(x+k,y-x)$ を使う。 $y-x$ を素因数分解して、素因数ごとにそれを $x+k$ が含むための最小の $k$ を考えればよい。 $y-x$ の素因数分解は、エラトステネスの篩の際に素因数を記録する前計算によって $O(\log(y-x))$ で行える。

Eは大変。0を無視し、丁寧に場合分けする。まず、1と2が隣接して現れるまでは一つの列で吸収できる。1の直後に2が現れ、二つ目の列ができたとしよう。このとき、3が現れないか、表れても直後に1が現れれば、二つの列の末尾が常に1と2になってすべて吸収できる。3の直後に2が現れても、その後1が現れる前に3が再度現れれば元通りになる。

ただ、3の直後に2が1個以上現れ、さらに続けて1が現れた場合のみ、三つ目の列が必要。そしてこれ以上多くの列は必要ない。今のことを正規表現っぽく書くと、/12/のあたりまでは $f=1$ 、その後/32+1/のあたりまでは $f=2$ 、残りは $f=3$ ということになる。もちろんこれの1と2を入れ替えたパターンもあるが、結局調べるべきパターンは4種類しかないので、すべて気合いで管理した。一発で通って安堵。

Fは最小費用流が説明されて、典型だから少し変えた次の問題が解けますかと書かれていた。その問題も流量制限を加えるだけだから典型だろと思っていたら案外難しかった。まず容量が奇数の辺にはあらかじめ1流しておき、残りの容量を全部半分にすることで偶奇の条件を忘れる。

あらかじめ流した分だけいくつかの頂点は需要・供給点になっていて、この値は偶数でなければならない。ただし正確には、頂点 $1$ と $n$ はその限りではない。サンプル4に助けられた。あとは頂点 $n$ から頂点 $1$ への辺を作ってまず需要と供給を満たし、次に頂点 $1$ から頂点 $n$ までコストが負の間流せるだけ流せば、求めるフローが得られる。

今言ったような2段階に分けず、需要と供給のための辺にめちゃくちゃ小さなコストをつけて必ず使われるようにしようとしたらWAだった。正直よくわかっていないが通ったのでOK。Library Checkerにフロー関係全部盛りの化け物みたいな問題があるらしく、ここから提出を拝借してきた人もいたようだ。

https://judge.yosupo.jp/problem/min_cost_b_flow

全完6位。この6位というのはopen hacking phase終了後の順位で、コンテスト終了直後は8位だったはず。Fで何人か落ちているのを見かけ戦々恐々としていたが、自分の提出は落とされなかった。

最近連載が始まったなろうを1作読了。「天外の観測者」。タイトル通り上位存在らしい主人公が人類を観測したり、眷属を通して干渉する話らしく、かなり楽しみ。現在連載されている最新話はちょうど主人公が今の状態に至るまでの話が終わったところで、ここからいよいよ干渉が始まるようだ。

https://ncode.syosetu.com/n8255hy/

しばらくTLを眺めた後午前3時頃に布団に入った。そこから1時間ハーメルンの更新をチェックして就寝。

12/13(火)

午前9時半ごろ起床したが、眠気でボーっとしていたら今日もセミナーに微妙に間に合わない時間となってしまった。

午前10時過ぎに大学に到着。午前中は同級生のセミナー。30分ほどしたところで寒さに耐えかね教室を移動することになった。エアコンが壊れてもう3週間目になるが、一向に直る気配がない。

エアコンが壊れているらしく非常に寒かった。
週記（2022/11/28-2022/12/04） - kotatsugameの日記

移動先の教室でそのまま正午過ぎまでセミナーを続行。今日はBöhm treeの一致に関する話だった。無限木になる可能性があるので、ラムダ式の構成に関する帰納法ではうまく言えないらしい。そこで、ノードが一致することをノードの深さに関する帰納法で一つずつ丁寧に見ていくことになった。

昼食を摂り、午後1時から自分の発表。証明の途中で目的がいまいち見えないとの指摘を受けた。そういえば、教科書には証明の前にアイデアと大まかな流れがしっかり書かれていたのに、そこを完全に無視してすぐ証明に突入してしまっていた。以前はそういうところも含めて発表の流れを考えられていたのに、今日忘れてしまったのは大失敗。反省。

また、終盤の議論がうまく伝わらなかった。ここはちゃんと教科書の記述をなぞりつつ、行間も埋めたと思っていたので、何が悪かったのかよくわかっていない。自分で付け加えた文言が何か混乱を招いたのだろうか。

午後3時前に終了。今日は博士課程の方の発表がないらしく、そのまま解散となった。帰宅し、準備してゲーセンに行く。午後4時半頃から閉店までいて30クレちょっと使った。グッズキャンペーンのため12/21までに貯める必要のあった30ポイントを今日だけで確保することに成功。

今日の成果はすごい。夕食を摂る前までは、新曲を埋めて理論値が一つ、またそれとは別に14+のAJを二つとパッとしない感じだったが、夕食から帰ってきて閉店までの2時間で15のSSSを三つ出した。

parvorbital SSS pic.twitter.com/coptti102g
— こたつがめ (@kotatsugame_t) 2022年12月13日

今日通常解禁された譜面。何回かプレイしていると前半の勝率はそこそこ確保できたが、後半は漫然とプレイしているだけではどうにもならない。改めて譜面をしっかり確認し、運指を考えた。

63小節目からはスライドのエアーを取る手をすべて逆にして、代わりにその近くのホールドを両手で取る。これで片手3鍵がほぼなくなるし、後からタップ交じりになるときも縦連が少なくて済む。またリズムに関して、ほとんどのところは慣れたら目押しで通るようになったものの、66小節だけ短いホールドが多くて辛い。しかしよく見るとほぼ同じ間隔である。そのことを意識したら劇的に改善した。

80小節からは左手親指を真ん中に固定して取った。右利きだから右手親指を固定したほうが良いのでは？と考えたもののうまくいかなかった。あとは急なトリルに対処できるよう譜面を覚え、頑張るしかなさそう。タップの巻き込みが辛いのは当然として、フリックもなかなか難しかった。固定しておいた左手を大きく動かす必要があって、意識の切り替えがうまくいかない。

最後は謎。初見の時は1アタで通ったのにそれからミスもアタックも大量に出るようになって大変だった。ただ、SSSを出したときはここに5-0で突入したはずで、気持ちに余裕があったのが幸いしミスは出なかった。

X7124 SSS pic.twitter.com/QQLzEquzGw
— こたつがめ (@kotatsugame_t) 2022年12月13日

7kに乗せたときから運指はほぼ変わっていないはず。というか、何か考える前に出てしまったというのが正しい。結局92・93小節がうまくいけば出るというところまではたどり着いていて、今日はうまくいったので出た。全部右始動だということを確認したのがよかったのかもしれない。

手元を撮りながらX7124のSSSを狙っていた。
週記（2022/10/03-2022/10/09） - kotatsugameの日記

otorii INNOVATED -[i]3- SSS pic.twitter.com/gnnceiswzs
— こたつがめ (@kotatsugame_t) 2022年12月13日

いつの間にかラストの超早い配置が通るようになっていて、すんなり出た。18・20・22・24小節あたりが苦手なのは相変わらずで、SSSを達成した回もそこで2-0出している。56-58小節は右手三つ左手三つを交互に繰り返して取っており、何も見えていないがうまくいくときはうまくいく。今日は勝率が高かった。ラスト、緊張でリズムが崩れたのか500点以上削られてしまい、少し心残り。

以上三つを立て続けに達成した後、Strange Loveを詰めていたらレート17を達成した。SSS+が導入されてからベスト枠の計算をしていないので今どのくらいかはわからない。

RATING 17.00 pic.twitter.com/TO61GrtPAQ
— こたつがめ (@kotatsugame_t) 2022年12月13日

詰めていたStrange Loveについては結局6.6kくらいで終了。中盤までかなり良いペースで進むことが数回あったが、終盤がどうにもならない。うまくいくときもあったはずなので、狙えないわけではないと考えている。

日付が変わったくらいに帰宅。疲れてPCの前に座った後立ち上がれず、2時間ほどTLを見ていたらしい。

シャワーを浴びてからラノベの新刊チェックと注文を行った。前回から1か月以上間が開いたこともあり少し多め。年末帰省した時に買って読む用として、ちょうどその時期に出版される本のうち何冊かはわざと注文しないままにしておいた。楽しみにしているシリーズの続刊があり、生協の開店を待たず入手できるという点でも嬉しい。

いくつか嬉しい新刊について。「黄金の経験値」の書籍版がついに発売されるらしい。イラストが非常に格好いい。副題やあらすじは何というかちょっとテンプレっぽくなっている気もするが、なろうのあらすじにあるような「NPCとフレンド登録する話」ではさすがにパンチが弱いのだろう。自分が読んだときもそこに惹かれたわけではなく、お試しで手を出したら一気に引き込まれたのを覚えている。

kadokawabooks.jp

次に「現代社会で乙女ゲームの悪役令嬢をするのはちょっと大変」4巻。3巻が出てから1年以上経過し、もう続刊はないかと諦めてしまっていたところで新刊情報を見つけ、非常にびっくりした。

over-lap.co.jp

布団に入ってスマホを触っているうち、午前5時くらいに寝落ち。

そういえば、今日は先週参加したDMOJのコンテストの期間が終了する日だった。ここに感想を書いておく。

2022 Bayview Secondary School Programming Contest - DMOJ: Modern Online Judge

P1、P2はよい。P3は値の範囲が大きくても入力の近くだけ見れば解けるやつだなあと思いながら、今回は特に工夫せず解けるためそのまま書いた。P4は問題文を読むのに苦労した。解法は二分探索で、off-by-oneエラーで1WA。

P5は各値について分割方法が何通りあるか独立に数え、掛け合わせる。素因数として2を含む個数を数えればわかるが、その分割方法を求める式を間違えて1WA。P6は $A$ の降順にソートしてdp。P7も $A$ の降順にソートして、優先度付きキューで $B$ を管理した。

P8は揃えるのに必要な操作回数 $\bmod 3$ を位置ごとに記録し、遅延セグ木に乗せた。区間内に3種類の値のうちどれが存在するかを持つ。TLの2secギリギリだが一発で通っているのでOK。区間の情報を長さ3の配列で表していたところを3bitで表現し、ビット演算をいろいろ使ったら、0.7secくらいになった。

37分ちょっとで全完し3位。

12/14(水)

午後5時半起床。今日はレポート、セミナー準備、TAの仕事とやるべきことが盛りだくさんである。

最初に日付が変わるまでが期限のレポートに着手したが、Classroomから講義スライドを開こうとしても開けなかった。ファイルが削除されてしまっているらしい。もしかして講義からしばらく経ったら資料を削除するタイプの先生なのかとも考えつつ、恥を忍んで見えないと報告してみたところ、無事再アップロードしてもらえた。

さらにレポートの期限が明日であることも教えてもらった。思いがけず今日やるべきことが一つ消えてラッキー。講義資料が消えており、またClassroomの課題に期限が設定されていなかったので、本当の期限がいつなのか勘違いしていた。ところで、期限が設定されていないので課題のリマインドがなく、この課題は提出に失敗する人が多いだろうなと思う。改めて報告する気力もないので放置。

課題からの解放感によってしばらくYouTubeに時間を吸い取られた。次はTAの仕事。明日発表分の資料、というか本のコピーが上がっていたので、それを見てコメントを加えた。

二面体群は、二次元の物体である二面体を三次元において裏返す対称性も含む。これに対し、三次元の物体を四次元において裏返す例として右手用の手袋を左手にはめる話が挙げられていた。しかし手袋は手を入れる口から裏返せるので四次元にする必要はなさそう。そういえば球を裏返す話を以前TLで見たなと思い出し、「Outside In」という動画を紹介してみた。冷静になると関係があるのかないのかよくわからない。そもそも四次元をイメージできないのでどうしようもない。

www.youtube.com

最後にセミナー準備に取り掛かった。以下のような理由から、今週は昨日と明日で2回セミナーを行うことになっている。

来週のセミナーについても話した。再来週は自分が集中講義のため参加できない。よって来週が年内最後になりそうで、2回行うことになった。今のところ火・木の予定。
週記（2022/12/05-2022/12/11） - kotatsugameの日記

教科書の今読んでいる章は残り補題一つと定理一つで終わるらしいから、そこまで進められればきりが良い。またその残っている定理は証明が5ページあって、やろうとしたら確実にセミナー1回では終わらなさそう。そこで、この定理を飛ばすことにした。

飛ばすといっても、セミナーで扱わないだけで自分は読んでおく必要がある。もしかしたら細かな議論を取り除けば発表できるサイズになるかもと期待しつつ読んでみた。しかしそれだけで3時間以上かかってしまい、要点を絞れるかどうかというより、そもそももう一度取り組むだけの気力が残らなかった。

すでに日付が変わっているが、それからセミナーの原稿を作り始めた。補題の証明をしたらメモが5ページになって、ちょっと足りないかもしれないと思ったので、追加で話すことを探した。火曜日のセミナーで紹介した補題を教科書から探してみたところ、これまで学んだ定理だけで証明できるらしい。ただ明日話すにはちょっと長かったので、その近くに書いてあった、今日扱う定理から示される別の定理について話すことにした。

午前4時過ぎに完成。シャワーを浴びて布団に入った後うっかりハーメルンの更新をチェックしてしまい、就寝は午前6時になった。

12/15(木)

午前9時45分起床。今日は山の上の教室ではなく川内キャンパスだからと余裕をぶっこいていたら、セミナーの開始時間に家を出ることになってしまった。

午後1時までは同級生のセミナー。ラムダ式で原始再帰関数や再帰関数を表現する話で、真偽値、リスト、自然数を定義していた。自分が知っているWikipediaにある定義とは少し違っていて、飲み込むのに時間がかかった。

1要素のリストの表現が2要素以上と異なっていて統一的に扱えない。また自然数がリストの長さとして定義されていて、デクリメントが書きやすいのは良さそうだが、0をデクリメントすると0ではなく変な値が返ってくるのがこれまた扱いづらそう。

昼食を摂り、TA関連で先生についてちょっと図書館に行った後、午後2時から自分のセミナー。5限があるので時間は2時間しかなかった。昨日はもうちょっと長い時間話すことになると思って準備していたが、駆け足で話したら何とか時間内に終えることができた。

今日扱う証明はどういう段階を踏んでいるか分かりやすかったので、発表にもそれを反映し、段階ごとに何が目的かを強調したのがスムーズに進められた理由かもしれない。あるいは単に自分が焦っているのが聞いている側にも伝わっただけか。

教室を移動して5限、TA。今日の発表はちょっと詰まり気味という印象を受けた。内容がこれまでやってきたのと少し違い、発表者本人も本の記述を細部まで理解できているわけではないようで、そこに自分と先生でいろいろ突っ込みを入れた結果、進みは芳しくなかった。

わからないことがあれば事前に質問してほしいと思うが、自分が学生の立場だったとしてわざわざ質問しに行く手間をかけるかというとそうでもないから、しょうがないという気持ちもある。ただの全学の講義なのだから、数学のセミナーらしく本の一字一句を解釈してもらうのは止めたほうがいいのかもと先生も仰っていた。

一方、それを補って余りあるほど熱意は素晴らしい。来週また今日の続きを発表することになって、講義後少し練習しようという話になったが、これがなんと1時間以上続いた。この講義のためにそれほどの努力をしてもらえるということに感動。自分も付き合っていろいろ質問に答えていた。

午後7時を回って解散。学食で夕食を摂り、少し雪がちらつく中原付で帰宅した。吐く息でメガネが曇り、前が見えず大変だった。

シャワーを浴び、昨日後回しにした生命情報システム科学のレポートに着手した。データが与えられるので分析して何か言えという課題。参考としてR言語のライブラリのチュートリアルがリンクされていた。

これまでもレポートにR言語を使うチャンスはあったが、どの回もデータを探してくる部分にドメイン知識が必要で、自分ではどうにもならなかった。今回は最初から与えられているので、それとチュートリアルのコードを組み合わせればすぐ形になりそう、と思っていた。実際無事グラフがいくつか得られたものの、思ったより上手くいっていない様子がある。主成分分析をしたら固有値の値がめちゃくちゃ大きくて、そこから何を言えばいいのかわからなかった。

よくわからないまま適当なことを書き、図表をいくつか貼って完成。午後11時過ぎに提出し、半からCF #838 div.2に出た。

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

Aは最初の状態で条件を満たしていなければ、どれか一要素に操作を連打して偶奇を変えればよい。どの要素を選んでも可能なので、全部試して最小の手数を求める。Bは全部2べきに合わせる。

Cは0と1が隣接する位置を考えると、extensionにおいてそこまでに出現した0と1の個数が等しくなる必要があると分かった。そのような位置で $s$ を切ると、できる部分文字列たちはそれぞれ0のみまたは1のみだから、extensionによって挿入される文字はその逆である必要がある。つまり、 $s[1,i]$ をextensionするとき、最後に0と1が隣接する位置までは何を挿入するかが一意に定まってしまう。残りは自由なので、その個数を $i$ を昇順に見ながら数えればよい。

Dは解けず。 $\gcd(p_1,p_j)$ を全部聞くとその $\max$ または $0$ が $p_1$ になること、 $2p_1\gt n-1$ なら $p_1=\gcd(p_1,p_j)$ となる $p_j$ または $p_1$ 自身が $0$ であること、そうでない場合も $p_1$ の倍数だけ集めて同じ操作を繰り返すことができることを考えた。 $p_1\ge 2$ なら操作を繰り返して最悪 $n+n/2+n/4+\dots\le 2n$ 回のクエリで答えられるが、 $p_1=1$ のケースがどうにもならなかった。

Eに進んで、こちらは解けた。まず木に対して辺の重みの決め方は高々一意である。適当に根付き木にして葉から決めていけばわかる。また $n$ が奇数のとき重みの決め方が存在しないことも分かった。重み $-1$ の辺を頂点から見てダブルカウントしたものは必ず偶数だが、奇数を $n$ 個、つまり奇数個足すと奇数になってしまう。

辺の重みがどう定まるかよくわからなかったので、根を $1$ とする木dpっぽく求めることにした。部分木の頂点数と、部分木の根に接続した重み $-1$ の辺数の偶奇を持つ。上のほうはケイリーの公式で求め、辺の寄与を求めて足し合わせる。しかしうまくいかない。

そもそもdpが $O(n^2)$ なので望み薄。上だけでなく下、つまり部分木自体もケイリーの公式で求められないか考えてみた。頂点 $1$ と頂点 $n$ を結ぶパス上にある辺を一つ取り、それを削除した時の連結成分で頂点 $1$ が含まれるもののサイズが $l$ 、頂点 $n$ が含まれるもののサイズが $n-l$ だとする。それぞれの木はケイリーの公式で数え上げられて、辺の張り方は $l\times(n-l)$ 通り。

最後に、見ている辺にどんな重みが割り当てられるか考えたい。重み $1$ が割り当てられたとすると、その辺を削除したときにも木全体、あるいはそれぞれの連結成分が条件を満たすことがわかる。つまり $l$ は偶数。重み $-1$ なら $l$ が奇数であることも言えて、逆に $l$ の偶奇から重みがわかるようになった。この辺りは手で実験していたら思いついた。

問題文中にケイリーの公式がわざわざ書いてあって面白い。その公式を知っているか問う問題にはしたくなかったのだろう。実際、辺の重みに関する考察がまた別途に必要であった。

Fを見て解けず、Dに戻ってしばらく考えていたらコンテスト終了。4完63位。ひどすぎる。

Dのupsolveをした。三つ要素を取り出したとき、そのうち一つを候補から外せるようだ。0が含まれていないなら何でもよい。三つが $(0,x,y)$ （ただし $x\lt y$ ）という組だった時、3通りのクエリの答えが $x,y,\gcd(x,y)$ となる。 $x,\gcd(x,y)\lt y$ ということをチェックすればうまく $(0,y)$ を残すことができる。コンテスト中はクエリ回数制限の $2n$ を $n+n$ だと思っていたが、この解法は $2+2+\dots+2$ と見ている。そういう意識の切り替えが一切できなかった。

しばらくネット小説の更新分を読んだ後、午前8時まで日記を書いていた。布団に入り、ハーメルンを開いて1作読了。

syosetu.org

「音楽チートで世に絶望していたTS少女がSIDEROSの強火追っかけになる話」。主人公のチートっぷりが非常に良かった。ネットで配信者として活動する主人公というのは何作品も漁ってきたが、クリエイターとして活動する主人公というのも気になる設定だなと感じている。最近記憶に残っているものだと、「Vのガワの裏ガワ」は主人公が自他共に認める神絵師で、これも良いなあと思っていた。しかし探してもあまり見つからないのが残念。

午前9時就寝。

12/16(金)

起きたら午後2時だった。ちょうど1on1の時間である。飛び起きて会議に接続した。

振られていたタスクはなく、また新しく発生することもなかったようで、今日はペアプログラミングになった。細かい計算がある部分だったので、自分でも紙に書きながらコーディング風景を眺めていた。結局特に指摘するような間違いも起こらず、うまく動くのを確認して解散。1時間半ほどだった。相手の画面を見ていただけと言えばそうではあるが、ちゃんとダブルチェックのように確認していたので貢献したという感触はある。

1時間ほどしたらサークルが始まるが、眠いので今日は休むことにし、布団に戻って二度寝した。

午後8時頃目覚ましで覚醒。yukicoderがあると思っていたらないらしい。三度寝はせず、ずっと横たわってハーメルンを読んでいた。午後11時頃布団から脱出し、半からECR140に出た。

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

Aは $x$ または $y$ がdistinctならよい。Bは $a_2,\dots,a_n$ の間で操作しても値が均されるだけで嬉しくない。よってそれらの数を小さいほうから順に使っていく。 $a_i$ によって $a_1\rightarrow\max(a_1,\lceil(a_1+a_i)/2\rceil)$ とできる。

Cはdp。今見ている位置にある文字と異なる文字が直近でどこに出現したかを持つ $O(n^2)$ 状態で、遷移もよく見ると全体で $O(n^2)$ だった。遷移がvalidであるかのチェックも前計算によって定数時間で行えるが、それをしなくても通る制約で嬉しい。

Dはトーナメントの段階ごとに勝ち上がることのできるスキルレベルの区間を計算。出力以外 $O(n)$ でびっくり。最大値と最小値だけ出力させるマルチテストケースにしなかったのはなぜだろう。答えが区間になることを見抜く問題だったのか。

Eは $c_i$ と $c_{i+1}$ のどちらかをアクティベートしなければならない、という条件たちになる。つまり重み付き最小点被覆で、半分全列挙で解けた。条件をbitで表現しておくと $n=m/2$ として $O(n)$ でチェックが行える。対になる値の取得はゼータ変換っぽい何かになり、全体で $O(n2^n)$ となった。

Fは解けず。値がほぼdistinctな場合、二つの部分木に同じ値が含まれるか調べる必要があって、それすらできなかった。時間いっぱい取り組むことすらせず逃亡しハーメルンを読んでいた。結果は5完5位。Fは $O(n^{7/4})$ という話を聞いた。すごい計算量だ。

布団に戻ってさらにハーメルンを読み続け、午前8時頃1作読了。「闇の正義スパンダム」。

syosetu.org

最近ランキング上位に載っているし、タグに「主人公最強」とあることで気にはなっていたが、スパンダムというキャラに良い印象がなく避けていた。しかし読んでみると非常に面白かった。ハリポタ原作でギルデロイ・ロックハート主人公の「私は誰でしょう？」しかり、わざとそういうキャラをメインに据えることによる目新しさ、そこから生まれる面白さというのは確実にあるようだ。

もちろん原作通りのふるまいをしているようではまた悪印象を抱かれるから、そうではない。この作品のスパンダムはとにかく最強で、またストイックだった。そういうぶれない主人公が好き。話も少年期からスタートしたのに中弛みなどなく、間をポンポン飛ばした後原作でルフィと関わる部分を描いてそのまま完結した。まあもう少し読んでいたいという気持ちはある。

それから少し他作品の更新を読んで、午前9時くらいに寝落ち。

12/17(土)

午後3時過ぎに生協の冷凍弁当を受け取り、1時間半ほどハーメルンを読んでまた寝た。

午後7時半起床。食事してシャワーを浴び、午後9時からABC282に出た。

HHKB Programming Contest 2022 Winter(AtCoder Beginner Contest 282) - AtCoder

A、Bはよい。Cは1文字ずつ見て、今括られた文字を見ているかそうでないかのフラグを切り替えていった。

Dはちょっと面倒。連結成分を一つずつ見て、二部グラフでないものが見つかったら即座に0を出力、そうでない場合は $N(N-1)/2-M$ から、連結成分内で同じグループに属する点をペアにする場合の数を引く。このとき引いたものだけが追加したときに二部グラフ性を失う辺の候補で、当然入力の辺を含むこともない。よって残りが答えになる。

Eはちょっと悩んだ。操作した要素を辺で結んでみると、どうやら木になるらしい。逆にどんな木にも対応する操作が存在する。辺のコストは全部前計算できるから、最大全域木を求める問題になった。

FはSparse Tableを作れと書いてある。いまいち自信がないので自分のライブラリを探しに行ったら、Disjoint Sparse Tableしかなかった。それを頑張って写したら何とか一発で通ったが、結構面倒だった。

Gは挿入dp。インデックスと類似度と $A$ 、 $B$ それぞれの末尾の値を持つと状態数が $O(N^3K)$ で、遷移が苦しい。よく見たら二次元累積和で書ける形で、本当にこれが想定なのかと疑いながら実装したら通った。 $P$ が素数であることは使っていない。

Exに1時間残したものの解けなかった。 $B$ の累積和を取って $C_i=B_1+\dots+B_i$ とする。 $r$ を固定し、 $\min\{A_l,\dots,A_r\}+C_r-C_{l-1}\le S$ となる $1\le l\le r$ を数えたい。式変形すると $C_r\le S+C_{l-1}-\min\{A_l,\dots,A_r\}$ となるので、右辺をデータ構造で持つことにした。

$\min$ の項が等しい $l$ の区間を管理すると、その区間が変化するとき対応する $l$ に対して値が少し変わる。これが更新クエリで、取得クエリは $C_r$ 以上の値を数えるというものになる。後者だけならrangefreqだが更新ができない。そこで平方分割することにした。かなりバグらせつつ何とか実装したものの、TLEしてしまい、3secを切ることすらできずそのままコンテスト終了。

7完41位。Exは分割統治らしい。最小値で切って、短いほうだけ見れば $O(N(\log N)^2)$ になる。見たことがあるはずなのに解けず、悔しい。

No.1496 不思議な数え上げ - yukicoder

コードゴルフ。C問題まで手を付けたがどれも最短を取れておらず、今回はダメダメだった。日曜日までちらほら更新があったため、それも含めて記録しておく。

Aはdc 18B→Perl 17B→Raku 16Bと更新されていて、dcだけが自分。PerlはA..Zというリストから必要な部分を切り出す方法だけ試していて、そもそも終端をZ固定ではなく入力から作るということに思い至らなかった。しかもそこで諦めてしまい、Rakuで文字コードのリストから文字列を作る関数chrsがあることを思い出せなかった。これがコードゴルフで出てくるのは初めてではないのに。

chrs | Raku Documentation

BはPerlでボロ負け。文字列のビット演算を使う。

Cは非常に面白い。1文字ずつ見るのはやめて、括られた文字を一気に読むような正規表現で短くなるらしい。それは間に"を含まない文字列という意味での/"[^"]*"/とか、あるいは最短マッチが書けるPerlなら/".*?"/でもよい。

この正規表現と/,/のORでマッチさせると、括られた文字に含まれる,はダブルクオーテーションを含めまとめてマッチするので、その文字列が1文字かどうかなどで場合分けすることで括られた文字でない,だけが見つかる。アスキーコードの妙で、マッチした文字列に'"'をbitwise ORすれば、,1文字のケースのみが.に変化するようだ。

atcoder.jp

午後11時半からCF combinedに出た。ハンドルネームか知らないが問題文中の人名がやたら長くてちょっと読みにくかった。

Dashboard - Polynomial Round 2022 (Div. 1 + Div. 2, Rated, Prizes!) - Codeforces

Aは1の前の演算子を交互に切り替える。

Bは、できるだけ同じ要素で埋めようとすると周期 $k$ になるので、 $\lfloor n/k\rfloor+1$ 回出現する要素が $n\bmod k$ 個、 $\lfloor n/k\rfloor$ 回出現する要素が $k-(n\bmod k)$ 個となる。 $a$ の最大値が $\lfloor n/k\rfloor+1$ を超えないことと、ちょうど $\lfloor n/k\rfloor+1$ になる要素が $n\bmod k$ 個以下であることをチェックすればよい。

Cは昨日のECR-Dと同じに見えてトーナメントでないから結構違う……かと思ったら解法はそれなりに似ていた。可能な最大値と最小値を求める。結論だけ言えば、 $s$ の使用するprefixについて、末尾から一致している文字の数を数え、人数から引けば答えになる。

Dはちょっと詰まった。1の個数を調べ、とりあえず達成不可能なケースをはじいておく。あとは1が不足している行に余っている行から移すのを繰り返すだけで揃えられれば明らかに最短手数。では、それは本当に可能だろうか？冷静になると当然可能で、なぜなら足りない行において0、多い行において1となる列はどんな場合でも必ず存在するから。操作の順序もなんでもよいことが分かったので、あとは頑張って実装。

Eは木dp。二つの駒のうち片方しか訪れなくてよい部分木があったら、もう一方の駒は上のほうで待っていることになる。このとき距離 $d$ 以上開けないよう適切な位置まで下りてくることになる。dfs 1回で書けると思うが、ちょっと混乱してしまったため2回使って丁寧に書いた。

F1。体力に対し豚が何匹いるかを記録する列を管理する。操作1は特定の位置をインクリメントすればよい。操作2は全体をずらせばよい。操作3は、「これまでずらした量」だけずらした列を現在の列に重ねることになる。これをうまく表現したい。

列を実際にずらす代わりに、「どれだけずらされているか」という値 $d$ を持っておく。また「これまでずらした量」 $D$ も持っておく。自分の方針では $d=D$ とは限らない。まず、操作1では体力 $x+d$ の豚を追加することになり、操作2では $d\leftarrow d+x$ 、 $D\leftarrow D+x$ とすることになる。

操作3だけは真面目に行うことにする。 $D$ だけずらした列を重ねられれば良い。 $D=0$ の時は全体に2掛けることになるので、特別に記録しておく。 $D\lt 2\times 10^5$ のときは愚直に計算し、 $D\leftarrow 2D$ とする。ここで $d\ne D$ となる。 $D$ の値は指数関数的に増えていくのでこの操作はあまり行われない。 $D\ge 2\times 10^5$ のときは何もしなくてよい。

列をmapで管理したら通ったが、そのままF2にも投げたらMLEで落ちてしまった。操作3をもうちょっと簡略化してみる。この先使う $D$ からいくつか選んで体力から引き、最終的にずらされた状態でも体力が残っているようにする方法の数だと考えられる。

今 $D$ は常に倍々以上に増えていくため、ある位置の $D$ が選べるなら、その代わりにそれより前の $D$ たちをどのようにでも選べる。このような制約下での数え上げは、大きな方から貪欲に取った場合を2進数だと思うことで求まる。

残り時間はGに取り組んで、解けず。包除原理で書き換えると答えが $[-1,1]$ の区間に収まるようになった気がするが、答えが愚直と全然合わなかった。

コンテスト後に順位表を見たら、Gがそれほど解かれていないのに順位がかなり下がっていてびっくりした。どうやらBのpretestが弱かったらしく、大量Hackで上位に躍り出た人がたくさんいる。システスは全部通って47位、レートは2732→2773(+41)。自分の部屋でBを落とした人が11人いて、これらをHackすることができていれば1ページ目に入っただろうと思うと残念。しかし本当にGが解けそうだったのだ。

システスを見届けてから日記を書き始めたが、朝方集中力が切れてラノベに手を出した。1冊読了。

「VTuberなんだが配信切り忘れたら伝説になってた」5巻。読んでいる自分のその時の気分でシリーズの評価が結構ばらけるが、内容は1巻から相も変わらずバカ騒ぎ。今日はこういうものが楽しめる気分だったので面白く読めた。次巻への引きに興味を惹かれたものの、これもまた圧倒的なネタの洪水に飲み込まれるのだろう。

別の本を開いてしばらく読み、正午就寝。

12/18(日)

午後7時起床。非常に嬉しいツイートがエゴサーチに引っかかった。

「Vのガワの裏側」、読んだ
こたつがめさんの週期で絶賛されていたのと、テーマ的にも自分が最近ハマってる V だったから読んでみたけど、非常に良かった
単純に話が面白いというのもあるけど、それ以上に主人公に好感を持てて良かった
— やまけー (@yamake_cpp) 2022年12月18日

「Vのガワの裏ガワ」は本当に面白かったのでおススメ。それはそうと、自分の書いた文章が人の意思決定に影響を及ぼしたことが嬉しい。読んだ本やネット小説の感想を日記に書くのはもはや惰性で続けていることだが、なんだか報われた気がした。と言っておいて、実は「非常に面白かった」と書いてあれば絶賛していると思ってもらって間違いないので、細かい感想まで読まれてはいないかもしれない。それでも嬉しさには変わりない。

しばらく日記を書いた後、昨日読み始めた本をまた開いた。そのまま読了。

「ケーキ王子の名推理」6巻。非常に面白かった。5巻が出たのが2年以上前ということで、日記に書くのはシリーズ6冊目にして初めてらしい。最初は日常の謎っぽい推理がメインだった記憶があるが、今は主人公や周囲のキャラたちの、恋の話がメインになっている。それが面白いのだ。ハッピーな話も一筋縄ではいかない展開を辿るし、ビターな話もその中に確かな幸福があって、かなり感傷的になれる。

ラストは短い間に展開が二転三転して気持ちの乱高下を味わった。その締めくくりがまたなんとも言えず悲しさと嬉しさが混じりあったもので、読後感が良い。ネタバレしないようにしたら曖昧なことしか言えなかったが、とにかく面白かった。

午後11時半からCF #839 div.3。今の本を読み終わったのがちょうどコンテスト直前だった。

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

Aはよい。Bは4通り試す。手数を答える問題ではないので回転方向に気を使わなくてもよい。Cはちょっと面倒だった。階差数列を取って、suffixの短いほうからインクリメントするのを和が $n-1$ になるまで繰り返した。

Dは隣接項の関係に注目。 $a_i=a_{i+1}$ なら何でもOK。 $a_i\lt a_{i+1}$ なら $x\le\lfloor(a_i+a_{i+1})/2\rfloor$ 、 $a_i\gt a_{i+1}$ なら $x\ge\lceil(a_i+a_{i+1})/2\rceil$ が必要。

Eは自分が変えなければならない要素すべてに青を塗るまでの手数が問題。先手・後手しか塗らなくてよい要素、どちらにとっても塗る必要のある要素をそれぞれ数えて判定する。自分しか塗らなくてよい要素を先に塗って、最後に「どちらにとっても塗る必要のある要素」が残ったら引き分けとなる。

Fは、一度変化したセルは二度と変化しないし、その周囲のセルは一度も変化しない。なので変化したセルについて変化前・変化後が完全に区別できるから、どの盤面がどの盤面より前に来るかわかる。この条件でDAGを作り、トポロジカルソートして、操作の復元を頑張ればよい。

G。 $a$ がソート済みとして、 $a_i\leftarrow a_i-i$ （ただし0-indexed）、さらに累積maxを取る。レートが $x$ の状態から $n$ 回戦うと、 $a_i\le n$ なる対戦相手には勝ち、そうでない相手には負ける。これで一周のシミュレートを高速に行えるようになった。 $a_i\le n$ となる対戦相手が一人以上増えるまで、あるいは一周の途中でレート $y$ を達成できるようになるまで何周か一気に進めるのを繰り返し、最後に端数を足せばよい。

1時間ちょっとで全完して8位。

しばらく日記を書き、午前4時前に布団に入った。明日は1限から対面で集中講義に出る必要がある。わかっているのになかなか眠れず、しばらくハーメルンを眺めていた。午前4時半就寝。