01/02(月)

午前11時ごろに起こされた。多少の二日酔いで軽い気持ち悪さがあるが、今日は昼から中華料理を食べに行くらしい。

幸い、車に乗っていても食事しても気分が悪くなることはなかった。ここでもコーンスープを頼んだ。かなりコーンポタージュに近い。

pic.twitter.com/6KR0EOLz7i
— こたつがめ (@kotatsugame_t) 2023年1月2日

百貨店に寄って帰宅。

夕食までは麻雀をしていた。この年末年始は自分の他に二人実家に来ていたため、父を加えるとちょうど四人になる。この二人というのは、片方は姉で、もう片方は……詳しく説明する理由も権利もないため、名言は避けておこう。

夕食は午後6時ごろだった。食後、先ほど述べた二人が帰るので見送った。

先週の週記を書き始めたが集中力がない。なろうから「剣聖と大賢者の正体が、落第貴族と呼ばれる俺な件について～しょうがないから守護神してるけど、さっさと変わってほしい暗躍学院ライフ～」を読了。

https://ncode.syosetu.com/n8008hz/

正体を隠す方法として、完全に影に隠れているのも好きだが、こうして複数の人間を演じるのも好き。最近投稿が始まった作品なのでこれからに期待。複数の人間を演じると言えば「セブンキャストのひきこもり魔術王」というラノベを思い出す。こちらは一人七役。設定がかなり好みで、今でも時たま思い出してはニヤニヤしている。

日付が変わる直前に週記を投稿した。せっかくの年明け一発目なのに時間に追われすぎて大したことが書けず、残念。できれば加筆したいものだが、校閲にすら手が回っていない以上実現可能性は低そう。

その週記の中で、2年前に読んだ本「〔少女庭国〕」に言及した。記憶が曖昧なので念の為確認しておこうとしたが、本棚を漁っても見つからない。レーベルに共通して本の背が少し高いので、見落としたということはなさそう。よくよく思い返してみるとたいぺーに貸した記憶があって、聞いてみたらどうやら返し忘れていたようだ。思い出せて良かった。

入浴し、午前1時半くらいからDMOJのコンテストに出た。明日の午後2時までなのでギリギリ。しかしここにコンテストの感想を書けるという利点もある。

DMOPC '22 December Contest - DMOJ: Modern Online Judge

P1は、 $N$ または $M$ が偶数の場合、相手が塗ったマスの点対称の位置を塗れば必ず半々になりそう。ヒカルの碁で見たことのある戦法だ。両方奇数なら中央のマスの分先手が1増えるな、と思って提出したらWA。

考え直してみると、中央に壁を作る感じで塗れば、先手は後手より1行または1列まるまる多く獲得できる。行と列のどちらであるかは後手が選べる。これで通った。

P2はかなり面倒。順列をサイクルに分解してから考えた。連結成分数は、サイクルの頂点全部が選ばれたら1減り、そうでない場合は選ばれた頂点だけ見たときの連結成分の数に分裂する。選ばれた頂点と選ばれていない頂点を結ぶ辺を、差分更新で数えることで求められた。

P3は非常に難しかった。答えを $H$ とし、 $H-h_i$ を1と2で埋め、1とそれより右の2をうまくペアにして全部使い切ることを考える。

もし $H$ と $h_N$ の偶奇が異なれば $i=N$ として操作しなければならないがこれは不可能。よって $H$ の偶奇が決まり、同時に必ず一度は1インクリメントする必要のある要素もわかる。そういう要素を右から順に見て行って、本当にペアが作れるかをチェックした。右に2がなければ $H\leftarrow H+2$ として無理やり作り出す。

さらに $NH-\sum_i h_i$ が3の倍数になるように $H$ を調整しておく。 $N$ が3の倍数だと不可能なケースも生じる。後は $H$ と $\sum_i h_i$ からわかる操作回数の分だけ、左から優先的に1で埋めていけばよさそう。

残りは1と2が入り混じる箇所でペアを作れず破綻するケースのみが問題。そのような位置を二分探索で求め、破綻するかどうかをチェックする式を作った。なかなか複雑だが $H$ の一次式になったので、この式を満たすくらい大きな $H$ が簡単に得られる。それをもとに $H$ を再調整すればよい。

ここまでも結構な回数のWAを重ねてきたが、最後のWAが一番衝撃的だった。最初の処理で1だけインクリメントする要素をチェックするとき、それとペアになる2インクリメントするインデックスも適当に固定していた。そのほうが後から操作回数などが扱いやすいから。しかし、この固定するペアも慎重に決めなければならないらしい。右のほうから貪欲だと落ちて、左のほうから貪欲だと通った。

すでに残り1時間しかなくかなり焦っていた。幸いP4はスムーズに解けた。解の構造を考えると、まず値札を動かさずに購入する商品を決め、その後一番高い値札を一番安い使っていない値札に付け替えるのを高々 $K$ 回行うことになる。値札を安い順にソートしておくと、この操作で使っていない値札が安い方から使われるため、ある位置が存在して「それより安い値札はすべて使われている」「それより高い値札で使っているものは付け替えていない」が満たされる。

