2022-11-28

週記（2022/11/21-2022/11/27）

11/21(月)

午後3時起床。生協に行ってラノベと菓子パン等を買ってきた。帰ってきてコードゴルフをしていたら午後4時半になったので、インターン先定例会に出席。

先週の1on1で自分が携わっていた部分は概ね完成したと認識している。今週は出力をチェックするくらいしかタスクがありませんと報告。

勉強会はStable Diffusionやより一般の画像生成AIについての話だった。最近よくTLに流れてくるのでかなり興味がある。タイムリーな話題でありがたかった。

画像の生成は、ノイズ画像を評価が高くなる方向に変形させ続けることで行うらしい。画像の各ピクセルをパラメータだと思うと、機械学習でlossを見ながらモデルを作るのとやっていることは大して変わらないように思う。この意味で、画像生成AIは学習の手順を学習していると言うことができないだろうか。多段階の構造があって面白いなと思った。

終えてから週記を書く。実は今日中に完成させるのは諦めていて、コンテストをいくつか穴あきにしたままとりあえず体裁だけ整えた。そこからセミナーの準備に取り組んで、集中が切れたら週記に戻ってコンテストを一つ埋めて、……という風に交互に進めていた。

午後11時を過ぎたあたりで週記を投稿。最終的にOpenCup代理、OUPC、CF combinedの部分が空欄のまま。

午後11時半からCF #835 div.4に出た。

Dashboard - Codeforces Round #835 (Div. 4) - Codeforces

Dまではよい。Eは01列の転倒数なのでインデックスの差で計算するのが簡単、と思って書ききったが、冷静になると前後にある01の個数を数えたほうが直接的でわかりやすかった。

Fは $k+1$ 日周期で報酬が多いクエストから行うことになる。 $k$ を二分探索。この $+1$ に由来するoff-by-oneで少し苦しんだ。

Gは $a$ 、 $b$ から各頂点に向かうパスの累積XORを計算してみて、それらの間に重複があればよい。ただし $a$ から向かうパスを計算するときは $b$ より先の頂点を無視する。

30分で全完し4位。

セミナー準備に戻り、午前3時に何とか完成。明日はいよいよMengerの定理を示す。教科書には証明が三つあって、そのうち二つ目までを準備した。最初、証明の終わりのマークを見落としていて、二つ目の証明がめちゃくちゃ長いと思い込んでおり、どうやって発表するかかなり迷っていた。よく見たら一つ目よりも短かったので拍子抜け。

その後、今日もDMOJのコードゴルフコンテストに時間を投入してしまった。午前5時に布団に入ってからさらに1時間程度スマホを触り、就寝。

11/22(火)

起きたら午前9時50分だった。立派な寝坊。この時間には目覚ましをかけていなかったので、逆にこのタイミングで起きることができたのは奇跡的。昨日買っておいたパンを食べて出発。

セミナーの教室に着いたのは午前10時半だった。午前中は同級生の発表。冒頭を聞き逃してしまったためついていくのに少し苦労した。こちらからは特に何も言わなかったが、一部同じ説明を2回繰り返してくれたらしく、申し訳なくも非常にありがたかった。

昼休みは購買で買ったものを食べた後ハーメルンを読んでいた。窓口が開く時間を見計らい、終了直前になってTA関係の書類を提出。

午後1時からは自分ではなく先に博士課程の方の発表が行われた。頑張って聞いていたが、まだ示せていないらしい部分に差し掛かり先生と黒板で議論し始めたあたりで限界が来て、ちょっと意識を飛ばしてしまった。先生に声を掛けられて一気に覚醒。叱るという感じではなく、単にこの後セミナーできるかを聞かれた。罪悪感がすごい。

午後3時半から自分のセミナー。昨日用意した二つの証明のうち片方を終わらせた時点で1時間半が経過していたため、そこで終わりにすることにした。教科書で言えば1ページにも満たない進捗だが、行間をかなり丁寧に補うとこんな感じになる。

終わった後しばらく先生にOUPC-Dの説明をしていた。先生が担当されていて自分もTAとして参加している木曜の講義が、ちょうど多面体を扱っているので、何か関係がないかという意図。自分が知っている解法がひたすら頑張るだけなので、特に実のある話にはならなかった。

https://onlinejudge.u-aizu.ac.jp/services/room.html#OUPC2022/problems/D

学食でホスフィンと合流して夕食。またゲーセンで会おうと言っていったん別れ、午後6時半ごろ帰宅した。

DMOJのコードゴルフコンテストが終了していた。9問中8問で満点を獲得し優勝。問題ごとに回答する言語が指定されていて、特定の文字数以下でACコードを書けるとその問題は満点となる。ゴルフ用語で言うところの「パー」である。それに数文字及ばない場合も適当な単調減少関数に従う部分点が得られて、9問目はそこまでしか縮められなかった。

Lyndon's Golf Contest 1 - DMOJ: Modern Online Judge

いくつかの問題にはメインで問うているテクニックがあるように思われる。満点を取らないと他人の提出は見られないが、自分の書いたコードについて少しポイントを記録しておきたい。

1問目は簡単。2問目は(n+1)の代わりに-~nを使いましょうという意図だと思う。特に今回、2乗されるので負号も省略できる。

3問目からちょっとてこずった。Pythonでtrueまたはfalseを出力する問題。YNeosテクニックを使うより、単に真偽値を文字列化して小文字にしたほうが短くなってびっくりした。この条件式を縮めきるのにも苦労している。

4問目は記号のみを使ってRubyでゴルフする。入出力は$<と$>、文字列長は正規表現で文字列の末尾を検索すると得られ、改行文字は$/に入っている。正規表現のテクニックはRubyで記号のみのコードを書く場合ほぼ必ず出現する。

5問目もかなり悩んだ。単に2重ループを1重に圧縮するだけでは全然縮まない。出力にputcharではなくputsを使えないか考えてみる。putsの戻り値について、出力した最後の文字、つまり改行文字を返す環境と、出力した文字数を返す環境の二通りがある。DMOJは後者らしく、それをループの条件式に入れたら縮んだ。あとは文字列用のメモリをまともに宣言しないようにする。

6問目は4問目とは対照的に、Perlでアルファベットと数値（とスペース）だけを使う。DMOJ\nを10回出力せよという問題。改行を出力する必要があるのに改行文字も$/も使えないが、こういう場合にはバージョン文字列v10を使うというのはAtCoderでも見たことがある。文字列結合もできないのでどうしたかというと、文字列置換で押し込んだ。

$_=v10はfor v10で1要素のループを回せばよい。文字列置換は普通s///だが、このスラッシュはパースできればどんな文字でも、アルファベットでもよい。オプションrを付けて置換すると$_と書かずに$_が得られ、それをx10することで10回分の出力を作れる。

7問目は約数を列挙する問題で、AtCoder典型。商列挙のアルゴリズムが使えることさえ知っていればコードゴルフ的には全く難しくない。かなり毛色の違う縮め方を要求されるからか、単独の満点だった。

Submission #35518851 - アルゴリズムと数学演習問題集

8問目にもかなり苦しみ、最終的には若干嘘が混じった解法で通した。530%getchar()という値が単調増加であること、足すと48の倍数になることをチェック。単調増加のフラグに和の下1bitを使うため、こういう大きな数を持ち出して偶数になるようにしている。48の倍数のあたりが嘘だが、作問側がそういうケースまで対処しきれているはずもない。

追記：ケースが追加されて落ちていた。

9問目は満点が取れなかった問題。フィボナッチ数列の指定された項を答える。ループをexecで書いて48B、 $\frac 1{\sqrt 5}\left(\frac{1+\sqrt 5}2\right)^n$ をroundして46B。後者は検索したら出てきてようやく気付いた。この問題の制約 $n\le 50$ なら精度が足りるというのもびっくり。

anarchy golfに同じ問題があって、パーが達成可能なこととそのStatistics、つまり文字種の構成までわかっていた。43Bを達成したコードにも複数あるようで、空白文字が存在しないコードとするコードがある。これはおそらく1行でも複数行でも書けるということだ。空白文字がなければループ構文は使えないし、一般項を書くとすれば空白文字を入れる必要性がなさそう。つまりexecを使う方針が有力に見える。

あとは、問題が公開された年から最短コードが提出された年まで結構空いているから、言語のバージョンアップによるものかもと考えた。昨日はこのあたりを調べてみたが箸にも棒にも掛からず。

anarchy golf - Fibonacci Number

また外出してゲーセンに向かう。しばらく遊んでいたらホスフィンも到着して、それからはマッチングしていた。成果は14+のSSS+が三つ、AJが二つ。またマッチングの間に再理論値が二つあった。特に「泥の分際で私だけの大切を奪おうだなんて」は3回目で、かなりびっくり。

ホスフィンとマッチング！理論値3回目出た！ pic.twitter.com/iQn2dBBU7G
— こたつがめ (@kotatsugame_t) 2022年11月22日

ガストで食事して帰宅。シャワーを浴びて少し日記を書き、布団に入った。スマホを触っていたら寝落ちしたらしい。おそらく午前2時頃である。

11/23(水)

午後3時半起床。久しぶりに起きる時間を定めず思い切り寝られた気がする。

昨日プレイした分でチュウニズムのグッズプレゼントキャンペーンのポイントが貯まっていたため、今日が期限のキャラクターと引き換えておいた。

大家さんのところに実家からカニが届いたらしく、夕食に招いていただいたためお邪魔した。カニだけでなくステーキも焼いてもらって非常にありがたい。腹いっぱい食べ、さらにお酒も飲むなどやりたい放題だった。

帰宅してから届いていたTCO Finalsのグッズを開封した。Tシャツの左腕を見せるときにグッバイ宣言のサムネのポーズが適しているのではないかと考え、1時間くらい格闘して写真を撮った。酔っていたのかもしれない。できるだけ似せようと思い、指の角度や腕・手の位置にはかなり気を使っている。

TCO Finalsのグッズが届きました
・賞状
・TCO Tシャツ
・マグカップ、帽子、ステッカー、手紙、謎の木
・腕にkotatsugameと書かれた長袖Tシャツ
（＋これらが入ったトートバッグ） pic.twitter.com/DOdNYOIW70
— こたつがめ (@kotatsugame_t) 2022年11月23日

実は生命情報システム科学のレポート期限が今日までだったので、ここから日付が変わるまで頑張っていた。AlphaFoldが大きく取り扱われていて興味深い。Google Colabでそれを動かすNotebookが公開されているので、適当に触って3Dモデルをグリグリ動かし、タンパク質の二次構造を確認したということを書いてレポートにした。これが自分の限界。

GitHub - sokrypton/ColabFold: Making Protein folding accessible to all!

それから2時間半ほどTAの作業。今週は発表資料が共有されていたので、読んでコメントを付けた。かなり久しぶりで勝手がわからなくなっていた。

寝るまでラノベを読んでいた。1冊読了。「双星の天剣使い」。

非常に面白かった。「公女殿下の家庭教師」や「辺境都市の育成者」の著者の新シリーズ。中華風の舞台でこれまでと似たような設定の主人公・ヒロインを描いており、他の2シリーズが好きならこれも確実に好きだろう。自分はそうだった。1巻から目立った功績を挙げているのが嬉しい。戦場のシーンが多く、名乗りを上げたりと何かと大きな声を出していたので、印象はこれまでと結構違う気がする。

この巻は「公女殿下の家庭教師」の新刊と同時刊行だった。これまでにもちょくちょくそういうことをやっていて、どのシリーズもネット小説発とは言えすごい速筆だと感じる。

別のラノベを開いてしばらく読んだ後、午前10時過ぎ就寝。

11/24(木)

午後3時45分起床。急いで準備して大学に向かった。生協でラノベを買いつつ教室に到着し、午後4時過ぎからTA。

今日の発表者が担当する部分はちょっと長めで内容も盛りだくさん。何を話すかが上手に絞り込まれていたし、実際の発表も全く問題なかったのに、計算が苦しくて結局時間がかかってしまった。多面体の双対をいろいろ紹介されても、イメージがうまくできないのでピンとこないし、詳しく説明していると時間がさらに足りなくなってしまう。辛いところ。

ちょっとオーバーして終了。これで学生の発表は一巡したが、PDF資料はあと一人分くらい残っている。一度は最初の人が発表することになったものの、中間テストなどで忙しそうだったので、自分と先生で少しずつ担当することにした。

講義後しばらく話して午後6時過ぎ解散。学食で食事して帰宅し、その後ずっとラノベを読んでいた。1冊読了。「一生働きたくない俺が、クラスメイトの大人気アイドルに懐かれたら」3巻。

非常に面白かった。前半は2巻の続きで、ヒロインの一人とさらに仲を深めていた。アイドル3人組のうち今のところ二人までが主人公に明確な好意を寄せていて、このまま3人目も攻略してしまうのかと思っていたら、後半は主人公の友人の恋愛に関する話だった。友人には好きな人がいるのにその人は主人公のことを狙っているという、かなり辛い人間関係。この解決のあたりはかなり好みだった。新しい設定が出てきて非常に気になる終わり方をしているので、次巻が楽しみ。

別のラノベを読んでいるうちに寝落ちした。午前2時半頃のはず。

11/25(金)

午後1時半起床。

月曜日に言っていたような出力のチェックを少しだけ行ったところで午後2時、1on1の時間になった。手持ちのデータを全部見たわけですらないが、とりあえずいくつか見た感じは正しく動いていそう。今の実装ではどうしようもないところは相変わらず間違っているものの、これは逆に思った通りの挙動をしているとも見ることができる。

最近やってきたコードの書き換えのタスクについては、これでひとまず完了ということになった。既存のコードと対応を取る部分が少し残っているようだが、そのコードのこともよく知らない自分にタスクとして振られることはなかった。

次のタスクの準備としてAmazon EC2のレクチャーをしてもらった。以前にも別の方に教わったのに、会社のお金でサービスを使うのが怖すぎて距離を置いていたため、残念ながらほとんど覚えていなかった。メモは残っていたので、それと今のタスク向けの設定をすり合わせし、午後4時くらいに終了。

シャワーを浴びて大学へ。生協でラノベを買いつつサークルの教室に向かい、バチャに参加した。

https://kenkoooo.com/atcoder/#/contest/show/e3f1b0a4-fb53-4a5f-97e8-82b623340a21

4問目と5問目でペナを出しつつ全完。6問目は2か月ほど前のサークルバチャでも出たもので完全に覚えていた。7問目は $O(|s|(\log|s|)^2)$ で解いた。コンテスト当時もそうだったらしい。1secくらいで通るのでかなり余裕がある。

感想戦を終えて閉店間際の学食で食事し、帰宅。7問目の解説を見ながら $O(|s|\log|s|)$ 解法でupsolveした。先頭のBの扱いがかなり面倒だが、どの方針でもちゃんと整理するとそれなりに綺麗な形で処理できる。

Submission #36773476 - AtCoder Grand Contest 050 (Good Bye rng_58 Day 1)

午後9時20分からyukicoder 369に出た。今日は3時間コンテストらしい。

yukicoder contest 369 - yukicoder

Aはよい。Bはコンテスト開始後しばらくWIPの表示が残っていて不安になるも、解くに当たっては問題なかった。dp。最初はconとそれ以外の部分に分けたりすることを考えていたがその必要はない。

Cは間違った実験をしてしまい、苦労して実装したのが合わず1時間近く格闘していた。 $X$ 個取り除く操作を2連続で行ってしまっていた。改めて実験しなおし、周期が $X+3$ であることをエスパーするとかなり簡単な形になった。

かなり出遅れたので以降はsolved数順に取り組んだ。Eは $\cup$ について閉じているだけでなく、 $\cap$ 、 $\bigtriangleup$ についても閉じているらしい。このうち $\bigtriangleup$ だけに注目して基底を数えてしまい2WA。1要素ずつ、常にその要素と集合に属するかそうでないかの状態が同じ要素を探して、そうやって互いに区別できない要素のグループの個数を考えればよい。

Hは簡単。 $1\le i\le N$ かつ $\max(P_1,P_2,\dots,P_i)=P_i$ となる $i$ を三つ選ぶ方法に対してそれを達成する $P$ を数え上げ、足し合わせればよい。これも積の和典型。三つ選んだインデックス同士の一致・不一致によって3パターンほど考えられるが、どれも $\sum_i\frac 1 i$ 、 $\sum_i\frac 1{i^2}$ 、 $\sum_i\frac 1{i^3}$ を適当に掛けたり引いたりすると求まる。

Dは奇数を開き括弧、偶数を閉じ括弧に読み替える。 $(L,R)$ についての条件は、その区間だけ見たとき正しい括弧列になると言っている。また全体についてもほぼ同様。 $N$ が奇数のとき閉じ括弧が一つ足りないが、この場合は勝手に $N$ をインクリメントしても問題ない。右端には必ず閉じ括弧が来るので、あとからそれを取り除けばよい。

以上により、正しい括弧列をいくつか重ね合わせた列を作る問題になった。重なった部分だけ見てもまた正しい括弧列になるため、逆に区間を分割して互いに素にして、それぞれを正しい括弧列にする方法を数え上げればよい。この分割は $L$ と $R$ をイベントソートして頑張ったが、 $Q$ が小さいことを利用してbitで包含の状態を管理し、同じものをまとめるという方法が使えたらしい。

残り時間はGを考えて解けず。そもそも $\binom{28}{8}$ がかなり大きな数だと思い込んでいた。

直後からCF #836 div.2。

Dashboard - Codeforces Round #836 (Div. 2) - Codeforces

Aは $s+{\rm rev}(s)$ 。Bは $n$ が奇数なら全て $1$ 、偶数なら $(1,3,2,2,\dots)$ のようにするとよい。

Cは $x\mid p_x$ 、 $p_x\mid p_{p_x}$ などを考えると $x\mid n$ が条件。辞書順最小という条件を忘れて1WA。 $x\mid y$ かつ $y\mid n$ かつ $x\lt y$ なる最小の $y$ を探し、 $p_x=y$ 、 $x\leftarrow y$ として $x=n$ になるまで繰り返せばよい。

Dは $L=\min_i a_i$ 、 $R=\max_i a_i$ とすると、 $L(n-1)+(n-1)(n-2)/2+R\le\sum_i a_i\le R(n-1)-(n-1)(n-2)/2+L$ 。逆にこの区間内ならどんな整数でも作れるので、その中に $(R-L)^2$ があればよい。 $L=3n$ 、 $R=5n$ とするとうまくいった。

Eは今日のサークルバチャの2問目を感想戦で丁寧に扱ったのが効いた。盤面の自由度は実は横一行＋縦一列ぶんしかない。まず盤面全体が $-1$ であるケースを先に取り除いておく。そうでない場合、 $-1$ でない数の座標を一つ選んで $(s_x,s_y)$ とする。それ以外に $-1$ でない数の座標を探し、 $(i,j)$ とすると、 $(s_x,s_y)$ と $(i,j)$ の和が $(s_x,j)$ と $(i,s_y)$ の和に等しくなればよいことがわかる。

よって、すでに置かれた数に関する条件が行 $s_x$ と列 $s_y$ の上のマスに関する条件に書き直された。これが矛盾していれば答えは0だし、矛盾していなければ、どの数も確定していない連結成分の個数だけ自由度があるとわかる。

Fは大変。0を1に変えるときは、そこから右に見て行って区間に含まれていない0を探し、間にある区間もまとめて一緒の区間にすればよい。いくつかの区間を削除して一つの区間を挿入することで達成され、区間の削除の手数を挿入時に押し付けることにすれば、2手で行える。

1を0に変えるときは、それがもともと入っていた区間を三つ以下の区間に分裂させればよい。1を $+1$ 、0を $-1$ と見て累積和を取ったとき、1が0に変わると区間の左端 $L$ に対して区間の右端が $L-2$ となる。このとき隣り合う2項が $L,L-1$ 、 $L-1,L-2$ となっている箇所が存在し、そこで区切ることができる。左からの累積minを持つセグ木上で二分探索して探した。

区間を一つ削除して三つの区間を挿入することになり、先ほどと同様に考えれば6手かかってしまう。しかしこの1は以前に0から変えたもので、0→1には2手しかかかっていないのだから、今6手使っても操作回数が十分少ないとわかる。

全完3位。

朝まで日記を書いた後、少しラノベを読んで午前9時就寝。

11/26(土)

午後3時半ごろ冷凍弁当を受け取った。

午後7時半起床。本当は午後5時頃起きてDMOJのコンテストに参加する予定だったが、眠気に負けた。今週末はコンテスト予定が詰まっていて、無理やり起きると支障が出るだろうという考えもあった。

しばらく日記を書き、午後9時からABC279。

TOYOTA SYSTEMS Programming Contest 2022(AtCoder Beginner Contest 279) - AtCoder

Aはvとwの文字数を数える。Perlで書いた。BはVim。以降はC++を使った。Cは行列を入れ替えてソート。

Dは $1/\sqrt x$ のグラフを見て三分探索する問題だと確信を得たが、値の範囲がよくわからずちょっと怖かったので、微分して求めた最適値 $\left(\frac A{2B}\right)^{2/3}-1$ の周りの整数を多めに調べた。

Eはあみだくじの横棒を1本削除する問題。削除しない状態であみだくじの結果を求め、削除する横棒で入れ替えられた2数を最後の結果において改めて入れ替えればよい。

Fはマージテクで、ボールに対し入っている箱、箱に対しついているラベル、ラベルに対しついている箱の3種類の値を管理することでうまくできる。CFの5hでたまに見るがいつも苦労しながら書くことになるので、ライブラリにしておくと便利なのかもしれない。

Gはマスを左から順に見てdp。今見ているマスを $i$ 、そのマスと異なる色が塗られた最も近いマスの番号 $j$ を状態に持つと、とりあえず $O(N^2)$ になる。遷移はよく見ると $(i,j)\rightarrow(i+1,j),(i+1,i)$ しかないため、セグ木のインデックス $j$ に対して $(i,j)$ の値を持てば、区間和取得と1点更新だけで書けてしまう。こういうdpが実家dpと呼ばれると認識している。実装はBITを使った。

Exは解けず。包除原理を使うと $I\subseteq\{1\dots N\}$ に対し $M\leftarrow M-\sum I$ として $(-1)^{|I|}\prod_k S_k$ を求める問題になる。これは積の和典型で2項係数になる。とりあえず $O( (M-N)^2)$ にはなったので、 $M$ を変化させたときの答えが最初 $200003$ 項を用いる多項式補完で出ないかと思い、結構な時間をかけて計算させてみたが、全然合わない。絶望してコンテスト終了。

Gまでの7完最速で9位。上に日本人学生が少なかったので賞金額が思ったより高そう。

午後11時からCGR24に出た。

Dashboard - Codeforces Global Round 24 - Codeforces

Aは $(l,r)=(1,n)$ 固定。なぜなら縮めても得しないから。Bは作れる最小の値が $\gcd(a_1,\dots,a_n)$ で、 $a_n$ 以下のその倍数の数が答え。Cは全部同じ値のとき $\lfloor n/2\rfloor$ 。そうでないとき、どんな値についてもそれ未満の値とそれ以上の値の間にありったけ辺を張れる。これが最適だと信じて出すと通った。

Dは最後に抜く杭を杭1に固定し、最後まで残っていた杭のうち最も杭1に近い杭2本を決め、その間で杭1を含まないほうの弧の上について杭をいくつ抜くか決めると、あとは階乗で場合の数が求まる。前半は $O(n^2)$ 、後半は2本の杭がどれくらい離れているかでまとめられるのでこれも $O(n^2)$ 。

Eは最大でどの値まで色を塗れるか考える。ペア $(a,b)$ を使うと、これまで $m$ だったところが $\max(a,\min(m,a)+b)$ と変化する。この値は $m\le a-b$ なら $a$ 、 $a-b\lt m\le a$ なら $m+b$ 、 $a\lt m$ なら $a+b$ となる。よって $k\le a_1$ なら常に可能、 $k\gt a_1+b_1$ ならどうやっても不可能。それ以外の場合は、残りの $(a,b)$ で同様に $k-b_1$ を作る問題になる。

最初に使うペアを決めたとき、残りの要素は $a+b$ の降順に並べ、 $k\le a+b$ なら $k\leftarrow k-b$ とするのを繰り返すのが最適。どのペアまで $-b$ に寄与できるかはセグ木上の二分探索で取得できる。セグ木の取得部分でミスしているのに気づかず4ペナ。周りもペナが多いから何か罠があるんだろうと思って、実装にミスがあるのを疑っていなかった。

Fは $(f(u,u)+f(v,v)-2f(u,v))/n$ が $u$ と $v$ を結ぶパスの長さとなる。これをかき集めて最小全域木を作れば、制約からそれが答えになっているはず。出したら通った。

G1はこんなの無理だろと思っていたが頑張ったら解けた。 $n$ が奇数の場合、2で割って切り捨てると1以外の数には必ず同じ値となるペアが存在する。このことを用いると1が存在する位置を二分探索できる。

具体的に説明する。 $L=Q(1,m,2)$ 、 $R=Q(m+1,n,2)$ としたとき、二つの区間に分かれたペアが $k=L+R-(n+1)/2$ 個あり、残りのペアは左の区間と右の区間それぞれの中で完結しているとわかる。つまり左の残り $m-k$ 個と右の残り $n-m-k$ 個のうちどちらか奇数のほうに1が存在すると確定する。1回の判定に2回クエリを投げるので、合計はちょうど20回。

$n$ が偶数の場合は $n$ にもペアがないので少し壊れる。先に $k=n$ で二分探索することで $n$ の位置を確定させ、それを見て補正することで上と同様のことができるようになった。追加のクエリが10回必要で、G1は解ける。G2以降は手も足も出ず。

7完31位で2631→2732(+101)。これまでの傷が深すぎて全く癒えない。

ABCのコードゴルフについて。Aはsedで文字列を置き換えてからwc -Lするとよい。

BはやはりVim。Yes・Noの出力を分岐する部分で1B縮められた。こういう問題は過去にいくつもあって、それらはほとんど今縮められたものと同じ方法で分岐している。コンテスト中に自力で再現できなかったとしても過去の提出を参照すれば自分で削れた1Bのはず。書きながら「もっと短い方法があったような」という違和感を覚えてすらいたのに何もせず、結果最短コードを取れなかったというのは非常に悔しい。

Cは各 $i$ に対し $S_i$ と $T_i$ で含まれる#の文字数が等しいか判定するという嘘解法が通っていた。TLで見つけ半信半疑で試したら確かに通ったので、これを縮めた。行と列を入れ替える必要がない今、#の文字数を数えるのはPerlが短い。前半と後半が等しいか見るのはちょっと苦労したが、最終的には正規表現で同じ列が2回繰り返されているかチェックした。長さが最大 $8\times 10^5$ なので結構時間がかかっている。

Dは $\left\lfloor\left(\frac A{2B}\right)^{2/3}\right\rfloor$ と決め打ちするコードが通っていたので、AWKで書いておいた。 $\pm 1$ に関する正当性はよくわからないが、この値が大きなときは $B$ が $A$ に比べて小さいので、誤差に吸収されてしまうのではないかと考えている。

Gは、上で説明した実家dpについて区間和の代わりに累積和を取りながら行うことで線形時間になる。これをRubyで実装し、さらにVimで書いたものが最短になっている。他は手付かず。

最近エアコンの水音が気になる。部屋に外の空気をうまく取り込めていないのが問題だと確認できたので、目につく換気扇のフィルターを掃除していた。これは昨年12月にもやっていたことで、生じた結果も同じ。つまり、吸気はそのままに排気だけが正常化されて、さらに水音がひどくなってしまった。

キッチンの換気扇をつけると、エアコンからポコポコと水音がし出した。
週記（2021/12/06-2021/12/12） - kotatsugameの日記

吸気口っぽいところをしばらく調べてみた。内側のフィルターには全然目詰まりがない。むしろ1年くらい放置したのに綺麗すぎることに違和感を覚え、さてはと思って外側を見に行くと、そこにもフィルターがあるのに気付いた。こちらが完璧に詰まっていて、空気が入ってこないのも納得。ここの掃除はネジを回してカバーを取る必要があるので、日が昇らないとできない。今日のところは諦め、窓を開けて眠ることにした。

午前6時頃に布団に入り、1時間ほどハーメルンを読んで就寝。

11/27(日)

午前11時起床。ICPC模擬地区予選のため大学に向かう。エアコンの水音についてはとりあえず放置した。このまましばらく置いておけば前回は収まったので、今回もそうなるかもという期待がある。

コンテスト20分くらい前に大学に到着し、コンビニで買ったパンを食べ、正午からコンテスト開始。このコンテストについては参加記を書いた。

kotatsugame.hatenablog.com

終了後、横浜で宿泊するホテルについて相談。同じ大学から出るもう一つのチームはもうホテルを取ったらしいので、我々もそこに合わせることにした。その後解散。

帰宅すると狙い通り水音はなくなっていたが、吸気口の外側のフィルターは気になるので掃除したい。日が落ちてしまったので、スマホのライト機能を使って強行した。何とかカバーを外し、埃を取る。ぎっしり詰まっていたのがボロボロ落ちてかなり爽快。しかしその後カバーを戻すのに非常に苦労した。

食事したりシャワーを浴びたりした後、午後7時半からCFで海外ICPC Regionalのミラーに出た。ソロで5h、コピペはありにした。

Dashboard - 2022-2023 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Preferably Teams) - Codeforces

Aから開いたら解けてしまったので最初の25分を投入した。結果簡単枠のペナがひどいことに。bitの包含関係で辺を張ると、まったく同じ要素以外の部分はDAGになっていて、これの最小パス被覆を求めればよい。最近TTPCで見たのでこの辺りの考察はスッと出てきた。

H - Colorful Graph

