05/02(月)

先週の週記を投稿してからの話。徹夜を決めた。ついでに新幹線の予定も早めることにしたので、時間的な余裕はすでにほぼなく、そそくさと出発。高校生の通学ラッシュと重なってしまい、駅から吐き出されてくる人々に逆らって歩くことになった。

仙台駅に着いて、朝食のパンをコンビニで購入して乗車。さすが朝早めの新幹線、さらに仙台駅始発ということもあってか、中はガラガラだった。

車内ではラノベを読んでいた。ふとTLを見ると、日曜日のOpenCup-Aが怪しいという話が流れてきた。詳しくは先週の週記に追記しておいた。解説のリンクをまだ手に入れられていないため、想定解がどのようになっているのかわからない。問題文に縦と横にしか切れないという注釈を書き忘れているのだろうと思うが……。

2022/05/04追記：Aは自明ではない。より正確に書けば、H×WH×Wのシートから同じ大きさの正方形をKK個切り出すとき、正方形の1辺の長さは最大いくらにできるか？という問題。特にH=WH=Wの場合、有名な未解決問題になる。問題文のどこを探してもそのようなことは書かれていないが、縦と横にしか切れないという制限を勝手に設けて解くと上に書いたようになる。
週記（2022/04/25-2022/05/01） - kotatsugameの日記

午前10時過ぎ、大宮に到着。このときもまだ車内はガラガラだった。僕が乗った先頭車両には他に1人しかいなかった。乗り換え待ちが40分程度あるので、一旦改札を出て駅前のゲーセンへ行き、1クレだけプレイ。素手なので軍手をつけている普段と感覚が違い、全然精度が取れなかった。

すぐ戻ってきてホームに上がると、今度はかなり人が多いようだった。列に並んでしばらく待ち、乗車。新幹線を外から見たときはかなり混んでいるように感じたが、何人か降りたのか多少座れる余地はあった。10分前から並んでいたこともあり、無事座ることに成功した。

車内ではカクヨムを1作読了。「絶対に目を付けられてはいけないVtuberに見つかってしまった」。正直あまり好きではなかった。登録者数1万人の主人公が登録者数100万人のヒロインに見つかってグイグイ迫られる、という展開に面白さよりも先に恐怖が来た。ギャグ時空なのでそういうことはないとわかっていても、めちゃくちゃ炎上しそうな展開に見えてしまう。主人公が弱気なのも好みではない。

kakuyomu.jp

ちょうど読み終わったあたりで黒部宇奈月温泉駅に到着。そこから父の車に乗り、食事しつつ富山市に向かった。どうせなら最初から富山駅で降りれば良かった。

パスポートセンターでパスポートの受け取り。3月末に代理申請をしてもらっていたのだった。受け取りの際に生まれ年の干支を聞かれ、答えに窮してしばらく上を向いて黙っていたら、係の人から「卯年ですか？」と助け舟を出された。そういうのでもアリなのか。

富山県のパスポートセンターに電話して代理申請について聞いてみた。こちらは僕が6か月以内に受け取りに行くことも含めて問題なく行えそうだったので、必要な書類を聞いておいて、再度パスポートセンターに行って申請書＋委任状をもらい、またその近くの写真屋でパスポート用写真を撮ってきた。これらとパスポートを合わせて、近々仙台に来る親に渡せば間に合いそう。
週記（2022/03/07-2022/03/13） - kotatsugameの日記

本屋に寄りつつ何も購入せず帰宅。パスポートセンターで貰ってきた、ゴルゴ13と外務省のコラボの海外安全対策マニュアルを読んだ。めちゃくちゃシュール。ゴルゴはそんなこと言わないだろというセリフばかり登場する。漫画は過去の話をコピーしてセリフだけ置き換えて作っている、と書いてあったような気がするが、そうだとしたらそれは凄いことだと思う。ネットでも読めるようなのでリンクを貼っておこう。

外務省海外安全ホームページ｜ゴルゴ１３の中堅・中小企業向け海外安全対策マニュアル

話自体に見覚えがあったので、もしかしたら5年前にパスポートを作ったときも同じ冊子を貰ってきていたのかもしれない。2021年に版が変わって後ろにコロナについての話が増えたようなので、そこは確実に今日初めて読んだとわかる。

パスポートセンターで貰ってきて読んだ pic.twitter.com/5N95SnLMV2
— こたつがめ (@kotatsugame_t) 2022年5月2日

布団に入って少しカクヨムを読み、午後6時就寝。

05/03(火)

午前4時起床。

カクヨムを1作読了。「幼馴染がVtuberになった、何故か配信の度に俺がトレンドに上がるようになった。」。面白かった。イラストレーターがVtuberになりそうになっているので気に入った。実質しぐれういさんみたいなところがある。ただ最近の更新は、女性Vtuberであるヒロインが男性である主人公に言及するのは炎上の元になるという話が始まって、少し不穏。

kakuyomu.jp

もう1作Vtuberモノのカクヨムを開いてしばらく読み進めたが、途中で止めた。俺TUEEEは否定したくないが、ヨイショが鼻につきすぎる。この感覚は作者の別作品を書籍で読んだときにも感じたもので、自分の苦手な作者であるとの認識を強めた。

【PV１７０万突破】ぼっちの俺がゲームスキルで大人気配信者になった件（相野仁） - カクヨム

午前7時から午前11時まで二度寝。起きてから部屋の掃除。実家に届いていた学位記の写真を撮った。

pic.twitter.com/POHWOaYkQA
— こたつがめ (@kotatsugame_t) 2022年5月3日

食事してしばらくハーメルンを読み、午後1時から灘校文化祭コンテスト 2022 Day1に出た。ソロ。

灘校文化祭コンテスト 2022 Day1 - AtCoder

Aはよい。Bはギャグみたいなもの。Cは2回くらいBFSをする面倒なやつ。Dは大変苦労した。全探索で解を見つけて、 $\{0,1,-2,3,\dots,N/2,\dots,-3,2,-1\}$ となっていることをエスパーした。これに気づけたのはかなり奇跡的な気がする。EはEven Degtreesを思い出せば連結成分ごとにかなり好き勝手できるとわかるので、見ている頂点の次数の偶奇を持って木dp。Fはfunctional graphに言い換えれば自明。Gは行ごとのdpを考えると遷移が多項式のべき乗になったので、二分累乗法で通した。700ms。

Hは与えられた点を連結にする辺だけ残した部分木を考えて、それの辺数の2倍から直径を引く。残す部分木の辺数（の2倍）については、dfs順に並べて円環と見たとき隣接する点の距離を足し合わせたら求まるらしい。典型90問で知った話。直径は、与えられた点だけを見てdouble sweepすれば求まる。葉となりうるのがそれらしかないため。Jは素因数を $1000$ 未満と以上に分けて、未満はそれぞれセグ木に乗せ、以上は個数をカウントした。何も考えずにセグ木を全部更新するとTLEしたので、関係する素因数のところだけ見るようにしたら1000ms。