この位置を全探索し、さらにいくつ付け替えたかも全探索する。付け替えた数が $K$ 未満なら、固定した位置より右側にはもう使った値札はないとしてよい。あったとすると、適当に付け替えたり、あるいは位置をずらすことでそのケースを考慮できる。従ってこのケースでは、右側から価値の高い順に付け替えた数だけ貪欲に取ることができる。左側は $O(NK)$ のdpで全部計算可能。

ちょうど $K$ 個付け替えた場合は、右側から値札を $K$ 個動かした後、余った金額でさらに品物を購入する可能性がある。 $K$ 個までタダにできるとした金額に関するdpを行いたいが、状態 $O(NC)$ で遷移がそれぞれ $O(N)$ となり当然不可能。しかしタダにするのは高いほうから $K$ 個なので、どの品物までで $K$ 個の権利を使い切るか全探索し、品物は価値を見て貪欲に取るという方法で状態 $O(C)$ に落とせる。これで間に合う。

残り20分ちょっとでP5とP6の部分点をかき集めた。P5は0を1にする以外値を増やす手段がないことに注意しながら値の大小に関するチェックをし、さらに0を1にするために必要な1をその左側から抽出できるか調べれば1行のケースは通る。P6は始点と周期を全探索する愚直で部分点1。部分点2は、周期を調べるときに探す文字列自体が周期的だったらスキップするという枝刈りを入れたら通った。計算量解析はよくわかっていない。

残り数分でP5がフローではないかと疑ったものの、コンテスト後にしばらくやっても通らなかった。450点。順位表を見ると、思ったよりP4が解かれておらず、代わりにP5とP6がたくさん通っていた。P6はrun列挙というやつだろうか。コンテスト中も頭を過ったが性質を知らないため手が出なかった。

それからラノベを1作読了。「あたしは星間国家の英雄騎士！」。「俺は星間国家の悪徳領主！」の外伝。モブ視点で本編主人公が語られるシーンは楽しめたが、それはごく一部にしかない。当然外伝主人公の話が多く、そちらにはあまり惹かれなかった。

午前8時過ぎ就寝。

01/03(火)

午後5時起床。

昨日参加したDMOJのコンテスト期間が終了していた。最終順位は9位で、レートは2854→2897(+43)。

夕食を食べた後、少しだけ買い物に行って、帰ってきてからはこたつに入ってラノベを読んでいた。テレビの音声で集中できず終いには眠くなってくる始末。よっぽど深夜のコンテストまで寝て過ごそうかと思ったが、スマホを弄っていたらそのタイミングすら逃してしまった。

入浴し、午後11時くらいに軽食をお願いしたところ、お雑煮と焼鯛が出てきた。思ったよりガッツリ食事して半からCF。今日はHello 2023。

Dashboard - Hello 2023 - Codeforces

Aは正規表現で書くと/R.*L/にマッチするのが条件、に見えて実は/RL/でよい。文字列がLのみまたはRのみの場合だけ不可能。

Bは、とりあえず $n$ が偶数のケースは $+1,-1,+1,-1,\dots$ とすることで構築できる。サンプルを見た感じ $n$ が奇数のケースは不可能だろう、という気持ちになったが、念のため証明しようとしたら構築できてしまった。まずすべての $i$ について $s_i=s_{i+2}$ であることがわかる。よって数列が $a,b,a,b,\dots$ とおけて、 $a+b=\lceil n/2\rceil\times a+\lfloor n/2\rfloor\times b$ が条件になり、 $n\ne 3$ なら $a,b\ne 0$ なる解が存在する。

Cはちょっと面白い。条件が $\dots+a_m\le 0$ と $a_{m+1}+\dots\ge 0$ で表現できて、左右それぞれ似た感じに解ける。例えば前者については、 $m$ 項目から左に値をどんどん足していって、どこかで正になったら値が一番大きなものの符号を反転するというのを繰り返せばよい。値の取得は優先度付きキューで行った。

Dは言われたことを丁寧に実装するだけ。 $x\lt b_i$ なる $i$ を含まないように区間を取って操作する。 $b_i$ が大きなほうから見て、含められない $i$ はsetで管理した。最初から $a_i=b_i$ であるような $i$ に注意する。

Eは面白かった。求めたいのは強連結成分であって成分外からの入次数が0なもの。トーナメントグラフをSCCに分解するとパスグラフになるので、その始点と言ってもよい。出次数で降順ソートするとSCCと同じ順番で並ぶことに素早く気づけたのがよかった。これはクエリ $n$ 回で求まる。どこまでが始点の強連結成分になるかは、さらにクエリを $n-1$ 回使って調べた。

Fはサイズが偶数の部分木を全部0にできる。これを元にした自明な木dpで判定が行え、それを丁寧に復元する。遷移はXOR畳み込みで、愚直に $32\times 32$ 回計算したがかなり高速だった。