あとはほぼsolved数順に解いた。Bはよい。Eは $a\gt b$ かそうでないかで場合分け。Mは $n$ の約数を全探索した。実際には $n$ でない中で最大の約数を見ればよい。Nは結果の桁数が決まっているので先頭から貪欲に。

Kは小さいケースを手で試して、右上から左下に向かう対角線上のマスを一つ抜けば残り全部通れるとエスパーした。しばらく縦横のサイズが同じじゃないと思い込んで苦しんでいた。

Dは $a$ を並べて隣接する2項の和が $m$ 以下になる位置の数を最大化する問題になる。和が $m$ より大になる2項があれば、そのうち大きな値を先頭に置きなおしても損しない。よって大きいほうからいくつかを先頭に並べてそこは諦め、残りを最適に配置してすべて $m$ 以下にできるよう頑張る。

残っている中で最大のものと最小のものを交互に並べるのが最適。ソート後のインデックスとペアにできる最大の値のインデックスを足したものを見ることで判定が高速に行えるので、諦める要素数が全探索できる。

Hは後ろから作っていくと貪欲でよい。 $i=1\dots n$ について $i$ 以外を並べる問題を解き、破綻した瞬間が答え。

Lは優先度の高い仕事から順にどのパートがどの日に終わるか確定させていく。曜日ごとに休日を、曜日と人ごとに働いた日をそれぞれ区間で管理する。人ごとに空いていない日の区間を管理しているのとほぼ同じことで、休日のぶんを全員に対しコピーすることができないので、こうやって集合を二つ見て頑張ることになっている。

Fは面白かった。契約を2次元平面の点 $(x,c)$ だと思うと、 $a$ を適当に選ぶことで選んだ契約からなる凸包に含まれる点がすべて作れる。よって客一人に対する売上の期待値が上側凸包を積分したものになる。契約を $x$ の昇順に並べ、上側凸包に含まれる線分を決め打ちながら間の積分値を足していくdpで解けた。

Gも面白い。あまり多くの文字数を一度に確定させようとすると場合分けが辛かったので、2文字ずつ確定させられないか考えることにした。先頭2文字と未確定の文字のうち前から2文字のパターン、先頭が0なので8通りについて、 $p$ や $q$ を聞くとどうなるか考えてみた。結果どのパターンでも $p$ と $q$ のどちらかなら2文字確定することが分かった。

例えば先頭が00、未確定の部分が10で、その未確定の部分を2文字含むように $p$ を聞くと、1または3以上が返ってくる。3以上ならよい。1だった場合まず?0が確定して、もしこれが00だった場合 $p\ge 2$ となっていないとおかしいため、10だと確定する。こういうものがどのパターンでもうまく存在してくれるようだ。

どちらを聞くべきかはうまくばらけているので、そこを乱択することで期待値的に $1/2\times 2+1/2\times 1=3/2$ 手で2文字確定させることができる。念のため手元でチェッカーを書き確かめてから出した。無事一発AC。

Cはまずカードの番号を忘れてよい。これまでスートごとに $a,b,c,d$ 枚ずつ出ているとしたとき、確率は $\left.\frac{(a+b+c+d)!}{a!b!c!d!}\times\frac{(4n-a-b-c-d)!}{(n-a)!(n-b)!(n-c)!(n-d)!}\middle/\frac{(4n)!}{n!n!n!n!}\right.=\left.\binom{n}{a}\binom{n}{b}\binom{n}{c}\binom{n}{d}\middle/\binom{4n}{a+b+c+d}\right.$ と書ける。

さらにそのもとで正答する確率が $\frac{n-\min(a,b,c,d)}{4n-a-b-c-d}$ 。 $0\le a+b+c+d\le\min(k,4n-1)$ に対してこれを求める必要がある。 $a+b+c+d=k$ の場合はさらにどの位置でそれが起こるかも考える必要があるが、まあどうとでもなる。

$a+b+c+d$ と $\min(a,b,c,d)$ を持ってdpするととりあえず解ける。正確にはこれまで決めた分の和と $\min$ 。この時点で $O(n^3)$ になっていて、定数倍は重いがそれ以上にTL 15secと非常に緩いため十分通る。実際後から試したら9secくらいだった。コンテスト中は試しもせず通らないと思い込み、累積和や畳み込みで無理やり $O(n^2\log n)$ に落とした。

残り30分でIに進んだ。少し余裕を持たせて必要な $x$ 座標を集め、その間を飛ばしたマス目の上でdijkstraすれば解けるはず。実装は終わったもののWAが取れず、そのままコンテスト終了。12完で14位だった。

SSRSさんにコードを読んでもらいIのupsolveをした。飛車角のような動きをする際、途中に別の駒がないかチェックしていなかったらしい。

文学部の集中講義の日程が出ていた。以前言及したもの。12/19-22らしく、思ったより近い。教室の情報も出ていたが文学部のキャンパスに不案内でわからない。講義開始までに一回偵察に行きたいと考えている。

他研究科の集中講義で面白そうなものがあった。ぜひ受講したいが、調べても日程が出てこない。
週記（2022/09/26-2022/10/02） - kotatsugameの日記

午前3時過ぎからはICPC模擬地区予選の参加記を書いていた。朝方完成し、公開。その後すぐ就寝した。午前8時だった。

2022-11-28

ICPC模擬地区予選 2022 参加記

2022/11/27に開催された模擬地区予選にチームAobayama_dropoutで参加しました。メンバーはha15さん・ホスフィンさん・僕です。

今年はどうやら横浜大会がオンサイトで行われそうだということで、競技ルールもコロナ禍前と同様のものが推奨されていました。

2022/Practice/模擬地区予選/案内 - ICPC OB/OG の会

よって我々も国内予選の時に使った大学の演習室に集まり、コピペなし・検索なし・同時コーディングなしで参加しました。

ただしPCが各自1台ずつあったのと、部屋の壁がホワイトボードで覆われていたのは本番と大きく異なる点です。

問題文：2022/Practice/模擬地区予選/問題文とデータセット - ICPC OB/OG の会

戦略

チームメイト二人が簡単とされているA・Bを通している間に自分が残りを読むというのはこれまで通りですが、そこで解けた問題があったとしてもすぐコーディングに入らず、他の人に任せてそのまま別の問題を読み続けました。これを徹底したという点で、これまでとは大きく異なる立ち回りでした。

読んだ問題の概要と制約、さらに解法がわかっているものはそれもホワイトボードに書きました。これはオンラインの頃HackMDでやっていたことの再現です。本番では、少し煩雑ですが紙を1問につき1枚用意するなどして対応することになるでしょう。

自分が読んで解法を考えた時間と、それが実装され通った時間が少し離れています。以下は時系列をできるだけ保存した状態で書きましたが、コンテスト中の行動を逐一覚えているわけではないため、一部前後する出来事があるかもしれません。

A問題のACまで

Cから開いて読み始めました。

Cはグリッドグラフ上ですべての辺を通る閉路ということで、ハミルトンだったかオイラーだったか覚えておらず検索しそうになってギリギリで思い留まりました。問題自体はすぐ解けるようには見えなかったので次に進みました。

Dは問題文がシンプルでとっつきやすそうです。実際、 $O(N^2)$ 状態のdpの遷移をデータ構造で頑張ることで、すぐ $O(N^2\log N)$ になりました。制約が $N\le 5000$ なのでちょっと怪しいですが、通るだろうと判断し、解けたことにしました。

E、Fは読んだだけです。

このあたりでホスフィンさんのAが2WAくらいしており、自分も読んでみたのですが、二人して信号が切り替わるタイミングの把握に失敗し、もう一つWAを重ねてしまいました。

改めて読みなおし、都合4度目の提出でようやく通りました。ヘルプに入ったならちゃんと腰を据えて読まなければなりませんでした。

B問題のACまで

haさんが読んでいたBはもう書けるそうなので実装してもらい、自分はまた問題を読み続けました。ホスフィンさんにもLから逆順に読んでもらいました。

Gも読んだだけでした。

Hはまたとっつきやすそうと判断しました。ちょっと考えてみると、SCCした後のDAGが一直線になっているため、そこを遡るようにdpすることでコストが求まりそうです。これも解けたと判断し、チェックの意味を込めてホスフィンさんに解法の説明をしました。

Iは読んだだけです。このあたりでBが通ったはずです。

D問題のACまで

今のところ解けているのがDとHです。Dは適当なデータ構造を、HはSCCを必要とするので、どちらにしても写経の必要がありました。Dのほうが素早く書けるだろうということだけ伝え、分担は二人に任せて自分はさらに問題を読んでいました。

Jは答えを二分探索すると、 $N$ 個の円で領域が覆われないか判定する問題になります。2円の交点や境界と円の交点であってほかの円に含まれないものが存在するかチェックすれば解けそうですが、計算量が $O(N^3)$ になってしまいました。

Kは構文解析で、どこかで見たような圧縮が施された文字列に関する問題です。

Lはホスフィンさんが書いた概要で把握していました。これで自分は全問題の概要を知ったことになります。

Kに見込みがありそうだと思ってしばらく考えてみたのですが、圧縮部分をスキップしようとしてもうまくいかないことに気づき、諦めました。

この間にDをホスフィンさんが担当することに決まって、データ構造としてBITの写経がされていました。区間MAXをする必要があるので普通ならセグ木を持ち出すところですが、区間の左端が常に全体の左端と一致するためBITでも書けます。定数倍的にも実装量的にもセグ木を持ち出す理由はないと説明し、そうしてもらいました。

さらに解法のコーディングも終わりかけていたので、少し見てインデックスなどに口出ししました。順調にサンプルが合って提出すると通りました。

H問題のACまで

haさんがSCCの写経を始めたのを後目に、I問題を考えてみました。情報を重み $x$ の辺 $a\rightarrow b$ と重み $-x$ の辺 $b\rightarrow a$ のことだと思います。すると情報の矛盾は辺の重みの和が0にならない閉路に対応します。

情報をちょうど一つ削除すると矛盾が解消されるそうですから、そのような情報は矛盾する閉路すべてに乗っています。さらに、矛盾しない閉路に乗る辺を一つ削除しても閉路の残りの部分が削除した情報と同じ意味を持つため、そのような閉路に乗っていないということも言えます。

このあたりで解法に見覚えがあることに気づきました。後から調べるとMulti-Universities Campの9回目で出題されていたようです。自分が担当した問題だったので記憶に残っていたのでしょう。

Cは重み付きの単純グラフに関する問題。ただしこの重みは、辺eeについて順方向に通れば+Pe+Pe、逆方向に通れば−Pe−Peとなる。
週記（2022/08/15-2022/08/21） - kotatsugameの日記

https://ac.nowcoder.com/acm/contest/33194/C

dfs木の後退辺で作られる閉路だけ考えたり、木上のimos法を使ったりすることで検出できることを覚えていました。ちょうど一つだけが候補になることを確認し、答えとすればよいです。

解けましたが、当時合わせるのに結構苦労した覚えがあったので、こればかりは自分で実装することにしました。

次は順位表を見て、C問題を改めて考えてみました。冷静になると全頂点の次数が偶数になるように辺を足せばよいです。最初の時点で次数が奇数の点は、グリッドの上下左右の辺上にあるもののみです。当然偶数個なので、それらの間のパスを考え、最小重み完全マッチングを解けばコストの最小値が求まります。

ただ、一般に解くのが難しいどころかライブラリを持っておらず不可能なので、どうにかして二部マッチングだと思う必要があります。ホスフィンさんが左右の辺と上下の辺で分ける方法を提案し、一度は解けた気になりましたが、後から間違っていることに気づきました。

このあたりでHが一旦書きあがり、バグった状態のコードが共有されました。

サイズ1の強連結成分の間に張られた辺をひっくり返さないような場合分けが入っていました。ひっくり返してしまうと元の向きに移動できないからとのことです。聞いた瞬間は確かになと思ったものの、よく考えるとその周りが残っていれば変わらず移動可能のはず。なのでその場合分けを抜いてもらいました。

ほかにもいくつか修正してもらい、サンプルが合ったところで提出。無事通りました。

I問題のACまで

I問題の実装に入りました。一度書いたことがあるコードなのですぐ書きあがり、サンプルも即座に合ってそのまま通りました。

C問題のACまで

上で紹介した二部グラフの分け方は、例えば辺を1本足して隣り合う頂点の次数を同時に変えるケースで壊れます。そこでグリッドの辺上の点を一周ぐるっと列挙して、source側とsink側に交互に振り分ければよいのではないかと思いつきました。

いくつかのケースを試してみてよさそうだったので、これで実装に入ってもらうことにしました。ホスフィンさんが担当することになりました。最小費用流の写経が必要でかなり大変です。

その間に考察を進めます。Lが解かれていたので考えました。まず、頂点の対応が1組わかっていれば木dpで解けそうです。

肝心の対応ですが、根を取り換えながら根付き木の同型判定を行うことでvalidなものを数えられます。先ほどの木dpも部分木同士の同型判定が必要なので、その結果を再利用できそうでちょっと嬉しくなりました。

根付き木の同型判定はハッシュを使うはずでしたが、どうするか覚えていません。仕方なく括弧列を使う方法をロリハで書くことを提案しました。頑張れば全方位木dpにもできるはずなので、根の取り換えが行えます。以上で理論的には解けました。

Cの写経が難航しているようなので、見て口出ししたり部屋をうろうろしたりしていました。この時点では、残り2時間以上あるのでC・Lを通してもう一問いけるかもなあと思っていました。

Eを考えてみることにしました。2-SATからSCCに帰着してもあまり嬉しくはなさそうなので、そのまま取り扱ってみます。clauseに関する条件から直前二つの変数の状態を持てばdpできます。

ここで、これまでいくつの変数を真にしたかを多項式で持ってみることにしました。するとdpの遷移が多項式の行列になります。特にどの多項式も高々1次なので、セグ木のようにマージしていけば $O(N(\log N)^2)$ です。

実際はここに行列積ぶんの定数倍が掛かりますが、TL 8secなのでこれで解けているものと考えました。実は全然ダメだったということを後から説明します。

Cは最小費用流の写経が終わり、いよいよ本題のアルゴリズムに入ったようでした。sourceとsinkに分ける部分で少し手が止まったのを見て、我慢できず実装を奪い取り、そのまま書き終えました。

しばらくデバッグし、サンプルが合ったところで提出。しかしTLEでした。間違いを見つけるのは任せて別の問題の実装に入るか悩みましたが、そのままPCにかじりついて自分でデバッグすることにしました。

dijkstraのpriority_queueが逆になっていたのと一部オーバーフローしていたのを直すと無事通りましたが、さらにWAを一つ出してしまいました。

コンテスト終了まで

残り1時間ちょっとあって、解けたと思われる問題がEとLです。Eのほうがすぐ終わりそうに見えたし、AC数が少なくて見栄えするだろうと思って取り組みました。

ところで、先ほどの解法はdpの遷移を要素が多項式の行列で表すというものでした。dpは4状態あるので行列のサイズは $4\times 4$ であるべきです。

ここを $2\times 2$ だと思い込んでいて間に合うと主張したのですが、行列積ぶんの定数倍がさらに8倍になるとかなり話が変わってきます。このことにNTTの写経を含めた実装を終えてから気づいたため、大変なことになってしまいました。

積の順番を勘違いしたりしつつ残り20分くらいで何とかサンプルが合いました。しかし提出するとTLE。 $O(N(\log N)^2)$ に定数倍64がつくとさすがに無理らしいです。手元で18sec程度だったので高速なNTTを使えば通る可能性はありそうですが、書き直す時間がありません。

最後の時間は、clauseを書き換えてインデックスの差を1以下にできないか考えていました。

振り返り

6完14位です。最後にEではなくLに取り組んでいればもしかしたら通っていたのかもしれませんが、実際に書いてはいないので何とも言えません。

自分がEと格闘している間にhaさんがKの考察をされていたらしく、ロリハでどこまで一致するか探索する方法を教えてもらいました。実装は相変わらず困難なものの、解法としてはかなりよさそうでした。

Dは $\log$ を付けてTLEしてしまい定数倍高速化に苦労した人をTLで観測しました。BITを採用したのはかなり良い判断だったようです。

今日はDでBIT、HでSCC、Cで最小費用流を写経してもらいましたが、解説スライドを読むとどの問題もそれらを使わない解法があるようでした。解けて満足するのではなく、フルスクラッチしやすい方針も考えてみるべきでしょう。

この辺りはICPCのオンライン開催が続いて全く意識しなくなってしまった部分です。C問題の実装が自分が思っていたより難航しているのに焦れてしまったのは反省すべき点でした。

今日はホスフィンさんが3問、haさんが2問、僕が1問実装しました。いつも一人だけ実装してばかりなので、これを他の人に割り振れたのは良かったのではないかと思います。

自分が考察を止めて実装に参加するべきタイミングがいつなのかはわかりませんでした。US配列を使い慣れておらず、他の二人とそれほど実装速度に差があるとも思えないため、今日くらい遅くてもいいのかもしれません。とりあえず写経は~~押し付けて~~任せてしまいたい気持ちがあります。

何にせよ、十中八九最後のICPCなので、悔いの残らない5時間を過ごしたいものです。

2022-11-21

週記（2022/11/14-2022/11/20）

工事中

11/14(月)

午後4時過ぎに起床。起きたら生協に行こうと思っていたが、そんな余裕のある時間には起きられなかった。

隙間時間に年末調整を終わらせた。先週金曜日、もとい土曜日朝方に送った質問にはまだ返信が来ていなかったので、待つのを諦めてそれっぽく書いておいた。そもそも自分の判断が合っているか確認する程度だったので、何かミスが発生するとは思っていない。発生しても死にはしない。

年末調整にチャレンジした。期限は11/14つまり来週の月曜日である。少し書類作成が進んだところで、インターンの給料の扱いに関して疑問が生じた。担当の方に質問を送ったが返信は月曜日になるだろう。
週記（2022/11/07-2022/11/13） - kotatsugameの日記

午後4時半からインターン先定例会。先週火曜日にちょっとコーディングしたが思ったより難しかったのであまり進んでいません、と報告。進行スケジュールもちょっと後ろ倒しになった。タスクの中にも終わらせないと使えないものとそうでもないものが混じっていると認識していて、ちゃんと前者を優先的に片付けるべきかもしれない。

勉強会はアルゴリズムパズルの話で、不変量を見つけて解く問題がいくつか紹介された。この発表は僕がインターンとして入社した最初の勉強会の続編みたいなもの。そのときと同じ問題が二つほどまた扱われたのでびっくりしたが、よく考えてみれば前回の発表以降に入社された方も多いのか。当時は順に指名されて意見を述べるという形式だったのに対し、今回は指名を待たず活発に議論が行われて、非常に活気があった。

再登場となった問題の一つについて、ほぼ同じものが発表から一月後くらいのARCで出題されたことにも言及された。懐かしい。

今日はパズル系の発表で、ミーティングに参加している人々と共に頭を働かせた。
週記（2021/09/06-2021/09/12） - kotatsugameの日記

Bはつい最近インターン先の勉強会でほぼ同じ問題が扱われており、難なく解けた。
週記（2021/10/11-2021/10/17） - kotatsugameの日記

勉強会を終えた後、午後8時前に完成させた先週分の週記を投稿した。2時間ほどTLを眺めたりYouTubeを眺めたりして時間をドブに捨て、そこからセミナーの準備。

途中机に突っ伏して寝てしまったりもしつつ、午前3時半に終了した。証明が長くて大変と思っていたが図が多いだけで実際はそうでもなく、終わってみれば準備したメモ書きは普段とほぼ同じ量になった。ただ証明の手順をどこから思いついたのかがかなり謎。気持ちがうまく汲み取れなくて感覚的な説明が思いつかなかった。その分丁寧に論理を追う必要があって、発表には少し時間がかかりそう。

シャワーを浴びて1時間ほど日記を書き、午前5時過ぎ就寝。

11/15(火)

午前9時半起床。準備して出発。

今日はかなり空腹で、多少遅刻してでも朝ごはんを確保したい。山の上の駐輪場に到着した時点で午前10時を回っていたため山の上の購買が開店しており、無事購入できた。実はこの直前に川内キャンパスの購買にも寄っていたのだが、そちらはギリギリ開店前だった。時間ロス。

ちょっと遅れてセミナーの教室に到着。普段は同級生の発表を先に行うところ、今日は発表する内容がないらしくすぐ自分の番になった。前回木曜日からそれほど日を置いていないのでそういうこともあるかという感じ。確かに自分もなかなか慌ただしいセミナー準備だった。

今日は命題を三つ示す。最後のものの証明に入り、自明なケースをいくつか処理したところで少し早めの昼休憩にしてもらった。ここからは一息でやりたい。購買で買ったパンやおにぎりを食べ、午後0時半から再開。そこからは30分ほどで終わった。思ったよりスムーズに進んだ。用意した図を見せるのではなく、自分で色チョークを使い描きながら説明できるのがやりやすい。わかりやすくもあることを願う。

次に博士課程の方のセミナー。最終的にはなんと6時間もやっていた。最初4時間は普通に進んだが、そこで出てきた命題が見た目より非自明で、残り2時間は全員が思い思いに証明に取り組んでいた。2重の極限で表現される値と1重の値の一致を示す必要があって、それっぽい議論はできても精密にやるのが難しい。イプシロンデルタでそういう2重になった値を扱ったことがなく、どうやるのかよくわからないしやる気にも慣れない。

途中でTAをしている講義の学生が質問に来られて、先生と一緒に対応していた。この講義は、今は先生が用意したPDF資料を使い持ち回りでセミナー発表を行っているが、もうそろそろ終わりそう。次も持ち回りで発表を行う予定で、今度は内容をある程度自由にしてよい。何をするかに関しての質問だった。あんまり実のあることは言えなかった。

次回のセミナーについて少し打ち合わせし、午後7時半に解散。いったん帰宅してまたすぐ外出した。ゲーセンに行く。

まず立ち食いそば屋で腹ごしらえ。これまで330円だったかけそばが350円に値上げされていた。もっと前は300円だった気がする。1年ほど前に比べれば最近は客足も戻ったように見えていたのだが。世知辛い話だ。

今日は新曲を埋めるので手一杯。一応の成果として、14+で新規のAJとSSS+を一つずつ出した。あとは15で最近プレイしていないものを適当に。結構ポンポン伸びるがSSSには遠く、あんまりやる気が出ない。

Air AJ pic.twitter.com/agaoplSXVk
— こたつがめ (@kotatsugame_t) 2022年11月15日

何気なく選曲したら一発で出た。ちょっと赤が多かったのが残念だが、中盤の階段……というより微ズレ配置で出さなかったのは偉い。直前のタップで焦るのでちょっと苦手。ラストの鍵盤はこれまで苦労していたのが何だったのかと思うくらい綺麗に通った。

Kattobi KEIKYU Rider SSS+ pic.twitter.com/6yoB6B9L0L
— こたつがめ (@kotatsugame_t) 2022年11月15日

焦らず押せるようになっていていい感じ。押すのが間に合うから焦らなくなったのか、焦らなくなったから脱力できて押すのが間に合うのか。意識的には後者である。といってもこのミスは変なところにある1/1タップで、直後のスライダー全体を押さえさせる配置に意識が向いて焦った結果なのだが。前半にも同じ配置があって、そこもギリギリで耐えていた。

今、チュウニズムはグッズプレゼントキャンペーンをやっている。ゲームで使えるキャラクターを引き換えるのに30クレ分のポイントが必要で、前回は4キャラクター一気に引き換えることができたが、今回は期間ごとに1キャラクターずつ引き換え可能となる。特に今のキャラは11/23まで。今日で必要ポイントが半分貯まったと思って確認したところ、1ポイントも貯まっていなかった。

なんとスーパーノバはキャンペーンに参加していない店舗だった。前回も同様の罠に引っかかって、その時は開店してすぐだから仕方ないかと思っていたが、それは特に関係なかったらしい。がっくり。あと1週間で30回プレイしなければならない。

直近2回スーパーノバに行った分のポイントがないことに気づいた。どうやら開店からキャンペーン終了まであまり間がないこともあって、キャンペーンの参加店舗となっていなかったらしい。
週記（2022/04/04-2022/04/10） - kotatsugameの日記

ラーメンを食べて帰宅。天気予報を朝に確認したきりで、雨が降る中自転車を漕ぐ羽目になった。一応折り畳み傘は用意していたが、自転車を置いて帰るほど強い雨ではなかった。

しばらくTLを見たりYouTubeを見たりした後、午前2時から日記を書き始めた。しかし眠気が非常に強かったため、1時間で切り上げて布団へ。横になってスマホを触っていたら寝落ちした。

11/16(水)

午前9時前に一瞬起きた。午後から1on1があるので、それに合わせて目覚ましをかけて二度寝。

午後1時起床。しばらくコーディングして午後2時から1on1に臨んだ。1時間弱で進んだ量など大したことがないので、それを説明した後はペアプログラミングのような感じで進行。その場で確認を取りつつ必要な機能を実装していった結果、先週の時点でのToDoリストを全部消化できてしまった。代わりに1on1は3時間半もの間続いた。それだけお付き合いしていただいて本当にありがたい。

今のところもう新たに実装するべきこともないようなので、出力を眺めて正しく動いているかチェックするのが来週までのタスクになった。1on1を終えてすぐ外出。今日こそキャンペーンのポイントが貯まるゲーセンに行く。

まず食事。麺類ばかり食べているとまずい気がしたので、いつも行くような店を避けながら商店街を練り歩き、ステーキハウスなる店に入った。いい値段のする肉がメインだが、定食くらいなら自分でも手を出せる。

食事 pic.twitter.com/tvL0ovKWoK
— こたつがめ (@kotatsugame_t) 2022年11月16日

GiGO仙台で閉店まで22クレ遊んだ。今日は主に14の未AJを埋めていて、新規に6譜面出せたため残り6譜面。特に赤の14は全部AJすることができた。さらに14+のAJ、15のSSSを一つずつ出した。

Aleph-0 MAS AJ pic.twitter.com/xuywbYED4U
— こたつがめ (@kotatsugame_t) 2022年11月16日

ラストの高速トリルは脱力を意識すると間に合った。かなり良い精度で揃ってうれしい、というよりここまでくるとあと1個減らしたかったという思いが強い。中盤気を抜いていたらしょうもない赤をいくつか出してしまった。その後ここまで綺麗に通るとは思っていなかったのだ。

蜘蛛の糸 SSS
スライド離して2個出したせいでギリギリ pic.twitter.com/zE3fmHFCBB
— こたつがめ (@kotatsugame_t) 2022年11月16日

久しぶりにプレイしてみたら序盤が上手で一気に7kまで伸びたため詰めた。追加4回で上のリザルトに。そろそろ出そうだし手元でも撮ろうかな、などと考えていたらうっかり手を離してしまったのだ。その後スマホアームをセットし、再度のSSSを狙ってみた。

すぐ序盤に癖がついてダメになってしまったが、たまに8k以上残して通るので、そこから後半を耐えるゲーム。鍵盤も譜面をよく見ることを意識したら通行料がそれなりに安くなった。閉店直前に8kにギリギリ届かないスコアの手元が撮れた。しょうもないところでミスを出したので悔しさが残る。動画で見ると序盤の手元の汚さが際立つ。これは本当に押せているのか？

蜘蛛の糸 6-1 手元 pic.twitter.com/GNrZ2ITjAr
— こたつがめ (@kotatsugame_t) 2022年11月16日

ゲーセンから出た後マックで食事した。紙ストローを初めて使ったが飲みにくいし口当たりも悪くて、SNSで不評ばかりなのも納得。

帰宅して日記を書いていた。最近はてなブログの編集画面で文字を範囲選択したら固まることがあって、いつもページを開きなおす羽目になっている。今日は勝手に取られるはずのバックアップからの復元もできず、1時間くらいかけて書いた文章が消えてしまってショック。ただこの1時間は何をどう書くか悩むことが多くて量はさほどでもなかったから、記憶からの復元がしやすかった。

午前5時前に布団に移動してラノベを開き、1冊読了。「メイジアン・カンパニー」。

「魔法科高校の劣等生」シリーズの続編である。本編が完結した高校の卒業式から時間が飛んで2年後、主人公世代が大学3年生になった時系列で開始した。あとがきによれば本編最終巻のエピローグも同じくらいの時間だったらしいが何も覚えていない。そもそもストーリーも怪しかったので、冒頭で高校3年間における主人公の軌跡がざっと概観されていたのには助かった。司波達也の実力は隠されている、というイメージが強く、本編ラストでは思ったより広く知れ渡っていたということを改めて知ってびっくりした。

内容は面白かった。主人公の出番が多くて嬉しい。ちょくちょく魔法大学でのシーンが挟まれるのはかなり好みだった。直接的に戦っていたのが新キャラだけなのは、主人公が強くなりすぎた弊害といったところか。それでも最後はきっちり締めてくれて満足感があった。

もう1冊開いてそれなりに読み進めたところで就寝。午前10時過ぎだった。

11/17(木)

午後3時半起床。ありえないくらい眠くて、TAから帰ってきたら仮眠しようと決意した。必死に布団から這い出て大学へ。生協で予約していたラノベを受け取った。

TA。最近発表資料が共有されない回が続いていて、今日も何も知らない状態で話を聞くことになった。黒板発表なので特に資料は用意していないとのことだが、原稿だけであってもそれをアップロードしてほしい。しかし人に見せるのを想定していないであろうものを引きずり出すのも申し訳ない。

こういうことを先生に伝えたら、板書の写真を撮って後でアップロードすることになった。写真は発表者が撮る予定だったが、忘れている様子だったので自分が撮っていた。このくらいは最初から担当するべきだった。

発表はなかなか堂々としたものでよかった。立体の図はかなり綺麗。文字は綺麗という表現には当てはまらないものの読みにくいわけでもなく、行が揃っているので印象が良い。ちょっと小さいかなとは思ったが指摘するほどでもなかった。