Iは区間に辺を張るテクをしてdijkstra、700ms。Kはかなり苦労したが、タイルIを2枚横向きに置く枚数を固定したら解けた。タイルLは2枚組で使う必要があって、Iの2枚組とLの2枚組を並べた後、間にタイルIを置いていく。タイルLに挟まれた箇所では横向きになるが、結局どこでも1枚ずつ置いていくことになるので、単純な重複組み合わせで書ける。最後にタイルLの向きを考えて $2^{A/2}$ 倍する。

残り20分でLに特攻し、解けなかった。11完で9位。Dは $\{-0,1,-2,3,-4,\dots,-(N-2),N-1\}$ と見るとわかりやすいようだ。2個ずつ見れば $\pm 1$ で、これで上手く行く理由も納得できる。Gは考察すると普通にcombinationで解けるらしくびっくり。自分が使った多項式は $\sum 2^{M-i-1}x^i$ で、これを $2^{M-1}\times\sum 2^{-i}x^i$ と見ると、確かにべき乗後の各項が閉じた形で表せる。

Iは頂点でコストがかかると考えれば辺のコストが0になって、dijkstraによる更新が高々1回になるので一度見た頂点は消して良くなるようだ。Kの解説はよくわからなかったが、 $f(x)^n$ の先頭 $N$ 項を求める話は $n$ が負でも適用できるということらしい。フィボナッチ数列の畳み込みをOEISに投げて一般化した漸化式をエスパーした人もいたので、そのような漸化式の存在が先頭 $N$ 項を求める話にも効いているのだろう。

コードゴルフ。Aはdc 13Bでホクホクしていたら12Bに縮められた。 $\lfloor N^2/2\rfloor-\lceil N/2\rceil$ 。BはRubyのcombinatio.sizeをそのまま使える。Vimで書いたものに1B更新があって取られた。Dは2段落前に書いた集合をRakuで実装。符号を切り替える部分がどうにも短くならず、あまり納得のいかないコード。他は手付かず。

upsolveを2問行った。まずコンテスト中に考察していたL。方針としては、頂点を深さごとに分類して、ある深さの頂点について問題を解くときに、1段深い頂点たちについて同じ問題を解いたときの辞書順で並べておいて使うというもの。考察のダメだった点として、頂点数の少ない子を先に使えばよいと考えていたのがある。一番浅い頂点が先に来るので嬉しいと思ったのだが、それ以前に部分木で大小関係が決まってしまうことがある。次に実装で、同じ部分木を生成する頂点には同じ順番を割り当てなければならなかった。この2点を修正してAC。

次にO。各机について、右にどこまで寄せられるかを計算できればよい。ある机 $i$ に対して、 $i\lt j$ かつ $A_i+A_j\gt K$ となるような最小の $j$ を求めてみる。この机 $j$ を限界まで右に寄せた後、机 $i$ もその1つ左まで寄せられるのではないかと考えた。これは $A_i\le A_j$ のとき正しい。机 $j$ の左に出てくる机は机 $i$ とも交換できるようになるため。そうでない場合は $2A_i\gt K$ なので、代わりに $A_i\le A_j$ なる $j$ を求める。机 $j$ の左に出てくる机を机 $i$ と交換できることを保証するため。机 $j$ の右には行けないのでその1つ左……とはならず、 $i\lt k\lt j$ で机 $i$ の左に出せない机の数も考慮に入れる必要がある。範囲内の $k$ ではすべて $A_k\lt A_i$ なので、 $A_i+A_k\le K$ ならほかの机も越えて机 $i$ の左に出すことができる。 $j$ を求めるのは区間MAXのセグ木の二分探索、後半の区間カウントはライブラリになっている。

ラノベを1冊読了。「転生ごときで逃げられるとでも、兄さん？」3巻。凄かった。凄い理由は一応ネタバレ配慮ということで次とその次の段落に書くので、これから読もうとしている方は注意して読み飛ばしてほしい。ストーリーに注目して感想を述べれば……いや、この本に限ってはそんなことをしても意味はないだろうか。前半もちょっとダークな感じではあるものの、素直にドキドキしながら楽しんでいた。

終盤のちゃぶ台返しがすごかった。これまでの展開が全部無意味になってしまった。ストーリーが意味を成さないというのはそういう意味。裏表紙のあらすじにある「神の筋書きさえ殺す」というのは完全にメタ的な意味だったらしい。章題も書き換えられていた。イラストページの最後にこの巻の目次がついていたのだが、実はそれは途中までしか載っておらず、本の途中で目次が追加されるというかつてない体験をした。300ページ以上ある本の目次なのに200ページちょっとで小節が途切れているのに違和感を抱くべきだった。

登場人物一覧も改めて書かれて、結構な数のキャラがあっけなく殺されてしまったらしく横棒を引かれていた。これも信じていいのか迷ってしまう。横棒が書かれている→死んでいる、ということは別にどこにも明記されていない。ただ、そういう機能的なページでは嘘をつかないみたいな信条もありえるので、本当にわからない。

部屋の整理を始めた。仙台から実家に送った段ボールのまま放置されていた既読本を本棚に詰める。現在すでに部屋の棚が満杯なので、これからは物を減らす必要がある。中学校のときに使っていた絵の具セットやらを捨ててとりあえず空けてみたが、キャスター付きの棚だったので本をギチギチに詰めるのはマズいようだ。実際、詰めてから動かしてみて、敷物から恐ろしい音が鳴っていることに気づいた。そこで、その場所に別の棚から物を移して場所を空けることにした。とりあえず今ある分は収納できたものの、すでに横向きに本を詰め込んでギリギリのため、本当にマズい。

入った pic.twitter.com/eEIKGhyHND
— こたつがめ (@kotatsugame_t) 2022年5月3日

F問題のコードゴルフを少し。コンテスト中はcombinationライブラリを持ち出したが、よく見るとただの階乗だったらしい。dcでも通ったので、それで縮めておいた。

布団に入ってハーメルンの更新を確認。読んでいるうちに寝落ちした。午前2時だった。

05/04(水)

午前9時前起床。しばらくカクヨムを読んでいた。

帰省してからテザリングばっかりしているので、気になって通信量を確認していた。過去の月も見ていると、面白い期間を見つけた。目に見える変化が3回しかない。ちょっと学食に行くだけではこんな急激には増えないので、この3回はそれぞれゲーセンなどのため街に出かけていった日を示しているはず。当時の日記を調べてみると、02/16、03/03、03/08、03/09にそのような外出をしていたとわかった。03/08-03/09をくっつけて考えれば、確かに3回であるようだ。

この月めちゃくちゃわかりやすいな。3回外出したらしいです pic.twitter.com/Bw1TXdsuMA
— こたつがめ (@kotatsugame_t) 2022年5月4日