Gはエスパーした。三角形を適当な辺を下にして置くと、上から一つ、三つ、五つ、……の三角形が一つの行をなし、積み重なっているように見える。各行には上下方向の辺がいくつかあって、例えばこの辺がすべて同じ向きだと、明らかにその行を境に行き来できなくなってしまう。よって、どの辺を下にしておいた時の行を見ても、上下方向の辺の向きはどこかで食い違っている必要がある。

これは必要条件だが、実は十分条件でもあるのではないかと考えた。当然一般には十分ではないものの、今回の状況から最小手数で達成すれば実際に強連結になるらしい。出したら通ってびっくりした。以下では証明を考えず、単に最小手数を求める。

まず三つの $s$ の末尾が等しければOK。そうでない場合、適当に回したり反転することで $s_1$ 、 $s_2$ の末尾を1に、 $s_3$ の末尾を0にできる。いちばん外側の辺の状況をイラストと合わせたということ。このとき左下向きの行は両端の辺の向きが異なるため、考えるべき行が水平のものと右下向きのものの二つに絞られる。

基本的に1辺の向きを変えたら条件を達成した行が一つ増えるが、辺を共有している行があった場合はそこを変えることで一気に二つ増やせる。後者をできるだけ行うと手数が最小になる。条件を満たしていない行の検出はインデックスを丁寧に考えると簡単な条件になる。辺を共有しているかの判定はもともと簡単。

Hはラウンド2回を一気に行うことでサイズ $n$ の問題をサイズ $n/4$ の問題に帰着できそうに見えたが、それでも全然間に合っていない。

7完20位でかなり良かった。レートは2705→2841(+136)。Dはおそらくバリカンで髪の毛を刈る操作を表していて、昔それをchminと言っていたのを思い出した。Eはソートした列をどこかで切ったときに末尾のほうから先頭のほうに向かう辺があるかどうかが末尾側の出次数の和を見ることで判定でき、クエリ回数が $n$ になるらしい。

CFの問題言い当ててしまったな https://t.co/PvvwXR1zW9
— こたつがめ (@kotatsugame_t) 2023年1月3日

システスを見届けた後はラノベの続きを読んでいた。午前5時半就寝。

01/04(水)

午前11時半起床。軽くお雑煮を食べて、父の車で外出した。

まず、昨年末に購入した礼服の裾上げが完成していたので受け取った。ついでに真っ白のワイシャツと真っ黒のネクタイを買ってもらったので、これでいつ葬式があっても準備は万端というわけ。もちろん葬式なんてないほうがいいから、せっかく買ってもらってなんだがこの先10年くらいは実家で塩漬けにしておきたいものだ。

外出。礼服を購入してもらう。自分くらいの年齢になると一着持っておくべきらしい。
週記（2022/12/26-2023/01/01） - kotatsugameの日記

その後富山駅で下ろしてもらった。午後1時半、よことKRmei氏と合流。今日は夜までこの三人で遊ぶ予定。

最初に駅前に新しく経ったMAROOTというビルを見て回った。昔マリエに入っていたはずの書店がこちらに移動してきておりびっくり。

次に、駅に入って回転寿司を食べた。あまりお腹が空いていなかったため控えめに。二人の近況だったり高校同期のその後だったりが聞けて面白かった。自分は高校以前の交流がほぼ途絶えてしまっているのでこういう機会は貴重。

その後ゲーセンに移動。駅前のゲーセンといえばゲームインさんしょう富山駅前店だったがすでに閉店している。ところが最近、駅ビルにGiGOが入ったらしい。駅から非常に近いためかなり便利そう。チュウニズムは旧筐体と新筐体が1台ずつだった。2種類の筐体が混在している店舗を見るのは何気に初めてである。よくTLに新筐体の待ちでトラブった人のツイートが流れてくるため良い印象がない。

ゲームインさんしょう富山駅前店が今月末で閉店するというツイートが流れてきた。
週記（2021/10/25-2021/10/31） - kotatsugameの日記

混んでいたので、2時間弱で切り上げて夕食へ。ラーメン一心という店に行った。ここは富山地方鉄道の駅の裏にあって微妙にアクセスが悪い。雨も降っていて大変……と思っていたら、KRmei氏が駐車場などを辿って濡れずに移動する経路を教えてくれた。

さっきのゲーセンがある駅ビルに戻って、1階上のブックオフに行った。ゲーセンと同様これもつい最近入った店舗。しばらくうろついていたらよこが帰る時間になったため、KRmei氏と共に見送った。このまま新幹線で東京に戻るらしい。

KRmei氏も今日富山を離れるが、出発は3時間ほど先のようだ。せっかくなのでカフェに入り、時間になるまでしこたま話していた。自分は何でもかんでもツイートするがKRmei氏はそうではない。私生活についての話が興味深かった。おすすめの動画などを教えてもらった。

どういう経緯だったか忘れたが競プロの話になって、何やら興味がありそうだったのでしこたま布教した。なんとすでにPythonを少し勉強したことがあるらしい。おあつらえ向きすぎる。問題文をそのままコードに起こすのはできそうなので、最近の傾向だとABC-Bまでは問題なく通せるだろう。そこから先は知識が必要になってくるが、教材ならいくらでもネットに転がっているからぜひ頑張ってほしい。