内容は元のpdfの担当部分と、追加で群の導入。途中で僕や先生がいろいろ口出ししたり質問したりと、そればかり記憶に残ってしまった。次回やるはずの部分に踏み込んだ議論もしていて、自分ばかり満足しているようでちょっと申し訳ない。

また群の例として二面体群 $D_3$ を挙げていたが、参考にした教科書が間違っていたらしい。三角形を3次元空間において変換を線形写像で記述するとき、変換後の $(x,y,z)$ がどんな値か考えなければならないところで、 $x,y,z$ 座標がそれぞれどこに行くかという置換の記法とごっちゃになったのか、結果として回転が逆向きになっていた。つまり、本来 $(x,y,z)\mapsto(z,x,y)$ となるべきところが $(x,y,z)\mapsto(y,z,x)$ になっていたのだ。指摘したがうまく飲み込めないようで少し詰まっていた。こんがらがる気持ちもわかる。

そうやってちょくちょく発表を止めていたら時間をオーバーしてしまった。講義終了時刻から15分経過したところで先生が $D_3$ の乗積表を書かせようとしたので、それはさすがに止めた。講義後少し話して解散。

TAの肩書引っ提げてやってることは学生の発表聞いて質問しまくるだけなの、これで給料発生していいのかってくらい楽すぎる。罪悪感
— こたつがめ (@kotatsugame_t) 2022年11月17日

学食で夕食を摂り午後7時帰宅。起き抜けは絶対仮眠するぞという気持ちだったが、今は少し元気な気がするのでこのまま夜中のTCOまで起きていることにした。そもそも寝起きで出るようなコンテストでもない。しばらくYouTubeを見た後、さすがに何か精進しないとと思って昨年のSemifinalの問題を解こうとした。

Appletが起動せず、焦る。再ダウンロードしたら直った。以下のリンク先の「CLICK TO DOWNLOAD」を押すのが正解。その少し上にある「download and install」を踏むとそれっぽいブログ記事に飛ぶが、ここにあるリンクは生きていなかった。

Competitive Programming at Topcoder | Topcoder

先週もダウンロードし直していて、以下のようにファイル名が変わったのを不審に思っていた。今日ダウンロードしたものは元に戻っている。TopcoderのDiscordによればこの短い間にまたアップデートがあったらしいので、そのせいだろう。

Appletをもう一度ダウンロードしてみたところ、なぜか動いた。ファイル名がこれまで使っていたものと異なっている。
週記（2022/11/07-2022/11/13） - kotatsugameの日記

まずTCO21 Semifinal 1。

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

Easyは単純そうなdpだが適当に書いたら $O(N^2C^2)$ になってしまう。到達できない状態が多いので、明らかなものはループの時点で弾いておけばよい。最初に提出したものは最大ケースでもチェックしたのにシステスでTLE落ち。dpのループの順番を変えたら枝刈りがやりやすい形になって通った。かなり時間がかかっていて暗雲が漂う。

Medは構築。最後のサンプルで=が強いことがわかる。前半の人と後半の人の対戦結果を常に=、それ以外の場所を=以外にすることで、前半のみ・後半のみから3人選ぶ場合以外は常に比較不能にできる。ただこれだけでは全然足りないので、前半のみ・後半のみの部分についてもできるだけ比較不能な三つ組を増やさなければならない。

解法ガチャをしばらくやっていたら正解を引き当てた。全体を $S_1,S_2,S_3$ に分けて、 $a_i\in S_i$ （ $i=1,2,3$ ）について $a_1\lt a_2\lt a_3\lt a_1$ となるようにし、 $S_i$ 同士については再帰的に決めるのが良い。実際どのくらいの数になるかは一切見積もらなかったが、試したら全ケース通った。

次にTCO21 Semifinal 2。

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

Easyは1命令のみのプログラミング言語の実装で、プログラムもメモリに配置されていて書き換え可能なので複雑そうに見えるが、解いてみたらそんなことをする必要はなかった。答えを $A$ 倍するのを $B$ 回繰り返せばよい。特に $A$ 倍する部分は命令を愚直に並べられるので、1重ループが書ければそれでよい問題だった。

Medは解けず。 $N$ 頂点のグラフのハミルトン閉路を探す問題になって、辺の数が少ないからdfsしたら求まるんじゃないかと思ったがダメ。大きな数から優先的に使うようにすると手元では $N=146$ くらいまで求まるも、そこでうんともすんとも言わなくなって埋め込みすらできなかった。

日付が変わってからは景気づけにPCK予選の問題を解いていた。数問なぎ倒したところでコンテスト30分前、集合時間になったためZoomに参加。そこからブレイクアウトルームに振り分けられて画面の共有を行った。

以下のようなことを言われていたが、そもそも複数枚の画面を一度に共有することができなかったので、アクティブなウィンドウだけ共有することになった。別のPCについては話題に出す時間がなかったので、黙ってシャットダウンしておいた。またこのとき英語が全然聞き取れなくて、監督者にはチャットで喋ってもらっていた。

参加者は競技中PCの画面を監督者に共有しなければならないらしい。モニターが複数ある人は全部。自分はそれに加え別のPCのモニターも目の前に固定された状態となるが、これについてはそのPCをシャットダウンしておけばよいだろうと思っている。念のため当日に確認するつもりだ。
週記（2022/10/31-2022/11/06） - kotatsugameの日記

午前1時、TCO22 Semifinal 1開始。あまり勝ち筋など考えず、気取ったこともせず、慎重に一問ずつ通すことにした。

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

Easyから面倒。5000桁以下の数 $N$ が与えられるので、ある数 $X$ とその10進表記を反転した数を足し合わせた形で表せるか判定し、構築する問題。leading zeroは許されない。まず $X$ の桁数として、 $N$ と一致するかちょうど1少ないかの二通りしかないことがわかる。両方試すことにする。

$X=\sum_{i=0}^m x_i10^i$ と置くと、 $X$ とその反転を足し合わせたものは $\sum_{i=0}^m(x_i+x_{m-i})10^i$ になる。この $x_i+x_{m-i}$ の部分を取り出した数列が逆から読んでも同じになるように、各桁の値を分解できればよい。 $N=\sum_{i=0}^m n_i10^m$ 、ただし $n_m$ 以外は一桁の数、と書いて両端から考えてみると、実はこの分解が高々一意であるとわかる。

例えば $i=0$ のとき、 $x_0+x_m$ の十の位は $n_m$ と、一の位は $n_0$ と一致している必要がある。こうやって作った数を $n_m$ 、 $n_0$ から引いて、繰り下がりを適当に解決した後 $i=1,2,\dots$ と進んでいけばよい。面倒だがまあ書ける。

この問題は自分でテストするのも簡単。 $X$ を小さい範囲で試して $N$ としてありうるものを列挙し、ちゃんと判定がうまくいっているか見ればよい。最初は $N=1009$ で落ちていた。これは $X=950$ などで達成できるが、 $x_0+x_m=19$ になって不可能と判定していた。とりあえず $x_0+x_m=9$ と置きなおせば解決して、また丁寧に考えることでこのケースのみが問題だとわかる。実際、以降のテストでは落ちなかったので、提出。

Medは謎。dpでは書けないようだが状態数も少なそう。石が置かれたlevelの最大値を全探索して後ろから枝刈りで調べたところ、最大ケース周辺で十分高速だったので提出した。levelの最大値がたくさん約数を持つとまずいかもしれないと思っていて、変なところに最大ケースがありそうで不安。また、答えを合わせるのにすら結構時間がかかっている。

残り数分でHardをオープン。goodな数 $X$ の最大値が小さいということだけ考えたところで終了した。

チャレンジフェーズ、今回は人数が少ないからか10分。最初にUm_nikのEasyを読んで、自分が $N=1009$ に対処したときのようなコードが見当たらなかったのでチャレンジしたものの失敗。これで点数を下げてしまったので他の人にもノールックで投げることが頭を過ったが、おとなしくシステスを待つことに決めた。実際読んでみたら、多倍長整数を使っていたり微妙なところでdpしていたりで隙がない。

システスを待っていたらYouTubeの生放送を見てよいと言われたので見に行った。シークバーを弄ってコンテスト中の自分への言及を探しているうちにroomのchatが活発になって、何やら結果が出た雰囲気が漂っている。慌てて最新の画面を見たら、何人かの提出が落ちていた。

自分の提出が落ちていなかったためyes/noの最中だと思い、しばらくお祈りしていたが、全然画面が動かない。ちょっと巻き戻したらyes/noをやっているシーンが見つかって、ようやくさっきまで見ていた画面がシステスの結果だったと気づいた。

システス前は8人中7位だったが、システスで上から3人落ちてきて4位に滑りこんだ。Final進出！特に5位とは5pt差だったから、ノールックなんてやろうものなら一切勝ち目はなかった。ちなみにratedだったらしく、レート変化は2774→2845(+71)。

TCO Semifinal 1 oo-, -1chal 4th
ということでFinal進出です pic.twitter.com/c3gUT0iekQ
— こたつがめ (@kotatsugame_t) 2022年11月17日

ふわふわした気分のまましばらくTLを見たり、YouTubeの生放送をチェックしたりしていた。自分のハンドルネームが「こたつゲーム」ではなく「こたつがめ」と読まれるようになっていて非常に嬉しい。touristが「こたつがめ」と言っているのはかなり現実感がない光景。また、システスで7位から4位になったことがcrazyとも言われていて面白い。

www.youtube.com

この発音については以下のシーンで一瞬話題になっていそる。

www.youtube.com

実は自己紹介の動画で、本当は「こたつがめ」と発音すると言っておいたのだ。それが以下。

www.youtube.com

TCO Finalsのための提出物を作り始めた。今日は自己紹介動画の撮影。
週記（2022/09/05-2022/09/11） - kotatsugameの日記

午前4時から3時間ほど日記を書いて布団に入り、ラノベを読んでいた。1冊読了。「キグナスの乙女たち」。

「新・魔法科高校の劣等生」と副題にある。外伝というには本編との関わりが薄く、新作というには濃い。こちらの主人公は司波達也世代が卒業してから1年後に魔法科高校に入学したので、昨日読んだ「メイジアン・カンパニー」より1年前の時系列ということになる。この2作は交互に刊行されているので、ネタバレ対策で自分もその順番で読もうとしていたが、このように年代が食い違っているのであまり注意する必要はなさそう。

内容は……やはり司波達也の雄姿が見たいという気持ちが強い。高校においてその名前が伝説となっていたため、話題に上るシーンがいくつかあったのは嬉しかった。正直なことを言えばこちらの主人公にはまだあまり興味を持てておらず、専らそのような描写を求めて読んでいたのだった。ただ明らかにメインではない。あとがきによればこのシリーズは「学園もの」らしいので、バトルすらあまりなさそう。めげずに読み進めていきたい。

午前10時過ぎ就寝。

11/18(金)

午後4時過ぎ起床。布団から這い出て午後4時40分からサークルのバチャに参加した。

https://kenkoooo.com/atcoder/#/contest/show/eb4e7d56-1580-4b4d-a8c1-7e016048c483

6問目のARC116-Eは合わせるのが難しい木dpだということを覚えていたのに、今日も1ペナ生やしてしまった。符号を切り替えて2種類の値を管理したら0で衝突してしまった。三つ目のサンプルがちょっと大きいのに弱めらしくて辛い。他は特に言うことなし。今日は参加者が僕含め二人で、感想戦もすぐ終わった。

その後日記を書いて、午後9時20分からyukicoder 368。

yukicoder contest 368 - yukicoder

Aは $2\le i\le N-1$ に対して $(i,N)$ を聞くことで $P_1,\dots,P_{N-2}$ がわかる。最後に $(N-2,N-1)$ を聞くことで $P_{N-1}$ が求まり、 $P_N$ は順列という条件から出る。

Bはちょっと難しい。 $P/Q$ が約分された形だとする。 $g=\gcd(N,M)$ 、 $N=N'g$ 、 $M=M'g$ とおくと $\frac 1 N+\frac 1 M=\frac{N'+M'}{gN'M'}$ となった。これをさらに約分できるとしても、それは必ず $g$ の約数によってである。つまり $N'M'$ はこの形のまま分母に残るので、 $N'M'\mid Q$ 。面倒だったので $N',M'\mid Q$ を全探索し、 $g$ は式変形で求め、出力する前にuniqueした。

Cは、1個しか出現しない数は後手によって削除され得る。1度消えると以降先手がいくら新しく作っても後手がまた削除してしまう。逆に2個以上出現する数は後手がいくら削除しても先手が新しく作れるので、ずっと存在し続ける。つまり先手は、最初の1手で2個以上出現する数だけ考えた時のmexを最大化すればよい。

実装にちょっと苦労した。最初の状態で2個以上出現していない最も小さな数を見つけて、それが0個しか出現していないならどうしようもなく、1個出現しているならどこかからもう1個調達できないか調べる。余った数を使うか、なければ最大の数を使うのが最適。

Dは最初 $(i\bmod j)=k$ となる $(i,j)$ を数えようとしたがうまくいかない。単に和を取る順番を入れ替えるだけでうまくいった。 $1\le j\le M$ に対し、 $\sum_{i=1}^N(i\bmod j)$ は $\lfloor N/j\rfloor$ と $j$ の多項式で書ける。商の列挙で $\lfloor N/j\rfloor$ を全探索し、出現する $j^0,j^1,j^2$ の和をそれぞれ閉じた形に直せばよい。

Eはちょっと面白い。 $x$ が一度 $A$ または $B$ の倍数になると、以降 $x$ を大きくしようと思ったときに使える操作が高々一意になる。また、最初に $X_A=\lfloor X/A\rfloor\times A$ とするか $X_B=\lfloor X/B\rfloor\times B$ とするかで二通りあるように見えて、例えば $X_A\lt X_B$ なら次は $\lfloor X_A/B\rfloor\times B=X_B$ となって合流してしまう。

この場合、最初に $X_B$ とするケースは無視してよい。 $X_A\gt X_B$ の場合も同様で、結局操作は初回を含めて常に高々一つしかないと思える。よって値を大きくし続ける操作列の長さを見れば答えがわかる。 $A\le B$ として、一度 $B$ の倍数になった後を考えてみよう。

次は $A$ の倍数になるが、この値は必ず $x+A-1\lt x+B$ 以下である。さらにその次は $B$ の倍数、もっと言えば $x+B$ になるので、2手で $x\rightarrow x+B$ が行われる。これを $x$ が ${\rm lcm}(A,B)$ の倍数になるまで繰り返すから、この間の操作回数は簡単にわかる。これで解けた。

Fも少し面白い。追加した辺がない場合の答えは一般の木のように各辺が使われる回数を考えれば求まる。辺を追加したことでなもりグラフになっているので、そのただ一つのループについて、新しく追加した辺を通る弧を使えば距離が近くなるような点対を考え、その分答えを減らす。

ループの頂点数は $O(N)$ なので、各頂点から生えている木のサイズが求まる。あとはループのどことどこの距離が縮んだかペアを全列挙して、どれだけ縮むかを木のサイズで重みづけすることでとりあえず答えは求まる。式が扱いやすいので2重ループを1重にするのも簡単。木のサイズを求めるのに結構時間を使ってしまった。

全完後は日記に戻っていた。午後11時半からはCF #834 div.3。

Dashboard - Codeforces Round #834 (Div. 3) - Codeforces

AはYesの途中から始まる場合が面倒そうだったので、先頭の文字を見てY始まりに揃えてから判定した。Bは $b$ がdistinctなのに気づいていなかったが他はよい。Cは $a\rightarrow b$ の間に何も挟まないか、 $l$ または $r$ を挟むか、両方挟むか全探索。

Dは $n\mid x\times 10^k$ かつ $x\times 10^k\le nm$ を満たす $x$ があるか、 $k=18$ から降順に判定。 $x$ は $n/\gcd(n,10^k)$ の倍数となる。最初、値も最大化しないといけないのを忘れていて、書き直すのにも少し手間取ってしまった。

Eは三つのserumをどの順番で使うか全探索。吸収は貪欲に行ってよい。Fは $a_n$ を $p-1$ までインクリメントする過程で達成されるか、そこからさらに1足した時の繰り上がり処理で達成されるか、どちらでもないかを判定。出現していない数を探すのは、出現した数を入れたsetを舐めれば十分高速。Gは $n$ から降順に見て配置。置ける位置のうちできるだけ後ろに置くと辞書順最小が達成される。

30分ちょっとで全完、2位。FGが結構速かったらしい。Dで手間取ったのが痛い。Gについてはこの方針が大正解で、データ構造を持ち出して頑張った人をTLで結構観測した。

また日記に戻っていたが、TCB53に参加しておかないといけないのを思い出し、午前1時から参加した。

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

4問目まではよい。5問目はテーマがデータ構造だからと言ってこの位置にBeatsが置かれるわけもなく、制約が小さいので愚直が通る。6問目は $O(3^N)$ 。最初のループでダメなケースをちゃんと弾いたり、一つ要素を固定してどの集合に入れるか決め打ったりすれば十分高速。

7問目は各 $r$ に対して最大の $l$ を尺取りで求める。値ごとの出現回数を管理するテク。 $Y$ の取得にはセグ木を使った。8問目は下位2要素を管理するセグ木だと思ってあらかじめ書いていたが全然違った。値をソートして昇順に舐め、それが2番目の最小値となる区間を数える。

ここまで理論値で一息ついたが、残り2問は両方手間取ってしまった。

9問目は部分列を部分文字列だと思い込んで実装してしまった。これで冷静さを失い、何をやっても解けそうなのにどうやるのかわからない状態にしばらく陥る。最終的には、各文字についてその後ろにある最も近い次の文字の位置を管理することで、各aに対しそこからスタートした場合の $X$ の末尾を求め、これをダブリングしてカウントを高速に行えるようにした。今冷静になってみれば、次の文字の位置それ自体をダブリングしたほうが簡単だった。

10問目は $i=N,\dots,1$ の順に解いた。SAとLCPを使いどこまでが以前に出現したことのある文字列か判定し、 $S$ の $i$ 文字目が0でない場合に残りを新しい値として加える。この新しい値をまとめて取得するために遅延セグ木を使った。 $i\le j\le N$ に対し、 $S$ の $i$ 文字目から $j$ 文字目までを数値と見たときの値を保存する。

更新では新たな数を先頭にくっつける必要があるが、その「先頭」が10の何乗の位かも持てば可能。つまり、 $(a,10^k)$ というペアを持っておき、新しい数 $s$ をくっつけるときに $(a+s\times 10^k,10^{k+1})$ とすればよい。サンプルがなかなか合わずかなり迷走。特に遅延セグ木の更新部分を疑っていて、情報が足りないのかと思いいろいろ追加してしまった。いったん紙の上で整理してからもう一度書き直したらすんなり合った。

9問目が制限21分のところ22分40秒で-2pt、10問目は24分のところ24分47秒で-1pt。まとめると、1時間ちょっとかかって理論値-3ptである。問題は別に難しくないので理論値も数人いるだろう。連覇は前回で終了。もっと盛大に時間オーバーしていると思ってかなり適当に投げてしまったが、WAが出なかったのはよかった。

日記に戻って書き続け、午前5時頃布団に移動した。そこから今日もラノベを1冊読了。「メイジアン・カンパニー」2巻。

この巻は主人公以外の視点が多く感じられた。1巻はストーリーに勢いをつけるために主人公が多めに動かされただけで、今後はこのくらいで進行するのだろう。それでも要所要所でしっかり決めてくれるので嬉しい。魔法を放たれた相手視点の描写もあってより満足できた。3巻の帯にはいよいよ大規模な魔法を使うと書いてあるので、さらに楽しみである。

午前7時半就寝。

11/19(土)

午後2時起床。午後2時半からOpenCupの代理コンテストに出た。

Petrozavodsk Summer 2022. Day 5. ZJU Contest 2 - Dashboard - Contest - QOJ.ac

OpenCup

1430-1930 OpenCup
-2000 振り返り

休憩と称して少しYouTubeを見ていた。QuizKnockが言語学オリンピックを扱った動画を出していてびっくり。かなりの宣伝になりそう。ただ、時間がなくてまだ見られていない。

📖 #QK新着動画 📖
【စိန်ခေါ်မှု】言語学オリンピックの問題って暗号解読じゃない？

暗号解読能力が試される大会!?
言語学オリンピックって面白い！

↓動画はこちら↓https://t.co/t5MUmhFbdX
— QuizKnock／クイズノック (@QuizKnock) 2022年11月19日

午後10時からのTCO Finalに備えてTCO Tシャツに着替えたり洗濯物を取り込んだりの準備をしていた。Zoomに集合するのは午後9時半の予定で、木曜日と同じなら画面共有するまでさらに10分から20分ある。しかしそれまでにABCが一段落しているとも限らないので、あまり当てにはできない。

午後9時からABC278に出た。

AtCoder Beginner Contest 278 - AtCoder

Aはよい。Bは面倒。Cはmapの値としてsetを持った。ペアのsetを持つほうが楽だったか。Dは直近のクエリ1のタイミングと、配列の各インデックスに対してそこを最後に更新したタイミングを覚えておいた。値を見に行ったとき、それより後でクエリ1が来ていたらインデックスに対する値は破棄する。

Eは各整数についてそれが見えなくなる組 $(k,l)$ を数えた。その整数が出現するX座標・Y座標の範囲を求めると、それを覆い隠せる $(k,l)$ は長方形領域になるので、全部まとめて2次元imosでカウントする。 $O(HW)$ 。imosの部分は愚直に足しても間に合う制約だが、焦っていて計算量の見積もりがうまくできなかった。Fはやるだけ。

午後9時半まで10分ちょっと残しGに突入。しかしかなり苦労した。区間の長さに対してGrundy数を計算する。よく見るとこの時点で $O(N^3)$ かかっているが、焦りすぎて気づいていなかった。計算と同時にその状態を達成するような操作方法も覚えておくと、後の操作が高速に取得できる。残っている区間はsetで管理した。

区間の左端を0に揃えたような形で操作の情報を持っていたら、ジャッジから返ってくる操作の情報もそれと同じ形式で取り扱ってしまい2WAした。45分ごろ何とかAC。

ABCの振り返りとコードゴルフは、それぞれTCO後・朝方に行ったがここに書いておこう。少し時系列が前後することになる。Exは問題を読んだだけで考察する時間すらなかったものの、かなり難しい問題だったようで、7完で7位を取れた。Gで何も考えず $O(N^3)$ を書いてしまいすみませんという気持ち。Eに比べてFが簡単すぎると感じたのに、結局Eのほうが倍解かれていてびっくりした。

コードゴルフ。Aは相変わらずVimが短かったらしい。今日は何も考えていないので悔しがる権利すらない。Bはやる気が出ない。パターンが少ないらしく、場合分けする解法が最短になっている。CDはAWK。以降は手付かず。

午後9時半からはTCO FinalのZoomに参加していた。案の定集合待ちの時間が発生していて、その間にギリギリでGのデバッグを完了することができた。直後から画面共有を開始して、午後10時からTCO22 Final。

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

Easyがあまり見ないタイプの問題で非常に苦しかった。75分ほぼ全部をこの問題のために費やした。順列を、区間の反転操作によってソートせよという問題。ただしこのとき最適な操作回数の2倍以下の手数で達成する必要がある。つまり2-近似アルゴリズムを構築せよという問題。

しばらく唸っていたら、隣接項の差が1でない箇所に注目するのがよさそうだと気付いた。順列がソート済みであればそのような箇所は存在せず、またどんな操作によっても高々2箇所しかそろえることができない。つまり1手で1箇所揃えられれば必ず2-近似になっている。

ただ、1手で1箇所そろえる手順すらわからない。ここで頑張って考察を進めるのではなく変な戦略を実装し始めてしまった。順列を隣接項の差が1であるような区間に分割すると、それらを1要素に圧縮して値の大小関係で再度番号を振りなおしたものがまた順列になる。これでサイズを小さくした問題を解き、要素を区間に戻して、反転してしまっている区間を直すというもの。インデックスの管理に苦労しながらなんとか書ききった。

この問題はテストケースも特殊。順列の長さは50以下だが、ジャッジのためには最適な操作回数を知る必要があるため、システスにはそれが計算できた順列しか含まれない。このためチャレンジは全探索できる長さ9以下の順列に制限されていた。正確にはシステスの内容をエスパーすればそれも使えるらしい。ともかく、チャレンジで入力されるケースがわかっているなら試さない理由はない。

実際に全探索して実行した。そもそもバグ修正にかなり時間がかかり、直った後も操作回数が多すぎて全然ダメ。そこで、サイズを小さくする過程で端から貪欲に揃えた場合も計算し、手数の少ないほうを採用した。左からやっただけでは落ちたが右からもやるとなぜか通る。かなり不安になる解法だがとりあえずチャレンジはされない。時間もないので提出した。

Medを開いて題意を理解したあたりでコンテスト終了。チャレンジはEasyを眺めていたが特に何もできなかった。隣接項に注目するのはよくて、さらに左端・右端の差も考慮すべきらしい。それができていればもうちょっとまともに解けたかな、という感想。

生配信でシステスを見守った。不安だったEasyが幸運にも通り、何とか正のスコアを確保できた。6位で賞金争いからは程遠いが、Finalという舞台で問題を解けたという事実にまずは満足したい。またしてもratedだったらしく、2845→2878(+33)。Finalsで合わせて+104した。

www.youtube.com

その後朝までDMOJでコードゴルフコンテストに参加した。期間の終了は火曜日だが時間制限がなく、いつ参加してもコンテスト自体の終了まで何度でも提出することができる。

Lyndon's Golf Contest 1 - DMOJ: Modern Online Judge

少しABCのコードゴルフをして午前7時半就寝。

11/20(日)

午後0時45分起床。午後1時からOUPC2022に出た。

https://onlinejudge.u-aizu.ac.jp/services/room.html#OUPC2022

OUPC

1300-1700 OUPC
-1800 Hのupsolve
ロドリゲスの回転公式

眠気が強いため布団に入り、午後7時から午後9時直前まで仮眠していた。起きてすぐARC152。

AtCoder Regular Contest 152 - AtCoder

Aは帰るなら二人組。なので二人組を座らせないよう端から1マスずつ開けて座ってみて、どこかで座れない二人組ができるかチェックした。400点だったので身構えていたがすんなり解けた。

Bはよくわからなくてエスパー気味に解いた。サンプル1は出発する休憩所を同じにしても達成できて、このとき説明にある休憩時間を一つにまとめることができたと思える。つまり一般に、同じ休憩所から出発するような最適解がありそう。その休憩所を全探索すると、すれ違うもう一つの休憩所は二人がそれぞれ $L$ だけ歩いた先にあってほしい。ちょうどその位置にない場合も左右で最も近いものを探してそれぞれかかる時間を計算し、最小値を出力した。出したら通って安堵。

Cはかなり頑張った。操作によって最大値と最小値の差は変わらないので、最小値を最小化する問題になる。この値を $x$ 、最大値と最小値の差を $W$ とおき、各 $a_i$ が $x$ からどれだけ大きいか表していると思うことにする。つまり $a_1=0$ 、 $a_N=W$ 。ここから $a_i$ によって操作してみよう。

本来の値は $a+x$ であった。 $a_N$ は実は $a_N+x$ で、これを $s=a_i+x$ で操作すると $2(a_i+x)-(a_N+x)=2a_i+x-a_N=2a_i+x-W$ になる。これが新しい最小値 $x'$ であり、操作できる条件が $x'=2a_i+x-W\ge 0$ と表せる。そのほかの要素も同様に、ただしオフセットを $x'$ とするところまで含め、 $a\rightarrow 2(a_i+x)-(a+x)-x'=2a_i+x-a-(2a_i+x-W)=W-a$ となる。全体を反転しているので当たり前で、もう一回操作すると元通りになる。

最小値が同じでも列が反転されているかそうでないか二通りあるのが扱いづらいので、反転後の列に対しては最小値に負号をつけてみる。 $x=x'=0$ のケースは答えが $W$ とわかるので区別しなくてよい。 $x'=W-x-2a_i\le 0$ となるが、ここからもう一度操作する場合どうなるだろうか。

本来の値は $W-a_i-x'$ である。今の最大値は $W-a_1-x'=W-x'$ なので、これを $s=W-a_i-x'$ で操作すると $2(W-a_i-x')-(W-x')=W-x'-2a_i$ となる。これが新しい最小値 $x''$ であり、上と同様操作できる条件は $W-x'-2a_i\ge 0$ でよい。なんと、 $x'$ と $x''$ の形が同じになった！

コンテスト中は大変興奮したものだが、符号を反転することを考えた時点で図形的意味を考えればもっとわかりやすかったかも。つまり数直線上で $2s$ だけ左右に動かしているのだ。しかも、いかにわかりやすくなったといっても解法には直接は寄与しなかった。

2回続けて操作するのをまとめて考えてみる。それぞれ $a_i$ 、 $a_j$ によるものとすれば、まず $W-x-2a_i\le 0$ 、次に $W-(W-x-2a_i)-2a_j=x+2a_i-2a_j\ge 0$ 。例えば $a_i=a_N=W$ 、 $a_j=a_1=0$ として $x$ を十分大きくすれば条件は考えなくてよい。つまり自由に $a_i$ と $a_j$ を選んで $x$ に $2(a_i-a_j)$ を加えられるので、 $g=2\gcd_{i,j}(a_i-a_j)$ 単位で調整できる。

つまり偶数回操作するなら $x\bmod g$ が答え。奇数回操作するなら最後の一回を全探索し、ちょうどいい感じになるように改めて調整すればよい。かなり大変なステップを辿ってきたので半信半疑で提出。一発で通ってびっくりした。