午前11時になって布団から脱出。昨日寝る前に縮めたF問題が更に縮められていた。適当にテストケースハックを試みると通ってしまったので、さらに-2Bで取り返した。

部屋の整理の続き。思い切ってゲーム機を捨てることにした。インターネットに接続して、DSiのうごメモを熱心に集めていた記憶がある。その中でもやはり有名なのは100%さんの棒人間バトルだろう。この作品（と関連作品）でSouthern Crossを知った人も多いと思う。検索すれば動画が出てくるのでピンと来ていない人はぜひ見てほしい。コピーが多すぎて、原作を見つけたときはかなり興奮した記憶がある。

懐かし〜 pic.twitter.com/7ege0iZ7Bm
— こたつがめ (@kotatsugame_t) 2022年5月4日

うごメモもインターネットにおける時代の流れに取り残されてしまったデータであるようだ。うごメモ発掘云々というタグが存在するのを見つけた。それなら、今手元にあるメモたちをただ捨ててしまうよりはいいかと思って、とりあえずSDカードのデータを吸い出しておいた。3165個。

日記のこの部分を書くときいろいろ調べているうちに、当時僕が熱心に作品を追っていたミラーパネルさんが今も活動されていることを知った。YouTubeに上がっているPV集がエモい。ただ僕としてはオリキャラの話やPVのほうが好みだったので、それが上がっていないのは寂しい。男の子2人と女の子1人の3人組がいたことを覚えている。

ミラーパネル【松坂奈夜】 - YouTube

午後1時から灘校文化祭コンテスト 2022 Day2。ソロ。

灘校文化祭コンテスト 2022 Day2 - AtCoder

Aは $M/\gcd(M,K)\mid N$ を判定。Bは $A=\max A_i$ を固定すると使える区間が定まって、 $A\gt 0$ なら $\min B_i$ は小さいほうがいいので使える区間を目いっぱいに選択、 $A\lt 0$ なら $\min B_i$ は大きいほうがいいので1点のみの区間を選択。 $A=0$ なら $0$ である。全ての $A$ について計算したものの最小値を答える。Cは今日もまた面倒なBFS。それで前計算してbitDPで答えを求める。

Dにかなり苦労した。グラフが連結であれば、辺数が頂点数以上であることを確認するだけでよい。よって連結成分に分解する方法を考える。1点 $u$ を選んで、それと接続されている頂点を全部集めたい。ある頂点集合 $U$ の中に接続されている頂点が存在するかどうかは、クエリ $U$ の答えよりも $U\cup\{u\}$ の答えのほうが大きいことを確かめることでチェックできるので、 $U$ を半々に分割していくことでそれなりに高速に求められそう。今の操作は $\{u\}$ がもっと大きな頂点集合になっても同じように行えるので、増えなくなるまで繰り返せば良いとわかった。ただ数ケースQLEしているらしい。苦し紛れに、QLEする直前にNoを出力するようにしたら通ってしまった。

Eはシュッと解けた。 $\sum_{i\ne j}\min(|A_i-A_j|,|B_i-B_j|)$ を求めたい。まず $A_i\lt A_j$ 、 $B_i\lt B_j$ 、 $A_j-A_i\le B_j-B_i$ と固定してみよう。すると $A_j-B_j\le A_i-B_i$ が得られるので、 $A-B$ を座圧してセグ木に $A$ の和と個数を乗せることでこのケースの総和が求まる。 $B_j-B_i\ge A_j-A_i\gt 0$ なので $B_i\lt B_j$ は自動的に満たされる。 $A_j-A_i\gt B_j-B_i$ の場合は $A$ と $B$ を入れ替えることで同様に。 $B_i\gt B_j$ の場合は $A_j-A_i\le B_i-B_j$ より $A_j+B_j\le A_i+B_i$ なので、 $A+B$ を座圧することになる。 $A$ と $B$ を入れ替えてもう一度やるのも同じ。以上で $A_i\lt A_j$ としたときの全ての場合を求めたので、2倍すれば答えになる。

Gは商列挙が面倒。 $\forall i.k\mid C_i$ という条件で数え上げた後、倍数のケースを引けば求まる。 $1\le k\le M$ について求めるのではなく $1\le k\le 10^5$ について求めなければならないのは注意。 $k$ を固定すると、各 $i$ に対して $C_i$ は $\lfloor B_i/k\rfloor-\lceil A_i/k\rceil+1$ 通り存在するので、これをかけ合わせればよい。区間の端点が変化するポイントは $O(\sqrt{A_i}+\sqrt{B_i})$ 種類しかないので、全部列挙してちまちま弄っていく。全体の積をセグ木で求めたらTLEしたので、掛け算と割り算を繰り返すことにした。ただしゼロ除算が困るので、そのようなケースは別にカウントしておく。これで4000ms。商列挙でMLEしてしまったので、pair<bool,int>をintに押し込んでデータを圧縮している。

Fは最小費用流。区間の端点を列挙することで、使える給水機の集合が等しい区間に分割することができる。分割した後の区間をそれぞれ1つのノードと見て、始点→給水機→区間→終点という感じに辺を張ればよい。コストが負になってしまうが、負閉路は存在しないので、最初のポテンシャル計算を手で行うことで問題なく計算できるやつ。今回はそもそもDAGなので、頂点番号がトポロジカルソート順になるように振って、先頭から順に計算した。後からよく考えれば、この場合はdijkstraがそのまま使えるので、ポテンシャルを0にしておいて問題なかったようだ。1回目の提出が2087msで、定数倍高速化して約1600ms。

Hは二重頂点連結成分分解。名前だけ知っていて、実装したこともこれを使う問題も解いたことがなかった。いろいろ調べるうちに、こちらも二辺連結成分分解と同様、分解後のグラフを木に見立てることができると知る。しかしその方法はかなり複雑に思われた。自分で実装できる気がしなかったのでもうちょっと調べ、以下のブログに何もかも書いてあるのを見つけた。このライブラリを貼り付けた後木dp。各頂点についてそれをLCAとするペアについて計算したが、解説を見て、単にそこを通る回数を数えればよかったということを知った。

Block-cut tree - ei1333の日記

Iは面倒。整理すると、長さ $N$ の順列であって、特定の $c$ 個の要素が $1\dots K$ 、 $K+1\dots 2K$ 、……の少なくとも一つを埋め尽くしているような場合の数が十分高速に求まればよいとわかる。包除原理で $O(c)$ で求まる。……と思ったのだが、この場合の数を後から指数として使うので、 $\bmod 10^9+6$ で求める必要があることに気づいた。恐る恐るfactorに投げると $2\times 500000003$ と素因数分解されたので、 $\bmod 2$ と $\bmod 500000003$ をそれぞれ求めれば復元できるようだ。後者は十分大きな素数なのでいつも通りmodintで計算できる。前者はリュカの定理などを使って気合いで頑張る。 $O(c)$ が十分高速であることは全く確認せず、とりあえず投げてみたら、通った。解説を見て $\sum c\le\sum_i\log A_i$ であることを知り、納得。