午後10時前にKRmei氏を見送り、自分も父に迎えに来てもらって帰宅した。すぐ入浴。

THE名門校という番組が母校を取り扱った回の録画を見た。いろいろあったが今は素直に懐かしさを感じる。壁が黒板なりホワイトボードなりになっていたのは、大学にも同様の設備があるから、かなり便利だったのだろうということがわかる。それほど活用できた記憶はない。

その他、今日おすすめされた動画をいくつか見てからSRMの準備に取り掛かった。都合よくこどふぉっていたのでノートPCの環境を整えようとしたが、Appletを起動した後プラグインの設定中に時間切れ。結局Web Arenaで参加した。SRM843。

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

最初に、EasyとMedを落としたことを明記しておこう。下にある解法はコンテスト中の自分のもので正しくないということに注意されたい。

Easyは、まず一周聴いても退店しないケースを除いた後、入店タイミングを各曲の開始時間として全探索した。これで何曲聴くかはわかって、さらに次の曲が始まる直前までずらすことでそのようなタイミングがどれくらいあるかも計算できる。

Medは+がいくらでも使えるので数の表現を考える必要がない。値の小さなほうからdpした。遷移は $+1$ 、 $+5$ 、あとは自分以下の数との掛け算で、最後のものは全体で $O(N\log N)$ となる。

Hardは謎。連結成分を頂点数で表現しその列を状態としてdpしたところ、TLには間に合わないが手元でそこそこ高速に動くコードが完成した。入力パターンがかなり少ないので、全部埋め込んで提出。

Medがチャレンジで落とされ、Easyはシステスで落ち、Hard 1完で10位。レートは2912→2894(-18)で何とか軽傷といったところか。

Easyは最初に取り除かなかったケースでも必ず全曲聴くことになるケースがあって、この場合入店タイミングはいつでもよい。自分の解法だと次の曲が始まる前に退店するケースしか考えていないため、「入店直後と退店直前で同じ曲を聴いている」ケースを考慮できていなかった。

Medは大きな数と大きな数を足し算する必要があり、上に書いた遷移では考慮できていない。やけに簡単に解けたから提出前に結構疑う時間を取ったはずなのに、何を考えていたのだろうか。

Hardは頂点数が $S$ を超えた連結成分を全部マージして扱うと十分高速になるらしい。これが1000点ってマジ？

朝までラノベを読んでいた。「現代社会で乙女ゲームの悪役令嬢をするのはちょっと大変」4巻を読了。3巻巻末で2021年冬発売と予告されていたのが1年遅れたわけは、後書きによれば「昨今の情勢と諸事情」らしい。昨年はなんともすごい年だったからわからないでもない。何であれ続刊してくれて嬉しい。

この巻は、これまで破竹の勢いでグループを拡大していた主人公が負ける話だった。なろう版でも読んだので展開は知っていたはずだがやはり辛い。ただ、改めて読んだことで前後関係への理解が深まり、納得はできたと感じている。

この先は金融以外のシーンも多くなりそう。なろう版では話がとっ散らかっていた印象もあるが、結局幼い主人公は金融に関して表舞台に立てないのだから、その分の無双を別の話で補給していく感じで楽しみたい。5巻出版は決定しているようだ。気長に待つ。

それに合わせてですが、五巻決定をご報告させていただきます。
　五巻は来年中に出せたらと思っているのですが、昨今の情勢から確実な日時が言えない事についてはお詫びさせてください。
　これも読者の皆様の応援の結果でございます。
　どうかこれからもよろしくお願いいたします。
— 二日市とふろう　(旧名:北部九州在住) (@hokubukyuushuu) 2022年12月25日

午前6時頃、父の朝食に便乗して自分の食事も用意してもらった。

布団に戻ってハーメルンを1作読了。「ナンジャモさんのお隣さん」。まだ3話しか投稿されていないが、転生前の手持ちがそのままということで、なつき度やレア度に関してニヤニヤできる設定が多い。

syosetu.org

午前7時頃寝落ち。

01/05(木)

午後1時半起床。久しぶりにメールの確認をしたら、指導教員の先生から一昨日届いたものを発見した。しかも返信を求められている。もはや謝るしかない。

そのまま布団でハーメルンを読んでいた。午後4時から午後6時半までの二度寝を挟みつつ、2作読了。

1作目、「消えた天才が喫茶店やってる話」。過去のバンド名をひた隠しにしているように見えて、早々にポロっと明かしているのが読んでいる側としては手っ取り早くて嬉しい。「音楽チートで世に絶望していたTS少女がSIDEROSの強火追っかけになる話」を読んでからオリ主が有名人なものを漁ってばかりいる。

syosetu.org

2作目、「ジム廃業して飛んでパルデア」。いろんな地方の、つまりいろんな世代の特殊なワザや能力を使っているのが面白かった。ポケモンのスカーレット・バイオレットが舞台だとナンジャモで配信者要素が摂取できるのがうれしい。

