07/11(月)

先週の週記を投稿してから寝るまでの話。

布団に入ってから、先週火曜日に提出した離散数学の課題の模範解答がアップロードされていたことに気づいた。改めて書いておくと、最後の問題が $\mathbb{Z}_{\gt 0}\times\mathbb{Z}_{\gt 0}\rightarrow \mathbb{Z}_{\gt 0};(m,n)\mapsto 2^{f(m)}g(n)$ という全単射を構成せよというものだった。ここで $f(m)=m-1$ と決めておく。

自分は $g$ として素因数分解した後の素数を一つずつずらすような写像を考え、頑張って必要な性質を示した。しかし解答は $g(n)=2n-1$ だった。目から鱗。特に自分の作った $g$ がただ複雑なだけの $\mathbb{Z}_{\gt 0}\rightarrow \mathbb{Z}_{\gt 0}\setminus 2\mathbb{Z}_{\gt 0}$ であるということは、冷静になると当たり前なのだが、見た目からはすぐにはわからないと感じている。

まあ減点はされていなかったのでOK。無事期末レポートを無視しても満点評価が得られることになった。午前9時就寝。

午後1時起床。直後からインターン先のミーティング。僕がしばらく前に適当に書いた実験コードが以来ずっと使われていて、しかし精度を上げるための重要な処理が抜けていたため、これまでの実験結果は参考程度にしかならないということが発覚した。申し訳ないという気持ちももちろんあるが、そもそも使ったことのない処理なので自分では発見できなかっただろうし、それよりもその処理を入れると精度が目に見えて上がったということに興奮している。

少しコードを手直ししたりもして、午後3時前に終了。すぐ購買に行って菓子パンを買い込んだ。

日曜日のCF #805 div.3の順位表を見ると、open hacking phaseが終わって11位になっていた。もともと13位だったのが上がった原因は、上の人の提出が落ちたからではなく、そもそも垢BANされたからに見える。

インターン関連の作業を始めて、その途中から定例会に突入。進捗報告は直前までやっていた作業のことで、○○をどうすればいいかわからないのが現状ですと発表したのに、そのすぐ後でググったら思いっきり出てきてしまった。慌てて進捗を用意しようとしているのがバレバレ。

ちなみにやっていたことは、エクセルファイルのブックをまたぐシートのコピーに関する不具合の修正。コピー後のセルの色がおかしなことになるケースがあって、調べていくうちに、色データがセルの書式というよりはブックに紐づけられた概念であることが発覚した。具体的には、ブックごとに数値→色という変換マップが存在して、セルの書式では変換前の数値で持っているらしい。

シートのコピーを実装したのは、日記によればもう5か月も前になるが、その時点でセルの書式がブックに紐づくものであることは知っていた。書式をブック間でコピーする関数があったのでこれを使えば全部解決と思っていたものの、実は色については数値の形式でコピーされていたようだ。コピー元とコピー先で先に述べた変換マップが異なるケースがあり、色がおかしなことになってしまっていた。正しくコピーするために色をRGB値から指定する方法を探し、見つかっていない状態で進捗報告の発表をしたのに、直後にググったら出てきたということ。

ブックをまたぐシートのコピーの難しさについて。
週記（2022/01/31-2022/02/06） - kotatsugameの日記

勉強会まで終えてから大学の課題に手を付けた。離散数学とハードウエア基礎は今期の講義が終了したようなので、あとはゲーム理論だけ。今日提出なのは第12回の課題で、これは教科書12章に対応している。課題となっているのは教科書の演習問題だが、本文でやったことを数値を変数に置き換えた状態でそのまま写すだけに見える。簡単。

すぐ終わったので、しばらくYouTubeに気を取られてから第13回の課題も終わらせることにした。教科書13章はエピローグみたいな位置付けなので何をやるのかと思ったら、なぜかまだ12章をやっていた。どうやら前後半に分けていたらしい。別に分量もそう多くないはずだが……。ともかく今度も演習問題で、こちらは図を描いたりと多少面倒だった。眠気に耐えつつ日付が変わったくらいで完成。

これで教科書を全部終えたのだから、多分今期の課題は終了だろう。本当は数理論理学特論という僕の指導教員の先生が担当されている講義も取っていたのだが、これは一度も出席できていないためほぼ放棄している。

ゲーム理論もハードウエア基礎も扱っている概念は初見だったものの課題は取り組みやすかった。なぜかというと、ある問題とその未知の解があったとき、解の存在証明ではなくそれを発見するためのアルゴリズムが講義で説明されていたからだと思う。詳しい理論まで理解が及ばずとも書いてある通りに手を動かせば解けてしまうのだから、楽しいかどうかはともかく楽だった。

ラノベの新刊チェックをして20冊ばかり注文した。1巻を買って、積んで、2巻を買い忘れていたラノベの3巻が発売されるようだったので、2巻とともに注文しておいた。自分が当時の新刊チェックで見落としたということが信じがたかったし、また「ある本を自分が買っていないこと」の判定は難しい。買ったラノベのリストはブログ記事にしているものの、ないことを判定しようとすると書き忘れが怖い。本棚をひっくり返しても見つからなくて、やっと買っていないことを納得した。

午前2時過ぎ就寝。

07/12(火)

午前8時起床。今日はゲーセンに行きたいのだが、まだ眠気があるため二度寝もしたい。とりあえず二度寝優先で、眠気を待ちつつラノベを開いた。