残り20分はK問題に取り組んでいた。どうせAlienDPだろうと思って適当に実装し、サンプルまで合わせるもWA。適当にポンポン投げて4ケースWAまでにじり寄ったが結局通せなかった。9完9位。

Bは試すべき区間を $N+1$ 種類に絞れるようだ。解説がなかなか理解できず苦労した。長さ1の区間で十分と書いてあるところは、 ${\rm argmax}_i\;A_i$ か ${\rm argmin}_i\;B_i$ を選ぶ場合を考えればわかる。Dはある頂点に隣接する頂点を全部一気に求めるのではなく、1つずつ求めるようにすればよかったらしい。 $U$ を半々に分割するとき、隣接する頂点を1つだけ検出する場合は、片方だけ聞いてどちらを次の $U$ にするべきか判別できるからだと考えた。ここで両方聞いてしまったときの定数倍が効くのを意識していなかった。

Eの解説の式変形は頭が良い。 $\max(|x_i-x_j|,|y_i-y_j|)$ を差の絶対値の和に置き換える箇所は、普段マンハッタン距離で45度回転しているテクの逆と見なせるようだ。初めて見る気がする。GはMLEした部分のデータの持ち方が違うだけで、変わらず商列挙が想定解だった。Fは解説と全く異なっていた。実行時間的にも想定解でないのは明らかで、何も考えずフローを流してしまいすみませんという感じ。

コードゴルフはA問題だけ。dcで解いておいたら、夜になって実は $\gcd$ を求めなくてもよいことが判明し縮められていた。 $M\mid NK$ を判定すればよかったらしい。言われてみればそれはそう。

Kのupsolveをした。AlienDPであることは間違っておらず、絵を取り外す時ではなく残すときにペナルティを与えるようにしたら通った。びっくり。これが本質的な違いとは思えなかったため、誤差が問題になっているのではないかと考えた。それで、日記を書いているとき、試しに全体を2⁶⁴倍して__int128で実装してみたところ、見事通った。この方法はちょっと覚えておきたい。ただ、long doubleでもそれほど変わらない桁数の精度があるはずなので、相変わらずよくわからないままである。

食事してしばらくSSを読んだ後、深夜まで日記を書いていた。今日の部分までたどり着かないうちに眠くなったので切り上げ、布団に移動。

そこからTLに流れてきたハーメルンを開き、1作読了した。「【ダンジョン配信】元社畜TS異世界転移者のホームレスから始まるダンジョン配信者生活!!」。主人公が強いのはいいが、現在初心者からステップアップするフェーズにあまり興味が持てない。正直なことを言えば手っ取り早く地位を上げてほしい。こらえ性のない人間になってしまった……。

syosetu.org

05/09追記：ハーメルンのほうでは削除されてしまっていた。なろうでは連載が続いているので、リンクを貼っておく。

https://ncode.syosetu.com/n3202hp/

午前2時過ぎ就寝。

05/05(木)

午前9時前に起床。昼前までずっと一度読んだなろうを読み返していた。

少し日記を書いてから祖母宅に行き、顔を見せた。会う度に僕の小学校入学以前の思い出を無限に語られるので正直辟易してしまう。思い出話を聞くのも孝行の一種であろうと理解はしているが、どうしてもそっけない対応になってしまう。ただ、じゃあ自分から話題を振って、今やっていることなどを説明したいかと言われると別にそうでもない。こうやって溝が深まるうちに残りの時間を過ごすのも、最近はまあそういうものかと受け入れてしまっている。

帰宅してまたしばらくなろうを読み、夕方になって焼き鳥屋に行った。混み具合はそこそこ。帰ってきてからもまた夜までなろうを読んでいた。

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

今日読み返していたのは「逆行転生したおじさん、性別も逆転したけどバーチャルYouTuberの親分をめざす！」。完結済みで、2月に閑話のようなものを毎日更新していたらしい。それを読んでからうっかり読み返しを始めてしまったというわけ。その閑話、配信アーカイブと名付けられている1話ごとの話が非常に良い。完結してからの話なので難しいことも苦しいこともなく、永遠の安寧を味わえる。

ハーメルンでいろいろVtuber小説を漁ってから読み返してみると、かなり毛色が違う作品だったなあと思った。かなり初期のVtuber界隈を題材にしており、Live2Dによる生配信ではなく3Dモデルによる動画投稿がメインの活動となっている。スーパーチャットの描写もなく、コメントとは会話せず、Vtuberから視聴者へは一方通行である。

https://ncode.syosetu.com/n3530fy/

午後11時半まで日記を書き、眠気が強くなったので布団に移動。少しハーメルンを読んで就寝。かなり久しぶりに、徹夜明けでもないのに日付が変わる前に寝られた。

05/06(金)

午前9時起床。

ハーメルンで読んでいた作品が1作、完結した。エピローグ5話がかなり良かった。中学卒業後からバンバン時間が飛んで、主人公たちの将来を描く。そういう締め方は一般に健康に良いとされている。

syosetu.org

仙台に帰る準備を整える。ラノベを3冊持ってきたのに、来るときの車内で読んでいた1冊以外はちっとも読み進められず2冊持って帰ることになった。昨日一日ネット小説に吸い取られてしまったのが痛い。昼前に家を出発。

昼食は回転寿司に行った。一応平日の昼間なのにそれなりに待ちがいてびっくり。写真の右に見えているのは白エビ軍艦。何気なく取ったら760円の皿で、大変恐縮しながら食べた。甘みがあり、巻いているとろろ昆布も合わさって非常においしかった。

食事 pic.twitter.com/vqOfEHKMV2
— こたつがめ (@kotatsugame_t) 2022年5月6日

黒部宇奈月温泉駅から新幹線に乗り、大宮へ。車内ではラノベを読んでいた。大宮に近づくにつれ人が増え、僕の隣の席も埋まってしまった。

大宮に到着。事前のチェックでは乗り換えの時間が5分でちょうどいいなと思っていたのだが、乗る予定だった列車がGW中の特定の日しか運行しておらず、30分後の新幹線を待たなければならなくなった。改札を出てゲーセンに行くとチュウニズムが埋まっていたので、待たずにすぐ引き返した。まだ微妙に時間があるので、ゲーセンとは反対側の出口にも出てみることにした。そちら側はペデストリアンデッキがあって、仙台駅を思わせる感じでなかなか面白かった。

こっち側初めて来た〜♥ pic.twitter.com/rPA9VBUcM3
— こたつがめ (@kotatsugame_t) 2022年5月6日