syosetu.org

今日の夕食は外食だった。どこに行くか決まっていないらしかったので焼肉と言い放ったら本当に連れて行ってもらえた。以前焼肉を食べた後の腹痛で救急車を呼んだのは記憶に新しい。今日はしっかり焼くことと、生肉を掴むトングと焼けた肉を食べる箸を使い分けることを意識した。

食事 pic.twitter.com/DGGs5TRUtt
— こたつがめ (@kotatsugame_t) 2023年1月5日

帰宅してハーメルン。「官能小説の世界に転生したらお隣さんが陵辱される直前の母娘だった件」を読了。R-18にならないくらいの淫靡さでよかった。

syosetu.org

入浴し、昨日のSRMのEasyをupsolveして、午後11時半からCF #842 div.2に出た。

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

Aは $x!+(x-1)!=(x+1)(x-1)!$ なので、 $x=k-1$ とすることで必ず条件を満たし、さらに明らかに最大。コーナーケースがあるのではないかと怪しんで $k=2$ など念入りにチェックしたが本当に何もなかった。

Bは要素の削除と追加を $k$ 個ずつ行うのではなく、一気に削除して一気に追加すると思ってよい。できるだけ多くの要素を削除しないままにしたいので、 $1,2,\dots$ の列がどこまで $p$ に部分列として含まれるかチェックし、その部分列以外の要素を動かす。

Cは値の降順に構築した。値 $i$ を埋める際は $a$ に出現する $i$ を数えて、3か所以上なら不可能、2か所なら $p$ と $q$ でそれぞれ置いてもう一方のマスを空きマスとしてチェック、1か所なら $p$ も $q$ もそこに置き、出現しないなら以前チェックした空きマスに埋める。

Dは操作後の数列 $n-1$ 通りを全探索する。完全に昇順に並べるケースとほとんど差がないので操作回数の差も小さい。具体的には $\pm 1$ になるので、どちらになるか判定。例えば $i$ と $i+1$ を逆転させて並べる場合、逆に最初の $p$ で $i$ と $i+1$ を入れ替えていると思うことができる。これを使って判定した。

Eは高々3回でソートできる。0回、1回、3回を数えて補正した。0回なのは最初から $p$ がソートされている場合で、1通り。1回なのは前 $n$ 要素または後ろ $n$ 要素がソート済みの場合で、 $2(2n)!$ から両端 $n$ 要素がソート済みの重複 $n!$ と全体がソート済みの場合を取り除く。

3回はちょっと面倒。前 $n$ 要素に後ろ $n$ 項に行くべき値があり、かつ後ろ $n$ 要素に前 $n$ 項に行くべき値があるケースである。包除原理で、全体 $(3n)!$ からどちらかを満たさないケース $2\times{}_{2n}\mathrm{P}_n(2n)!$ を引き、両方満たさないケースを足した。最後のケースは真ん中 $n$ 要素にいくつ前 $n$ 項に行くべき値があるか全探索すると求まる。

Fはジャンプする際 $\min(a_i,a_{i+1},\dots,a_j)=a_i,a_j$ になると分かったがそれ以上先に進まず。5完14位。

R-18のハーメルンを1作読了。「投げ銭アクメ系バーチャル配信者」。ちょっとついていきにくい描写もあるが序盤や番外編はなかなか好みである。

https://syosetu.org/novel/273699/

今日起きた時に発見した先生からのメールに今更返信。その後朝方までほかの人のブログ記事や動画を見ていた。午前6時頃に今日の昼食として用意されていたものを食べ、しばらく日記を書いた。

市役所の業務が始まるのを待ってマイナンバーカードを受け取りに行った。パスワードの設定は、希望の文字列を紙に書いて提出し、それを職員が見てPCに打ち込むことで行うらしい。パスワードを他人に見せるのが前提となる仕組みを、誰もおかしいとは思わなかったのだろうか。

帰宅して就寝。午前9時半だった。

01/06(金)

午後3時起床。

そのまま布団でR-18のハーメルン「セックスごっこをしてくれた幼馴染みとガチセックスする」を読了。腐れ縁なのでやり取りの口調が乱雑だが、盛り上がるとちゃんと引っ込んでくれるのは好み。

https://syosetu.org/novel/270067/

身を起こしてラノベを開いた。午後8時前に「紅蓮戦記」2巻を読了。面白かった。魔法でできることがかなりシステマチックに設定されているため、ファンタジー戦記モノとして読みやすいし、主人公の強さが魔力量のみでなく戦い方の点からもしっかりと感じ取れる。その二つを軸に面白いように勝つので、シンプルに楽しくもあった。

新しく出てきた敵国の王女様についてはちょっと消化不良気味。主人公を低く見積もる様子が念入りに描かれたので、終盤でスカッとした勝ち方をするのかなと思っていたが、そうではなかった。上で述べた魔法の制限もあって、王女様との戦闘は無双できるような状況ではなかったのが残念。