D。 $N-1$ は偶数なので、 $N$ は奇数。 $\gcd(N,K)=1$ の場合は簡単。そうでない場合、例えば $(N,K)=(9,3)$ を考えた。9角形の上に3角形を三つ書いた図で考察していると全然構築できなかったが、何気なく036、147、258という $3\times 3$ のマス目を書いたのが大正解で、こちらで捉えなおすとすぐうまくいった。

より一般には $\gcd(N,K)\times(N/\gcd(N,K))$ のマス目になるが、縦横両方奇数なので $3\times 3$ の場合を拡張することで構築できる。方法は公式解説にあるもの（を回転・反転したもの）と一緒だった。実装時は実際にマス目を作って辺を張るとやりやすい。

Eは謎。全体のXORは0なので、重み $w$ のボールとその左の総XOR $L$ に対し、右の総XORは $L\oplus w$ と書ける。例えば $w_1$ の場合、左に進んでいくと困るため $L\le L\oplus w$ 、 $L=Z$ を使って書き直すと $Z\le Z\oplus w_1$ が必要。

次に $w_2$ について、最初に左に進まないなら $Z\oplus w_1\le Z\oplus w_1\oplus w_2$ 、左に進むなら $w_1$ とくっついた後さらに左に進んではいけないので $Z\le Z\oplus w_1\oplus w_2$ となる。 $Z\le Z\oplus w_1$ がわかっているので、最低限必要な条件は $Z\le Z\oplus w_1\oplus w_2$ にまとめられる。

より一般に $Z\le Z\oplus w_1\oplus\dots\oplus w_i$ になりそう。つまり $Z$ は $w_1\oplus\dots\oplus w_i$ の最上位bitを持っていてはいけない。同様のことを右から、つまり $w_i\oplus\dots\oplus w_{2^N-1}$ についても行い、持っていてよいbitを数えれば $Z$ の種類数が求まる。

実際には $w_1\oplus\dots\oplus w_i=w_{i+1}\oplus\dots\oplus w_{2^N-1}$ なので、右から行う必要はない。これまた半信半疑で出したら通った。かなり素早く解けた。

40分近く残してFに辿り着き全完もあるかと思ったが、解けなかった。 $1$ から $N$ までのパスとそこから生えた木を考えればよいことしかわからず、両端の木の頂点数が極端に多いケースだけ処理して提出してみるも、当然のようにWAだった。5完7位。

コードゴルフはA問題のみ。解説に二人組のインデックスを使う簡単な式が書かれていたので、それをdcで実装した。

午後11時半からCF combined。

Dashboard - Pinely Round 1 (Div. 1 + Div. 2) - Codeforces

Aは全体が一致しているか、そうでないなら $a+b\le n-2$ である必要がある。この $-2$ は二つの順列を違うものにするために必要な分。

Bはどれか1要素を残して操作していくのがよいと思い、出現回数が最も少ないものを見て答えた。しかし3ケース目でWA。改めて考えなおすと、連続する3要素が相異なる位置があれば、そのような位置が操作後も残るようにできることに気づいた。つまりこの場合の答えは $n$ 。そのような位置がなければ $a_1$ と $a_2$ が交互に並んでおり、答えは $n/2+1$ だとわかる。

Cは最初に $A_i=\{i\}$ として、条件を満たすようトポロジカルソートしながら集合の和を取っていけばよい。

Dはcarryが発生する桁の区間がいくつあるか考える。そのような区間は、最下位桁が $(1,1)$ で、最上位桁のもう一つ上が $(0,0)$ で、間は $(1,0),(0,1),(1,1)$ であり、1桁につきちょうど1だけcarryが発生する。またcarryが発生しない桁は $(0,0),(0,1),(1,0)$ のどれかである。 $2^{n-1}$ の位でcarryが発生するかどうかでパターンを分けると、あとは3のべき乗や重複組み合わせを掛けることで求まる。

Eは大変だった。初手で結構な時間をかけて選ぶ頂点集合が連結であることを示せたと思ったのに、そこから先に進めたわけでもないしそもそもその結論も間違っている。

どの頂点を選んでも、それともともと連結でなかった点は全部繋がる。つまり選んだ頂点がもともと属していた連結成分がどうなるかだけ考えればよい。クリークは全部一気に選ぶしかないため、そうでない場合を見た。クリークではないので頂点 $u$ と $v$ であって辺 $uv$ がないものが存在する。 $u$ だけで操作してみる。

$u$ を削除したときの連結成分それぞれについて、 $u$ からの辺があるかを考える。最初の状態で、ある成分のすべての頂点から $u$ に対して辺が出ていれば、 $u$ で操作したときその成分が孤立してしまう。そういうものがなければよい。あれば、適当に選んで $A$ とし、今度は $A$ の適当な頂点 $w$ で操作したときのことを考える。

これによって、 $w$ から $(A\setminus\{w\})\cup\{u\}$ 以外の頂点に対して辺が作られる。特に辺 $uv$ が存在しないことから $v\notin A$ なので、 $wv$ という辺ができる。さらに、最初の状態で $u$ を削除すると $v$ と $w$ が非連結になることから、 $w$ を通らない $uv$ パスが存在すると言える。これは $w$ で操作した今も変わらず残っている。

二つを組み合わせることで $w$ と $u$ が連結、さらに $u$ と $A\setminus\{w\}$ の各頂点の間には辺があるので、ここも連結になることがわかる。以上よりすべての頂点が連結になった。

ここまででもかなり時間がかかっているのに、さらにクリークの扱いでWAを重ねまくってしまった。1頂点や2頂点のクリークがあればそれを全部選ぶのがよい。3頂点以上のクリークしかない場合も、クリークがちょうど二つであればサイズの小さいほうを全部選ぶしかない。三つ以上ある場合、なんと適当なクリーク二つから1頂点ずつ選べば全体を連結にできる。これに気付くのが非常に遅かった。初手で示したつもりだった、選ぶ頂点が連結という命題への反例となっている。

Fは解けず5完、しかもかなり遅めで192位。2681→2631(-50)。Eは次数最小の頂点を選ぶとうまくいくらしい。

なるほど、そんな簡潔実装が。

証明です。
・次数最小の点を a とする
・反転後に、到達不可能になる点 b が存在すると仮定
・b の反転後連結成分を S とすると、S の任意の点に a から辺があることになる
・よって deg(a) >= |S|
・deg(b) <= |S| <= deg(a)
・最小性よりこれらは全て等号、クリーク
— maspy (@maspy_stars) 2022年11月20日

TCB53が終了していた。理論値が一人しか出なかったようで、それに続く2位。しかしその理論値の方には時間でも負けている。まさに完敗。

昨日に引き続き、今日も朝までDMOJのコードゴルフ大会に時間を投入してしまった。午前6時からは日記を書いていた。

途中、土曜日の日記で言及したQuizKnockの言語学オリンピックを扱った動画を見た。2問目のふくらPさんがすごすぎる。この問題を解くにあたって何をする必要があって、さらにどうすればそれができるのかを完全に理解している。言オリの問題に初めて触れたとは思えない。

須貝さんは動画を見る限りでは1問目の解答の理由があいまいで、クイズのように何回も回答できたら多少はあてずっぽうで解いてしまうよなあと思っていたが、3問目はしっかり考察に基づいて正解を勝ち取っていてこちらもすごい。

www.youtube.com

日記が全然書き終わっていないまま布団に入った。少しだけハーメルンを読み、午前9時就寝。

2022-11-14

週記（2022/11/07-2022/11/13）

11/07(月)

午後4時半の少し前に起床。すぐインターン先の定例会に参加した。

先週の進捗は何といってもバグが取れたことに尽きる。今までは新しい仕様に対応するための下地作りといった感じで、それが終了し今週からいよいよ機能を追加して実際に対応させるフェーズに入る。順調順調と思っていたが、僕にこの作業を振ってくださった方が今日言っておられたスケジュールと照らし合わせるに、この先も余裕があるわけではなさそう。あいまいな感じだったので努力目標とは思うものの、早く終わるに越したことはないのでこれからも頑張っていきたい。

勉強会は……わからない。一体何の話だったんだ。定期的に行われる数学回で、今日は線形代数の中編と題されていたが、中身は超関数とかフーリエ変換とか。冒頭でフーリエ展開をしたところまでは、基底だから線形代数なんだなあという気持ちが持てる。しかしそこから先は何がどうしてどういう話題が出てきたのかすら掴めなかった。

圧倒されたまま午後6時半終了。それからはずっと週記を書いていて、午後11時過ぎに校閲まで終わらせた状態で公開できた。過去の週記には仕上げが終わっていないものがいくつか残ってしまっているが、現在のものを完成させるのを優先させている。なぜこんなにも毎週ギリギリなのかということについては、土・日・月にしこたま書いた反動でそれ以外の日はだらけ切ってしまっているから、と自覚している。

TTPCの解説スライドを読んでいた。H問題のメモリ制限の意味と自分が引っ掛からなかった理由を知ったため、先週の週記に追記しておいた。

TTPC2022 解説 - Google スライド

11/07追記：最大流のライブラリを使うと逆辺を持つところで制限に引っかかる。自分は蟻本にある2部グラフの最大マッチングを求める専用のライブラリを使っていたため難を逃れたようだ。
週記（2022/10/31-2022/11/06） - kotatsugameの日記

また、K問題をupsolveした。しばらく何も見ずに考えて、一人が出す手を固定してよいとか、012を割り振ると「あいこ」と「和が3の倍数」が同値になるとか考えていた。しかしまったく先に進めず、早々に諦めてスライドをちょっと見たら、9元連立方程式と書いてあってひっくり返った。パターンが9個しかないことには気づいていたが、本当にそれが正解の方針だとは……。

手計算で頑張って解くと2変数だけが残り、 $l_a\le a$ 、 $l_b\le b$ 、 $a+b\le m_{a+b}$ という範囲を動く整数 $a,b$ について $f(a)g(b)h(a+b)$ の和を計算する問題になった。この式が $\sum_{a,b}f(a)g(b)x^{a+b}$ を畳み込みで求めた後 $a+b$ を全探索すれば求まることに気付くのも少し時間がかかった。

Submission #36311842 - 東京工業大学プログラミングコンテスト2022

愚直に手で解きました pic.twitter.com/AkvNMVNM9M
— こたつがめ (@kotatsugame_t) 2022年11月7日

ラノベを1冊読了。「前世は剣帝。今生クズ王子」4巻。主人公の無双シーンは面白いものの、自分語りだか回想だかが多すぎてかつ読みづらいという評価をしていたシリーズ。3巻を読んでからしばらく時間が空いたが、記憶よりも読みやすくてびっくりした。1巻の時点では伏字にされていたキーワードが話が進むにつれて明らかにされた結果、文章の体をなしたということだろうか。1巻はもう実家に送ってしまったため実際どうだったかは定かでない。バトルシーンは相変わらず良い。主人公が「剣帝」と呼ばれた理由が明らかにされ、これもなかなか捻ってあって面白かった。

午前4時前に、10月中旬に行われたJOI一次予選（第2回）の問題が公開されていたのに気づいた。

JOI 2022/2023 一次予選 (第2回) 過去問 - AtCoder

JOI 2022/2023 一次予選 (第2回) の過去問 AtCoder ページを公開しました！https://t.co/quy5Vi0lii
— kichi2004 (@kichi2004_) 2022年11月7日

公開されたのは午前2時頃らしい。慌てて解いたものの、目ぼしい問題は縮め切られていた。AとCはほぼ自明で、Bは別方針でも最短タイにしかならなかった。一方Dは何とか縮めることができた。

9月に行われた第1回は、直後にTLで検索すると問題内容に関する言及やコード長が確認できたので、それを元に事前に問題内容を予測してC以外の最短コードを書いておくことができた。コンテストページが公開されたらそれらを自動で提出するようなスクリプトを回して放置しており、その後無事最短コードが取れたのだが、今回はほとんど言及がなくてダメだった。一応ページは開いておいて定期的にリロードしていたものの、タイミングも悪かった。

しばらくなろうやラノベを読んで、午前6時半ごろ就寝。

11/08(火)

午後1時半起床。

眠くて布団から脱出するのに30分以上かかった。そこからしばらくコードを書いて、午後3時から1on1。はっきり言って1時間弱では全然進められていないが、少なくともタスクの一部が思ったより難しいことは分かった。そういう困難も含めて行ったことを共有し、次に何をするかの判断を仰ぐ。

月曜日の日記でも書いた通り、これまでは下地作りで、ここから新たな仕様への対応が本格化するものと認識していた。しかしこれは異なっており、実のところすでにある程度形になっているようだ。扱うデータの設計が上手くて、それに沿ってコードを書き直した時点で対応もほぼ完了している、というか。残りやるべきことをリストアップしていただいたが思ったより少なかったのに驚いた。今日やり残したことも含まれている。今後はそれを一つ一つ潰していきたい。

午後5時終了。食事した後、夜からのSRMに備えてAppletを起動してみたが、証明書の確認に失敗した。はいはいいつものね、と思ってJavaの構成から設定を変更しに行ってみたら、以前同様のことがあって変えたものがそのままになっていた。

これまでの対処法が使えずどうしたらいいか途方に暮れて、とりあえずAppletをもう一度ダウンロードしてみたところ、なぜか動いた。ファイル名がこれまで使っていたものと異なっている。いつの間にかアップデートでもされていたのだろうか。

Competitive Programming at Topcoder | Topcoder

無事レジったので布団に入り、仮眠。午後6時半から午後8時45分まで寝ていた。気合いで身を起こし、午後9時からSRM841。直前になってC#とVBが使えないとアナウンスがされたらしい。それでもratedなのか……。

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

Easyは簡単。各bitが立つ確率がサイコロごとに求まるので、適切に掛け合わせてXORが立つ確率も求められる。簡単すぎて逆に怪しくなり、誤差がたくさん出るのかとも考えたものの、結局そのまま提出した。

Medは大変だった。leadした回数を考えなければならないのに、leadした時間の和、leadした時間の最大値と2回も誤読してしまった。さらに悪いことには、最初の誤読に対する解法は真の問題に対する解法とほぼ変わらなかったのに、2回目の誤読に対する解法だけちょっと変わったdpができてしまい、都合2回もコード全体を書き換える羽目になってしまった。このせいで時間を食って点数が大変なことに。

解法は $25^6$ 状態のdpで、1次元だけサイズ2にして配列を使いまわすことで空間計算量を削減した。やっとの思いでサンプルを合わせた後、念のために最大ケースを試したらTLEして絶望。しかしdpの値が0だった場合にスキップしたら十分高速になった。到達できない状態が思ったより多かったらしい。

残り20分でHardに進むも何もわからず。チャレンジフェーズではMedで上のような高速化をしていない提出がないか漁ったものの見つからなかった。EMはちゃんと通って2完19位、2829→2774(-55)。Hardはyukicoderでほぼ既出で、何やら名前の付いたアルゴリズムを使うらしい。

No.1069 電柱 / Pole (Hard) - yukicoder

ラノベを2冊読んだ。1冊目、「前世は剣帝。今生クズ王子」5巻。シリーズ最終巻。追い求めていたラスボスとのバトルがあったが、情報もスルスル集まって実際に戦うまでそれほど苦労したようには見えない。思ったよりあっさり終わったなという印象。結局回想シーンに登場した人々は一部を除いて誰が誰かよくわからなかった。人数が多すぎたし、あとがきにも本筋と関係ないのであまり掘り下げなかったとある。ただ作者の中では設定がいろいろあったようなので、減らしてほしいというのは酷か。

2冊目、「ブラックな騎士団の奴隷がホワイトな冒険者ギルドに引き抜かれてSランクになりました」6巻。名前がカタカナ3文字のキャラクターが多く、5巻を読んでから間が開いたこともあってなかなか読みづらかった。6巻になってから言及することでもないか。内容はヒロインの一人が体を乗っ取られて悪事を繰り返してしまうというもの。しかし主人公が強すぎて、乗っ取っていた敵が戦わずして降参するというアクロバティックな解決方法だった。拍子抜けだが、そのシーンに至るまではそれなりに面白かった。

セミナー準備のため教科書を読み始めた。木曜日に発表する分。前回は一度通して読んでからどういう風に話すか考えるという手順を取れたが、今回はそれほど時間的な余裕がない。それでも2回読んでおくと準備が楽になったので、今回は流れの確認と思って証明以外の部分だけ読むことにした。

途中で寝そうになったものの、朝までかけて発表するであろう分を読み終えた。眠気も消えたためそれから日記を書いていたら、結局購買が開く時間まで起きていることになったので、学食に行って食事し、注文していた本や菓子パンを購入して帰宅。

少しYouTubeを見て正午就寝。

11/09(水)

午後9時頃起床。まだ寝たい気持ちはあるが生活リズム的にもセミナー準備の進捗的にももう起きなければまずい。頑張って布団から這い出た。

しばしばYouTubeに気を取られつつ、午前4時半までかけて準備終了。体感としてちょっと少ない気もするが、メモ書きのページ数だけ見れば普段通りに見える。あとはどの程度図を描いて論述を省略するかということになるだろう。

余裕ができたと思ってコードゴルフしていたら午前6時を回ってしまった。急いで就寝。

11/10(木)

午前9時過ぎ起床。ちょうど3時間くらい寝た計算になる。

昨日寝る前に縮めた問題を確認したらさらに縮められていたので、しばらくそれとにらめっこしていた。昨日考えた方針の一つを再検討した結果運よく最短コードを取り返せたはいいものの、家を出るのがかなり遅くなってしまった。午前10時に少し遅れてセミナーの教室に到着。

午前中は同級生のセミナー。僕が教室に入った時にはすでに先生と何やら議論をしていたので、少し前提知識の説明をしてもらった後自分も参加した。特に発表という形でまとまっていたわけではなく、教科書の記述をより精密にできないかという予想を話していたらしい。見ていた限りでは肯定的に解決されて、自分でも直感的な理解が得られたので納得している。反例を作れたと思ったこともあったがただの勘違いだった。

午前中はそれで終了。正午から1時間は昼休みで、食事した後ノートPCでコードゴルフしていた。朝に縮めたコードがさらに縮められていたので、それに取り組んでいた。今度は大幅に縮め返すことに成功。ABC276-Cである。

atcoder.jp

後ろから見て初めて $P_i\lt P_{i+1}$ が成り立たなくなる $i$ を探し、 $P_{i+1\dots N}$ をreverseした後適切な $j$ について $P_j$ と $P_i$ を入れ替える。自分が昨日縮める前の時点では、いったん $P_i$ たちを配列に保存して、それを見ながら後ろを再構成していた。ところが保存しなくても直接$iを見て後ろにくっつけていけばよい。使った値に空文字列を入れておくことで不要な部分が出力に影響しないようにできる。その分数列の間に空白が入ってしまうがジャッジ的には問題ない。

ではどのタイミングで後ろにくっつける・空文字列を入れる作業をするかということで、今朝の時点では $i$ を見つけた後に行っていた。「適切な $j$ 」を見つけるループとまとめてあり、そのまとめ方で細かな改善がいくつかあって取ったり取られたりしていた。

そこで $i$ を探しながら行うことにすると、大変短くなった。 $i$ を探すループには式を入れられる隙間がいくつもあって、問題なくreverse用の作業ができる。さらに、2回目のループでは $j$ を見つけることだけに集中できるので式が短くなるようだ。あとは入力の読み方などに細かい改善がいくつも入って上のコードが完成した。

午後1時からは自分の発表。特に時間管理などしていなかったのでたまたまだが、ちょうど2時間で昨日用意した分を発表し終えることができてうれしい。今日の証明はちょっと長めで、最初に全体を概観してから説明に入ろうとしたところ先生から待ったがかかって例を要求された。用意していないしその場で作れるとも思えず窮してしまうも、先生がサッと描いたグラフがそのまま使えて感動した。

教科書に載っている魔法のような手順の証明に、感心はしても何か疑問を抱いたことはない。例がなくても論理が正しければ大体は納得してしまう。実はこれらは、研究者として良くない性質ではないか。今日のセミナーなどまさに対称的で、同級生は教科書を読んで抱いた疑問を突き詰めていた。セミナー発表自体は行われず、それについて先生から苦言を呈されていたが、しかしそうやって教科書を疑うような姿勢はこの道を進むならいつか必ず必要になるのだろう。

セミナー終了後しばらく打ち合わせをして解散。5限のTAのため山を下りた。

生協でラノベを買って教室に向かう。まだ4限の時間帯だったので、何食わぬ顔で教室に入って話を聞いていた。内容は生物で、目が悪く最後列からは黒板もスライドも見えないし、先生の声が小さくて聞き取りやすさも微妙。結局1ミリも理解はできなかったが、教室の広さを体感できたという意味では非常に有意義だった。何か説明するときはもっと大きな声・大きな文字である必要がある。

TA。今週も発表資料が共有されていないので、その場で話を聞くだけの楽な仕事になった。今日の発表者は二人。一人目は以前の発表、前回はまた別の話だったので2回前のときにやり残していた部分。説明に自分で納得いかなかったらしく、同じ内容を何度か方針を変えて喋っていたものの、自分が見ている限りではどれでも特に問題なかったしちゃんと理解できた。

二人目はGeoGebraによる図をたくさん用意しており、その場で点を打ったりしながらスマホのメモ書きを見て喋るという発表の方法だった。それ自体はよいが、細部の説明に入るたび方針を考えて少し詰まっていたのが気になる。自分にも覚えがあることで、準備段階では自明な考察に見えてもいざ教壇に立つと内容が飛んでしまうというのはあるある。

また、計算すれば資料に乗っている式や値が出るのは当然だが、だからと言って全部飛ばしてしまうのは講義の趣旨にあまり沿わないと思う。自分は資料のその部分をまだ丁寧に読んでおらず、興味もあったため、余った時間でいろいろ計算してもらった。以上2点に関して、メモ書きであっても事前に発表内容を共有してほしかったという気持ち。

講義後30分ほど質問対応をして終了、学食で食事して帰宅。疲れて結構な時間をボーっとYouTubeを見るのに費やした。

午後10時過ぎからは日記を書いていたが、同時に社築さんのサーモンランの配信も見ていた。「総理大臣によるサーモンラン」という動画シリーズにハマった結果、サーモンラン自体にも興味を持っている。非常に面白くて、午前1時くらいに終了するまでずっと気を取られていた。

www.youtube.com

制限時間ギリギリかつノルマ未達の状態で社築さんが死んでしまいこれはダメかと思ったら急に納品数が伸びてクリアしたり、3人死んでいるのに最後の一人がボスを倒してクリアしたりと、劇的なシーンが何度もあってかなり配信映えしている。特に後者は時間的に最後のバトルだったこともあって本当に興奮した。

午前3時くらいに切り上げて本を開いた。1時間くらいで閉じてハーメルンに移行し、午前4時半に寝落ち。

↓このツイートのイラスト3枚目は自分がイメージらしい。本を持っているのがそれらしい特徴だろうか。片目が前髪で隠れているのもふわふわのくせっ毛も可愛らしく、非常に嬉しい。競プロをやっていただけで美少女化イラストを描いていただけるとは、人生何があるかわからない。

とある赤コーダーさんたちを美少女化らくがき！ひさぶりにオタク活動してたのしかった
ご本人の目に触れませんように…と投稿してしまうの、一種の性癖であり深夜のお赦し　るるる pic.twitter.com/ZKv4twa3u3
— burioden (@burioden) 2022年11月9日

11/11(金)

午前11時半起床。

昨日寝る直前に読んでいたハーメルンをそのまましばらく読んでいたが、1時間ほどで放棄した。各話のタイトルを見た限りではこの先最新話まで主人公の出番がなさそうで、息切れ。

覇王、自由気ままに旅をする。 - ハーメルン

別のハーメルンを開いてそのまま読了。「俺は基本ソロの剣士なんだが、自称凄腕の盗賊とバディを組まされている。～お兄さんってぇ、陰キャのぼっちですよねぇ～」。主人公の淡々としたキャラと正統派の強さが読んでいて心地よかった。ちょっとシリアスな内容の話が数話ずつで展開されていく形式も読みやすい。

syosetu.org

午後3時過ぎに寝落ちして、目覚ましで午後7時に起きた。サークルをサボってしまった。うっかり午前中に起きてしまって、それから二度寝しなかったのが完全に失敗。自分の意志でハーメルンを読むのをやめられない。

目覚ましをこの時間にセットしてあったのはちょうどAHC016が始まる時間だから。まだレジってすらいなかったので急いで情報を入力し、問題文を開いて読んだ。読んだだけ。

HACK TO THE FUTURE 2023 qual（AtCoder Heuristic Contest 016） - AtCoder

ハーメルンに戻る。今日はどうやらyukicoderがないらしいので特に起きたままでいるつもりもなく、午後8時半ごろまた寝落ち。日付が変わる前に起床した。

ハーメルンを1作読了。「科学技術全盛時代に精霊の居場所は」。遊戯王の二次創作で完結済み。主人公はカードの精霊を見ることができる。見えるだけでデュエルが強いなどの設定はなかったものの、ちゃんと精霊と交流して絆を深めているのが良かった。主人公の回想に出てきた精霊がクライマックスで表れて印象的。その話のあとがきに怪しい空行があったため反転表示すると、精霊の内心が書かれていて、読んでニヤニヤできた。

syosetu.org

それから昼間までで本を4冊読んだ。

1冊目、「令和の化学者・鷹司耀子の帝都転生」。なろうで読んでいた作品の書籍化。結構な数の注釈がつけられており、より理解が深まったように感じる。なろうだとわからない専門用語もスルーしがち。ちょっと範囲選択して検索するだけで説明が読めるのに、その手間を惜しんでしまう。一方注釈を真面目に読んでいたら読了にかなり時間がかかってしまった。構造式まで出して説明されていた薬品や物質については、相変わらず眺めるだけになっている。

2冊目、「陰キャだった俺の青春リベンジ」2巻。前半のイベントは、主人公が努力して期末テストで学年一位を取るというものだった。「常に一位」とか「勉強して上位に」はよく見るが、トップにまで上り詰めるのはなかなか見ない気がする。この順位で勝負していた敵キャラを見返していて爽快。後半はヒロインの実家にお呼ばれし、親バカの父と問答。逆行転生モノらしく、一周目の人生で鍛えられた精神面で認めさせる気持ちの良い展開だった。

ラノベを読むことがヒロインと主人公の共通の趣味だが、逆行転生しただけあって挙げられるタイトルが古めで、自分では全部はわからなかった。そのままの形ではなく少し変えられているのでなおさら。

3冊目、同じく「陰キャだった俺の青春リベンジ」3巻、球技大会とお泊まり。運動が苦手な主人公なりに球技大会も練習から頑張っていたが、その前振りで描かれた一周目の人生における失敗のほうが記憶に残ってしまった。スポーツに関しては努力して成功することに現実感を持てない。主人公の家にヒロインが泊まるシーンは、主人公の家庭が2巻で描かれたヒロイン側の家庭と全く違う印象なので、2巻の焼き直しではない全く新しい感覚のやり取りが楽しめた。

4冊目、「ブラックな騎士団の奴隷がホワイトな冒険者ギルドに引き抜かれてSランクになりました」7巻。6巻でほとんどなかった分7巻では主人公のバトルが見られるかとワクワクしていたし、口絵も新技で圧倒する場面だったのでより楽しみにしていたが、思っていたのと違ったためあまり楽しめなかった。技を使うと幼児っぽい人格に切り替わるとは……。主人公の出生について少し明らかにされたので、それ関連の設定として意味のある描写だとは思う。

合間の時間に、また年末調整にチャレンジした。期限は11/14つまり来週の月曜日である。少し書類作成が進んだところで、インターンの給料の扱いに関して疑問が生じた。担当の方に質問を送ったが返信は月曜日になるだろう。それからまた書類作成を再開するためギリギリ。

TAも年末調整をしなければならないらしく、大学からメールが来ていた。読んでみるもほとんど意味が分からない。
週記（2022/10/31-2022/11/06） - kotatsugameの日記

午後3時前に就寝。すぐ生協の冷凍弁当配達で起こされ、受け取った。

11/12(土)

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

Daiwa Securities Co. Ltd. Programming Contest 2022 Autumn (AtCoder Beginner Contest 277) - AtCoder

Aはよい。ゴルフ的にもすぐには短くならないと思って次に進んだ。Bは正規表現を使えばよかったと後悔しながら頑張って文字を比較した。

Cははしごを $\min(A,B)$ でソートしてどこまで行けるか管理するというのを考えたが、よく見たら途中の階では上り下りできなかったのでグラフの問題になる。頂点番号が大きいので座圧して、UFで解いた。

Dは $A$ がソートしてあるものとすると、 $A_i$ または $(A_i+1)\bmod M$ が $A_{i+1}$ と等しいような区間の和の最大値を求める問題になる。列は円状に並んでいるものと見なすので、最初に条件を満たさないような位置を探して先頭に来るようrotateし、区間を貪欲に伸ばせばよい。実装しながら列を2倍にすれば楽だったなと思ったものの、そのまま書き上げたら無事通った。

Eはスイッチを押した回数の偶奇を持って01BFS。Fは0を無視してよく、行の入れ替えは明らか。列の入れ替えは列ごとの大小関係のうち必要なものだけ抜き出し、それを辺だと思ってループがないかトポロジカルソートして調べた。ただし同じ値が多いケースで大量の辺を張ってしまう可能性があるので、適切に超頂点を作ってまとめた。

Gは $i$ 回目の移動で頂点 $u$ にレベル $X$ で来る確率が $p$ だとすると、知りたいのはすべての $i$ と $C_u=1$ なる $u$ について $pX^2$ の和。 $(i,u)$ を状態として $\sum pX^2$ を管理しようとすると、レベルアップの処理が $\sum pX^2\rightarrow\sum p(X+1)^2=\sum pX^2+2\sum pX+\sum p$ となる。よって $\sum p$ 、 $\sum pX$ 、 $\sum pX^2$ を管理しておけば更新も含めて計算できる。