ようやく来た新幹線に乗り仙台へ。人はそこそこ、1席開けて座れるくらい。また車内ではラノベを読んでいた。午後6時に到着。ホームに降りてみると、今乗ってきた列車にここから乗り込むらしき人が大量に列を成していてびっくりした。

駅前のヨドバシカメラで板タブを購入。液タブのモニター機能がないやつ。昨年からオンラインのゼミだったり競プロ配信だったりで、手書きの図を即座に画面に映せるようにしたかったのだ。この先使う機会がどれくらいあるかわからないので一番安いものを購入。それでも6000円くらいした。

たいぺーから誘われたので一緒に食事する。待ち合わせはサイゼ。行ってみるとたいぺーがスープを注文していたので、間違い探しをして待っていた。今日はかなり冴えていて、たいぺーが食べ終わる前に10個全部見つけることに成功した。気分よく店を出てしばらく食事する場所を探し、やよい軒に入った。

食べた後少し本屋をうろついて帰宅。しばらくYouTubeを見てからシャワーを浴び、板タブの設定を始めた。初期設定では3枚並べたモニターが横幅を圧縮されて小さいタブレットの画面と対応しているようだったので、これを1画面のみに対応させたい。設定画面に最初からその対応を弄るページがあることに気づかず、wacom IDの作成と製品登録が必要だと早合点してしまった。このIDの登録にもかなり苦労した。twitterログインだけだとダメで、直接メアドで登録したら成功。ここでようやく最初から設定できたことに気づいて、無事1画面だけに対応するようにできた。

ラノベを1冊読了。「時々ボソッとロシア語でデレる隣のアーリャさん」4巻。夏休みの期間ということで、この巻では生徒会長を目指すバトルはお休みし、全編ラブコメだった。前半のデート2本はシンプルに好みのシーン。そこから生徒会合宿に行って、そこでヒロインからの恋心に主人公が気付くシーンがある。普通はくっつくまでずっと勘違いじゃないか悶々しているところ、途中でそうやって明言するのはなかなかびっくり。確かに、この主人公ならそういうところも目ざとく気付くほうが納得感がある。一方で主人公からヒロインに向ける感情にはまだ決着がついておらず、この巻のラストはそれに続くようなシーンで終わった。途中の伏線らしき描写から予想していたのとは違う人物が最後の挿絵に描かれていて、どういう関係だったのだろうかとかなり気になっている。

午前1時から、今日買ってきた板タブを考察に使ってみようと競プロ配信を始めた。

まず、この配信内で起こしてしまったことについて。yukicoderを解いていて、うっかり問題一覧のページに遷移したところ、僕がテスターをした未公開問題の問題名・難易度・タグ・writerが一瞬配信画面に映ってしまった。その時点での視聴者数は7人。即座に配信の巻き戻し機能をオフにし、また配信終了後にアーカイブを非公開にしたのでそれ以上の拡散はないものと信じているが、これ以上は視聴者の良心に恃むしかない。writerに連絡を取って何とか許していただけたものの、作られた問題には代わりとなるものが存在せず自分では何をどうしても贖うことができないため、大変肝を冷やした。

配信で解いたものについて。最初にCF #764 div.3を埋めた。A、Bはよい。Cは先頭から見て、残りの要素で作りにくい値を作るようにしたら通った。コメントで値を $n$ から降順に作ればよいと言われてびっくり。 $n$ 以下になるまで $2$ で割った後、同じ値を同一視してよいことを意識していなかった。このことがわかれば、僕の解法の「作りにくい値」とはすなわち作れるうちで最も大きな値であったこと、それを貪欲に作ってよかったことがわかる。Dは作る文字列の長さの偶奇を決め打つ。Eはdp。Fは二分探索。適切に $c$ を定めて、 $\lfloor x/n\rfloor$ が増えるかどうかを判定の条件とする。ちょっと面倒。Gは辺集合を持ち、上位bitから見て、そのbitが立っていない辺だけ使っても全域木が作れるなら辺集合を更新することを繰り返したら通った。

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

次に、今日のyukicoder 342のA-Eを解いた。A、Bはよい。Cは、子の数が1の頂点にそれ以下であぶれた部分木のうち最大のものをくっつけてやりたいので、あぶれたものをマージテクで管理。Dは半分全列挙。Eはちょっと難しい。最初、bitごとに考えようとしてしばらく詰まっていた。 $i$ を固定すると $j$ の条件が $i\le j\le L+R-i\le R$ と書けるため、 $2i\le i+j\le L+R$ とわかる。区間全体のXORを、さらに $L\le i\le (L+R)/2$ でXORするため、 $(2L,2L+1),(2L+2,2L+3),\dots$ のようなペアごとに出現回数の偶奇が変わる。ここで、ペアになる2数のXORは $1$ であるから、奇数回出現するペアを数えるだけでよい。 $L+R$ が偶数の場合はそれだけ単独で出現するので、別に数えておく。

yukicoder contest 342 - yukicoder

コメントでオススメされて少し前の問題を1問解いた。実際面白かった。とりあえず重複を取り除く。張る辺の $\gcd$ を決め打ってみると、 $g$ で割り切れる要素のうち最小のものとそれ以外を繋ぐことだけ考えれば十分とわかる。そこから、各頂点に対して接続している最も重みが小さい辺を求め、それらで最小全域木を作ろうとしてしまいしばらくWAを重ねた。実際は、先ほど絞り込んだ辺を全部使って最小全域木を作らなければ連結にできない場合がある。

No.1917 LCMST - yukicoder

午前3時半ごろ配信終了。配信アーカイブは非公開のままにするのではなく、見せてはいけない部分だけカットして公開してはどうかと言われたので、そうすることにした。アーカイブをダウンロードして、手元でカットして再度アップロードする必要があると思っていたが、実はYouTube Studio上で簡単に行えるようだ。そういえば、Vtuber小説で配信アーカイブのカット編集に言及していたものがあった気がする。ずいぶん手軽そうに書いてあったのは、こういう機能が存在したからなのか。先ほど触れた配信の巻き戻し機能のオン・オフもVtuber小説から得た知識で、ちゃんと現実にも存在しているんだなあと感動した。

カットした動画が反映されるのにはしばらく時間がかかるようなので、今日は非公開にしたまま布団に入った。午前5時就寝。

05/07(土)

午前10時半起床。YouTubeを見たり本を読んだりしていた。

フォローしているアカウントを頂点、共通のフォロワー数が多いペアを辺としてグラフを作り表示するサービスがTLに流れてきたので、自分も試してみた。頂点が多いのでかなり壮観。ただめちゃくちゃ重いし、出力した画像のサイズもそのままではツイートできないくらい大きくて大変だった。

Furland

6172頂点64248辺#bunnypaws pic.twitter.com/qdX8WsLaFY
— こたつがめ (@kotatsugame_t) 2022年5月7日

昨日の配信アーカイブの編集が完了していたので、ほかに映ってはいけないものが映っていないことを確認して公開設定に戻した。