それ以外はスッキリまとまっていた。あまりにもまとまりすぎているためさてはと思ったら、案の定この巻で完結だった。ラストでその後について少し語られたのがありがたい。概ね満足していると言って良いだろう。

食事と入浴を済ませ、午後9時20分からyukicoder 372に出た。

yukicoder contest 372 - yukicoder

Aは $\max(A_1+A_2+A_3+B,3\max(A))$ 。 $A_1\le A_2\le A_3$ という条件に気づいていなかった。Bは和の中身が $n\ge M$ なら必ず0になるので計算しなくてよい。

Cは $a$ と $b$ を全探索。 $x=a(p^{-1}+p^{-3}+\dots)+b(p^{-2}+p^{-4}+\dots)=\frac{pa+b}{p^2-1}$ となるため、これが $1/N$ より大という不等式を解けば $p$ の範囲が求まる。分数が出てくると扱いが面倒なので、全体を4倍して $(2p-Na)^2\lt N^2a^2+4Nb+4$ と変形した。

Dはよくわからなかったので8次元累積和を計算した。値を周囲から包除原理のように集めてくる方法で計算したため、1マスのために $2^8$ マス見る必要があって1100ms。後から考えてみれば8方向に累積和を取るほうが簡単かつ高速だった。

Eは惑星の距離がいかついが実はギャグ。 $T_i\ne T_j$ ならどこかのタイミングで恒星から一直線に並ぶため、円運動の半径の差になる。 $T_i=T_j$ の場合は位置関係が変わらないため $(X_i,Y_i)$ と $(X_j,Y_j)$ の距離になる。これを使ってコストが $\max$ のdijkstraを行う。後者はもともと根号がついているため、それを外すだけでコストが求まる。前者は誤差が怖いので適当な範囲を調べて求めた。

Fを見て逃亡を選択。より多く解かれていたGに逃げ込んだ。いかつい式を丁寧に解釈すると $\sum_{n=L}^R\sum_{i=1}^{n-1}\binom{n}{i}^2$ になって、内側の和をWolfram|Alphaに投げたら $\binom{2n}{n}-2$ となった。あとは $\binom{2n}{n}\bmod M$ を一つずつ丁寧に求める。

$M$ を素因数分解して $\bmod{p^e}$ ごとに計算し、中国剰余定理で復元した。すべての値を「素因数 $p$ の個数」と「残り」の組として保持する。階乗をこの形式に直すのはルジャンドルの公式っぽく行えて、除算も「残り」の部分だけ真面目にやればよい。その「残り」は $\bmod{p^e}$ で計算する必要がある。うっかり $\bmod p$ で計算していたため、全然合わずかなり長い間苦しんだ。

Gに時間を取られこれ以上は解けず、6完9位。

何もやる気が出ずラノベに手を出した。「ブラックな騎士団の奴隷がホワイトな冒険者ギルドに引き抜かれてSランクになりました」8巻を読了。主人公が、政治的な事情もあってヒロインの一人と結婚した。そんなメインを張るようなキャラだとは思っていなかったためかなり衝撃的だった。そして次巻、完結らしい。ずいぶん急だと感じたが、実際未解決で残っている話は少ないのかもしれない。よく覚えていない。

仙台には明日帰る。乗車券の有効期限が明日までなのとABCがあるから。仙台から持ってきた本が1冊、帰省の道中で買った本が7冊だった。今読み終えた本で帰省中に7冊読んだことになるから、仙台に持ち帰るのはたった1冊。完璧。

午前5時まで日記を書き、布団に入ってハーメルンを1作読了。「グロリアス軽戦車」。途中絵が描けず逃亡したあたりで苦しくなって少し間が開いていた。読んでみると案外すぐに回復して、結局はハッピーエンドになってくれた。

syosetu.org

午前6時半就寝。

01/07(土)

正午過ぎ起床。なかなか起きられなかったため昨日考えていたスケジュールは破綻してしまった。まあABCまでに仙台に着けばよいので余裕は結構ある。その上年末年始だから臨時列車が走っているらしく、ちょうどよい時間にかがやきがあった。来るときも乗ってきた途中停車が全然ない速い新幹線。

食事して荷物をまとめ、出発。富山駅までは父の車で送ってもらった。残り20分で特急券を買う必要がある。改札横の券売機は1台が修理中で残り1台に数人待ちがいたが、みどりの窓口の中に3台あってそちらは待ちなしだった。無事購入に成功。父と別れ、乗車した。

持ち帰ってきた本を開いたが眠気が強く、大宮まではずっと寝ていた。乗り換えて仙台までは、今度はなろうをずっと読んでいた。結局本はほぼ進まず。

午後5時半ごろ仙台に到着し、即座にゲーセンに向かって午後8時前まで11クレプレイした。新曲を埋めたのと14+のSSS+が一つ、また新年初の理論値も出した。チュウニズムのグッズキャンペーンは今最後のキャラクターと引き換えられる期間で、今日で無事必要ポイントを集め終わった。一安心……と思いきや、チュウニズムデュエルが終わっていない。01/11までにあと10クレほどプレイする必要がある。