ここまで40分もかかっていないのにすでに全完が出ていてびっくりした。しかも、Exはそれくらい簡単なんだと思ったのに全然解けない。

値の上限と下限を考えて、更新が起こらなくなるまで条件を使って伝播していくコードを書いた。 $(A,B)$ を辺だと思ったとき二部グラフになるなら値を交互に上限と下限に揃えることで満たせる。そうでない場合にどうするかは全く分からず、残り時間が少なくなってから再帰で全探索っぽく決めるコードを投げたら2ケースWAだった。そのままコンテスト終了。

7完最速で11位。Gの公式解説が $X^2$ を分解する方法でびっくり。それで解けることを考えもしなかったし、自分の解法のほうがストレートだとも思う。

Exの解説を開いたら2-SATと書いてあってひっくり返った。こんなの見えないし見えたとしても1位が速すぎるだろと思っていたら、ECR130-Fで既出だったそうだ。出て、考察して、解けなくて、コンテスト後に2-SATだと知り、そこで終わっていた。upsolveしていれば何か違っただろうか。

https://codeforces.com/contest/1697/problem/F

しばらくコードゴルフした後、午後11時半からCF #833 div.2。

Dashboard - Codeforces Round #833 (Div. 2) - Codeforces

Aは実験。 $n$ が奇数のとき $(n+1)/2\times(n+1)/2$ をちょうど作れるらしく、それに $1\times(n+1)$ を追加してもサイズは増やせないので答えは $\lceil n/2\rceil$ 。

Bは数える部分文字列の末尾と文字の種類数を固定するごとに、種類数の条件と、各文字が種類数以下の個数しか出現しないという条件を同時に満たせるような先頭としてありうる区間が定まる。各文字の出現位置を順に管理しておけばよい。区間の幅を足し合わせる。

Cは0の位置の直前で切って考えることができる。切ってできた各ブロックについて、先頭の0を適切な値に合わせることで、累積和を取ったものに一律で値を足せる。この操作でブロック内で最も多く出現する値を0に変えればよい。先頭ブロックだけは先頭に0があるとは限らないので注意。

Dは、まず $d$ が偶数の間 $a$ 、 $b$ 、 $d$ を2で割った。途中で $a$ または $b$ が奇数だと不可能。そうでなければできそう。 $a\;{\rm OR}\;b$ を壊さないように $2^{30}$ の倍数を足すことで $d$ の倍数を作ることを目指す。適当に下の桁から決めてもうまくいかないようだが、 $d$ が奇数であることより $\left(2^{30}\right)^{-1}\pmod d$ が存在するため、これを求めて $2^{30}$ の係数を計算すればうまくいく。

Eは後ろから見て累積maxの位置を管理しながらdp。インデックスと値を状態として持ち、一つ右を先頭としたときの累積maxのうち、値が自分以下だったものから遷移してくる。遷移元に割り振る値は今見ているところに割り振る値以下である必要があるが、さらに累積maxは狭義単調増加なので、それらの間で同じ値を割り振ることがないよう注意する必要がある。サンプルを合わせるのに手間取った。計算量は $O(nm)$ で、制約で $nm$ が上から抑えられているため十分高速。ここはちょっとあからさま。

Fは解けず。手数は多くなるものの、一応任意の位置の値を別の位置の値にXORすることが可能だったので、例えばこれでswapを実装した場合回数を無視すれば解けている。しばらく手で試してみて、両端からどんどん作っていく方針がよさそうに見えたが、回数制限が厳しくどうにもならなかった。5完26位。

ABCのコードゴルフ。CF前にやったものも含む。

Aはコンテスト終了直後にVimで書いたらすぐ短くなってびっくりした。同じ長さのコードが開始直後に提出されており当然負け。Bは正規表現をテストケースハックで縮めていたらそれ以外の部分がダメダメだったらしく大幅に更新され、負け。Cは後述。

Dは列を2倍にして尺取り。列全体を一つの区間だと思ってしまい、その和が $\sum_i A_i$ を超えるケースの処理では、答えと0との $\max$ を取るのではなく、区間を伸ばす前に和を $\sum_i A_i$ で割ったあまりに置き換えることで短くなった。以降は手付かず。

Cで嘘解法が通っているのに気付いた。これまで到達した最高階を $M$ として、 $\min(A,B)\le M$ なら $\max(A,B)$ まで行けるというもの。コンテスト中に一瞬誤読していたままの問題である。実のところ $A$ と $B$ の大小関係を見るのがそこそこ面倒なので思ったほどは縮まなかったが、それでもこの解法が現在の最短になっている。

CodeChefが一対一のゲームをリリースしたとTLで話題になっていたので、夜中に少し参加した。同時に問題を読み始め、提出欄でコードの穴埋めをして先にACしたほうが勝ちらしい。3戦戦ったが、人が少なく毎回同じ灰色の人と当たってしまい、申し訳なくなってやめた。それに問題の質、特に問題文があり得ないくらいひどくてエスパー必須だし、穴埋めするコードの変数名と問題文の変数名が合っていないし、今のところまともに遊べる状態ではないという判断。

Games by CodeChef: Compete against other players

朝までかけてラノベを1冊読了。「アラサーがVTuberになった話。」。ハーメルンで読んでいた作品の書籍化。やはり良かった。改めて読み返すのも楽しかったし、要所要所にイラストが追加されていて一見の価値あり。この巻の内容はハーメルンにあるものの2章までで、特に展開が変わったということはない。ちょっと本が分厚いが、クライマックスに相応しい展開をちゃんとラストに持ってくるのは上手いなあと思った。最初からこうやって分割されるのを意識していたのだろうか？

実はもう続刊が決定しているらしい。また2章分だとすれば、2巻のラストは自分の大好きなシーンになりそう。今から非常に楽しみである。

【お知らせ】
『アラサーがVTuberになった話。』
重版＆続刊決定しました。
これもひとえに皆様方のご支援の賜物と深く感謝申し上げます。
そして、2巻でも引き続きのご支援よろしくお願い致します。 pic.twitter.com/VdnED8zYLN
— とくめい@アラサーV重版＆続刊決定 (@hameln_tokumei) 2022年11月10日

しばらく日記を書いて午前9時前就寝。

11/13(日)

午後2時半起床。ダラダラしていたら食事する暇がなくなり、午後3時からOpenCupの代理コンテスト。

Petrozavodsk Summer 2022. Day 3. Qingyu, flower and their friends’ Contest - Dashboard - Contest - QOJ.ac

今回は難易度が高かったようで、チームで14問中MJGAICEの7完。これで2位、完数としては1位タイで、0ACの問題が5問あった。自分はEFを読んで解けんなあと言ったあと、特殊な言語でプログラムを実装するKに特攻してこれも解けず、コンテスト終盤にCの考察を受け取って実装だけした。一発で通ったのはよかった。

Cは隣接項の差の絶対値がちょうど1で総和が $n$ であるような正整数列に関する数え上げ。すると長さと最大値のどちらかが $O(\sqrt n)$ になるらしい。最大値が小さいものはdpで解けて、そうでないものは初項が大きいか、途中でしきい値を超えるかの $O(n)$ 通りしかなく、それぞれ長さを全探索できる。値が十分大きいと、以降数列の要素が正であることをチェックしなくてよいため、いくらか状態をまとめて計算したものから値を引っ張ってくることができる。ここも自分には少し難しかった。

自分が読んでしばらく詰まっていたEは、チームメイトがパッと見てすぐパスを交わらないようにたくさん取る問題だと解釈し、これでかなり見通しが良くなってびっくりした。この問題はそのままチームメイトが考察を完成させたのだが、ともかくそうやって考察の初手で正しい方向に進む能力から全然違うんだなあと実感している。他の問題も考察メモを見たら、自分にとっては非自明な考察が最初にポンと書かれていたりして感服するばかり。

コンテスト後に1時間ほど振り返りをして解散。それから朝まではダラダラ日記を書きながらYouTubeを見たりハーメルンを読んだりしていた。集中力が持続しないのにこうやって時間をかけるのはあまり良いことではなさそう。今週は前半頑張ってみたが木曜日の途中から溜めてしまっていた。

少し教科書を読んで午前9時前に就寝。

2022-11-07

週記（2022/10/31-2022/11/06）

10/31(月)

布団に転がってずっとハーメルンを読んでいた。寝るのを諦めたのは午後2時を回ったころ。そう決めたなら、夜になって力尽きてしまう前に週記を書き上げて投稿しなければならない。先を読みたい気持ちを抑えて何とか布団から脱出した。

シャワーを浴び、しばらくコードゴルフした後、一瞬大学生協に行って菓子パンとラノベを買ってきた。帰宅してからしばらく日記を書き、午後4時半からインターン先定例会へ。

木曜日にコードを書いたのが先週の進捗。そして金曜日の1on1に寝坊した。これについては改めて謝罪した。今週は改めて行われる1on1で判断を仰ぐのと書いたコードの修正を行う。修正するべき問題は、出力物だけ見れば軽微なものに見えるがまだ原因もわかっていない。もしかしたら根深いものかもしれず、どのくらい時間がかかるかとか詳しいことは見通しが立たない。

勉強会はつい最近TLで話題になっていた、ディープラーニングで行列積を高速化する話についてだった。非常に興味深かったため、眠気で頭が回っておらず聞き逃したところがいくらかあるのが残念。Strassenのアルゴリズムのようにして積を計算する回数を減らすことで高速化されており、それをディープラーニングする準備として、行列積の要素を積の和に分解して表す方法の数学的な定式化と、そこから一人ゲームに帰着するアイディアが紹介された。このゲームを学習すればよいのだ。

評価において実機上で動作する時間も用いることで、そのアーキテクチャに最適化されたアルゴリズムが得られるらしい。明示的に何かしなくても勝手にキャッシュ効率を考えたりしてくれるのと同じ効果があるものと考えられて、この汎用性には本当に驚かされた。自分が07/20の勉強会で取り上げたBLASの行列積では、アーキテクチャごとの最適化はさながら職人芸で専門性が非常に高そうだった。

内容はNumPy、というかそれが呼び出しているBLASという線形代数ライブラリにおける行列積の実装について。
週記（2022/07/18-2022/07/24） - kotatsugameの日記

いよいよもって眠気がまずい。落ちる瞼に抗って何とか週記としての体裁だけ整え、午後7時半ごろに投稿した。また今度加筆修正の必要があるが、今はとにかく眠い。布団に倒れこんで午後8時くらいに就寝。就寝報告のツイートをする間すらもなかった。

11/01(火)

午前2時起床。

それからずっとハーメルンを読み続けていた。午前8時半に1作読了。「ようこそ孔明のいる教室へ」。

syosetu.org

非常に面白かった。Aクラススタート、しかも原作キャラを差し置いてクラスのリーダーポジションになるという展開。それだけに主人公の能力は非常に高く、爽快な無双を楽しめた。特に3章はクライマックスの描写も含め非常にかっこいい。また派閥の部下を一人しか持たず、その人からズブズブに依存されているというのはどことなく退廃的で興奮する。

1時間ほどコードゴルフしてからセミナーに向け出発。教室で同級生と合流したものの、時間になっても先生が来ない。メールを送ろうとしているうちに同級生が、我々がセミナーの日時を間違えていることに気づいた。11/02に行われると認識していたのに、その日付を深く考えず二人してセミナーは毎週火曜日に行われると強固に信じ込んでしまっていたのだ。実際は明日である。

しょうがないので帰る。2限のために登校してきた友人を交えて少し話した後、山を下りた。生協に寄って食事し、ラノベを購入して帰宅。

10月分の読書記録をツイートした。先月は上旬をシャングリラ・フロンティアに費やして、その後もずっとハーメルンばかり読んでいたようだ。

10月の集計
買った：27冊
読んだ：8冊
積読：+19冊
積読（累積）：+119冊
— こたつがめ (@kotatsugame_t) 2022年11月1日

しばらくコードゴルフしてから午後1時くらいに布団に入った。ハーメルンを読み、午後2時半に寝落ち。

午後8時半起床。ひそかにゲーセンに行こうと思っていたが、当然のように失敗してしまった。また1時間ちょっとコードゴルフ。

TAも年末調整をしなければならないらしく、大学からメールが来ていた。読んでみるもほとんど意味が分からない。幸い期限までしばらくあるし、今日対応するのはすっぱり諦めることにして、布団に倒れこんで本を読んだ。ラノベを2冊読了。

1冊目、「現代ダンジョンライフの続きは異世界オープンワールドで！」。竜に寵愛を受けた主人公が何かする作品だと思って買ったが、1巻は寵愛を受けるまでの話だったので、今のところは特に好きとも嫌いとも言いにくい。とりあえず2巻を待ちたい。主人公のキャラはあまり好きではなく、ヒロインはそこそこ好き。展開については、バトルシーンが前半にしかなくあっさり終わってしまったこともあり、それほど盛り上がりはなかったと感じる。

2冊目、「無能と言われ続けた魔導師、実は世界最強なのに幽閉されていたので自覚なし」。著者に見覚えがあると思っていたが、著作リストを見て納得。「神話伝説の英雄の異世界譚」を書いた人だった。そちらは独特の格好良さ、良い意味での厨二臭さがある作品という印象だったので、長文タイトルのテンプレラノベとなかなか結び付かなかった。新作がこのようなパッケージになってしまったのは、まあ商業だから仕方ないのだろう。

中身は前作と変わらず良かった。ヒロインなのにやたら生傷を負わされるのも前作通りで、その分主人公がやってくるクライマックスでの解放感がある。主人公の世間知らず設定については、実力についての行き過ぎた謙遜がなかったのは読んでいて好印象だが、そもそも別に必要ないのではと思ってしまう。まともに展開に関わるのは大体お色気シーンで、これも商業だから仕方ないとはいえ格好良さを求めて読む身としてはノイズになっている。それはそれとしてイラストが好みのため興奮はする。

ネットで話題になっていた記事を読んだ。非常に良い。みくのしんさんは小説こそ読んだことがないものの読解力が非常に高いようで、描写に関する鋭い指摘にはちょくちょくハッとさせられた。ティッシュで時間を把握するのも上手い方法だなと思った。そうやってガヤを入れる様子も交えて読んでいくと、ただ「走れメロス」を読むより作中の雰囲気が一層感じられて、終盤は一緒になって泣いてしまった。この名作を改めて丁寧に読む機会が得られたのが嬉しい。

omocoro.jp

ハーメルンの更新を確認して午前7時就寝。

11/02(水)

午前9時15分起床。準備して山に登った。今日こそセミナーである。

今日は午前中だけで、同級生と二人で1時間ずつの予定。実際には少し伸びて1時間半ずつになった。自分の発表は前回分の残りなので、特に言うことなし。

同級生の発表を聞きながら自分の中でも証明の方針を考えるのだが、黒板で発表されるのがそれより遠回りしていると感じたら口出しせずにはいられなくなってしまう。それで実際に短くなればいいものの、実際に計算してみると大して変わらなかったり失敗したりしていてひどすぎた。途中で自覚したため、その後はどんな証明もとにかく最後まで聞くことを意識していた。

山を下りて学食で食事し、散髪も済ませた。ラノベを買って帰宅し午後3時から1on1に臨む。

先週木曜日にひとまず終わらせたコードの書き直しについて説明をした後、生じている問題、出力が以前のコードと少し違う原因を探り始めた。1行1行見ていくしかないのかな、面倒だなと思っていたら1on1のお相手にすぐ原因を見抜いていただいた。以前にも同様のことがあったが、やはり大本のコードを書かれただけあるなと感じるところである。原因は、同じだと思ってコピペした部分が実は微妙に異なっていたこと。

その周りで連鎖していくつか修正が必要になったものの、とにかく元のコードに合わせることを意識して書き直したら見事出力が一致する。しかしチェックの過程で、実はいくつか元のコードより適切な出力をしているのではないかという話になった。これまで気づいていなかったケースにたまたま対応できているらしい。なので、最終的にはそれを改善として取り入れたものが完成版となった。

ここからは思う存分リファクタリングや機能追加ができる。次に実装するものの指示を頂いて、3時間弱で終了。

疲れ果ててしばらくTLを眺めた後、日記を書き始めた。そこそこで切り上げて午後9時前に就寝。

11/03(木)

午前1時半起床。朝までかけて本を2冊読んだ。

1冊目、「ifの世界線」。SF短編アンソロジー。どの短編も面白かったが、最後のものが最も衝撃的で、他の短編の印象が少し薄れてしまうくらいだった。以下ネタバレ注意。

「うたう蜘蛛」はオチが良かった。終盤まで何が何だかわからないまま読み進めてきて、そこで何の話だったのかを理解させられる。

「パニック──一九六五年のSNS」はミステリ風味。特に短い短編なので真相もあっさり明かされるが、なかなかビターなものだった。SFという感じはあまりしない。実は本自体、この短編の著者である宮内悠介さんを目当てに買ったのだが、ちょっと期待外れという感じ。

「一一六二年のlovin' life」は設定が面白い。和歌に詠訳（＝英訳）を添えて発表するのが当たり前となった世界において、和歌の名手と詠訳の名手が出会う話。教科書で見知った和歌も英語になるとまた違った感触がある。三十一文字では徹底的に省かれていた描写が、英訳するにあたって言葉を補われることから発生するこの感触の違いについては、作中でも言及されており自分も同意するものである。

「大江戸石廓突破仕留」は時代小説の皮を被ったSF小説。冒頭の描写から異物の存在に気付くが、その時点ではまあSFだし、ちょっとした小道具だろうと飲み込んでしまう。しかしそれこそがこの作品の根幹なのであった。

「二〇〇〇一周目のジャンヌ」が最後の短編で、衝撃的だと言ったもの。タイトルの通り「周回」の話。非人道的すぎる設定からして笑い事ではないはずなのに、TAS動画を見ているようなワクワク感が自分の中にあったことを否定できない。20001周目にたどり着き、これまでの閉塞感が一気に取り払われた中でのジャンヌの行動によって強烈な読後感を得た。

またそういうインパクトだけでなく、でびでび・でびるさんのコメントを改めて読んで気づいた流れもある。つまり、ジャンヌの最後の行動はただ周回に倦んだからではなく、信心が最後の最後でループし元通りになったとも考えられるのだ。

【発売まであと5日】
『ifの世界線　改変歴史SFアンソロジー』

いかいのとびらがひらかれた……でびでび・でびるさま（ @debidebiru_sama ）より伴名練さん「二〇〇〇一周目のジャンヌ」へのコメントをいただきました。世にも恐ろしい推薦文をご覧ください。#ifの世界線 #10月14日発売予定 pic.twitter.com/jjWpqBUXDR
— 講談社タイガ (@kodansha_taiga) 2022年10月9日

2冊目、「灰原くんの強くて青春ニューゲーム」3巻。面白かった。2巻でそれとなく示唆されていたように、主人公グループの中で人間関係の矢印があちこちに向き、読んでいる側としてはやきもきさせられる。視点人物たる主人公が気付いているもの、あからさまに描写されてはいるが気付いていないもの、描写すら曖昧で本心がよくわからないもの。ただ、この巻のメインは1巻から出ているヒロインと主人公の関係についてだった。これまでは実は表面的な付き合いだったらしい。そこから急速に仲を深め、一気に主人公が好意に気付くステップまでたどり着いた。しかし次巻はまた別の騒動がありそうで、この巻みたいにストレートに進展することはなさそう。どう遠回りしていくのか楽しみ。

そこからハーメルンを読んで午前11時にまた就寝、午後3時前に起床。

午後3時からOpenCupの代理コンテスト。OpenCupと同じプラットフォームでのバチャという形式だったが、問題はQOJでも見られるようだ。そちらへのリンクを貼っておく。

2021-2022 ICPC North America Championship - Dashboard - Contest - QOJ.ac

これが今期初めてのOpenCupであり、チームが組み直されて初めてのコンテスト参加となる。新しいチームは他二人が自分より圧倒的に強いので何か貢献できるのかと不安になっていたが、終わってみると2問解いたのに加えてペアプログラミング的なことも少ししたため、何もできなかったわけではなかった。チームとしてはなんと13問すべてが解かれ、touristを擁するチームに続く2位となっている。順番はBMJDAKGCLFIHE。

自分が解いたAとGについて。Aは入力から感染タイミングとしてあり得る日付が確定するため、それを満たしながら伝播していくシミュレーションをすればよい。最初の感染者は一人ずつ試さなくても全員同時に行える。また感染タイミングが二日しかないので、自分が移した人にまた移されるケースを考えなくてよい。自分はこれに気付かず、bitsetで誰から移ってきたか管理していた。制約がやたら小さく、それでも問題ないくらい計算量的に余裕があった。

Gは水路をグラフだと思うと、木またはなもりグラフの集まりになる。実際は辺がループや根に向かう方向に向きづけられている。各観光スポットについて、それに隣接するマスがこの木の上にいくつか乗っているが、特にループに近いものだけマークすると、どのようなパスを辿ってもマークしたマスが1回しか出現しなくなる。これで重複が省けている。

自分よりループに近いマスがあるかの判定は、候補として高々 $4-1=3$ 個を全探索し、木において祖先かどうか見ればよい。自分はダブリングで求めた。グラフをちゃんと木として整理しないまま実装を進めたためバグがないか不安だったが、何とか一発で通った。

他はEFHを読んで考察していた。Eは数列の累積和を取ったものの期待値を求める問題で、期待値を求めた後累積和を取ればよいことに気づいておらずダメダメ。チームメイトが誤差に苦しんでいたので、制約が小さいことを利用し多倍長で計算することを進言してみたら通った。Fは手も足も出ず。

Hは場合分けゲーで、状態数が多すぎるため絶望。チームメイトが計算量の許す範囲でどれを全探索するか方針を示したので、それに乗っかって細かい部分のダブルチェックを行っていた。考察メモだけ確認してコードのほうはノータッチだったが、一発で通ったのには感動した。実装が上手すぎる。ボス問はこのEとHだった。

全完して解散かと思ったら、コンテストの振り返りが始まった。これは去年のチームではなかった行事。Aから順番に担当した人が問題概要と解法のポイントを述べていった。正解の道筋だけ見せられると自分でもできそうという気持ちになるが、実際は思いつけるかどうかのほかに本当に実装できるのかということも考えなければならない。

Gの自分がダブリングを使った部分についてほかの方法がないか聞き、オイラーツアーして区間の包含に帰着する方法を教えてもらった。冷静になるとそれはそう。自分の実装では根がどれかわかっていないので、計算量的にも許される以上、あの場で取る方針としてはやっぱりダブリングがよかったのかなと思う。

すべて終わって午後9時。食事し、TCO Finalsのルールを確認して、午後10時半からFinalistのミーティングに参加した。

Zoomに接続して話を聞いているだけ、そもそも英語をあまり聞き取れないので何もしていないとも言える。参加者は競技中PCの画面を監督者に共有しなければならないらしい。モニターが複数ある人は全部。自分はそれに加え別のPCのモニターも目の前に固定された状態となるが、これについてはそのPCをシャットダウンしておけばよいだろうと思っている。念のため当日に確認するつもりだ。

午前3時くらいまで日記を書いていた。途中、rating-historyがそろそろ使えなくなることを知ったので記録の意味でツイートしておいた。

というわけで https://t.co/roTjozWzPx は 11/8 くらいで死にます　使ってくれてた人々ありがとう
— beet (@beet_aizu) 2022年10月7日

Solved By kotatsugame
Topcoder: 150
Codeforces: 2085
AtCoder: 4127
AOJ: 1322
yukicoder: 1479
library-checker: 25
Sum: 9188
https://t.co/0nO54qH8aU
— こたつがめ (@kotatsugame_t) 2022年11月3日

布団に入ってハーメルンを開いたがすぐ寝落ちしてしまった。

11/04(金)

午前11時起床。

布団でハーメルンの「極めて傲慢たる悪役貴族の所業」を読了した。面白かった。転生先の体に引っ張られて傲慢な態度を取ってしまうという設定が好み。日本人的な礼儀正しい精神と拮抗した結果、ちょうどいい俺様具合になっていて、読んでいて好印象だった。やはり貴族なのだからある程度の尊大さはあってほしい。

syosetu.org

午後1時くらいに外出、ゲーセンに行く。まず腹ごしらえのため蕎麦屋に入った。天ぷらそば1杯で1700円。大盛りにすればよかったなと思いながら食べた。たまには良いものを食べようと思っての行動だが、正直な話普段食べている330円のかけそばとの違いが判らない。何なら麺の太さ・硬さ的には後者のほうが好みだったりする。海老天は巨大で良かった。

食事 pic.twitter.com/TQZuJgpJfD
— こたつがめ (@kotatsugame_t) 2022年11月4日

スーパーノバはチュウニズムが埋まっていたので、ちょっと歩いてGiGOに行った。今日も新曲をメインにちょうど30クレプレイ。14+が多めだった。低難易度から理論値が3譜面出たのと、新曲ではない14+のAJが一つ出た。

星の器～STAR OF ANDROMEDA　AJ pic.twitter.com/tLgYk4VAft
— こたつがめ (@kotatsugame_t) 2022年11月4日

途中のゴミ付きトリルが押せて感激。何回かプレイするとダメになりそうなくらいギリギリだったが、ダメになる前に出せた。真ん中にスライドを敷きながら両端でトリルする部分について、左手始動であることをちゃんと確認したのが功を奏した。ラストでスライド持ち替えをミスって一敗している。

一発で鳥出た　二度とやりたくねえ pic.twitter.com/kZJXblpQyB
— こたつがめ (@kotatsugame_t) 2022年11月4日

SON OF SUNのULT譜面。譜面動画を見た限りではSSSにも苦労しそうという印象だったが、実際にプレイしてみると終盤までSSSボーダーを超えていたので、ラストは何もかも忘れて全押し手首エアーで通した。代償として手首を少し痛めたため、二度とプレイしたくない譜面に。

今日の理論値 pic.twitter.com/lriWswP9p1
— こたつがめ (@kotatsugame_t) 2022年11月4日

前二つはやれば出る譜面。Mami Mami Zoneは急に揃ってびっくりした。端フリックでノリノリになれる譜面で結構好み。その近くにあるホールドにスライドを交差させる配置で、わざと持ち替えずに手をクロスさせるのが楽しい。

午後8時過ぎにゲーセンを離脱。つけ麺を食べて午後9時前に家にたどり着いた。準備してyukicoder 367に参加。今日のコンテストは問題文に難があった。

追記：この件についてはwriterの方とリプライでやり取りした。土曜日の日記のうち、最後のほうに書いてある。

yukicoder contest 367 - yukicoder

A。合同式の法を記述するのに独自の記号を使うのではなくちゃんと\pmodを使ってほしい。解法は全探索。式では $C$ 、 $B$ の順に出現するのに入力では逆順に与えられるため最初取り違えてしまった。

Bは再帰。必要になるのは $S_{0\dots 19}$ なのでメモ化すら必要なかった。どうせ $S$ は相異なるだろうと思ってuniqueもしていない。定義が循環していないことについては、問題文ではなく解説にでも書いておけばいいんじゃないかと思ったが、ここはまあ好みか。

C。相変わらず\pmodを使っていないうえ、なぜか入力の数列が配列の形で書かれている。しかもここで記号の衝突を起こしており本当に勘弁してくれという感じ。デカデカと場所を取って配列のindexingの説明をしているのに問題の内容には一切関係がないのも耐え難い。よく見たら入力も無駄に複雑な書き方をしている。writerもtesterも本当にこれでOKだと思ったのか？本当に？

問題文には中国剰余定理の復元をせよと書いてある。手持ちのものがgarnerのアルゴリズムしかないので、とりあえず $B$ たちを互いに素にした。ライブラリのどの部分でオーバーフローが起きうるかすぐにはわからなかったので、使用を諦めてこの段階で $n$ を全探索してみたら爆速で通った。

Dは $\binom{M}{N}\bmod{10^8}$ を答える問題。素因数分解した形を求めることで除算を回避した。階乗に含まれる素因数の個数は高速に求まる。 $M\lt N$ のケースで1WA。

E。いきなり視力検査が始まって笑ってしまった。問題文が不親切すぎる。Cで配列のindexingとかいうクソどうでもいいことをあれだけ丁寧に説明していたのに、こっちは論理式ポンと置いて終わりとは、どこをどうバランス取ったらそうなってしまうのか。 $\land$ にいちいち括弧がついているのも目がチカチカして苦しい。論理式を括弧の数を数えながら読むのは良い体験ではないので、日本語で書いてほしかった。

解法。全探索したら解けないかなと思ったが、 $|V_5|=2^{16}$ なのでここだけは真面目に解く必要がある。後ろ四つの条件から $A_2\ne A_1,A_3,A_4$ と $A_0\ne A_5$ がわかっていて、先頭の条件はたぶん $m_{A_0}\subseteq m_{A_1}$ のはず。まず $A_0=A_1$ のとき、 $m_{A_5}\in m_{A_0}=m_{A_1}\in m_{A_2}$ が得られて、この三つの集合が相異なることがわかる。逆にそうであれば集合の作り方から $m_{A_2}$ がほかのすべての集合を要素に持つためよい。

$A_0\ne A_1$ のときもやはり $m_{A_5}\in m_{A_0}\subseteq m_{A_1}\in m_{A_2}$ が成り立つが、このためには $A_5,A_0,A_1,A_2$ が相異なる必要がある。つまりどうやっても満たせない。 $N=5$ の時だけ以上のことを判定するコードを出したら通った。