午後3時就寝。次に午後5時半、目覚ましで起床。またしばらくYouTubeを見て、午後7時くらいに布団から起き上がった。食事し、シャワーを浴び、人の日記を読んだり自分の日記を書き進めたりして時間を過ごし、午後9時からAGC057に出た。実に5か月ぶりのratedである。

AtCoder Grand Contest 057 - AtCoder

A。 $a$ が $b$ の部分文字列であることは、 $b$ の最上位桁か最下位桁を落とすことを繰り返して $a$ にたどり着けることと等しい。よって、数を頂点とし、最上位桁か最下位桁を落とした数に向かって辺を張った有向グラフを考えると、良い集合はすべてのペアがこのグラフで互いに到達不可能でなければならない。ここで、このグラフで入次数が0である頂点を選ぶのがよいと思った。確かコンテスト中は、入ってくる辺があるならそれを逆に辿った頂点を選ぶことにしてもよいから、と考えていたはずだが、これは良い集合の状態を保てない操作のため、理由としては間違っている。しかし結論は合っていて助かった。

入次数が0である頂点を数えるため、桁数に注目する。 $R$ の桁数を $r$ としたとき、 $r$ 桁の数は全部数えて、 $r-2$ 桁以下の数は数えない。 $r-1$ 桁の数については、最下位桁に $0$ を増やすか、最上位桁に $1$ を増やした数が $R$ 以下ならば数えない。つまり $r-1$ 桁の数 $x$ は $\min(x+10^{r-1},10x)\gt R$ のとき選べるということで、この不等式から $x$ の下限が出せる。 $L$ 以上という条件を確認し忘れて1WAしつつ通した。

B。2進数で桁を揃えたい、というところから考察を始めた。 $X$ の影響を実験してみると、 $A$ の上位桁であって数回操作しても弄れないところは、そのあと何回操作してもずっと弄れないままであると感じた。そうならば、最小値を達成する桁数はそれほど大きくならないはず。各要素の操作回数を決め打つと、達成できる値が区間で表せて、このときの最小値は区間の右端の $\min$ から左端の $\max$ を引いた値（負なら $0$ ）になる。左端が最も小さい要素を選んで1回操作し、また最小値を求める、ということを繰り返せばよさそう。 $\max$ は単に変数を更新すればよく、 $\min$ にはmultisetを使うことにした。区間の右端で判定するとオーバーフローしたり操作を試す回数が足りなかったりしたらしく、左端が2⁶²未満の間という条件でようやくACした。2200ms。

残りのsolved数は絶望的。若干多かったDに進んだ。とりあえず $S$ が奇数の場合は自明で、しばらく実験して $S$ を割り切らない最小の数 $p$ が重要そうなことに気づく。 $\{S/2+1,\dots,S-1\}$ という集合があって、ここからいくつか選んで $x\leftarrow S-x$ とする（反転と呼ぶ）と考えられるが、このときまず反転後に $p$ の倍数になるものが選ばれる。それ以降は大きい順に、反転しても良い数列になるなら反転することを繰り返すことになる。 $S$ を作れないという条件は、反転した数だけ無視してチェックしても答えが合ったので、そうした。

そうやって $p$ の倍数にならないのに反転するものを出力してみると、ある数 $x$ が反転されたら $x-p$ も反転されているようだった。なので、 $x\bmod p$ ごとに最大の $x$ を求められればよさそう。そのような $x$ について、 $S-x$ は $S$ を $p$ 未満の数で割った数の近くになっていそうだったものの、この時点で時間切れ。適当にコードを弄って実験結果と一致するか試すのを何度も行っていたので、もうちょっと頭を使うべきだった。

2完3ペナ118位、パフォーマンス2670、レートは2852→2835(-17)。軽傷で済んでよかった。まずAの考察が正しくなかったのがヤバい。Bもまともな考察をしていなくてヤバい。左端の上限をちょっと下げるとすぐWAになってしまうので、通ったのは本当にたまたまだったらしい。

コンテスト中にとんでもないリザルトが出回っていた。つい最近別の人が1落ちを出していてかなり驚いたものだが、そこから理論値がなかなか出ず、大変苦労している様子がTwitterで見られた。その人を差し置いて先に全部噛み合わせたのは、やはりこの人だったか、という感想。

混沌を越えし我らが神聖なる調律主を讃えよ
ALL JUSTICE CRITICAL‼️‼️‼️‼️‼️‼️‼️‼️‼️‼️‼️‼️‼️‼️‼️‼️‼️‼️‼️‼️‼️‼️
閉店滑り込みで間に合ったー！！！！！！！ pic.twitter.com/QvwjjnzpRw
— す (@Kokor0_N) 2022年5月7日

www.youtube.com

解説を読んでDを通した。反転する数の集合を考えるのはよくて、それが和で閉じていることには一切気づけていなかった。ここは考察が必要だったところ。解説の「 $X$ に追加できる次に小さい数を探す」の部分はかなり難しい。これまで反転した数だけで作れる値を $\bmod p$ で分類し、それぞれ最小のものだけ保存しておく。次に追加する数 $\bmod p$ を全探索する。先ほど保存したそれぞれの数 $T$ について、 $T$ に今追加する数を何回足せば $T\bmod p$ と $S\bmod p$ が一致するかが前計算でわかる。そうやって一致させたときに $S$ 以下になっていると、さらに $p$ を足して $S$ を作れてしまうので、これが $S$ より大になるという条件が追加する数の下限を与える。 $T$ を全部試して $\max$ を取り、全探索した中でこの値が一番小さいものが、次に追加できる数となる。それを用いて $T$ の集合を更新する。

コンテスト中にたどり着けたところからもまだかなり遠かったな、という印象。無理だ。

日記を書き始めたが、朝方はかなり集中を切らしてなろうを読んだりしていた。寝る前にatgolferを確認するとAGC-Aが結構縮んでいたので、自分もゴルフしてみた。 $L\le l$ として、区間 $[l,R]$ が良い集合であるときの $l$ の最小値を求めたい。二分探索せずとも定数時間で求まるらしい。 $R$ の桁数を $r$ と置いて、 $l=\max(L,\lfloor R/10\rfloor+1,\min(r-10^{r-1}+1,10^{r-1}))$ としたら通った。これをdcで書いて60B。

dcコードをずっと睨んでいたが特に縮まないうちに椅子の上で一瞬寝てしまったので、布団に移動。午前9時就寝。

05/08(日)

午後2時半起床。しばらくYouTubeを見てから起き上がり、日記を書いていた。

午後5時からOpenCup。Grand Prix of Yuquan（と書いておかないと後から読み返したとき辛いことに気づいた）。今日はかなり調子が良かった。チームでFDJBCHILMAの10完11位、自分はDBCIを解いた。M問題の問題文に急に魔理沙のイラストが出てきて面白かった。

www.pixiv.net