まぜそばを食べて帰宅。途中で、新幹線で読んでいたなろうを読了した。「Killer Queen～FPSで幼馴染(美少女)を最高に幸せにする方法～」。

https://ncode.syosetu.com/n7715hb/

主人公が強くてよい。現実感との兼ね合いかポロっと負けてしまうことも何度かあったが、FPSの競技シーンを知らないのでもうちょっと無双してくれたらなあとか考えていた。配信をサポートするのに会社を立ち上げたり、過去のしがらみが顔を出したり、風呂敷は結構広がっているものの残念ながらエタっているように見える。後者についてはしっかり向き合うと辛そうだし、順調なところで途切れているのはむしろ読みやすかったかもしれない。

午後8時半ごろ帰宅。準備して午後9時からABC284に出た。

AtCoder Beginner Contest 284 - AtCoder

Aは1行読み飛ばして残りはtac。readを無引数で実行するとジャッジの環境では何も読まれないらしく、 $N$ が出力に残って1WA。手元と挙動が違う。bashで通したあとVimで書き直したら縮んだ。

ここからはC++。BCはやるだけ。Dは $\sqrt[3]N$ まで調べると $p$ または $q$ が見つかる。 $p$ が見つかればよい。 $q$ が見つかれば $p=\sqrt{N/q}$ とわかるが、うっかり $q+1$ から順に試し割りで見つけようとしてしまいTLEを出した。続けて行っているから合わせて $O(\sqrt[3]N)$ だと思ってしまった。

Eはよくわからないが10⁶本見つかった瞬間打ち切るdfsで通るだろうと思って提出。案の定通った。Fは $T+{\rm rev}(T)$ と ${\rm rev}(T)+T$ それぞれにZ-algorithmを適用すれば解ける。

Gは $A$ をfunctional graphと見たとき、 $i$ からスタートしてループに入るまでの長さが $S_i$ になる。 $S=S_i$ となる $i$ と $A$ をまとめて数え上げた。ループの長さを $L$ とすると、まず頂点を $S$ 個選んで並べ、その後にループの頂点を $L$ 個選んで並べ、残りはなんでもよい。つまり ${}_N\mathrm{P}_{L+S}\times N^{N-L-S}$ 通り。これに $S$ を書けて足し合わせたい。

$S$ と $L$ でループを回すのではなく $S+L$ と $S$ でループを回すとよい。上の場合の数は $S+L$ ごとに一定で、 $S$ の寄与だけ別に計算することができる。 ${}_N\mathrm{P}_{L+S}$ は割り算を使わず計算できるので $\bmod M$ でも安心。

Exには手も足も出ず、残り時間はコードゴルフをしたりシャワーを浴びたりしていた。7完15位。水曜日に競プロを布教したKRmei氏も無事コンテストに出ていただけたようだ。今回はグラフを扱うテクニックを知らないとCが解けないので、解説を読むなりしてぜひ頑張ってほしい。

コードゴルフ。AはVim 9Bが最短でよさそう。提出時間の差で勝ち。Bは今のところdc。CはPerlで、負け。Dはfactorを使うまではよくて、文字列置換で答えを作れることに気づいてVim 35Bでホクホクしていたらdcに投げたほうがもっと短くなるらしく大敗。EはPerlがTLEしたので放置。以降は手付かず。

午後11時からTROC #30に出た。

https://tlx.toki.id/contests/troc-30

Aは $\max(N,\lfloor N/Y\rfloor\times X+(N\bmod Y))$ 。Bは $A$ の値を区間に伸ばすと見なせるやつで、 $B$ から隣接する重複要素を取り除いたものが $A$ の部分列になっているかチェックすればよい。FA。Cはいくつか手で試し、どうせ $2\min(N,M)$ だろうと提出した。

Dは $-1$ を全部取り除いた列と同じ値が達成可能で、当然最小。そこに $-1$ を入れると、bitごとにどのタイミングで切り替えるかの自由度が生まれる。それを掛け合わせたものが答え。

Eは最初に最小全域木を求め、その上のimosで必要な辺をチェックした。reading-zeroをつけないようにするなど出力が面倒。

Fの操作は $K$ 項まとめてswapすると読み替えられる。そこからかなり時間がかかった。結論から言えば、要素を $i\bmod K$ でグループ分けしたとき、それぞれをソートするだけで全体もソートされることと、各グループで転倒数の偶奇が等しいことが条件になる。

1項だけずらして2連続で操作することであるグループだけ転倒数をちょうど2変化させることができ、1変化させようとしたら1回の操作で全グループ一気に変える必要がある、ということから後者の条件が出る。前者のチェックし忘れで1WA。

順位表を見てHに進んだ。最初に $A$ 全部のbitwise ANDを全体から引いておくことで、両方のグループのbitwise ANDを0にする問題になる。2段階の包除原理を行った。つまり、まず最初の包除原理で一つ目のグループのbitwise ANDを固定し、二つ目のグループのbitwise ANDが0になる場合の数を数えるためにさらなる包除原理を行うということ。