Fはアハ体験。 $M$ シャッフルの遷移をすべて求めたい。各 $n$ について、 $D=n^2+4$ 、 $\alpha=\frac{n+\sqrt D}2$ となって、 $\left\lfloor\frac{\alpha^M}{\sqrt D}\right\rfloor\bmod{10^4}$ が次の値である。 $n$ と $\sqrt D=\sqrt{n^2+4}$ のような非常に近い2数について $(n+\sqrt D)^M$ の整数部分を求める問題は何度か見たことがある。絶対値の小さな数 $(n-\sqrt D)^M$ と足し合わせると整数になることを利用するのだった。

No.344 ある無理数の累乗 - yukicoder

しかし今回の場合、よく見ると分母に余計な $2^M\sqrt D$ が来ているのでうまくいかない。ここでしばらく手が止まった。どうにもならないので $n=1$ の場合を考えてみようとして、紙に $\left(\frac{1+\sqrt 5}2\right)^M$ と書いたところで、強烈な既視感に襲われた。これは……フィボナッチ数列の一般項の一部だ。

と言ったものの何もないところから降ってきたわけではなく、あらかじめ実験によって $n=1$ のときがフィボナッチ数列になることは分かっていた。ともかく、これは答えに近そう。正確を期するためググってみると、なんと分母に $\sqrt D$ もあって完璧。やはりこれが正解の方針らしい。

一般項を出す手順を利用するなら、三項間漸化式 $a_{n+2}=na_{n+1}+a_n$ を持つ数列を考えればよさそう。 $a_0=0$ 、 $a_1=1$ として計算を進めると、 $\beta=\frac{n-\sqrt D}2$ を使って $a_n=\frac{\alpha^n-\beta^n}{\sqrt D}$ となった。 $n=0$ でなければ $\beta^M$ の絶対値は十分小さいので、行列累乗で $a_M$ を求めれば答えも出る。 $n=0$ は $M$ シャッフルで変化しない。

シャワーを浴びて午後11時半からCF #832 div.2。

Dashboard - Codeforces Round #832 (Div. 2) - Codeforces

Aからちょっと難しい。 $s_1=a$ とするのが最適。どんな $S$ と $T$ についても、三角不等式 $|S+T|+|-T|\ge|S|$ から $|S+T|\ge|S|-|T|$ が導かれるため。Bは左のほうにあるAと右のほうにあるNを入れ替えた。 $\lceil n/2\rceil$ 回で可能。

Cは $a_1=1$ のとき負け、そうではなく $\min a=1$ のとき相手に $a_1=1$ の状態を押し付けられるので勝ち、そうではなく $a_2=2$ のとき……と考えていくと、 $a_1=\min a$ かどうかで定まるとわかる。

Dはちょっと難しい。まず、操作によって区間で立っているbitの個数の偶奇が変化しないため、少なくとも全体のXORが0である必要がある。この時点で取り出した列が奇数長の場合は解けている。偶数長の場合、端のどちらかが0だったらそこを無視することで奇数長のケースに帰着できる。そうでない場合、間のどこかで分割して奇数長の列を二つ作り、それぞれ1手ずつかける方法しかない。両端の値を同時にXORに含める方法がないので、独立に揃えられなければアウト。

間で分割する方法を探すのは、累積XORの値とインデックスの偶奇に対してインデックスのリストを保存しておき、取り出した区間内にちょうど良い箇所があるか探すことで行える。列全部が0である場合は答えも0となるが、これを取り出した列が偶数長のときにチェックしておらず1WA。気づくのに時間がかかった。

Eは手も足も出ず。いろいろ和の形で立式した後Wolfram|Alphaに投げていたが、うんともすんとも言わないものと超幾何関数を持ち出されるものしか作れなかった。終盤は眠気にほとんど負けていた。4完36位。

YouTubeを見つつコードゴルフし、午前4時から少し日記を書いて布団に入った。

ハーメルンの「高嶺清麿の実力至上主義の教室」を読了。主人公の能力が高いのはいいが、ツッコミ役なのはあまり好きではなかった。これについてはそもそも原作の設定がこの作品に合わないのだろう。ギャグを求めて読んでいるわけではないのだ。

syosetu.org

ほかのなろうをつらつら眺めているうち、午前7時くらいに寝落ちした。

11/05(土)

午後0時半起床。午後1時からTTPC2022に参加した。ソロ。

東京工業大学プログラミングコンテスト2022 - AtCoder

Aは $\gcd(Y-X,X-2015)$ の約数を列挙する。Bは財布の中の金額を持ってdp。魔法によって可能な遷移はあらかじめ求めておいた。Cは同じ値も適当に区別して順序付けることで中央値が一意に定まるようにした後、各値についてそれが中央値となる場合の数を数える。Dは木dp。Eは毎回 $O(|S_i|)$ かけて $a$ 、 $b$ がどこまで伸ばせるか計算する。どの文字が次に・前にどこに出現するかのテーブルを前計算しておけばよい。

Fで詰まった。最初は先頭から決めていこうとしていた。ひとつ前の要素は大きければ大きいほど良い。今の値を $x$ としたとき可能なひとつ前の要素を $f(x)$ と表して、この $f$ を更新していけると考えた。明らかに折れ線になるべきなのにうっかり一つの線分だと勘違いしたまま実装してしまい、long doubleで落ちてから有理数に書き換えてみたり無駄な時間を過ごした。勘違いに気づいて改めて考えなおし、実は $(i,R_i)$ で下側凸包を作ればいいんじゃないかと思って書いたら通った。

Gも凸包関連。 $d$ を固定したとき、 $L_i'=L_i-d\times i$ 、 $R_i'=R_i-d\times i$ とおいて $\max(\min R'-\max L'+1,0)$ 通りだけ数列が作れる。CHTを考えれば内側の $\min$ や $\max$ を折れ線グラフにできて、適切に区間を分割することで単純な一次式に $\max(\ast,0)$ をかませた値の和になる。ここまでくれば後は丁寧に場合分けすることで解ける。

より多く解かれていたLに進んだ。完全順列の拡張みたいなもの。最初に選んだ、後ろの項を固定して漸化式を作る方針は間違いだったらしくうまくいかない。包除原理を考えるとすんなり解けた。 $\lfloor i/M\rfloor=\lfloor P_i/M\rfloor$ を満たす $i$ が少なくともいくつあるか決め打って、その位置と $P_i$ の選び方を数え上げる必要がある。 $[0,M)$ 、 $[M,2M)$ 、……と $M$ 個ずつのブロックを作ると、その中でだけ入れ替えが行われるので、一つのブロックに注目して $i$ をいくつ使ったかを次数にした多項式を計算すれば、 $N$ 乗することで全体に対応するものが得られる。

Mはすんなり解けた。積の部分を $I\subseteq\{1\dots N\}$ についての $\prod_{i\in I}x_i\times\prod_{i\notin I}A_i$ の和と書き下し、和の取り方を入れ替えた上で $|I|$ についてループを回す。 $\prod_{i\notin I}A_i$ のほうは多項式 $\prod_i(A_i+x)$ を畳み込みで計算することで求まる。 $\prod_{i\in I}x_i$ は $M$ を素因数分解した後、素因数ごとにどれだけ $I$ に入れるか決めていても間に合う。

Hもすぐわかったが罠に引っかかった。SCCするとDAGをパスで被覆する問題になって、調べると二部マッチングに帰着できることがわかる。復元もマッチングを取ってくるだけらしい。しかしWA。実は「パス被覆」というと頂点がdisjointなものを指す。これはDiestelでも使われていた定義で、読んでいて謎に思った部分。今は適当に頂点を飛ばせばdisjointでなくてもよい。ではどうするかというと、ありうるパスすべてについて端点のペアを二部マッチングの辺とすればよいのだ。これで飛ばすべき箇所をスキップできる。

残り時間はIとOを考えていた。Iは $D$ を上位bitから順に見て分割しつつUFを管理することを考えた。binary trieの上でdfsしている感じで、戻るときにundoすればよさそう。しかし辺がうまく分割できないと勘違いし、深いところで何度もチェックする必要のある辺が大量にあった場合に間に合わないと思って諦めてしまった。

Oはセグ木のクエリのように列を分割して構築していくのがよさそうに見える。こう制限すると、行うべき操作リストとその間の依存関係が得られるので、4並列で最適に並べよという問題になる。ハードウエア基礎で習ったデータフローグラフのスケジューリングというやつだ。当然一般には解けないので、何か問題特有の構造を見抜く必要がある。実は適当な貪欲で解けないか？と思い、自分に直接または間接的に依存している最も遠い操作までの距離が大きいものから四つずつ取っていくコードを書こうとした。結局時間切れ。

ABCDEFGLMHの2700点で18位。Hは解説の別解に相当するらしいが、メモリには一切気を使わなかった。実際 $7000\times 7000$ のint型が190MBくらいだし、DAGなのでその半分弱になると考えればメモリ制限256MBは余裕のある値に見える。しかしよくよく提出を確認すると、最大250MBくらい使っていてギリギリだったらしい。

11/07追記：最大流のライブラリを使うと逆辺を持つところで制限に引っかかる。自分は蟻本にある2部グラフの最大マッチングを求める専用のライブラリを使っていたため難を逃れたようだ。

また、解説を読んでIの勘違いに気づいた。上位bitから見たとき、今見ているbitで使えるか使えないか判断がつかない辺集合というのは完全に分かれているようだ。よって深いところで何度もチェックする必要のある辺などは存在せず、上に書いた方針で解けてしまう。考察の初めのほうに書いたテーブルが間違っていて絶望。ソロ参加が近い点数で塊になっているため、一歩抜け出すためにもこれは是非とも解きたかった。upsolveしておいた。

それから朝方になってOの上に書いた方針を実装したが、当然のようにWAだった。解説を読んだ感じ、分割を決め打った時点で間違っていそう。

しばらくコードゴルフして、午後9時からABC276。

AtCoder Beginner Contest 276 - AtCoder

Aは正規表現ではうまく書けないようだったのでおとなしくPerlのrindexを使った。 $S$ の先頭に1文字足しておくことで答えを調整。見つからなかった場合はもともと-1が返るのでちょうどよい。

Bはよい。Cはprev_permutationという関数があるのを知っていたが、一応自分で実装した。末尾から逆順に見て単調減少である間取り出し、残った列の末尾の要素を取り出した列に含まれるそれより少しだけ小さい要素と入れ替え、残りを昇順にソート、あるいは単にreverseして後ろにくっつける。

Dは要素ごとに2で割り切れる回数と3で割り切れる回数を求め、残りが一致しているかチェック。求めた回数を見て全体の操作回数を求める。Eは単に始点からdfsしたら通った。

Fは何をやっても解けるはずだが面倒な手順を選んでしまったか。あらかじめソートして順序付けておく。ありうる $K^2$ 通りのカードの取り出し方について、 $\max(x,y)=a$ となるのは先ほどの順序で $a$ 以下であるカードの枚数を $k$ とすれば $2k-1$ 通り。これを管理した。新たなカードを追加する際は、それに対応する $k$ を新しく計算するとともに、これまで存在したカードの $k$ についてもいくつか1増やす必要がある。前者はBITでよいとして、後者に区間ADDで対応するため遅延セグメント木を持ち出した。

Gはあっけなく解けた。数列 $a_2-a_1,a_3-a_2,\dots,a_N-a_{N-1}$ を考えると、この和 $S$ が $S\le M$ を満たし、かつ全要素が $\bmod 3$ で0でない場合に $M-S+1$ 通りが答えに加算される。この係数は $a_1$ が取れる値の範囲から来た。 $N-1$ 個の要素のうち $k$ 個が $\bmod 3$ で1、残りが2だとすると、残り $R=M-k-2(N-1-k)$ をどう割り振るかという問題になる。

数列の要素としては3ずつしか割り振れない。 $0\le i\le R/3$ として $3i$ だけ使うとすれば、 ${}_{n-1}\mathrm{H}_i$ 通りの割り振り方があり、答えに加算されるのは $R-3i+1$ である。 $(R-3i+1){}_{n-1}\mathrm{H}_i$ を $R$ の係数とそれ以外に分けてあらかじめ累積和を取っておくことで、 $R$ もとい $k$ を決めるごとに答えへの寄与の総和が出せる。

Exに1時間くらい残したが解けなかった。0にするべきマスはすぐわかる。残り1と2については矩形領域内にある2の個数の偶奇が問題になるので、 $Q$ 本の $N^2$ 元連立方程式を解ければ各値を確定させることができる。しかし当然間に合わない。二次元累積和を考えると変数を減らせそうだが、一部のマスは0と決まっており、そこを弄る必要が生じて壊れてしまいそう。壊れないような位置の組み合わせだけで累積和を表すと、今度は変数が減らないかもしれない。お手上げ。

7完15位。解説を読む。Fの遅延セグメント木を使った部分について、答えの差分を考えればBITでよかったことに気づいた。Exは、0のことを考えずにマスを埋めたとしても結局必要になるのは0にすべきでないマスだけなので、条件が満たされているかどうかは壊れないようだ。もうちょっと別の言い方をすれば、自分は0だと確定したマスすべてに1を入れて残りを考えていたが、ここで入れる値は何でもよかったということ。

コードゴルフ。AはPerl 19BがVim+wcの17Bに負けた。日記を書いているとき、 $S$ の先頭に1文字足す部分の改善を思いついた。19Bのほうでは$/を連結していたが、文字列を単項マイナスすると先頭に負号が挿入された文字列となるので、これを利用するほうが短い。試すと最短タイの17Bになった。残念。

BはPerlで、負け。CはRustのprev_permutationがそれなりに短かったもののRubyで真面目に実装したらちゃんと縮んだ。DもRuby。そろえる値を $\gcd_i a_i$ に固定し、余った素因数2と3を数える方法。以降は手付かず。

金曜日のyukicoderの問題文について、改めてイライラしてきたためTwitterでお気持ち表明したところwriterの方からリプライをいただいた。以下のツイートのツリーにある。

日記に書こうと思ってたけどTwitterで言うか。昨日のyukicoder-C問題の問題文について、
・なぜか\pmodを使わず[]で法を表記している
・問題と関係ない配列のindexingを説明している
・上二つの記号[]が衝突している
でさすがに勘弁してくれという感じhttps://t.co/qdPNUPHgb3
— こたつがめ (@kotatsugame_t) 2022年11月5日

少しやり取りして、\pmodを使うこと、数列は配列の形式でなく下付き添え字で書くことについては納得いただけたらしい。「競プロでは普通こうする」とばかり言って具体的な根拠を何一つ用意できなかったのは申し訳ないところ。最近のAtCoderの問題文では特別な理由がない限り全部そうなっているから、くらいが理由になるだろうか。

ただ、「 $\dots$ 」で省略することについては、厳密性が失われるためどうしても避けたいそうだ。自分は、少なくともこの問題文のような使い方において「 $\dots$ 」が厳密性を損なうとは一切思っていないが、その根拠は競プロerとしての前提知識に依存してしまっているので主張するには弱い。ある程度競プロに慣れた人間が読みやすい問題文を目指している自分に対し、writerの方は数学好きなら競プロに不慣れでも把握できるような問題文を目指しておられたので、それは意見が合わないわけだ。

省略記号についてはXORや転倒数などの用語のように下で説明するのはどうかとか、厳密さを重視した問題文と競プロっぽく書いた問題文を併記してはどうかという意見を提案しておいた。

午前4時からは日記を書いていたが、昼前に切り上げてラノベを読んだ。1冊読了。「冴えない僕が君の部屋でシている事をクラスメイトは誰も知らない」。

今年4月に発売された本で、買ってすぐ読み始めたのに途中で放り出したまま半年も止まっていた。内容はあまり好みではなかった。タイトルの「シている」がわざわざ片仮名交じりになっていることから示唆されるように、性行為が扱われている。もっと言えばセックスフレンドの話である。主人公がヒロイン二人の間で優柔不断な態度を取り続けるという、言ってしまえばありがちな展開が、そういう描写によって生々しさを増していて肌に合わなかった。クラス内の人間関係も一部ドロドロしていて辛い。

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

11/06(日)

午後9時過ぎ起床。

昨日のリプライに続きが来ていた。実際に問題文が修正されたらしい。また自分は修正前のような問題文にOKを出したtesterこそ罪深いとも考えていたのだが、実際に議論した上でwriterの方の意向を最大限反映した結果だったようだ。このことを聞けたのは、道理のない悪感情を抱くことが避けられたという点で非常によかった。

そういうやり取りをするうち時間は過ぎて、午後11時半からCF。CodeTON Round 3でcombinedである。

Dashboard - CodeTON Round 3 (Div. 1 + Div. 2, Rated, Prizes!) - Codeforces

Aで少し詰まった。 $n$ がやたら小さいので探索で解くのかと思ったものの、値が足し算で変化するため状態数は多そう。考察で条件を見つけたい。swapできないとあまり嬉しくないように思ったので、swapでソートできる条件を考えてみると、 $a_1=1$ ならとりあえずよいことが分かった。このときどんな $j,k$ を取ってもswapできるので後ろが揃えられて、先頭は1なので当然最小となる。

逆に先頭以外に1があった場合、それを先頭に持ってくることも、足し算で値を大きくすることもできないため、どうやってもソートできないことに気づいた。つまり $a_1$ さえ見れば判定できる。わかってからサンプルを見たらかなりあからさまで、がっくり。

Bは簡単。 $x=0$ または $y=0$ のケースは個別に求めるとして、そうでないケースは文字列の一部を取るより全体を取ったほうが $x$ も $y$ も大きくなって嬉しい。よってそれだけ調べればよい。

Cはまあまあ面白い。操作によって、各インデックスで $a_i$ と $b_i$ のどちらか一方のみが変化する。よって最初の状態で $a_i=b_i$ かそうでないかがすべての $i$ で一致している必要がある。一致していた場合、 $a$ だけ見て全部0に揃えたとき、 $b$ は全部0または1になっている。全部0ならOK。全部1の場合は、 $(1,n),(1,1),(2,n)$ の3手で $b$ のみflipすることで全部0にできるため、これもOK。制限の $n+5$ 手には十分収まる。

Dも簡単。まず $a_i\mid a_{i-1}$ がすべての $i$ で成り立っている必要がある。 $b_1=a_1$ として、以降 $i\ge 2$ について $b_i/a_i$ と $a_{i-1}/a_i$ が互いに素であればよい。そのような $b_i$ の数は、 $a_{i-1}/a_i$ の素因数だけ見て行う包除原理で求められる。係数がメビウス関数になるやつ。素因数分解がボトルネックに見えるが、 $a_{i-1}/a_i$ の総積が $m$ 以下なので十分高速。自分は $a_1$ を素因数分解しておいて、その結果を更新する方法で実装した。

Eはちょっと面白いかもしれない。まず一つの文字列に対して必要な操作回数を考えてみる。右に一つシフトする操作は、任意の文字をそれより左に移動させる操作に読み替えられることに注意。(を $+1$ 、)を $-1$ として、全体の和を $c$ 、累積和の最小値を $m\le 0$ とする。括弧の個数を対応させるため、少なくとも $|c|$ 文字追加で挿入する必要がある。