Dはソートして小さいほうから順に取る場合しか考えなくてよい。全部同じケースで配列外参照を起こしたり、割り算を掛け算に直して比較するときにオーバーフローしたりで2ペナ生やしてしまい大変だった。Bはある条件を満たす数を数えるという問題だが、条件がかなり厳しいので、実験して全部埋め込めそうと感じた。PCが空くのを待って実験を回すと、なんと1つしか見つからなかった。サッとコーディングしてAC。Cは、チームメイトの考察を眺めていると連結成分ごとにサイクル基底を取ればよいことに気づいた。同意を得られたので実装。 $S=T$ のケースにしてやられ、1ペナで通った。

Iも順当に解けた感じ。 $u\lt v$ かつ $p_u\lt p_v$ とすると、 $u\lt i\lt v$ かつ $p_u\lt p_i\lt p_v$ なる $i$ に対して一気に差分が求まればよい。 $A_i-B_i$ で場合分けしてみると2通りしかないようだったので、それぞれ対応する列に持っておいて、大小関係を満たす要素をカウント。これはrangefreqというライブラリにしてある。書き始めてから $C_u$ と $C_v$ の更新がそこそこ大変であることに気づいたが、変更される位置を集めて $A_i$ 、 $B_i$ の計算をやり直せばよかった。実装はかなり面倒。一発で合って嬉しかった。

以降は考察のみ。MはMAOであることを指摘し、しばらく考えてみたものの、操作回数の上限が $2L^2$ で全然ダメだった。通したチームメイトの手法もよくわからない。Kは難読。必死に解読するも微妙な箇所が残ってしまった。基本、言われたとおりに書けば工夫せずとも通りそうだったが、ABCが近づいてきたのでHackMDにいろいろ書いて逃亡。結局僕が書いた考察もまだ難読だったらしく、実装はされなかった。

午後9時からABC250。

AtCoder Beginner Contest 250 - AtCoder

Aで入力の1行目と2行目を取り違え1WA。Bはよい。Cは順列と、各要素からインデックスを引けるテーブルを持てばよい。このテーブルは逆順列である。右端のswapを誤読してサンプルが合わずびっくりした。Dは $q\le \sqrt[3]{N}$ を全探索。Eは、数列 $A$ の各項に対し、その要素が数列 $B$ で出現する位置のうち最も左のものを計算する。そうして作った数列の先頭 $x$ 項における最大値が $y$ 以下のとき、 $A$ の先頭 $x$ 項は集合として $B$ の先頭 $y$ 項に含まれるとわかる。逆も行うことで集合としての一致が判定できる。Fは操作を何回でも行えると誤読してかなり長い時間固まっていた。1回しか行えないので尺取りでOK。

Gはなかなか解けず、苦労した。売値が高い日から貪欲に売ってみたりして迷走し、残り10分になって考え方を変え、ようやく正しい解法が得られた。先頭から見て、売る日・何もしない日を管理する。今見ている日の株価が $P$ であるとする。この日はまだ買う日にはなれない。売るとした場合、何もしない日を1日選んでその日に買ったことにするか、売る日を1日選んで、それとペアになっている買う日を代わりに今見ている日とペアにするか。前者は単純に何もしない日が1日減り、後者は売る日が1日減って何もしない日が1日増える。どちらか利益が大きいほう、または何もしないことを選ぶ。

これが最適であることは、コンテスト中は証明しようとしなかった。サンプル3を試したら合っていたので提出、残り2分で通った。今日記を書いているときにも考えてみたが、どうにもよくわからない。公式解説における説明もかなり難しかったので、行間を少し埋めておこう。まず、多重集合の操作は「 $A$ を2個追加」→「最小の要素 $m$ を削除して答えに $A-m$ を加算」と言い換えられる。 $A$ を1つだけ追加する場合が、 $m=A$ となって対応している。このことは最短コードを読んで気づいた。

$dp$ の折れ線は $j=0$ からスタートして単調減少、加えて上に凸である。傾きはある位置を境に $-A$ 以上から未満に切り替わるので、 $\max(dp_+,dp,dp_-)$ はその位置に横幅 $2$ 、傾き $-A$ の線分を付け加えた形になる。これは $j=-1$ スタートになっているので、一番左から横幅 $1$ の線分を削除する。つまり、傾きの列である多重集合に $A$ を2個入れて、最小の要素を削除。操作が正しいことは確認できた。

答えに加える値も見る。 $j=0$ における値の変化を追いたい。もともとそこにあった点は、折れ線 $dp_+$ において $j=-1$ の位置にずれ、次の折れ線に必ず存在してくれるため、ここから $j=0$ に戻せばよい。まず $dp$ が $dp_+$ になるタイミングで上に $A$ ずれて、その後右に $1$ 個ずらすとき下に $m$ ずれるため、合わせて確かに $+A-m$ となっている。

7完98位。Fも遅いしGも解けないしでプライドがボロボロになりそうだった。何とか耐え。Eは解説とかなり雰囲気が違う。いろいろやり方があるらしい。

コードゴルフ。Aは $4-(\lfloor 1/R\rfloor+\lfloor R/H\rfloor+\lfloor 1/C\rfloor+\lfloor C/W\rfloor)$ をdcで書いた。[x code]dxのテクを使って、まったく同じcodeを2回実行する。スタック操作をうまく組み合わせるとそこそこ縮んで21B。BはPerlで書いた。あまり短いとは思えないが自力では縮まない。なんだか僕が考えもしなかった書き方がありそうな雰囲気。DはRubyで書いてVimで縮めた。解説とは逆に $q$ を全探索することにすれば、全探索できることが容易にわかるし、 $p$ をカウントするテーブルも同時に作ることができる。というかstackに直前の素数を入れて、条件を満たさない間popしていけば十分。他は手付かず。

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

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

Aは $c$ と $a$ をこの順に $n$ から全探索。 $c$ を減らす前にカウント配列の $(p_c,n]$ に $1$ 加えると、 $b$ を決めるごとに $d$ の個数が即座に求まる。 $a$ を減らす前に $b=a$ とした場合の $d$ の個数をそうやって求め変数に足しておき、減らした後の $a$ が $p_a\lt p_c$ を満たす場合にそれを答えに加える。特別なデータ構造を使わず全体で $O(n^2)$ になり、気持ちよかった。

Bは縦横をそれぞれ計算。横は、各 $1\le i\le nm$ について $(i-m,i]$ に'1'があるか調べ、あったなら $i,i+m,i+2m,\dots$ に $1$ 加算。 $i$ に加えてから $m$ 個おきの累積和を取る。縦はインデックス $\bmod m$ が不変なので、その列で初めて'1'になるインデックスを求め、それ以降に $1$ 加算。縦横が入り乱れてちょっと頭が壊れそうになったが、一発でサンプルが合って興奮した。