1冊読了。「同い年の妹と、二人一人旅」。旅ラノベということで風情があるなあと思って購入したものの、あまり風景描写に興味が持てなかった。そもそも旅に興味がないのかとも思ったが、例えば2chの旅スレまとめを読んだこともあるので、それを文章とイラストだけで表現するのが肌に合わなかったのだろうか。写真を見てなんぼという気持ちがある。

別のラノベを開いたりYouTubeを眺めたりしてから午後1時になってようやく二度寝。その後午後3時くらいに目覚ましをかけていたはずが起きられず、午後5時前にようやく目を覚ました。すぐ準備して家を出る。今日は夜遅くになると雨が降るらしいので、地下鉄を使った。

まず食事。つけ麺屋。連れだって訪れた客を並んで座らせるため、という店の都合で席を移動したところ、海苔をサービスしてもらった。

ヒルベルトの無限ラーメン屋は人が一人来るたびに無限人が席を移動するためサービスの海苔が無限枚必要らしいです
— こたつがめ (@kotatsugame_t) 2022年7月12日

いざゲーセン。今日は新曲だけ。14+が3曲通常開放されたので詰めて、SSS、AJを一つずつ出した。もう一つ、「Re：End of a Dream」はまだSS+。14+の全鳥が剥奪されてしまった。

脳天直撃 SSS
ラストのトリルの速さを分かっておらず無事SSS+割って涙 pic.twitter.com/ZkqhG7gO3b
— こたつがめ (@kotatsugame_t) 2022年7月12日

数回で出た。BPMが遅いので案外押せた。ラストのトリルがどれくらいの速さか分かっておらず、そこで確か0-2出したはず。もったいないのでSSS+を狙おうとしたものの、以降SSSすら出なくてびっくりした。どうやら数回で出たのは運がよかっただけらしい。

色彩過剰のダイアリーミュージック AJ pic.twitter.com/vTCvKsHKnD
— こたつがめ (@kotatsugame_t) 2022年7月12日

以下のツイートにある2枚目の画像（51、52小節目）は黄タップを無視し赤タップを両手で取るだけでよいということを聞いていたのに、配置を覚える前にそこ以外全部揃ってしまった。しかしAJが狙えるということが分かったため、頑張ってみた。

ここで全部出た pic.twitter.com/GNfbUaetj4
— こたつがめ (@kotatsugame_t) 2022年7月12日

実際に両手で取ろうとするとたまに抜けるので、TLで助けを求めたところ、左手小指をスライダーに固定しておくと抜けないと聞いた。どうやらトリルに合わせて小指がズレて、黄タップを擦っているのと同じ判定になるらしい。これで結構安定した。

プレイするうちに中盤がボロボロ崩れてきてもう大変。ついにラストの配置にも癖がつき始めた頃合いで出た。最高精度でラッキー。この時のラストは緊張もあってリズムが完全に頭から抜け落ち、本当にギリギリで押せていた感じだった。

午後11時前に離脱。予報通り雨が降っている、どころか土砂降りだった。急いで帰宅してシャワーを浴びたら、午後11時半からのCF #806 div.4にギリギリ間に合った。

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

Aは条件式を頑張って書いた。最初に大文字あるいは小文字に揃えた場合とどちらが速く書けたかは微妙なところに思える。Bはやるだけ。Cはサンプルを見て題意を把握した。Dは前半の文字列長を全探索。存在判定はsetの定数倍がちょっと怖かったのでソートしておいて二分探索した。Eは回転させて一致するマスを列挙し、0と1のどちらに揃えるか決める。すでに見たマスにフラグを立てておけばどこをスキップするか考えなくてよいし、中心だけ特別扱いする必要もない。Fは $a_i\lt i$ なる $i$ だけ集めたあと、それらの中で $i\lt a_j$ を満たす $(i,j)$ を数える。 $j$ ごとに二分探索した。

Gは30回badな鍵を使った段階で得られるコインがなくなってしまうため、それ以上の回数を同一視してよい。よってbadな鍵を使った回数を持つdpが可能。上限を20回にしていて1WA、気づいた後余裕を持って40回に増やしたところint型に対し最大で幅40の右シフトをすることになり、これは壊れてしまうらしくさらに1WA。特に2WA目は未定義動作っぽかったもののまさか本当にそこで落ちているとは信じられず、出し直してACするまでにかなり時間がかかった。

open hacking phase開始時点で25位。Gのせいで1ページ目から陥落した。残念。

今日は画面とマイク音声を記録していたので、コンテストの残り時間で編集して、終了後に投稿した。パソコンの前に座ったのがコンテスト開始ギリギリだったため、何とかマイクの設定まではできたもののページサイズを変えるのを忘れていてショック。そのうえG問題で詰まりまくってしまったためボツにすることも考えたのだが、無事全完はしているのだし、たまにはへなちょこなのもいいだろうと思って公開した。

www.youtube.com

少し日記を書いた後YouTubeを見ていた。

にじさんじ甲子園という大規模コラボイベントが現在進行中である。参加するVtuberがほかのVtuberをモデルにした野球選手をパワプロで作り、対戦するというものらしい。ここで、モデルにするVtuberを決めるのにドラフト会議という形式を取っている。パワプロには興味がないのだが、ドラフト会議で決定したチームを描くファンアートは非っ常～～～に良かった。すでに存在するコラボユニットが集まったり、これまでなかった組み合わせが生まれたり。ハッシュタグで検索してニヤニヤしている。