決め打った二つのbitwise ANDは共通のbitを持たないため、全体で3²⁰通り調べればよい。しかし手元で2.5secくらいのものを提出したのにサンプルでTLEしてしまった。3²⁰通り全部計算するわけではなく条件のチェックなどが入るため、計算をまとめるのも難しい。

いろいろ見方を変えた結果、「 $i\subseteq j\subseteq i\cup I$ なる $j$ に $+1$ 」というクエリを2²⁰回処理できればよくなったが、解けただろと思っていろいろ試しても全然高速にならず愕然。そのままコンテスト終了。

終了3分後にHが通った。上のクエリが微妙に高速化できたようだ。 $i$ と $I$ のサイズを比べて小さいほうの部分集合を全探索する。 $I$ のほうが小さい場合はそのまま $+1$ すればよい。 $i$ が小さい場合は20次元のimos法、つまりゼータ変換を考えると、 $i$ の部分集合と区間の終端を表す $\pm 1$ を置く場所が対応していて、最後にゼータ変換することで必要な $+1$ だけがうまく行える。

Hが思ったより解かれており6完23位、2786→2771(-15)。優しい。ジャッジがAtCoderくらい強くてHの3²⁰を通してくれたらもっと優しかった。

しばらくYouTubeを見たりハーメルンの更新を読んだりした後日記を書いた。午前7時半就寝。

01/08(日)

午後4時起床。布団に横たわったままハーメルン「お辞儀様の娘はTS転生人外幼女」を読了。

syosetu.org

主人公以外の視点がちょくちょく挟まるのが嬉しい。ホグワーツとどう関わるのか楽しみにしていたが、最新話の時点でハリーは5歳。まだかなり遠そう。しかもすでに原作からかなり外れていて、全く先が読めない。

午後7時過ぎに布団から脱出して食事。

01/11にホスフィン・たいぺーと遊ぶ。いつものように外で食事してから我が家で家飲み。そのための酒類やボードゲームをいくつかAmazonで購入した。ボードゲームについては有識者に意見を聞き、「ito」「タギロン」「ギャンブラー×ギャンブル！」を注文した。

3人で遊べてAmazonで買えるボードゲームを探しています
— こたつがめ (@kotatsugame_t) 2023年1月8日

午後11時半からECR141に出た。

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

Aは降順に並べると大体うまくいく。最大値が二つ以上あるケースが問題で、特に全要素が等しい場合不可能。そうでない場合は最大値でない要素を一つ先頭に置けばよい。

Bは $1,n^2,2,n^2-1,\dots$ と並べるだけであり得る差がすべて得られるらしい。行列をジグザグに埋めた。

Cは勝利回数 $k$ を全探索。基本的にコストが安い人から $k$ 人に勝つことを目指すが、 $k+1$ 番目の人だけは勝利回数が $k$ 回または $k+1$ 回となって自分の順位に影響するため、その人に勝つか負けるかは両方試す必要がある。

Dは次の操作に使う項の値を持ってdp。それが0なら2種類の操作のどちらを選んでも列は同じ。0でないなら他の列と重複しない新しい列が二通り得られる。

Eはちょっと手こずった。すべての $i$ で $\left\lceil\frac{a_i}k\right\rceil\le\left\lceil\frac{b_i}k\right\rceil$ を満たすことが条件。最初、商列挙で調べようとしたが、 $O(n\sqrt n)$ が2.5secくらいかかって間に合わない。改めて式をよくにらみつけると、これは $[b_i,a_i)$ に $k$ の倍数がないことと同値。この区間にチェックを入れておき、 $k$ ごとにその倍数のチェックを全部見に行くと $O(n\log n)$ で解けた。

Fは順列が一つの場合、それをfunctional graphと見たときの連結成分数を $n$ から引いたものが答え。 $i$ で操作すると $i\rightarrow i$ というサイクルが独立するが、すべてのサイクルがそのような1点のみのものになるまでの操作回数なので、各サイクルにつき一つずつ操作しないインデックスがある。

順列が二つの今も同様に、操作しないインデックスの個数を最大化することを考える。そのようなインデックス集合の条件は「どちらの順列でも一つのサイクルに二つ以上乗っていないこと」と書ける。これは最大流で表現できる。

Gは手も足も出ず、6完9位。Eを商列挙で通した人がいるらしい。どうやったのか見に行くと、 $\sqrt{b_i}$ で処理を分けるちょっと面倒な書き方だった。商列挙自体は、商が $q$ となる最大の除数が $q$ で被除数を割ることで求まるのを使うとシンプルに書けるのだが、こちらだと割り算の回数が少し多いようだ。

新春TechFUL Coding Battle 2023に参加した後日記を書いて午前9時半就寝。火曜日までなのでここには何も書けないし、正確な時刻を記録するのも躊躇われる。実はECRが終わってからTechFULを解き始めたというわけでもない。とりあえず点数が見える部分は理論値で通せた。

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