Cはfunctional graphと見て連結成分に分解。頂点の値を昇順に並べると、係数を $\dots,-2,-2,(0,){+2},+2,\dots$ のようにするのが最適。何回か見たことがある。3種類それぞれカウントして、 $1$ から順に小さい係数を割り当てていく。最初、頂点番号の係数ではなく区間の係数を見てしまい、最適な割り当てを作れずに1WAした。

Dは難しい。まず、操作はバブルソートの一部になっている。 $k$ 回操作したら後ろ $k$ 項は決定される。逆にこれを巻き戻してみよう。例えば $k=1$ のときを考える。末尾の $n$ がそれ以前にどこかにあったはずで、その位置は、先頭であるか、または先頭から見て累積maxが変化する点の直後である。また累積max以外の場所は一切変化しない。途中に $n$ を置いた場合はその直前にある値に乗り換え、同様にして先頭までたどり着いたら巻き戻しが完了する。ここで（ $n$ 以外の）累積maxの個数 $c$ を考えてみると、1回操作を巻き戻した後、その個数は $0\le i\le c$ について $i$ 個になるのが $\binom{c}{i}$ 通り存在する。無視していた $n$ を戻して $i+1$ 個。 $n$ の代わりに $n-k+1,\dots,n$ として順番に巻き戻した後の場合の数を数えたい。 $c$ を次元に持つdpを手で計算して $k$ ごとにOEISに投げると、 $k!(k+1)^c$ であると判明した。

後は、 $k$ 回操作後の列を $c$ ごとに求められればよい。挿入dpに $c$ を保持する次元を増やすと多項式と見れて、遷移が1次以下の式の掛け算になった。大量の1次式の積をセグ木みたいにまとめていって $O(n(\log n)^2)$ で計算するやつを実装。最大ケースでも1.3sec程度になったので提出したら、爆速で通った。そういうケースがpretestに入っていないようでかなり心配だが、まあ解けたのでヨシ！

残り1時間。Eのsolvedがかなり少なくほぼ諦めモードだったが、何とか気力を奮い立たせて考察を始めた。とりあえずbeautifulな区間の右端を $r$ と固定してみる。この時、左に見て累積maxが更新される位置の列を $\dots,(m_a,i_a),(m_b,i_b),\dots$ （ $m_a\gt m_b$ 、 $i_a\lt i_b$ ）として求められる。 $\max=m_b$ と決め打ち、 $l$ であって $i_a\lt l\le i_b$ かつ $p_ip_j=m_b$ となるような $l\le i\lt j\le r$ が存在するものを求めよう。

$1\le j\le r$ のそれぞれについて、 $m_b/p_j$ が整数となるか調べ、整数ならば $m_b/p_j$ が列のどこに位置するか取得して、その位置 $i$ であって $i\lt j$ を満たすものだけを集めて最大値 $i_{m_b}$ を計算すれば、 $l$ は $i_a\lt l\le \min(i_b,i_{m_b})$ とわかる。 $i_{m_b}$ の計算では、 $m_b$ と制限せず $p_j$ の倍数を全部調べる方法で、 $r=1\dots n$ 全体が調和級数 $O(N\log N)$ で計算できる。

さて、 $r$ を $1$ から順に調べるごとに、累積maxの列の $(m_b,i_b)$ それぞれを見て上のような区間に1足せば、 $r_i=r$ であるようなクエリについて $[l_i,r_i]$ の区間和を求めることで答えがわかる。しかし累積maxを毎回見るのはどう考えても間に合わないため、高速化が必要。ここで、 $i_{m_b}$ の更新回数が $O(N\log N)$ であることに注目する。現在列に存在する累積maxであって更新されたもののみ取り扱えばよさそう。今取り扱わなかったものについては直前と全く同じ値が足されることになるが、その「同じ値」が足される回数は、対応する $i_{m_b}$ が最後に変化した位置（あるいはその累積maxが出現した位置）と $r$ の差で求められる。つまり $r$ の1次式なので、区間和と同様遅延セグメント木に乗せ、取得の際に $x=r$ とすればよい。

かなり大変そうだが何とか書き始められそう。実装したら、コンテスト終了の10分ほど前にとりあえず書きあがった。デバッグも含めると間に合わないかな、と思いつつサンプルを試したら、なんと一発で全部合ってしまった！恐る恐る提出すると通った。これで5完。

システスも全部通って27位、レートは2869→2916(+47)。DとEがかなり通されていて、思ったより伸びなかった。Dは求めたい値が多項式 $f$ に対する $f(k+1)$ だったので、最初から $x=k+1$ として積を取ればよかったらしい。 $n\le 10^6$ で $O(n(\log n)^2)$ を2secは攻めているどころの話ではない。ただ僕が書いたコードはかなり高速だったようで、コンテスト後にいくらかHackの試みを観測したが結局落ちていない。Eは2次元の領域和で解いた人が多い。そちらはよくわかっていない。

OpenCup-Kを解いた。問題文に書いてある表から数値を取り出してコードに埋め込むだけ。コンテスト中に残した読解が微妙な箇所は、僕が考えていたことが間違いだったようだ。経験値を溜めてレベルを上げるとき、特定のレベルで一旦ストップしなければならないと書いてあったのを、経験値をたくさん稼いで一気にスキップできないだけだと勘違いしてやたら面倒なことをしていた。実際は、そのレベルに到達した瞬間未反映の経験値が全部消し飛ぶらしい。端数を管理しなくてよいので簡単になる。

OpenCupのページでは問題文が画像で表示されるため、僕は以下の表を全部手動で埋め込んだ。しかし、実はPDFの問題文も存在するらしい。

OpenCup-K通した。バカが書いた問題文 pic.twitter.com/re72y0NxFU
— こたつがめ (@kotatsugame_t) 2022年5月8日

05/09追記：原神というゲームの経験値テーブルだったらしい。OpenCupでこのゲーム見るの何回目だよ。レベルシステムをちょっと調べてみたところ、途中のレベルでストップしていたのはレベル上限の解放が必要だったからということが分かった。それなら未反映の経験値が全部消し飛ぶのも納得。こういう知識がないとまともに読めないような問題文はカス。経験値テーブルをドンと置いて何食わぬ顔をしている時点でカスか。また、以下のツイートにあるリンク先のテーブルは微妙に異なるようだ。具体的には49Lvにおける値が違うのと、81Lvに80Lvと同じ値が1個挿入され、以降一つずつずれている。

なんか、こんなものをわざわざ問題のために用意するはずがないと思ったらこれが出てきて、これコピペすればってなってたhttps://t.co/M25UIdDSMy
— 有為 (@uwitenpen) 2022年5月9日

朝まで日記を書いていた。今週は微妙に遅れ続けており、今日は土日の部分を書いていた。朝方、ABC-Gの正当性を考えていたら急激な眠気に襲われたので、週記の完成を明日に回して寝ることにした。午前8時半就寝。