#にじさんじアルプススタンド - Twitter Search / Twitter

布団に入ってから、ハーメルンを読み返したり捜索掲示板を徘徊したりして眠いのに3時間ほど起きていた。午前6時を回って就寝。

07/13(水)

正午、エリアメールの爆音で目覚める。雨がヤバいらしい。

TCO22のR4にStage3とR3で2回進出を決めているのがほかのユーザにバレていた。TopCoderのDiscordに以下のような投稿があった。Stage3の結果はメールで通知されていなかったので、うっかりR3に出てしまうのはしょうがないはず。俺は悪くねえ！まあ、自分がR3開始前にR4に進出したことを知っていたのは日記やTwitterから読み取れてしまうのだが……。

バレてて草 pic.twitter.com/aO3j3b3JCG
— こたつがめ (@kotatsugame_t) 2022年7月13日

ハーメルンで新しい作品を読み始めた。ずっと読み続けていて、午後4時くらいにまた寝た。

午後9時半に再度起床。TLでTCO regionalのメールが届いた人を観測したため意気揚々とメールボックスを開いたものの、自分のところには来ていなかった。迷惑メールもチェックしたが、ない。TopCoderからのメールはいくつか受け取る設定になっているので、単純にお呼ばれしていないということのようだ。残念。もしかして上に書いたズルのせいか？

代わりにと言っては何だが、DDCCの本戦に進出できていた。ちなみに全完は40分弱だった。TLを見る感じこのタイムなら一般枠でも結構余裕だったらしい。

布団でずっとハーメルンを読んでいたが、さすがに明日のセミナーの準備をしないとまずいと思い、午前3時ごろにようやく身を起こした。

まずDDCC本戦に出場するためGoogleフォームを埋めた。会場に向かうためどの駅を使うか選択する項目があって、去年は参加記によれば大森海岸駅だったらしいが、調べると大森駅のほうが新幹線からの乗り換えが少ないようだ。今年はそちらにした。24卒ということで交通費が出るため、指定席に乗ることにして料金を計算。往復で2万3千円ちょっとだった。

シャワーを浴び、食事し、昨日投稿した動画のサムネイルを設定。open hacking phaseを終え、25位から変わらなかったようだ。良い順位ではないため今回は表記していない。

ほかにやることもなくなり逃げ場を失ったため、満を持して教科書を読み始める。午前5時だった。そこから準備を続け、午前10時半に就寝。

07/14(木)

午後2時半ごろ気合いで起床、すぐ出発。いつの間にか駐輪場の工事が始まっていて、原付を停める場所に少し苦労した。

セミナーの発表はいい感じ。ちょっとメモを見る回数が多かったかなと思うが、それ以外はスムーズに進んだ。準備の一部でHallの結婚定理を5通りの方法で示したのだが、これは時間がなくて一つだけ説明するに留まった。5通りも用意したのは教科書に書いてあったということ以上に発表時間が余らないようにするという目的だったので、そういう水増しをしなくてよかったのは良いこと。

二つの集合が一致するのを示す部分で両方向の包含関係を見たのだが、先生の指摘でもうちょっと簡単になることが発覚した。片方の証明が実は同値変形に書き換えられて、結論から仮定へも辿れたということ。この辺りはちょっと意識が行き届いていなかったなと感じる。手を動かしたら示せるので手を動かした、というだけでは発表として物足りない。ただこれも徹底するのは難しいポイントである。

終わってから黒板の写真を撮った。

pic.twitter.com/4XzGVEv7J6
— こたつがめ (@kotatsugame_t) 2022年7月14日

学食で食事して帰宅。降水確率40%でちょっとビクビクしていたが、何とか天気は崩れなかった。

帰宅してからは疲れ果ててPCの前から動けず、ずっとネットサーフィンしたり動画を見たりしていた。

www.youtube.com

日付が変わってから布団に入り、さらにしばらくスマホでYouTubeを見ていたようだ。午前1時半就寝。

07/15(金)

午前8時起床。ハーメルンを読み続け、正午就寝。次に午後3時起床。

即座にインターンのミーティング開始。以前タスクがないことをメンターの方に伝えておいたのだが、この度別の方の元に手が回らないタスクがあるということで、その方とのミーティングだった。ちょっとしたヒアリングと、大まかなタスクの内容について説明を受けた後、必要なコードを手元で動かす準備をした。新しくライブラリをちょっとばかり入れるだけで動いたのは楽でよかった。

しばらくYouTubeを見てから、ゲーム理論の課題をこなした。月曜日に今期の課題は終了だろうと自信満々に書いたのに、いつの間にか第14回の講義スライドと課題が出ていて目を剥いた。スライド冒頭を見ると教科書11章と書いてあって、なぜ戻っているのかと首を傾げていたが、内容としては教科書に書いてないことをやっているように見える。課題はちょっとした証明で、詳しいことまで理解せずともスライドと同じことを同じようにやればいいため簡単。面倒でもない。

午後7時半から午後10時まで布団に戻って寝ていた。シャワーを浴びて、午後10時半からCF #807 div.2。序盤はサイトが不安定で、B問題から軽量サイトのほうで提出していた。

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