$c\ge 0$ のときは)を $c$ 個後ろにくっつけるべきで、その後 $-m$ 回のシフトで累積和の最小値が $0$ となるようにすればよい。操作回数は $c-m$ 。 $c\lt 0$ のときは(を $-c$ 個前にくっつけるべきで、累積和の最小値は $m-c$ となる。累積和の末尾の値が $c$ だったことから $m\le c$ とわかり、相変わらず $m-c\le 0$ となっている。よって先ほどと同様シフトを $-(m-c)$ 回行う必要があって、操作回数は $-c-(m-c)=-m$ 回。

まとめると、操作回数は $-m+\max(c,0)$ 回とわかった。あとは頑張ると求まる。自分は部分文字列の先頭文字を固定し、 $-m$ のほうは $m$ とそれが担当する区間を管理するstackで、 $\max(c,0)$ のほうはBITで適切な位置の和を取得することで計算した。先頭文字を一つ左にずらすときの値の変化を、これまで見てきた値に加えられるオフセットの変化だと捉えればよい。

ここまで1時間。しかしFが解けなかった。とりあえず操作する区間に含まれる0は連続しているとしてよい。操作の順序が何通りかあるのが大変なので、できるだけ左のものから操作していくことにした。全部1で埋めた二つの区間を用意し、その間に0がいくつかあったと思ってそれを全部1にした時の新しい区間を作る感じで、どんどん大きくしていく。

操作がこのタイミングで初めてできるようになったという条件を入れる必要があって、状態が2次元になった。そこから二つ取ってくるので遷移が全体で $O(n^4)$ になる。ここから $O(n^3)$ にするのもそこそこ面倒で、追加でもう一つ落とすにはインデックスが入り乱れすぎており絶望。

5完96位で2678→2681(+3)。highestから300も下のレートでこうも微動だにしないと、さすがに自信を失ってしまう。明らかな衰え。冷静になって考えてみると、最近のまともなratedはもはやCFにしかないのか。AtCoderに続きCodechefもTOKIも消えたし、SRMは質が悪いし、DMOJは謎。精進の習慣を失ってしまった堕落者にはつらい時期だ。

その後午前5時までかけてFのupsolveをした。解説がなかなか読めず疲弊。適当にdpテーブルを定義すると計算順序に困る。短い区間を1で埋めるために、より右にあるもっと長い区間が必要になるからだ。そこで1で埋まっていない区間のほうを数えることにするといい感じになるらしい。

長さ $i$ の操作し切った文字列があって、そのうち左から $1\le j\le i$ 文字だけ1が連続しているものを $dp_{i,j}$ とする。 $j=i$ のケースは $2^{i-1}$ から $j\lt i$ のケースを引くことで求まる。先頭1文字が1と確定しているので自由度が $i-1$ になっている。残り $j-i$ 文字が全部0の場合は $dp_{j,j}$ 通り。そうでないとき、次に出現する1までに0が $k\ge 1$ 文字あり、またその1が $l\ge 1$ 文字連続しているとする。

間の0を埋められないという条件が $j+l\lt k$ で表現できる。左 $j+k$ 文字の決め方が $dp_{j,j}$ 通りで、残り $i-(j+k)$ 文字のうち左から $l$ 文字が1なので、ここは $dp_{i-(j+k),l}$ 通り。掛けて場合の数が出る。左から1が連続している部分の長ささえわかればその右がどうなっていようとあんまり関係ないというのも意識できていなかった。コンテスト中の別の方針では11...100...0のような文字列だけを数えようとして失敗していた。

今説明したのは遷移に $i,j,k,l$ が登場するため $O(n^4)$ で、コンテスト中と何も変わっていないように見えるが、こちらは $O(n^3)$ に落とした時の遷移が綺麗な形をしているためうまくいく。具体的には、 $dp_{j,j}$ をくくり出して後から掛けられるのがうれしい。まあ綺麗といっても2次元配列を斜めに見るような累積和が必要になるので、そこそこ大変ではあった。

いったん計算量の悪いdpを書いて、遷移を見て計算量を落とせないか考えるというのは、ハマると抜け出せない方針のため避けるべきだと思っていて、実際コンテスト中もやっぱりダメだったかと思っていた。しかし公式解説も $O(n^4)$ から $O(n^2)$ に落としていて驚愕。実際にコードを書こうとすると長くなるので、ちゃんと紙の上で考えられるようになるべき。

Submission #179837858 - Codeforces

朝までかけてラノベを2冊読んだ。

1冊目、「冴えない僕が君の部屋でシている事をクラスメイトは誰も知らない」2巻。新キャラとしてヒロインの姉が登場し、主人公とヒロイン二人の間の微妙な関係性が彼女によって引っ掻き回されることで前に進むという巻。実際に変化が見られるのはヒロインたちの心情のみだった。そもそもこの巻のメインがヒロインの掘り下げだったらしい。それにしても主人公がずっと中途半端な態度を取り続けるだけというのは印象としてあまりよくなかった。

「この世界、わたしに都合がいいようです！」2巻。1巻を読んだのは去年の4月。3巻が1年以上出ていないため続刊の見込みは薄そうという考えがあり、かなり適当に流し読みしてしまった。この巻はあまり主人公の活躍がなく、現代知識で何か発明してもそれを振るうのが新キャラの妹だったり、ラストは母親が締めたりといった感じ。薄れて消えそうな頼りない記憶によれば、1巻では主人公のバトルがあったはずなので、ちょっと残念。

合間に本の注文を行った。12月刊行のラノベをメインに17冊。読んだラノベに挟まっていたチラシに買っていない本を見つけたからだが、念のためといろいろ確認するうちに米澤穂信さんの新刊がいつの間にか出ていたことを知った。慌ててそれも注文。発売日からあまり間を置かずに気づけてよかった。

「わたしたちには、切り札が必要だった」
放課後の図書室で当番をしていた堀川次郎と松倉詩門は、忘れ物の栞を見つける。栞に用いられた押し花は、猛毒のトリカブトだった。一枚の栞が探索と推理の日々を導き、誰にも知られないはずだった過去があばかれてゆく。『栞と嘘の季節』は11月4日発売です。 pic.twitter.com/2J7PGoOvjN
— 米澤穂信 (@honobu_yonezawa) 2022年10月29日

午前9時からは日記を書き、正午就寝。先週の週記は修正すると言っておいてまだ手を付けられていない。

2022-10-31

週記（2022/10/24-2022/10/30）

10/24(月)

午後4時起床。余裕をもって定例会に参加できた。

今日報告できる進捗は先週水曜日に書いたコードと金曜日の1on1の内容。言葉でまとめると簡潔になるが、実際のところ普段よりかなりコードを書いたなという感触があるため、自信を持って発表できた。といっても週に二日も働いていない。

勉強会は圧縮アルゴリズムの話。アルゴリズムが小さなデータにおいて解説されるときは非常に細かい改善に見えていたものも、ちゃんとデータが大きくなるにつれてスケールしていくのが興味深かった。例えば、4bitで $0\dots 15$ を表すのではなくそこに来る数が $1$ 以上なので $1\dots 16$ を表すことにする、と聞くと微妙な感じがするが、入力が大きくなればもっと大きな数になるとわかってもっとずらせると聞くと確かに効果がありそうな気がしてきた。

会議を終えて午後8時に先週の週記を投稿。今週もこまめに書いておいたので、もう校閲まで済ませてある。

やる気が出ず、微妙な眠気を抱えながらYouTubeで2時間ほど溶かしてしまった。シャワーを浴びて気分を切り替え明日のセミナーの準備に取り掛かる。

先週日曜日の日記に、用語の定義を間違えていて予習がやり直しになったと書いた。実はこのやり直しが終わっていない。しかしいざ切羽詰まってみると案外進むもので、数時間かけながらも発表予定の範囲を一通り理解して行間を埋めることができた。尻に火が付いたからというより、単に紙に示したいこと・示したことをまとめながら読んだのがよかっただけかも。寝っ転がって頭で考えるだけではメモリ的な意味で無理があったようだ。

予習しながらまとめた命題リストを見てどの順番で話していくか考え、原稿を作る。方針をメモしただけの証明を肉付けするのもこの部分で行った。一度概観しておくと、似たような議論を繰り返す部分をあらかじめ補題に抜き出しておけたりして、かなり書きやすかった。急がば回れと言うし、時間に余裕がないときでも下書きしてから原稿を作るようにしたほうがよさそう。

午前4時過ぎに何とか完成。食事して午前5時就寝。

10/25(火)

午前9時起床。チンタラ準備していたら学食に寄る時間がなくなった。コンビニでゼリー飲料だけ買いつつ大学へ向かう。今日は午前10時からセミナー。

午前中は同級生の発表。前回の発表が先々週ということで記憶があやふやな上、その先々週は時間が足りず発表されていなかった（はず）のところをスキップして次の部分に入っていたため、ちょっとついていくのに苦労した。自分の早とちりで存在しない間違いを指摘してしまったりと大変。内容も難しくなってきている。

これが午後0時半くらいに終了し、購買に駆け込んで昼食を確保。食事して午後1時から2時間は自分の発表だった。

黒板の使い方は自分なりに考えてやっていけたと思う。後々使うことは左に寄せて書き、右に証明を書いては消し、書いては消しとする。その証明自体は、グラフの性質を正確に見ていこうとした結果記号が乱舞して、確かに初見ではわかりにくくなってしまったかもしれない。細かい話は教科書を読んでいる自分が理解していればよくて、発表時は多少なりともイメージに頼るべきか。

一つ、証明できたと思っていたところができていないのに説明の最中に気づいて、黒板の前で少し固まってしまった。少し考えたら議論が完成したのでボヤ程度の出火。しかし上手く証明がつけられたのは偶然というか、その場で閃きがあったからこそなので、本当に危ないところだった。

今日の最後はD3の方の発表。前回の続きっぽいイントロから式変形に入ったところで、不等号の周りの変形が符号によっては怪しいことを発見。指摘して議論していたら、教室に留学生の方が二人ほどやってこられた。どうやら指導教員の先生の講義を受講していて、レポート問題の質問があるらしい。ちょうど発表も止まっているのでその質問に全員で取り組むことになった。先週のセミナーで解いていたもの。

先生が講義で使用するスライドに載せられた演習問題を解いて議論していた。
週記（2022/10/17-2022/10/23） - kotatsugameの日記

最初は交代で話すのを他の人が聞くスタイルだったのに、いつの間にか1対1が二つできていた。自分はその片方。つたない英語を紙とペンでカバーしながら四苦八苦しつつ解き進めていった。本当に伝わっているかは知らない。大まかな流れを全部説明しつつところどころで計算してもらってみたが、題意を伝えられなかったのか前提となっていてほしい知識が足りないのか、あまりうまくいかなかった。

そもそもその講義が数学科向けというわけではないので、先生もそこは織り込み済みだったのか、必要な事項が講義のスライドに全部載っていて感動した。それを探し当てて適用するのを繰り返す形に。面白いかどうかはともかく解けはする。

終えて大学を出たのが午後7時半。コンビニに寄ってパンを買い込みつつ帰宅。道中で自分の出した答えが間違っていることに気づいたため、すぐさま修正のメールを送っておいた。そんなことをしていたら食事する時間もなく、午後8時からSRM840。Roomに赤が二人しかおらず、代わりに青が大量にいた。

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

Easyから面倒。よく見ると $N\le 10^9$ でかなり腹が立った。解法自体はUFでサイズ管理するだけなのに無駄な座圧要素が入っており本当に嫌な気持ちになる。

Medはdp。挿入dpっぽく相対的な大小関係だけ考えると、直前の値未満にいくつ空きがあるかを持つ方法が思いつく。あとは直前に増加しているか減少しているかだけで、とりあえず状態数は $O(N^2)$ になる。もう解けているだろうと見切り発車で書き始めて初めて、遷移が区間に対する加算になることに気付いたが、最後にimos法、というより単に上または下に累積和を取るだけで対応できた。

prefixとして1項以下しか与えられなかった場合、直前に増加しているか減少しているかわからないため、両方に1代入しておくのが初期状態となる。 $N=1$ のときこれを両方カウントしてしまうことに気づいて、最初に弾いておくことにした。このケースはチャレンジできそうなので覚えておく。

Hardは乱択。とりあえず $S$ としては $N=2P^K$ と互いに素なものだけ考えてよい。 $S$ のべき乗が初めて1になるまで辿る値の総和ということで、とりあえず個数を考えてみることにした。カーマイケルの定理によれば $\lambda(N)=P^{K-1}(P-1)$ 乗すれば必ず1になるらしい。

適当に選んだらこのくらいの周期を持つものが出てきそうに見える。しかし本当にそれが最大か、実は周期の長さが同じでも辿る値が異なるものがあるのではないかと結局よくわからなかったので、今度は実験することにした。

適当な $(P,K)$ を選び、 $S$ の候補すべてについてどの値を辿るか見てみる。すると、周期の長さと辿る値が完全に対応していることが分かった。また周期が最大の $\lambda(N)$ のものは他の周期の倍くらいの数を辿っているため、明らかに総和も最大になりそう。実際試した範囲では最大だったから、周期が $\lambda(N)$ のものの存在を信じたうえでどうにか見つけて答えることにした。

これは乱択が十分高速に動作するはず。 $2$ でも $P$ でも割り切れない数 $S$ をランダムに持ってきて周期の条件をチェックする。周期は $\lambda(N)$ の約数なので、約数で全探索することでも行えるが、実際には $\lambda(N)$ の各素因数 $p$ について $\lambda(N)/p$ 乗して1にならないか調べるだけでよい。これは原始根を求めるときのテク。

チャレンジフェーズでは上に書いたケースでMedを一つ落とした。システスはHardが落ち、6位。レートは2807→2829(+22)でしょっぱい。

Hardのミスは、 $\bmod$ が $10^{14}$ オーダーのため掛け算がlong longでもオーバーフローすることに起因するものだった。当然そんなことはわかっていたのだが、何を考えていたのか__int128_tではなく__int64_tを使っていた。これはひどい。

Hardの背景には、 $\mathbb{Z}/N\mathbb{Z}$ の可逆元の集合 $(\mathbb{Z}/N\mathbb{Z})^{\times}$ が乗法を演算として巡回群になるという定理があるらしい。そのような $N$ の形は限られており、その一つが $2P^K$ のようだ。周期 $\lambda(N)$ の数の存在さえ信じられれば、 $\left|(\mathbb{Z}/N\mathbb{Z})^{\times}\right|=\phi(N)=\lambda(N)$ ということからその数が $(\mathbb{Z}/N\mathbb{Z})^{\times}$ を全部辿って、当然総和も最大になることがわかる。

integers.hatenablog.com

しばらくコードゴルフしつつYouTubeを見ていた。ちょうどプレミア公開されていたにじバラ #39。

www.youtube.com

屋外のロケだとVTuberが現実に居るという「存在感」があっていいなあと思いながら見ていたら、テントを張るシーンで内側に明らかに人がいるのが見て取れてびっくりした。22分56秒時点。ろふまおの屋外ロケでは影すら写さないよう徹底していたので、こういうシーンがカットされないのは驚き。3Dモデルではなくパネルを置いて撮影しているのも含め、ちょっと適当なのがにじバラっぽさなのだろうか、それにしたって危険じゃないかと心配してしまう。

https://www.youtube.com/watch?v=f2gNxg9w6BM&t=1376s

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

10/26(水)

午後1時くらいに起床。生命情報システム科学という講義で木曜日が期限のレポート課題を課されているため、その講義スライド3回分を布団で読んでいた。

2回目の講義でDNAのアラインメントを行ういくつかのアルゴリズムが紹介されて、特にdpによるものは疑似コードまで載っており、AtCoderで予習済みと思ってニコニコしていた。しかし3回目の講義に入るともうアルゴリズムの話は影も形もない。残念。生物学的な知識が足りないのか読んでも全然頭に入ってこないので、今はとりあえず最後まで目を通すことを目標とした。

Genocon2021 ー DNA Sequence Analysis Challenge - AtCoder

それを終えて午後3時過ぎに布団から脱出。しばらくコードゴルフして、午後5時前に外出した。ゲーセンに向かう。

10/13に大型アップデートがあってから初めてのゲーセンということで、今日はほぼずっと新曲を埋めていた。高難度にいくつかやり残したものがある状態で閉店。成果としては、14+で詰めた2曲でSSS+とSSS+寸が出て、あとは「トンデモワンダーズ」で理論値が出せた。

トンデモワンダーズ　理論値！！！！！！！ pic.twitter.com/Idb6TvgGev
— こたつがめ (@kotatsugame_t) 2022年10月26日

以前の日記にも書いた通り非常に好きな曲なので狙ってみた。とはいえまさか13+でこうもうまく出せるとは。譜面のどの部分も安定しなかったが、特に中盤とラストにある変なリズムの部分が苦手なので、これは期待薄かなと思いながらプレイしていたところ、4落ちから急に全部揃った。

トンデモワンダーズが収録されるらしい。かなり好きな曲なので最高。
週記（2022/10/10-2022/10/16） - kotatsugameの日記

その理論値を含め手元動画をいくつか撮っていたので、帰宅してから投稿した。店に1台アーム付きの筐体が用意されていたので、自前のスマホアームではなくそれを使用した。ちゃんと画面上端からスライダーの下まで画角に収められ、いい感じ。

トンデモワンダーズ理論値手元 pic.twitter.com/LVlYuHoe2L
— こたつがめ (@kotatsugame_t) 2022年10月26日

しばらくなろうの読み返しに時間を費やした後、10月・11月に刊行される本をチェックして注文した。20冊。最初はあまり新シリーズに手を出さないように心掛けていたが、物足りなさを感じてしまいどんどん基準が緩くなって結局普段通りの冊数になった。

リストを眺めていると見覚えのある単語が目に飛び込んできた。昨年末読んだなろうが書籍化するらしい。予約しておいた。

なろうを1作読了。「鷹は瑞穂の空を飛ぶ～プラスチックの専門家が華族の娘に転生したので日本は化学立国になります～」。
週記（2021/12/13-2021/12/19） - kotatsugameの日記

https://t.co/ugNdeSQ0xX
「【旧題：鷹は瑞穂の空を飛ぶ】令和の化学者・鷹司耀子の帝都転生　～プラスチック素材で日本を救う～」更新しました！
書影が公開されました！野上武志先生の素晴らしい表紙にビビッと来たら、ぜひ予約注文をお願いします！https://t.co/5CkCE4OCkT pic.twitter.com/jOivXP0vYM
— 雨堤俊次/コモンレール (@commonkryng) 2022年10月21日

「ifの世界線」というSFアンソロジーが出版されていた。宮内悠介さんの名前があるのに惹かれてあらすじなどを確認していると、なんとVTuberでびでび・でびるさんの推薦コメントがあるのを見つけた。これも購入。

【発売まであと5日】
『ifの世界線　改変歴史SFアンソロジー』

いかいのとびらがひらかれた……でびでび・でびるさま（ @debidebiru_sama ）より伴名練さん「二〇〇〇一周目のジャンヌ」へのコメントをいただきました。世にも恐ろしい推薦文をご覧ください。#ifの世界線 #10月14日発売予定 pic.twitter.com/jjWpqBUXDR
— 講談社タイガ (@kodansha_taiga) 2022年10月9日

午前6時就寝。

10/27(木)

午後2時起床。昨日書籍化を知ったなろうは、昨年末に一気読みしてから開いていなかったので更新が溜まっていた。しばらく布団の中でそれを読んでいた。

午後3時半ごろに布団を脱出し、TAのため大学に向かった。生協でラノベを買いつつ教室へ。今日発表分の資料がまだ共有されておらず、明日から学祭だからもしかして休みかもと思っていたが、普段ととくに変わりなく行われるらしい。資料も共有されていないだけで作成済みだった。

何を話すか知らない状態で今日の発表を聞くことになったが、普通そういうものか。内容についてはしっかり完成されていて良かった。その場では言うべきことがほぼ見当たらない。単に座って普通の学生と同様に話を聞いているだけだった。普段からこういう業務だと楽だなと思ったものの、今度はそれで給料を貰うことに耐えられないので、良し悪しといったところ。

講義後先生が質問対応をされていたからか、自分にも質問が来た。先生が講義でたびたび話題に出しておられた群論と今扱っている多面体の関係について。二面体群の話を例に挙げればいいかなと思ったら、空ではうまく言えず愕然としてしまった。後半はもっと大まかな話になって、自分の好きなことをいろいろ喋り散らかしたが、質問に答えるという点では褒められたものではなかったと自省している。

学食で食事し、学祭の準備で活気づく大学を背に午後7時帰宅。

しばらくコードゴルフしてからレポートに取り掛かった。水曜日の昼過ぎに読んでいたスライドのもの。改めて読解に挑戦するも相変わらずよくわからない。Rのパッケージを用いてプログラムを書くという課題もあって、こちらは環境とデータさえ用意すればチュートリアルに従うだけでそれなりに形になりそうだったので手を出してみたものの、肝心のパッケージを動かすためにUbuntuに入るRより先のバージョンが必要だと知った。

手動でアップデートしてもよかったが、慣れないことをすると罠にハマりそう。おとなしく通常の課題に取り組むことにした。まずRで行うはずだったことをWebサイト上で行う。この部分はある程度わかっていて、ただし得られたものを見ての考察ができない。時間いっぱい格闘して何とか文章は書けたが頓珍漢な内容だったら恥ずかしいなという気持ちがある。ともかく提出には成功した。

解放感からハーメルンを開き、1作読了。「ようこそクズヒモ男の教室へ」。

syosetu.org

もうよう実原作のハーメルンも数作目だから展開を覚えてしまって、ちょっと申し訳ない気持ちにはなるもののその分スムーズに読めるようになった。個人的にAクラススタートの設定のほうが最初から盛大に動けて好きで、Dクラススタートのこの作品もどうせAクラスの人間と深い仲なら主人公もそちらに合わせてしまえばいいのにと思っていたが、今のままで十分面白い。まだAクラスと対決するシーンまで進んでいないので、その深い仲のキャラはクラス対抗にはあまり顔を出していない。これからが楽しみ。

午前4時から4時間ほどインターンのためのコードを書いた。以前から話題にしていたコードの書き直しについて、とりあえず一通り終わらせることに成功。ようやく出力物が得られるようになったので、以前のコードで作ったものと比較するプログラムも整えて、チェックしておいた。おおむね合っており盛大にバグっているということはなさそう。細かい違いの原因を探すのはまた今度にする。

コードが動くことは確認できても、出力を生成する段階まで書き直し終えないと正しく動いているかどうかがわからないのはちょっと困る。また出力が得られたとして、その形式がこれまでと変わっているので、比較する方法についても考えなければならない。
週記（2022/10/17-2022/10/23） - kotatsugameの日記

布団に入り、今日起きた後に読んでいたなろうの続きに取り掛かって午前10時くらいに最新話に追いついた。戦争部分は主人公の出番が少なくちょっと物足りなかったが、章が変わって自動車の話になると出ずっぱりになったため、満足。

https://ncode.syosetu.com/n1453gs/

午前10時半就寝。

10/28(金)

午後3時過ぎ起床。今日予定されていた1on1は午後2時からということで、つまり盛大な寝坊である。

インターンを開始して1年が経過し初めてやらかしてしまった。午後1時半くらいの目覚ましで目を覚ました記憶はあるが、45分あたりにも目覚ましをかけているからということでうっかり二度寝に入ってしまい、それが思ったより深かった。最近は緊張感が薄れてしまったのかこういうギリギリを攻めることが多くて、だからいずれ訪れる破滅だったのだろう。Slackで平謝り。1on1は今日これからではなく別日に行うことになった。

正直まだ眠いため、その後も布団にいた。しばらくなろうを読んで午後5時に寝落ち。午後8時半に再度起床した。

少しコードゴルフして午後9時20分からyukicoder 366。

yukicoder contest 366 - yukicoder

今日のセットではEのテスターをしているから、まずその話をしておきたい。下に引用した日記で言及していた問題がこれだ。もともと星3.5ということで依頼を受けており、その時は解法が結構ごつく制約も少し小さいものだった。提出一覧の底のほうに名残がある。ところが今の解法で解けたため、制約を上げて星を減らすことになった。

減らすといってもいくつにするかは判断が難しいところ。個人的には星3弱という評価をしていた。しかしこれは自分がすんなり思いつけたからであって、タイミングによってはとことんハマってしまいそうな問題。結果としてはsolved数の逆転も起きなかったため安心した。

TLにyukicoderのテスター依頼が流れてきたので、引き受けてしばらく取り組んでいた。
週記（2022/10/03-2022/10/09） - kotatsugameの日記

そのほかの問題について。Aは面倒。何気にFAを取っていた。Bは貪欲。 $1+1$ と $0+2$ をできるだけ作って、あとはよしなにする。きちんと証明しなかった。Cは $a_j'$ と $a_{j+1}'$ を固定し、それが部分列として連続して現れる場合の数を考えた。 $a_j'$ のほうを場合の数ごとまとめて計算することで線形時間になる。そもそも求める値が $a_1'-a_k'$ であることにすら気づいていなかった。

Dは難しくかなり時間を使った。マスを一つ飛ばしに見た時の値の差などに注意して条件をいろいろ考えていたが、最終的にはほぼ直感。一番上の行に左から一つ飛ばしで連番を埋め、一番下の行で先ほど埋めなかった列を右から見てまた連番を埋める。これを上下ともに2行ずつずらしながら行うと行が一つ飛ばしで埋まる。間の行に対しても同じことを、今度は左右を逆にして行うと、見事にすべてのケースで正しい答えが得られている。

Fに取り組むも解けず、5完。最小費用流が当然のようにTLEしたので、ソートして貪欲っぽく解こうと頑張っていた。

また少しコードゴルフしていたが、すぐになろうに手を出してしまう。椅子に座っているのも疲れて布団にダイブし、寝落ちしそうになりながら昼前までずっと読み続けていた。午前10時くらいになって身を起こし、シャワーを浴びて日記を書き、午後1時前に就寝。

10/29(土)

午後5時半起床。

CFに向けた準備をしていたらWindows Updateの通知が来ているのに気付いた。考察の途中に再起動されても困るので、コンテスト開始まで残り10分を切った状態でUpdate開始。幸い特に時間がかかることもなくすぐ復帰できた。

午後6時からCF #831 combined。スタートは正確には午後6時5分、またコンテスト時間が2時間45分ということで、ただでさえABCとのインターバルが10分しかなかったのに、直前で5分こどふぉったためもっとひどいことになった。ABC Unratedの身としては逆に楽しくなってくる。

Dashboard - Codeforces Round #831 (Div. 1 + Div. 2) - Codeforces

Aは $n=2$ は適当に、それ以外は偶数を作ればよい。Bは $a$ と $b$ を適当にswapした後 $\sum a+\max b$ を最小化する問題。常に $a\le b$ となるようにswapして損しない。こう言えば証明の方針もすぐわかるが、コンテスト中は $\max b$ を最大化する方面から考えてしまったためうまく示せず、よくわからないまま提出してしまった。

Cは謎。 $a$ がソート済みとして、とりあえず $|w_1-w_2|$ を $a_n-a_1$ にはできるらしい。そのとき $|w_2-w_3|$ を $a_2-a_1$ または $a_n-a_{n-1}$ にできたので、大きいほうを出力してみた。WA。しばらく考えて、あえて $a_n$ ではなく中途半端な位置の値を使い $(a_k-a_1)+(a_k-a_{k-1})$ 、あるいは $(a_n-a_k)+(a_{k+1}-a_k)$ にしたほうが得する場合があることに気づき、再度提出してACした。

コンテスト中は正当性を示さなかったが、今考えれば $w_2$ を全探索していたのだとわかる。答えを $a_n-a_1$ 以上にするためには $w_1,w_3\le w_2$ か $w_1,w_3\ge w_2$ である必要があって、それぞれの最適値が上に書いた値となる。

Dも謎。 $(1,1),(n,m)$ のほかに1マス空きがあればその空きマスを自由に動かせるらしい。なので、各値を $(n,m)$ に入れる直前にはどれだけの値を $(1,1)$ から外に出しておかなければならないのか求め、その個数が $NM-3$ を超えないかチェックすればよい。空きマスが1行＋1列必要だと勘違いして1WA。

Eは木dp。挿入dpっぽく大小関係だけ考えることにする。あるノード以下の部分木から作れる非減少部分列は、そのノードを含むか含まないかで二通りに分けられる。前者は葉まで一直線のパス上のノードしか使わない場合。後者はそれ以下のどこかで枝分かれがある。これまで枝分かれがあったかどうかを状態に持てばよい。

Fは難しかった。まず状態をどうやって表すか考える。完全にエスパーで、これまで作った集合の個数 $c$ とそのサイズの和 $s$ を持てば、次にどんなサイズの集合まで作れるか計算できると思った。試したところ正しそう。あらかじめ全 $(c,s)$ について $O(n^2)$ で前計算しておき、これを使ってdpする。dpは、使うサイズ $t$ を降順に決めつつ、 $(c,s)$ を状態として遷移していくもの。ただし $ct\le n$ である範囲しか見なくてよいため、ループが $O(n^2\log n)$ になる。

問題は前計算の部分。1回以上現れる要素だけ考えた時の頻度配列を $V$ とすると、状態 $(c,s)$ では各 $v\in V$ について $\min(v,c)$ 以下だけ $s$ に寄与していると考えられる。寄与の和が $s$ 、あるいは $s$ 以上となる条件下で、寄与を引いてもまだ余る $v$ の個数をできるだけ多くしたい。

$c\lt v$ のときは最大の $c$ 寄与するとして問題ない。 $c\ge v$ のときは、まず $v-1$ だけ寄与していると思って起き、 $s$ に足りない分だけそこから追加で1引っ張ってくるのが最適。これで、 $c$ ごとに $O(n)$ の計算を行えば状態 $(c,\ast)$ に関する値が求められて、十分高速になった。

ところがこれは日記を書いている途中に整理したものであって、本番はもうちょっと面倒なことをしていた。余らせるのを1以下に固定してよいことに気づかず、最初は二分探索、後から $s$ を動かしながら線形探索で求めている。1余らせていては足りない場合の計算は、高速化しないと間に合わなかったので、考察を進めて上と同じものを導いた。

Gには30分弱残した。 $s$ の小さいほうから見て順に $t$ を決めればすべてgoodにできるはずだとわかり、その時必要な隣接関係の管理にはDancing Linksっぽいものが使えそうというところまでたどり着いた。しかし実装してみるとサンプル1すら合わず、デバッグの時間もほぼなくそのままコンテスト終了。

ABCまでのインターバル5分ではシステスが終わるはずもないが、日記だからここに結果を書いておく。6完62位で2668→2678(+10)。しょっぱい。しかしpredictorでは壊れていたのか-30以下を示していたため、得した気持ちになった。

午後9時からABC275。

AtCoder Beginner Contest 275 - AtCoder

Aからちょっと面倒。短い書き方がすぐ出せないのでC++で解き、縮めようとせずBに進んだ。Bはdcで一発。慌てて提出した。

Cはちょっと難しい。正方形の角2点を全探索し、そこから座標の足し引きでもう2点を探す。2種類あるが素直に計算していると特定の一方のみが見つかる。この4点をチェックして正方形をカウントすると同じものが4回数えられるため、最後に4で割って出力した。

Dは2と3が分母に来る分数を切り捨てた値しか使わないため、メモ化再帰。EとFはdp。今回はこの3問が非常に簡単だったため調子に乗っていたら、Gで思いっきり詰まってしまった。

G。とりあえず答えの初期値を $\max_i C_i/\max(A_i,B_i)$ としておく。あとは2種類以上の商品を使う場合だが、特に $A_i\gt B_i$ と $A_i\lt B_i$ から1種類ずつ使うのだろうとエスパーした。この二つをうまく組み合わせることで、重さと体積の合計を等しくできるからである。

実際に計算してみる。使う商品を $(A_1,B_1,C_1)$ 、 $(A_2,B_2,C_2)$ と固定して、 $A_1\gt B_1$ かつ $A_2\lt B_2$ という仮定もおく。すると前者を $B_2-A_2$ 個、後者を $A_1-B_1$ 個だけ集めたものがピッタリになる。それで得られる価値を重さまたは体積の合計で割ったものが $\frac{C_1(B_2-A_2)+C_2(A_1-B_1)}{A_1B_2-A_2B_1}$ 。これを $f(X)/X$ だと思って最大化したい。

式変形と変数の置き換えを繰り返し、何とか解けそうな形まで持っていった。まず分母分子を $A_2B_1$ で割ってみる。 $x_1=A_1/B_1-1,y_1=C_1/B_1,x_2=B_2/A_2-1,y_2=C_2/A_2$ と定めると、 $\frac{y_1x_2+y_2x_1}{x_1x_2+x_1+x_2}$ になる。さらに分母分子を $x_1x_2$ で割り、 $i=1,2$ について $x_i'=1/x_i,y_i'=y_i/x_i$ と定めることで、 $\frac{y_1'+y_2'}{1+x_1'+x_2'}$ まで単純化できた。

$(x_1',y_1')$ を全探索し、 $(x_2',y_2')$ を $y_2'/x_2'$ が最大となるものとして定めればよさそうに見えたが、WA。適当に乱択しても当然通らない。そこで、 $x_i'\leftarrow x_i'+1/2$ と改めて置きなおし、 $\frac{y_1'+y_2'}{x_1'+x_2'}$ にして同じ方法で最大化を試みたところ、見事通った。

時間がなかったのでExはあまり考えず、コードゴルフにかまけていた。7完54位。Gは $\frac{y_1'+y_2'}{x_1'+x_2'}$ までたどり着けたら二分探索で容易に答えが出る問題だということに気づけなかった。品物を高々2種類しか使わないことについては相変わらずよくわからない。少なくとも、自分は極限をうまく言い換えられていなかったようだ。

コードゴルフ。AはVimで、入力を1行1要素に直す部分でいつものテクを忘れており負け。Bは最初に提出した特に工夫のないdcコードが今のところ最短らしい。DはRuby。EもRubyで、こちらは負け。他は手付かず。

今日もまた布団に横たわってなろうを読んでいたが、今度は午前6時前に脱出することに成功した。しばらくYouTubeを見た後、日記を書き、布団に戻って再度なろうに手を出す。午前10時くらいに寝落ちした。

10/30(日)

午後2時45分起床。気合いで身を起こし、午後3時からAHC015に出た。

TOYOTA MOTOR CORPORATION Programming Contest 2022（AtCoder Heuristic Contest 015） - AtCoder

開始後しばらくはコードゴルフをしていた。yesコマンドを使って出力。最初に提出したものではちゃんと99個で出力を終えていたが、その後無限に出力するコードでも通った。

その後シャワーを浴びたりしつつ考えをまとめ、真面目に取り組んだ。箱を傾ける関数、スコアを計算する関数、先読みする再帰関数などを実装し、開始2時間くらいで「1回操作するたびにその2手先の評価値の期待値を最大化する」コードが完成した。これが134.4M。直後、終盤4分の1くらいは3手先を読むようにしたものが136.9Mとなった。

終盤で3手先を読むターンが増えればスコアも上がるらしいので、ここから1時間以上かけて高速化を図った。次のキャンディーが来る位置を全探索した後傾けるのではなく、一度傾けた箱の状態を少しずつ書き換えるようにして、シード値0で常に3手読むのにかかる時間を10秒から9秒に短縮。しかし焼け石に水。

一部やたら動作が遅いケースがあるようで、それに合わせると他のケースのスコアも落ちてしまう。よって内部で時間を計りながら方針を切り替えるしかない。10回に1回3手読んでみて、その時間をこれから毎ターン使っても間に合うか判定。138.6Mになった。ほかのチェックもいくつか試してみたものの、結局これが最高スコア。

正確には138649423点で31位、パフォーマンス2411、レートは1911→2031(+120)。Heuristic黄色になれた。

この問題は、移動させることによって空いた空間に次のキャンディーを入れると認識するのがよかったらしい。3種類のキャンディーをそれぞれどの端に集まるか決めて、次のキャンディーが入る空間を空けるように操作するという貪欲解法で、自分の最高スコアに近い値が出せるようだ。

[AHC015]
下・右・左に集める色を決める。
・次が下に集めるものなら上に寄せる
・右・左に集めるものなら、いま上に寄っているなら下に、そうでなければそれぞれ左・右に寄せる
この貪欲？が1投目の138M
これに毎ターンモンテカルロして期待値最大の行動をするようにして150Mくらい
あとは調整
— tomerun (@tomerun) 2022年10月30日

午後11時くらいまでなろうを読んだ後は朝方まで日記を書いていた。その間にやっていたことをいくつか。

まず、土曜日のCF-Gをupsolveした。コンテスト中に考えた方針は合っていた。ポータル同士の隣接関係について、ある面から別のある面にたどり着けるとしてもその逆が成り立たないことが問題。ポータル内部でレーザーが曲がるとこれがずれてしまう。各面に対し、そこに入ってくるレーザーがどこから来たかと出ていくレーザーがどこに行くかを区別して持ったら解決した。サンプルを手で試す時間があれば解けたと思う。

Submission #178614438 - Codeforces

ハーメルンを2作読了。

syosetu.org

「蹄物語」。阿良々木暦視点だと地の文が長すぎてあまり話が進まないため内容はまだよくわからない。化物語シリーズっぽい、あるいは西尾維新っぽい文章を書こうとしているのは感じ取れて、おおむね成功しているのではないかと思う。

syosetu.org

「俺の家に巫女がいる」。完結済み。博麗霊夢と同棲と聞いてウキウキしていたらシリアスだった。展開の謎は最終話までに回収されたが、主人公の設定はよくわからないまま終わってしまった。

午前6時くらいに切り上げて布団に入り、ハーメルンを読み始めた。これがあまりに面白くて睡眠に失敗。週が変わるため一応このあたりで日記も日付を変えておくが、実際はそのまま徹夜で月曜日に突入した。

2022-10-24

週記（2022/10/17-2022/10/23）

10/17(月)

午後2時過ぎに目を覚ました。もうひと眠りできるくらいの時間。ただし今日は、先週の週記を書き上げた上明日のセミナーの準備までする必要があるので、このまま起きて取り掛かる。まず週記を完成させることにした。

午後4時半からインターン先定例会。先週の進捗報告を休んだので、今週は2週分まとめての発表となった。大層なことをできていないので話す内容が増えてやりやすいという側面もある。

勉強会はプログラムの設計の話だった。開発をやりやすくするための設計方針はいろいろあるだろうが、どれに対してもそのアンチパターンこそが正解となるシチュエーションが考えられそう。ただそういうコーナーケースばかり考えていてもしょうがなくて、自分はまず何か一つの方針に則って設計するということを体験しなければならないはず。

勉強会の終了からしばらくして、週記が完成した。今週はなんと校閲まで済ませてある。午後8時に投稿した。ちなみに一つ前の週の週記は校閲が終わっていない。先週はその週の週記を書くことに注力していたのだ。

いよいよセミナーの準備に取り掛かろうとしたものの、眠気が強くなってきた。それでやる気も出ずしばらくTLを眺めていたが、さすがにこのまま過ごすのは効率が悪すぎるということで仮眠を取ることにした。夜中にコンテストがあるので、それまで2時間、午後9時半から午後11時半まで寝ていた。起きてすぐECR137に出た。

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

Aは $6\binom{10-n}{2}$ 。 $a$ は読み捨てた。Bは1と2を両端に置けばよい。Cは蓋をされている箱が連続する区間を求め、その一つ左を含めた中でどれに蓋をしないのが一番被害が少ないか計算。うっかり右からdpしてしまって、蓋が左隣より遠くにある箱に被せられてしまい1WA。

Dはちょっと面白い。立っている最上位bitを最も大きな値にしたいので、 $s_1$ としては $s$ 全体を選ぶのが良い。特にこの段階で先頭に1が現れるまで文字を削除しておくと便利。1が出現しなかった場合は別に処理する。次に、 $s_1$ で立っていない最も上位のbitを求める。存在しない場合はまた別処理。このbitを立てるのが次の目標になる。複数の方法がある場合は、そのうち答えが最も大きくなるものを選ばなければならない。

ここで入力がランダムであることが効いてくる。立っていない最上位のbitは上から少し探せばほぼ確実に見つかるのだ。あるbitを立てるためにはそれより上位からずらしてくる必要があるので、試すべき候補数が十分少ないことが分かった。あとは全探索すればよい。

Eは難しかった。二つのレーザーが同時に発射された直後の相手の耐久値でdpする。まず、以降二つのレーザーが同時に発射されない場合は単純な二分探索で答えが求まる。そうでない場合、次にレーザーを同時に発射するタイミングは必ず、どちらかのレーザーがちょうど何回目かのチャージを終えたタイミングになるとわかる。そもそも $h$ 回もレーザーを打てば耐久値を0にできるので、これは全探索しても $O(h)$ 通り。状態も $O(h)$ 通りなので間に合う。

Fもちょっと面白い。集合に入りうる各値について、それが入るような演算子の決め方が何通りあるか数えることにする。 $S_{i-1}$ まで決めた時点で $x$ が入っている場合の数が $a$ だとし、次の $S_i=[l_i,r_i]$ と $op_{i-1}$ について考える。これまでの決め方が $3^{i-2}$ 通りとなることに注意。

$l_i\le x\le r_i$ のとき、 $\cup\rightarrow 3^{i-2}$ 、 $\oplus\rightarrow 3^{i-2}-a$ 、 $\cap\rightarrow a$ より $2\times 3^{i-2}$ となる。それ以外のとき、 $\cup\rightarrow a$ 、 $\oplus\rightarrow a$ 、 $\cap\rightarrow 0$ より $2\times a$ となる。まとめると、 $[l_i,r_i]$ に対して $3^{i-2}$ をセットした後全体を2倍すれば表現できる。これは遅延セグメント木に乗る。

Gは面白かった。文字列の各prefixに対して、それを分割する方法を数え上げるdpをする。メモリの制限でdp配列を持つことすらできないが、実はそもそも見るべき位置が少ない。遷移してこれない位置にだけ着目すると、そのような位置から今見ている位置までの部分文字列がフィボナッチ文字列になっている必要があって、短いフィボナッチ文字列が少ないことからわかる。

ただこのままでは判定ができないので、もうちょっとインクリメンタルに更新する方法を考えた。今見ている位置までの文字列が、あるフィボナッチ文字列のprefixとなるような位置を持つことにする。これが十分少ないことは実験エスパー。特に今出現しうるフィボナッチ文字列は、 $f_0$ 以外は十分大きな、例えば $f_{32}$ のprefixであるから、 $f_{32}$ から適切な位置の文字を取得してきて今見ている文字と比較することで、その文字まで見てもまだprefixであるか否かが判定できる。長さがちょうどフィボナッチ数のprefixだった場合のみ遷移元として不適切となる。

フィボナッチ文字列から位置を指定して文字を取得するのは、フィボナッチ文字列の構成を逆に辿ることで行える。 $f_0$ の取り扱いに注意。出したら3300msで通り、全完4位。

朝までセミナーの予習をしていた。Dilworthの定理は半順序集合に対するものだが、Diestel 2.5.2の証明においては推移律しか使っていないように見える。反射律を入れても仮定は前順序というやつで十分。しかしどこを調べてもそういう内容が書いていなくて不安になった。ツイートしたらmaspyさんから同意のリプライがもらえたので、少し安心。

先週から発表の原稿を事前にメールで共有するように言われていたので、少し丁寧に書いたものをスキャンして送信。その後コードゴルフをして午前8時就寝。

10/18(火)

午前10時半にインターホンの音で起床。MHC Tシャツが届いた。注文してからまだたったの五日であるためびっくりした。

MHC Tシャツ pic.twitter.com/xZljRXqwUa
— こたつがめ (@kotatsugame_t) 2022年10月18日

その後二度寝できずずっとTLを見ていた。正午くらいに布団を脱出し、生協に寄りつつ山に向けて出発。午後1時からセミナー。

最初2時間は先生が講義で使用するスライドに載せられた演習問題を解いて議論していた。実際に解けるのか、難易度はどうかとか。特に一つ目の小問は、最初問題だけを見せられると明らかに知識が足りなかったが、スライドにある事実を認めればアイディア一発ですぐ出る問題でちょっと面白かった。行列に関する命題を、行列を構成する要素を一列に並べて数列に関する命題に帰着するというもの。

その後2時間で自分の発表。後期から教室が変わって黒板が小さくなり窮屈そうだなと思っていたものの、今くらいのサイズのほうが全体を行き来できて、それがわかりやすいかはともかくやりやすかった。関連することをうっかり黒板の両端に書いてしまったりすることがよくあるが、特に問題にならなかった。内容は途中結構質問が入ったため、昨日準備したもので時間的にちょうどとなった。予習して自分だけ理解しているからといって、ぼんやりした説明のまま進めてはいけない。

その後しばらく来週のセミナーや木曜日のTAについて打ち合わせをして解散。ホスフィンに誘われて学食に行き、1時間以上話していた。

午後7時半帰宅。非常に眠いため、早々にシャワーを浴びて布団に入った。午後8時半から午前2時まで寝ていたらしい。

食事してTAの業務。木曜日の発表スライドがもう共有されていたので、読んでコメントや指摘をした。結構丁寧にやっているのでTAとしては明らかに過剰な業務となるが、絶妙に知っているようで知らない分野なので、読んでいて勉強になる。あとは単純にスライドに対してあれこれ言うのが楽しい。

それが終わってからTCB52に参加した。日曜日終了なのでここに感想を書く。

1問目が微妙に面倒。制約の「文字列の長さが4以上」と「tech型またはful型である」というのを最初読み落としてちょっと戸惑った。2問目から5問目まではよい。

6問目はちょっと読解に時間がかかった。 $i$ 番目を含む周囲の文字から $i$ を特定する問題とわかってしまえば、左右に追加で何文字聞けばわかるか調べる方針が出る。それぞれ $l$ 文字、 $r$ 文字とすると、 $A$ の長さは $l+r+\min(l,r)$ とできる。制約が小さいのでこれでも解けるが、実は $l=0$ または $r=0$ の場合しか考えなくてよい。

7問目はSA＋LCP。各suffixがSAにおいてどこに出現するかもセグ木で持っておく必要がある。クエリごとにそれを用いてどこからどこまでのLCPを求めればいいか計算する。8問目はどのインデックスの文字を持ってくるか貪欲に決定してよい。先頭から順に最も近いものを選ぶのが最適。すると単に数列の転倒数を求める問題となる。

9問目はtrie木。10問目はABCに2値に制限された問題がある。この二つで考察が必要なかったため、普段の回と比較して高速に解くことができた。30分ちょっとで理論値達成。この合計解答時間については、「解答所要時間」ではなくコードの詳細ページから「合格経過時間」を見て和を取れば正確な値がわかることを知った。

G - Range Sort Query

しばらく日記を書いた後、少しコードゴルフをして午前8時半就寝。

10/19(水)

午後2時前起床。準備してオンライン会議に接続し、いつも1on1をしている方とのペアプログラミングに臨んだ。

コードの仕様が少し変わって今のままでは対応できないので、書き直す作業が発生しているらしい。今日はその初手の設計段階だった。早速月曜日の勉強会で学んだことが活かせる機会、に見えて、元あるコードを書き直すのを優先すべきなので、コードの構造に対して何か変更を入れるというわけではなさそう。とりあえず肥大化したファイルの分割だけはどうしてもとお願いした。

3時間くらいかけ、大まかな話がまとまりつつあるところで今日はいったんお開きに。タスクとしてはコードを読んでおくよう依頼されたが、どうせ読むならという気持ちで自分でもブランチを切って書き直してみることにした。ペアプログラミングといってもこちらはずっと手を動かしていなかったため意欲が増すばかりで、その分この後4時間くらいずっとガリガリ書いていた。

コードが動くことは確認できても、出力を生成する段階まで書き直し終えないと正しく動いているかどうかがわからないのはちょっと困る。また出力が得られたとして、その形式がこれまでと変わっているので、比較する方法についても考えなければならない。

TCO22 Finalistへのインタビューが公開されていた。顔面と本名とハンドルネームが紐づけられた状態で大公開。ちなみにこの顔写真は一ノ関駅にあった顔出し看板で撮ったもので、当時の日記にも言及がある。

tco22.topcoder.com

一ノ関駅にピカチュウのポケモントレインの顔出し看板があって、そこでもホスフィンに写真を撮ってもらった。
週記（2022/09/05-2022/09/11） - kotatsugameの日記

pic.twitter.com/U0HSTai6gE
— こたつがめ (@kotatsugame_t) 2022年10月19日

ホスフィンから競プロっぽいという論文が送られてきたので、YouTubeに気を取られつつ読んだ。タイトルになっている部分をなんとなく理解するまでで、他いくつか載っていた細かな話題に関しては見ていない。

Depth-First Search Using $$O(n)$$ Bits | SpringerLink

普通にdfsするとバックトラックのために $O(n)$ 要素保存する必要があって $O(n\log n)$ Bitsかかるが、そこを改善したらしい。改善といっても空間計算量を減らした分時間計算量に押し付けていて、 $O(m\log n)$ 時間かかっている。保存する要素を直近の $O(n/\log n)$ 要素にすることで空間計算量を減らす。するとバックトラックが行えないタイミングが $O(\log n)$ 回あるので、それらについては $O(m)$ 時間かけて頂点の訪問状態を見ながら再構築するようだ。頂点の訪問状態もまた $O(n)$ Bitsで表現できる。

まだわからない部分もある。隣接リスト形式のグラフを扱っているので、各頂点についてリストのどこまで見たかを覚えておく必要があるはず。その情報分、 $O(\log m)$ Bitsはどうやって保存するのだろうか。グラフに多重辺が大量にあったりすると $O(\log n)\subsetneq O(\log m)$ になってしまいそうなものだが。

しばらくコードゴルフした後、今日もまたTAの業務を行った。明日発表する人がそれほど時間を使わなそうということで、もう一人も少し発表する予定になっていて、その人の発表資料が共有されていたのだ。非常に面白いことが書かれていたのでぜひ図にしたいと思い、POV-Rayでプログラムを書いてGIF画像を作成した。

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

POV-Rayでアニメーションを作るのは少々面倒。基本的に一枚絵しか生成できないので、それを大量に用意してつなぎ合わせる必要があった。実行時に+KFF100などとオプションを与えると、ここに書いた数だけ生成される。画像を変化させるためには内部でclockという値を使うようだ。枚数によらず0から1まで線形に変化するので、適当に三角関数をかませることで、アニメーションらしく端でゆっくり動くような周期的な画像たちが得られるようにした。

上のツイートに貼ったGIF画像は実際に100枚連結している。これはImageMagickで作った。コードゴルフ大会で触れて以来久しぶりの登場。特に何か実装するわけでもなく、ググって出てきたコマンドをそのまま実行したら便利に動いてくれたので助かった。

少し日記を書いてから布団に入り、ラノベを読んで午前10時就寝。

10/20(木)

午後3時起床。眠気が強く、布団から脱出するまでにはしばらく時間がかかった。準備して大学へ。

教室に向かう前に生協に寄った。またしても出荷メールが届いてしばらく経つのに入荷メールが届いていない本があるので、それの確認。探してもらってみると、なんと出荷メールすら届いていない本もすでに入荷されていた。富士見ファンタジア文庫のラノベなのでちょうど今日が発売日。聞くところによると、メール送信に不具合があって一時期メールがうまく届かなかったらしい。もう復旧しているようだ。

前みたいに店頭に並べられたわけでもなく無事受け取れたので、特に問題はなかった。改めて教室に向かい、5限、TA。

一人目の発表者のスライドが60ページくらいあったのでもしかしたら今日だけで終わらないのではと疑っていたが、蓋を開けてみれば1時間も使わずに終わってしまった。必要なことが全部スライドに準備されており、もたつく様子がなかったのがすごい。

最後に付け足された発展的な内容、グラフの種数を用いたオイラーの多面体定理の一般化は非常に難しく、当人の説明の後先生に言われて自分なりに補足してみたりしたがそれでもあまり伝わった気がしなかった。どんな事実を認めてほしいか明確化するべきだったかもしれない。あとは具体例か。しかしトーラスの上に交差のないよう描かれた種数1のグラフを即座に作れるわけもなく。今考えてみれば、平面的でない簡単なグラフを適当にもってこればよかった。

余った時間で二人目。話し始めは少しまごついていた様子だったものの、一度軌道に乗った後はずっとスムーズに進められていて良かった。昨日自分が作ったGIF画像による図については、発表者の方でも何か用意してみてほしいとアドバイスをしていたが、さすがに昨日の今日では用意できていないだろうなと思っていたら、なんとすでに完成していた。GeoGebraによるもので、GIF画像に比べて手で動かせる点が優れている。

講義後しばらく、質問に来た学生と先生と話して終了。食事して午後7時過ぎに帰宅した。

しばらくYouTubeを見ていた。「総理大臣によるサーモンラン」という動画シリーズで、どういう技術が使われているかは知らないが岸田総理大臣っぽい声のスプラトゥーン実況。非常に面白い。基本的には実況らしい簡潔で的確な発言ばかりで構成されつつも、要所要所に政治家一流の迂遠な言い回しを用いているバランスがいい。時たま政治答弁みたいなゲームとほぼ関係ない話をペラペラ喋るのも面白かった。

そもそもスプラトゥーンというゲーム自体が面白いのかもしれない。初めて見るのに何となくルールが把握できるのはすごい。たまにTLで目にする「シャケ」とか「サーモン」が一体何なのか知れたのはよかった。その敵キャラを含め、命名が特徴的なのもいい感じ。

www.youtube.com

午後9時前に布団に入って就寝。起きたら午前2時半だった。ECRがあるのを完全に忘れており、目覚ましをかけてすらいなかった。マラソン以外皆勤の状態を4か月ほど維持していたのが途切れてしまい残念でならない。

意気消沈しつつもぞもぞ起きだして日記を書いていた。午前9時になって切り上げ、布団に入ってラノベを読み始める。眠れずそのまま読み続け1冊読了。

「転生魔王の大誤算」5巻。前の巻を読んでから結構間が開いたのでいろいろ忘れていることも多かったが、そもそも発売自体が遅かったためか要所要所には設定の大まかな説明があって、問題なく読み進めることができた。内容については4巻が非常に面白かったので期待していたものの、盛り上がりが物足りず残念。主人公の強みと敵の相性が悪くあまり活躍しているように感じられなかった。この敵は今後も登場するようなので、その顔出しという側面があったのかもしれない。

午後2時から1on1。水曜日にドサッと実装したので、それをお見せして判断を仰ぎたいと思いセッティングした。うっかり睡眠に失敗してしまいちょっと眠気が強い状態での会議になってしまったが、必要なところは聞けたし決められたのではないだろうか。水曜日に実装しながらメモを残していたため、うまく回らない頭でも議題を出せたのがよかった。気になっていた点のうちいくつかは、とりあえず動くものができてから考えるべきとの判断が下され、確かに……という気持ちに。ひとまず今あるコードを愚直に書き直していきたい。

しばらくコードゴルフして午後6時就寝。

10/21(金)

午前0時半起床。サークルのバチャとyukicoderをスキップしたのは、今度こそ自分の意志である。

寝る前に縮めたコードがさらに縮められていて、そこで新手が出ていた。AWKで $\max(\ast,0)$ を行う際は、先頭に文字列0を連結した後数値として解釈すればよいらしい。値が非負なら負号がないため全体が十進数として解釈されるが、負号がある場合はその直前で数値としての解釈が終了するため、0となる。

atcoder.jp

Perlにおける特殊変数$-に代入する行為も同じく $\max(\ast,0)$ 、正確に言えば $\max(\lfloor\ast\rfloor,0)$ という効果を持つが、それを利用した最短コードが大量にあることからもうかがえるように、これは非常に影響範囲の大きな更新である。というのも、これを利用することで一般に $\max(a,b)=a+\max(b-a,0)$ 、 $\min(a,b)=a-\max(a-b,0)$ と書けるからである。これまではa<b&&a=bとしていたところがa+=0b-aと書けるだけでも-1Bである上、bを変数に持つ必要がなくなればさらに縮む。

朝まで数時間最短コードのリストを探し続け、20個弱縮めた。中には8Bも縮んだものも。

atcoder.jp

午前8時から2時間ほど日記を書き、布団へ。横になって教科書を読むつもりが、少し目を瞑って考えているうちに寝落ちしたらしい。午前11時半に一瞬起きて、このタイミングで就寝報告のツイートをした。

10/22(土)

午後4時過ぎに冷凍弁当を受け取った。この前後合わせて1時間くらいは起きていた記憶がある。その後また二度寝した。

午後8時起床。しばらくコードゴルフして、午後9時からABC274に参加した。

キーエンスプログラミングコンテスト2022（AtCoder Beginner Contest 274） - AtCoder

Aはまず $\lfloor 10000B/A\rfloor$ を計算して出力する方法で解いた後、しばらくコードゴルフした。dcの出力を加工する方針には早々に見切りをつけて、printfとフォーマット文字列"%.3f"を使うのをいろいろな言語で試していたが、その方針なら当然ながらAWKが最短となる。これに気づくまで10分くらいかかった。

Bはよい。Cは入力の意味が少しややこしくて、題意も含めての把握に時間がかかった。Dは偶奇で分けると1次元の問題になり、さらに $A_1$ 以外は符号を好き勝手に決めてよい。復元が必要ないのがありがたかった。Eは巡回セールスマン問題をちょっと変えるだけ。

Fは $x$ がちょうど魚 $i$ の位置であるとしてよい。この $i$ を全探索し、すべての魚の位置を魚 $i$ に対する相対座標で表しなおすとかなり見通しが良くなった。各魚について、それが区間 $[0,A]$ にいるような $t$ 全体の集合は、 $\emptyset$ 、 $\mathbb{R}_{\ge 0}$ または両端が有理数の区間になるので、三つ目をイベントソートする。

Gはちょっと面白かった。まず監視カメラは障害物またはグリッドの端を背にしてしか置かない。さらに下向きに置いたカメラとそれが監視する最も遠いマスに上向きに置いたカメラは同一視できる。左右も同様。こうやって定めた置くべきカメラの候補について、それを置かなくてよいケースというのは、担当するすべてのマスを直交する向きのカメラで監視できている場合のみである。

ところがこうやってカメラだけに注目した言い換えをすると辛い。互いに干渉するカメラ間に辺を張ったグラフは二部グラフだし、いかにもフローで解きそうな見た目をしているのに、うまく流量や頂点の意味を設定できなかった。貪欲を考えてもすぐ反例が見つかる。しかし、この反例の図を描いているうちに「最小点カバー」という直観が得られた。

コンテスト中はこの段階で深く考えずに実装してしまったが、マスに注目して条件を観察すれば正当性もすぐわかる。各マスについてそれを監視できるカメラはちょうど二つしかなく、どちらかを設置しなければならない。つまり、その二つを結ぶ辺があって、選んだカメラ＝頂点のどれかに接続している状態。これより選んだ頂点は点カバーとなっている。

二部グラフなので最小点カバーのサイズと最大マッチングのサイズは一致する。この事実を使った記憶が以前になく、その点に面白さを感じた。

Exは解けず。ローリングハッシュも値に乱数を割り当てたZobrist HashもXORで壊れてしまう。特に後者が壊れることについては実装が終わってから気づいたため、絶望してしまった。7完20位。Gは最初にマスに注目していれば燃やす埋めるがすぐ思いつけたかもしれない。

コードゴルフ。AはAWK解を提出するまでに10分経過していたため速度差で負けたかと思ったが、最短が取れていた。BはRakuで、各マスを0と1に変換した後列ごとの和を取る方針。2次元のリストの要素を変換するに当たってはメタ演算子Xが使えず、ネストしたリストにも再帰的に適用されるハイパー演算子>>を使う必要があった。Cは今の最短コードを縮められず。以降は手付かず。

しばらく無為にTLを眺めた後、午前2時から日記を書き始めた。午前6時就寝。

10/23(日)

午前10時半起床。

二度寝するつもりだったのにグラフのcutの定義を間違えていたことに気づき眠れなくなった。ちまちま教科書を読んでいたのがやり直しに。教科書の定義はWikipediaでいうcut-setであり、自分は単に取り除くとグラフが非連結になる辺集合だと思っていた。

Cut (graph theory) - Wikipedia

1時間くらい身悶えしたあと布団から脱出。準備して牛越橋に向かった。今日はそこの下の河川敷で競プロサークルの芋煮会を行う。昼過ぎから雨が降りそうなので徒歩。

到着すると、とりあえず火だけ起こされていて、近くに住んでいる人の部屋で具材が準備されるのを待つ時間だった。適当にうろうろしていたら雨が降り出したため、橋の真下に移動。改めて火が用意され、周囲に石を積んでかまどを作りながらさらに待機した。

具材と水が入った鍋が到着し、かまどが不安定なことが発覚。金網も購入されていたものの、その上に乗せても撓んで不穏なだけなので、直火で温めることになった。鍋は二つあったので、火を分割し、それぞれの周りに改めて石を組む。鍋が乗せられるよう思ったより小ぢんまりと作られた。この辺り自分はほぼ見ているだけだった。

鍋を温めている間にかかった費用の清算。大体1万円程度と聞いていたため、先輩風を吹かせ全額出すつもりで用意してきた。金は出すから準備は任せた！という気持ちでいたが、結局その場にいたもう二人のM1、ホスフィンとha15さんとの三分割になったし、その二人は結構準備や持ち込みをしていたため、自分だけ貢献度の低い人間に成り下がってしまった。

このころが一番雨が酷かったはず。橋の下にいるので大丈夫かと思ったら、上に排水口の出口があって大変だった。鍋を温めている位置が真下から少しずれただけの位置で、風の具合によっては見事吹き込んできたため、蓋を開けるときは傘でカバーしながら耐えていた。

煮えたら味を調え、完成。食後は焼きマシュマロをしたり、金網でソーセージや餅が焼かれたりして、お腹一杯になった。うっかりワインも飲んでしまった。

食事 pic.twitter.com/dmRFMvRThm
— こたつがめ (@kotatsugame_t) 2022年10月23日

食事 pic.twitter.com/QdZs49Lmo9
— こたつがめ (@kotatsugame_t) 2022年10月23日

片付けが済んだらすぐ帰るつもりだったが、具材を用意していた部屋に数人集まるらしく、自分も転がり込んでよいようなので、そこからCFに参加することにした。ノートPCは一応持ってきてある。充電も満タンなので、2連戦には十分耐えられるだろう。

午後4時50分からCF #829 div.1。

Dashboard - Codeforces Round #829 (Div. 1) - Codeforces

A1は $n$ が奇数なら明らかに不可能で、実は偶数の場合必ず可能。二つずつ見ると、 $[a_i],[a_{i+1}]$ とすれば $a_i+a_{i+1}$ 、 $[a_i,a_{i+1}]$ とすれば $a_i-a_{i+1}$ が達成できて、どちらかは0になる。それを集めてくればよい。A2も間の0を適切に扱うことで同様のことができる。

A1からA2に書き換える際、一か所そのままにしていて1WA。今思えばこの時点ですでにアルコールを摂取したことによる判断力の低下がみられる。

Bは $a!$ を $a+1$ 個集めて $(a+1)!$ にするのを繰り返せばよい。配列で個数を数えながら計算する。これは簡単。

Cに1時間半かかって何もかもが崩壊した。初手がわからなかったため、手計算でサンプル三つ目のケースを求めようとしたのが間違いだったのか。そもそもこの計算すら失敗しまくって大変だった。最終的に正しい値が得られ、その途中計算をもとに実験エスパー＋OEISで解いた。

それぞれの0に対しその前にある1の個数を数えた列を考え、これで状態を表す。サンプル三つ目のケースを解くためにはいくつかの状態に対して答えを求める必要があったが、それらはすべて $15$ または $75/4$ になった。いかにも何かありそうだ。期待値のループを解消したときに出てくる $\binom{n}{2}$ を無視すると、値は $n$ に影響されないようなので、そこだけ観察することにした。

Rubyの有理数を使っていろいろ試してみると、 $1$ 、 $5/4$ 、 $49/36$ 、 $205/144$ 、 $5269/3600$ が登場した。まず分母が順に $k!^2$ となっていそう。その時の分子の列は $1,5,49,820,21076$ で、祈るように調べてみるとOEISに載っていた。まとめると、この数列は $\sum_{i=1}^k 1/i^2$ らしい。

A001819 - OEIS

どういう基準で $k$ が定まるのかはエスパー。作った列のうち $k$ より大きな値が $k$ 個以下しかない、という条件を満たす最小の $k$ が求めるものらしい。どういう計算になっているのか全く分からないまま実装し、AC。

残り10分ちょっとしかない。Dに進んだ。一応Cで詰まっている間に問題だけは読んでいて、空きマスの移動をグラフと見てdijkstraすればよさそうだとわかっていたものの、ダメなケースがありそうに見えてちょっとまごついていた。まあこの時間がなくても実装は間に合わなかっただろう。そのままコンテスト終了。

489位で2825→2668(-157)。ここ2回で300近くレートを落としている。2600台にまで落ちたのは去年の3月以来のこと。

次のCFまでの時間で少し感想戦を行った。Cは今ある値とソート後そこにあるべき値が異なる位置同士のswap以外無意味らしい。ソートを0だけ先頭に集めると読み替えて、0があるべき位置にある1の個数を減らしていくと見なせば自然だろうか。最初に転倒数を考えたので、そこで01列の転倒数をインデックスの差で計算する方法が思い浮かべば、もしかしたら至れた発想かもしれない。自分は期待値の線形性を利用できないか探るほうに進んでしまった。

素面だったとしても解けたか怪しい気がする。ただ、金輪際ratedの前に飲酒はしないだろう。

帰る人を見送り、15分後からCF #830 div.2。

Dashboard - Codeforces Round #830 (Div. 2) - Codeforces

Aからちょっと難しい。 $i=n-1,n$ で操作すれば条件を満たせるので、答えは3以下となる。あとは場合分け。Bは01列をソートする問題ということで、先ほどのC問題のトラウマが蘇ってきて苦しかった。連続する同じ文字を圧縮した列で実験して解いた。

Cは難しい。まず、区間を狭めてもXORの減少分が和の減少分を超えることはないため、最大値は $f(L,R)$ となる。あとは区間の幅をどこまで狭められるか。狭めた区間での $f$ の値が $f(L,R)$ と等しくなるためには、和の減少分がそっくりそのままXORの減少分に一致しなければならない。

とりあえず $a_i\gt 0$ として考えると、区間の幅を狭めるごとにXORの立っているbitが狭義単調に減っていくと言えて、制約のもと幅30も縮めればXORが0になってもう狭められなくなる。よって全探索可能。 $a_i=0$ をあらかじめ削除しておけば元の問題でも同様に計算できる。

Dは計算量が謎。深く考えずに出したら通った。どちらもオフラインで解いた。D1は $x$ に対してそれが挿入されたクエリ番号を覚えておき、同じ $k$ のクエリをまとめて倍数を調べつつ、クエリ番号を比較して早いクエリからどんどん答えを確定させていった。D2は $k$ をまとめるときにクエリ番号をsetで持ち、倍数を調べるたびそれが集合に入っていない時間帯のクエリを削除するのが高速に行えるようにした。

Eは解けず。遅延セグメント木で、更新を区間の幅に応じて二通りの方法で行った。狭い区間の場合は単に全探索。広い区間の場合は $x$ の約数を全探索し、それが $\gcd(x,b)$ となる $b$ の最小値を探す。後者については $b$ の検索部分を前計算できる。ところが全く間に合わなかった。6完12位。

2連戦を終えて残っていたとりゐさんと感想戦。Dは最悪ケースの想像がつかないので計算量がよくわからなかったのだが、やはり小さいほうに詰まっているのが大変そうという結論になった。つまりいつもの調和級数。

そろそろ帰るが、その前に部屋をちょっとうろうろさせてもらった。夕方この部屋にお邪魔したときからめちゃくちゃ広いなと思っており、興味に勝てなかった。ハリー・ポッターの本を見つけたので、自分は積んでいるのに「ハリー・ポッターと呪いの子」の話を振ってみたりした。

午後10時くらいにお暇し、コンビニに寄って解散。帰宅後疲れ切ってYouTubeを見ているうちに寝落ちしそうになったため、布団に滑り込んだ。午後11時半就寝。

午前3時に一度起きた。焚き火の煙で燻された服のまま寝てしまったため、布団にちょっと臭いが移ってしまった。とりあえずシャワーを浴びた。

TCB52が終了していた。今回は理論値達成者が多くいたが、そこでは2位に10分以上速度差を付け、全完者の中でも最速の圧倒的勝利。これで3連覇、しかもすべて理論値での優勝となった。最高の気分。

7問目は区間の幅が2以上の場合、LCPがすべて同じ文字になるらしい。気づいてみれば当たり前で、ある文字列とその先頭を削除した文字列の前からいくらかが等しい場合、その部分の文字が全部一致していなければならない。SAなど持ち出さなくても解けたようだ。

upsolve二つ。まず今日のdiv.1-D、やはりdijkstraで解けた。解説を見て正当性を理解。同じsunbetを2回動かしてしまったり、逆に2回動かさなければならなかったりする場合どうするか気になっていたが、そのようなケースはないらしい。2回目に動かそうとした時点でそこに十分なスペースができていることが、手で試せばわかる。

Submission #177691400 - Codeforces

次に今日のdiv.2-E。コンテスト中に試した2種類の更新を使って平方分割したら通った。バケットサイズガチャで4敗。バケットの中で一要素ずつ更新するには $\gcd$ を計算する必要があるので、サイズは小さめがよいかと思ったが、一つのバケットに対して計算するのにも $x$ の約数の個数だけ時間がかかるため難しい。というかなぜ通っているのかわからなくなってしまった。正しくは、各バケットとあり得るすべての $x$ に対して答えを前計算できるらしい。

Submission #177695805 - Codeforces

午前6時から4時間ほど日記を書いて就寝。