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)$ に落とした。