Aはソートして $\forall i.\;h_i+x\le h_{i+n}$ を判定。Bは左端から動かしていくことで基本的に $\sum_{i=1}^{n-1}a_i$ 回の操作で達成できる。ただし途中に $a_i=0$ なる $i$ があったらそれぞれ1回操作して埋める必要があるので、その分増える。埋める時も端から移動させればそれ以上余計なコストはかからない。

Cは毎回操作を後ろから全部見ることで、求める文字の最初の文字列における位置を求める。このとき各操作ごとに文字列長を求めておく必要があるが、上限が制約にないのでオーバーフローに気を付けなければならない。と思っていたものの、最大でも $n\times 2^c\lt 2^{18}\times 2^{40}=2^{58}$ にしかならないので大丈夫だった。日記のこの部分を書いているときに気づいた。

Dはちょっと時間がかかってしまった。文字列の隣接XORを取ると $01\leftrightarrow 10$ という操作に言い換えられるので、あとは先頭から $1$ の位置を合わせていけばよい。

Eはかなり手間取った。セグ木の区間 $[l,r)$ を表すノードに $r-1$ の個数・ $r-1$ をもう一つ作るために必要な $l-1$ の個数・それ以上 $r-1$ を作るために必要な $l-1$ の個数（ $=2^{r-l}$ ）を持たせることで、ノードのマージが行える。あとはセグ木上の二分探索で答えが求まると思っていたのだが、 $r-1$ の個数がゼロか非ゼロかに単調性がないことに気づいた。追加で答えも持つようにするだけでよかったのに、ここで実装方針を大きく切り替えてしまった。

操作を可能な限り行った後にどの値が残っているかを持つことにした。区間をsetで管理することで効率的に扱える。しかしサンプルを合わせて提出するとREになってしまい、このデバッグに非常に時間がかかった。最終的に小さめのランダムケースでもすぐ再現することに気づいて、それを見ることで何とか直せた。バグの原因はif-else文で処理を切り替える際、条件判定の途中でイテレータを弄るため最初のif文だけ二重になっていて、内側のif文に入らないうえ外側のelse文も実行されない場合があるというものだった。

Fは乱択アルゴリズム。最初にランダムなTF列を用意してクエリを出力する際にXORすることにすれば、以降求める答えもランダムなTF列だと見なしてよい。まず全部Fの場合を聞いて、以降 $W$ 文字ずつ決めていくことにする。bitDPで計算したところ、 $W=4$ のとき平均2.625回のクエリで決定できることが分かった。この時 $n/W\times 2.625\le 1000/4\times 2.625=656.25\lt 675$ なので、ギリギリQLEしないはず。とりあえずプレテストは一発で通った。

DEで詰まったもののFを通して、システス後も全完のまま11位。Fはシステス中に手元で回していたら何十回に1回QLEしてしまうことが分かったが、何とか通ってくれた。実は $W=9$ とするとちょうど6回のクエリで必ず決定できるらしい。そこまで行くとさすがに全探索できない。 $W=4$ だと実行時にbitDPすることで答えを埋め込まずに済んだ。

その後午前10時まで必死に日記を書いていた。今週は月曜日から溜めてしまっていた。そういえばICPC国内予選の参加記も書いていない。何もかもハーメルンが面白すぎるのが悪い。

「黄金の経験値」が書籍化するらしい。

https://ncode.syosetu.com/n0806fu/

【朗報】
黄金の経験値さん、カドカワBOOKSより書籍化が決定した模様
— 原純 (@harajun1001) 2022年7月15日

布団に入って2時間ほどハーメルンを読み、1作読了。「二郎になりました…真君って何？」。

syosetu.org

Fateシリーズの二次創作で完結している。面白かった。主人公は半神半人で5000年近く生きている。良い。古代スタートということで、原作前は主人公が歴史に介入していく感じで自分の好みだった。原作スタート後は急にキャラが増えたりしてちょっと置いて行かれ気味だった。原作を知らないが故の苦労。

大体好みだっただけに、後半の主人公の行動が気になる。何物にも邪魔されないだけの圧倒的な力を持って好き勝手行動しているとされながら、結構ポンポンと人を助ける描写が入るのがあまり好みではなかった。自分の興味関心の向く先以外ではもうちょっと腰が重くなるような性格だと嬉しい、気がする。かと言って自分とその仲間のことだけ考え、周囲の迷惑を顧みないような主人公も気に入らないはず。自分の中の基準が一体どのあたりにあるのかよくわからなくなった。

正午ごろ就寝。

07/16(土)

午後3時半ごろ、生協の冷凍弁当を受け取った。直後からまた入眠することができ、最終的に午後8時に起床。シャワーを浴びたり食事したりして午後9時からARC144に出た。

AtCoder Regular Contest 144 - AtCoder

Aは題意を掴むのに少し時間がかかった。まず $x=\frac{10^N-1}9$ を考えることで $M=2N$ とわかる。このとき $x$ としては2倍したときに繰り上がりしない数であればなんでもよいはず。このあたりでサンプルを確認し、思った通りになっていたので実装、AC。Bは二分探索。最近のARCらしくないド典型だと感じて、見落としていることがあるのではないかとちょっと提出をためらった。

Cは思ったより難しかった。辞書順最小のことを忘れると、 $K+1,\dots,N,1,\dots,K$ という並べ方が一番素直。これでダメならダメだろう。このとき $1$ の位置を見て $(N-K+1)-1=N-K\ge K$ である必要がある。つまり $2K\ge N$ 。さて、 $K=1$ の場合は $2,1,4,3,\dots$ のような形になる。ここから類推すると、最初に数列 $1,\dots,N$ を用意したあと $\frac{N-2K}{2K}$ 回、前から $2K$ 要素を切り出して前半と後半を入れ替えるのが最適になるはずだ。

最後に残った $2K$ 個以上 $4K$ 個未満の要素については、一番初めに作った $K+1,\dots,N,1,\dots,K$ のような並びにしかなれないと思った。これを作って提出したところ、WA。慌てて全探索のプログラムを書き出力を比較してみたところ、 $(N,K)=(7,2)$ で間違っていることが分かった。 $3,4,1,6,7,2,5$ が答えのところ、 $3,4,5,6,7,1,2$ を出力してしまっている。

$1,2,3,4,5,6,7\rightarrow 3,4,1,2,5,6,7\rightarrow 3,4,1,6,7,2,5$ という変換がされていると考えられる。つまり、 $2K$ 要素を切り出すのを $\frac{N}{2K}$ 回行ったあと後ろ $2K$ 個の前半後半をswap。ただしこれも常に行うというわけにはいかなかったので、前から切り出し終わった残りの個数を見て $0$ 個ならそのまま、 $1$ 個以上 $K$ 個未満なら少し巻き戻して最初に提出したのと同じものを作り、 $K$ 個以上のときだけ満を持してswapした。小さいケースを念入りに試してから提出し、無事AC。

Dは難しい。まず、 $f(0)$ と各 $f(2^i)$ を独立に決めたとき、任意の数 $x=\sum_{i\in I}2^i$ （二進法で書いた形）について $f(x)=\sum_{i\in I}f(2^i)-(\#I-1)f(0)$ が成り立ち、かつ問題文にある二つ目の条件が満たされることが分かった。あとは一つ目の条件。常に $f(0)=0$ なら簡単なのになあと思ったが、全然そんなことはない。

$f(x)$ の最大値と最小値を考えたい。ここで、各 $f(2^i)$ を $f(0)$ と比較してみる。 $R=\{0\le i\lt N\mid f(2^i)\gt f(0)\}$ 、 $L=\{0\le i\lt N\mid f(2^i)\lt f(0)\}$ とおいたとき、 $f(x)=\sum_{i\in I}f(2^i)-(\#I-1)f(0)=\sum_{i\in I}(f(2^i)-f(0))+f(0)$ であることから、 $\max f=\sum_{i\in R}(f(2^i)-f(0))+f(0)\le K$ かつ $\min f=\sum_{i\in L}(f(2^i)-f(0))+f(0)\ge 0$ となることがわかる。

簡単のため、 $a_i=f(2^i)-f(0)$ とおこう。元の問題は $f(0)$ と各 $a_i$ を $S_R=\sum_{i\in R}a_i\le K-f(0)$ かつ $S_L=\sum_{i\in L}a_i\ge-f(0)$ を満たすように決めるものと書き直された。

$0\le f(0)\le K$ は全探索できないため、しなくてもよい方法を考える。 $S_L\ge-f(0)\Leftrightarrow-S_L\le f(0)$ と $S_R\le K-f(0)$ を辺々足すことで $S=S_R-S_L\le K$ が得られる。ここで実は $S=\sum_{i=0}^N|a_i|$ となっている。またこのとき $0\le-S_L\le f(0)\le K-S_R\le K$ を満たす $f(0)$ は $K-S+1$ 通りある。これで $f(0)$ を決め打たなくてよい上、 $S_L$ と $S_R$ の区別には興味がなかったことが判明し、 $|a_i|$ とその符号を決める問題に帰着された。

符号を考える前にまず $a_i=0$ の場合を取り除く必要がある。 $a_i\ne 0$ なる $i$ が $0\le n\le N$ 個あったとする。 $a_i=0$ なる $i$ の決め方は $\binom N{N-n}=\binom N n$ 通りであり、それ以外のものについて符号の決め方は $2^n$ 通りある。次に、各 $n\le S\le K$ に対し、 $n$ 個の正整数の列であって和が $S$ となるようなものの場合の数を求める。これは写像12相の一つとなっており、 $n=0$ の場合を取り除けば求める数は $\binom{S-1}{n-1}$ である。さらに $f(0)$ の決め方 $K-S+1$ も掛け合わせる。

まとめて、 $n=0$ の場合を足し、 $K+1+\sum_{n=1}^N2^n\binom N n\sum_{S=n}^K\binom{S-1}{n-1}(K-S+1)$ が答えになると分かった。内側の $\sum$ をWolfram|Alphaに投げると無事閉じた式になったため実装し、AC。 $K$ が大きいのでcombinationは $n$ を増やすごとに比を考えて少しずつ更新していく形にした。コードはかなり短くなった。

Eは解けず。始点と終点が同じで途中に $A_i=-1$ なる頂点 $i$ を通らないような経路をいろいろ求め、それらの差を取って $\gcd$ を計算しまくり、最後に適当な $1\rightarrow N$ の経路とも $\gcd$ を取れば答えになると考えたものの、高速に計算できているわけでもないし答えも全然合っていない。結局4完39位だった。

Dの解法を一所懸命に説明したのに、公式解説とだいたい同じになってしまった。どうやら数え上げ方はほぼ一本道らしい。コンテスト中はその道を探していろんなところを行ったり来たりしたものの、こうやってある程度整理して説明しようとすると自然と収束していく。

コードゴルフ。Aはdc。Dはコンテスト中に求めた式をRubyで求める、コードをVimで作った。Bはシンプルな二分探索のコードがRubyで提出されており、縮みそうにない。他は手付かず。

午後11時半からCF #808 div.1に出た。

Dashboard - Codeforces Round #808 (Div. 1) - Codeforces

Aからちょっと難しかった。コンテスト $1\dots n-1$ のどこかでIQが $0$ になるなら、代わりにコンテスト $n$ で $0$ になるとしても損しない。こうするとコンテスト $n$ 開始時点でIQが少なくとも $1$ である必要があって、特に $2\rightarrow 1$ となる瞬間があったならそれもできるだけ最後に近いコンテストであるとして問題ない。そうやって後ろから見つつ、今見ているコンテストが始まる時点での必要IQを（ $q$ を超えないように）管理すればよい。

Bは謎。1回操作すると $\sum a$ が元の数列における $a_n-a_1$ になると分かった。それらをソートしてランレングス圧縮すると要素数は $O(\sqrt{a_n-a_1})$ 。こうなると同様にして残り $n-2$ 回愚直に操作してもよさそうに見える。これ以降の要素数はうまく見積もれなかったものの、とりあえず常に $O(\sqrt{\max a-\min a})\subset O(\sqrt{a_n-a_1})$ であり、また $\max a-\min a$ が減らなくなったら $a$ はほとんど $0$ になっていることもわかる。 $a_n$ に制約がついているのも使えているため、ある程度自信を持って提出できた。

Cは最小全域木を取って $1\dots n$ のそれぞれを根としたとき、最小全域木に含まれなかった辺であって端点が先祖・子孫の関係にないものがある場合のみアウト。これを判定するため、含まれなかった辺 $(u,v)$ について、その辺のせいでアウトになってしまう頂点にマークすることを考えた。 $uv$ パス上の頂点のみがそうだと思ったものの、サンプル2が合わない。 $uv$ パス上の頂点から別の方向に向かって出ている辺の先の部分木もマークしなければならないことに気づいた。

これは難しいので、逆にアウトにならない頂点にマークした。 $u$ から見て $v$ の方向以外にある頂点と、その $u$ と $v$ を逆にしたもの。木上のimos法で計算することにすれば、基本的には頂点 $u$ と $v$ に $+1$ するだけでよい。 $u$ が $v$ の先祖（あるいはその逆）の場合だけちょっと面倒で、 $u$ から $v$ に向かって1歩進んだ頂点が必要になる。LCAをダブリングで計算するのと同様に求められるため、OK。

Dは解けず。2乗の木dpに見えるもののマージが書けない。左の部分木から頂点が消えるのと同時に右の部分木から頂点が消える場合を処理するのが非常に難しい。とりあえず計算量を考えずに書いてサンプルは合ったものの、そのままでは高速化できない。 $S_1=S_2$ を許して解いてから除原理っぽく計算すればいけそうだと思ったが、具体的な計算方法がわからずコンテスト終了。

システスは全部通って3完39位、レートは2964→2959(-5)。Cまでがそこそこ速かったので助かった、か？ARCと同じ順位だったのは面白い。

午前9時まで日記を書いていた。ちゃんと月～土の部分の校閲まで終わらせることができたので、日曜日に必死になって2万文字読み返す必要はない。2万文字と書いたが、果たして今週の週記はそれだけ肥大化するだろうか？いまここを書いている時点でおよそ1万5千文字であるが、明日はOpenCup＋ABC＋Lunchtimeと盛りだくさんなので1日で5千文字くらいは増えそうな見込み。

明日のコンテスト開始まで、直前の準備を考えても7時間ちょっとの睡眠時間がある。案外余裕だなと思って布団に入ってから新しくなろうを読み始めた。これが面白くてなかなか止まらず、就寝が午後1時半になってしまった。愚か者め。

07/17(日)

コンテスト開始時刻である午後5時の直前まで起きられなかった。当たり前。

なんで布団に入ってからの7時間を4時間なろう3時間睡眠と振り分けてしまったのかがわからない。本当に助けてくれ
— こたつがめ (@kotatsugame_t) 2022年7月17日

すでにフラフラの状態でまずは1戦目、久しぶりのOpenCup。今日はGrand Prix of Seoul。チームでMADHGFJCEKをこの順に解いた。僕はADCの考察・実装とEの実装をした。

Aはbitで状態を持ってBFS。Dは平面に縦横合わせて3本の直線を引き、乗っている点の重みの和を最大化する問題で、座標軸を入れ替えることを考えれば縦3本と縦2本・横1本の場合が解ければよい。このうち前者は自明。後者は横の直線を全探索して、それに乗る点を逐一取り除きつつ上位2要素を持つセグ木で縦線を決める。縦横がちょっとややこしかったが、何とか書き切ってみるとそのまま通った。

Cは平面上の点をクラスタリングするアルゴリズムに関する問題。まず中心を2点決めて、各点を近いほうの中心に対応する集合に入れ、次に各集合におけるX座標・Y座標の中央値を求めて新しい中心にする、ということを繰り返す。最初に決めた2点に応じて何ステップでどんな中心の組に収束するか求めよというもの。実は単純なメモ化再帰でよい。なぜなら、このような分け方は点たちをある直線で分割した形になり、そのような分割のされ方は $O(N^2)$ 通りしかないから。この事実は今年3月のCook-Offで見た。

遷移の種類は高々N2N2個らしい。
週記（2022/02/28-2022/03/06） - kotatsugameの日記

内部で分割し新しい中心を求めるのはnth_elementを使えば $O(N)$ で書けて、合わせて $O(N^3)$ 。TLEしてひっくり返ったもののオーバーフローを見つけて、無事2回目の提出でAC。

Eは面白かった。じゃんけんの手の列があって、勝ち負けを比較関数だと思ってバブルソートする問題。より正確に書けば、1回の操作では隣接する要素を先頭から順に見て、それぞれ前の手が後ろの手に勝つならswapする。この操作を $T$ 回繰り返した後の列を出力する。

最初に1回シミュレートするのがかなり上手い考察方針で、列が分割できることに気付けた。例えば先頭がグー（R）だったとき、グーが追い抜ける手であるチョキ（S）とRSRRRSSRのように交互に出現する部分をその後ろ（パー）から切り離すことができる。

このような列に対して $T$ 回操作した後の状態を考えるのは、ランレングス圧縮して考えると見通しが良い。例えば上の列は $[1,1,3,2,1]$ に変換されて、これに操作を繰り返すと $[1,1,3,2,1]\rightarrow[0,1,3,2,2]\rightarrow[0,1,2,2,3]\rightarrow\dots$ のようになる。かなり綺麗にまとまって、実装は一瞬で完成した。

午後9時前にフェードアウトして食事し、ABC260に出た。

AtCoder Beginner Contest 260 - AtCoder

Aはうまい書き方が思いつかず、結局種類ごとの文字数をカウントして解いた。この問題を含め、今日は全部C++だった。Bは面倒なだけ。Cは $(r,b)\rightarrow(r,b+Xr)\rightarrow(r+b+Xr,(b+Xr)Y)$ という変換を繰り返す。それぞれレベルが $(n,n)$ 、 $(n-1,n)$ 、 $(n-1,n-1)$ に対応している。何か閉じた形で表せるのかと少し考えてみたが、少なくともきれいにはならなかった。

Dは場に見えているカードをsetで管理。それぞれの山はvecterで管理して、カードからvectorが取得できるようにインデックスを記録して……と考えていたが、そういうテクいことをしなくても直下のカードだけ記録しておけばよい。

Eはよい数列の右端 $r$ を全探索し、左端としてありうる最も右の位置を計算。組 $(A_i,B_i)$ に対して $L_i$ を $r\lt A_i$ なら $0$ 、 $A_i\le r\lt B_i$ なら $A_i$ 、 $B_i\le r$ なら $B_i$ と定めたとき、求める位置は $\min_i L_i$ になるので、 $L_i$ をsetで管理しつつ差分更新した。

Fはよく見ると $T$ が小さいので鳩ノ巣原理。このタイプの鳩ノ巣原理は何度も見ている。メモをmapで行ったら $O(T^2)$ 回のアクセスでTLEしてしまい、vectorに十分多く要素を詰め、ソートして重複を探したら通った。後から気づいたが普通に2次元配列でよかった。Gは縦横無尽にimos法を行って全マスに対する答えを求めておく。 $N\times(N+2M)$ の配列が必要になってかなり怖かった。

Exには手も足も出ず。FPSをこねくり回すのだろうなと思っただけ。どうやらみんな解けなかったようで全完は一人しかおらず、Gを通した時点で2位だったのがそのまま保存されて7完3位だった。

少しコードゴルフして午後11時半からCodeChef、July Lunchtime 2022 div.1。もう体力ゼロなのにここから3時間と聞いてそこそこ絶望した。

https://www.codechef.com/LTIME110A

LARGEFAMは簡単。子が少ない人を優先的に使っていけばよい。

STRINGXORはちょっと難しかった。まず $A$ に $1$ がない場合を取り除いておく。 $1$ があるならそれを使って操作を繰り返すことで全部 $1$ にできるので、そこから $B$ を作ることを考えてみる。 $111\rightarrow 110,011$ であるが $111\not\rightarrow 010$ であるということから、 $0$ を作るときはどこかの $11$ に押し付けるようにしなければならないことがわかった。

$B$ に $11$ があればそこに押し付けて変換可能。ない場合も、 $11\rightarrow 00$ を考えると $B$ における $00$ を $11$ だと思ってよいことになるため、 $00$ が代用できる。逆に $00$ も $11$ もないとき、そもそも $B$ は操作を1回以上行った後の列ではない。よってこのときも $A$ に $1$ がない場合と同様、初期状態で $A=B$ か判定すればよい。

BINHAPPは少し手間取った。まず、文字列のbeautyとは $1$ の個数から $0$ の個数を引いたもの（と $0$ の大きいほう）である。実際、分割後の列はそれぞれこの値が正になっているため足すとbeauty以上になり、一方beautyがちょうど $1$ であるような部分文字列を先頭から切り出し続けることで一致させることができる。happinessは連続部分列におけるこの値の最大で、全体・左端・右端・内側の組がモノイドになるためセグ木に乗り、文字列の連結操作が入っても解ける。

しかしここで連結する順番をバラバラにしてよいのに悩まされた。最初はモノイドのop(l,r)を計算するときにop(r,l)も計算して最大値を採用すればよいかと思ったが、これでは自由度が足りないようだ。つまるところ、区間から「左端」だけ使うもの一つ・「右端」だけ使うもの一つ・「全体」を使うものいくつかを選んで足し合わせていると見なせて、すでに左右が埋まった「内側」に新しく「全体」を足す場合なども存在すると気づいた。ただし、一つの文字列だけで完結してしまう「内側」に「全体」を足すことはできない。なので「内側」を2種類持つことにして、何とか3回目の提出でAC。

TREERETは謎。2点 $u,v$ を選んでもう1点と合わせて聞くことで、その点が $uv$ パス上の点か、 $uv$ パスの内側から生えた部分木の点か、 $u$ から見た $v$ の子か、 $v$ から見た $u$ の子かの4状態に分けられる。パス上の点は二分探索で整列させることができる。そこから生えた部分木の点はどこから生えているのかを二分探索できる。よっていくつかの部分木に分割できたので、それぞれで再帰的に解いた。これを提出したらもともとの制約の場合のみQLEして56点だった。

手元の二分木で試すと2000回ほどオーバーしているらしい。やはり3頂点しか聞かないというのは無駄が多そう。少しいじっているうちに別方針を思いついたので、そちらを実装することにした。クエリの答えが $\sum_{s\in S}s$ になるような集合 $S$ を管理する。ある頂点を追加してもしこの条件が満たされなかったら、その頂点は $S$ の頂点たちを結ぶ木の内部の点であるか、もしくはある $s\in S$ の部分木となる。このような $s$ もクエリの答えから特定できる。

こうやって各 $s\in S$ の部分木と $S$ の内側の木に分けられたので、それぞれで再帰する。ただし、内側の頂点が一つしかない場合は、その頂点と $S$ の頂点をそれぞれ結んでよいとわかるため先に処理しておく。実装して同様に二分木で試したところ、最初は先ほどと同様クエリ回数が2000回ほどオーバーしていたものの、頂点をシャッフルすると一気に5000回まで減ったため、提出。満点となった。

あとは部分点のみ。INVRETの部分点1は $i\lt F_i$ なら $2F_i$ を、 $F_i\lt i$ なら $-2F_i$ を答えに足し、最後に $i\ne F_i$ なる $i$ が存在したなら答えをデクリメントする。その時点での答えが $0$ より大かを判定したほうが操作回数は少なかったか。部分点2は全探索で、合計29点。TREEQUERの部分点1は愚直。以上で439点を確保した。

残り時間はより得意そうだったINVRETに注力した。思っていることが書けたと思ったのにバグっていて、チェッカーを書いていないため提出しまくることになってしまい、しかも結局通らなかった。点数は変わらず、最終的に5位で終了。

コンテスト終了後にチェッカーを書いてデバッグしたところ、無事バグが取れた。提出すると85点だった。まあ追加で50分くらいかかっているのでどうしようもなさそう。コンテスト3時間は長いなと思っていたのだが、終わってみると実は全然足りなかったことが分かった。

方針はマージソートで、ソート済の列を最後にまとめてcomposeすることでメモリ上の位置を連続させておくのがよい。さらにその後ろに番兵を設置することで、固定回数のループを回せばマージができるようになる。左右の列の先頭インデックスが $F_l$ と $F_r$ にあるとき $F_{F_l}$ と $F_{F_r}$ を比較し、列 $F$ に $F_l+(F_{F_l}\lt F_{F_r})$ と $F_r+(F_{F_r}\lt F_{F_l})$ を追加して、そのインデックスを新しい $l,r$ にする。

今見たように、操作列を生成するコードでは「ポインタのポインタ」みたいなものを扱うことになり、頭を壊してしまった。バグもこれに関係するもので、ただ1か所「ポインタ」でよいところを「ポインタのポインタ」を扱ってしまっていた。無念。最近DMOJでも制限された操作でプログラムする問題があって、そちらもただ一つのバグのせいでギリギリ満点を逃してしまったことを覚えている。人生そういうのばっかり。認知バイアス。

5位なのでレートは上がった。2697→2765(+68)で、ついに2月に記録した最高値を2だけ更新した。しかし現在CodeChefはレートシステムの転換期らしいので、単にそのおかげにも見える。

ABCのコードゴルフについて。Aの前にそれ以降の話をする。BはRubyのmax_byと集合の引き算で頑張る。Cはdcでループを回して計算。先ほども述べたように、閉じた形にできたとしても短くはならなそう。Dより先は手付かず。

Aはコンテスト中にVimで24Bを達成しホクホクしていたのに、2Bも縮められていた。何もかもが絶妙な噛み合い方をしていて天才的で、逆立ちしても書けないと思う。-1を書く代わりに0を書いて後からデクリメントするというのが大本のアイディアに見える。削除しつつレジスタに入れるのがddからxに縮むうえ、その操作後のカーソルは右に一つ進んでおり、このためlコマンドがいらなくなる。以上が-2Bであった。

atcoder.jp

明日は午後1時からMulti-Universities Campというコンテストがあるため、睡眠時間を確保しようと日記を書かずに布団に滑りこんだ。しかしそこからなろうを2時間ばかり読んでしまった。馬鹿野郎。午前8時前に就寝。

ちなみに今週の週記の文字数だが、書き上げてみると2万文字を余裕で突破した。日曜日はおよそ6千文字だったらしい。