08/14(月)

午前10時半くらいに目を覚まして、正午までは布団でスマホを触っていた。起きてからは先週の週記を書いた。

午後4時半からインターン先定例会。先週休んだので2週分の進捗報告と行きたいところだが、先週も先々週もまともに稼働できていない。ちまちま作業していた件について喋って終わり。

勉強会はPythonのパッケージマネージャー「Poetry」について。別にこれ特有の仕様というわけではないが、ライブラリのバージョン要件を記述するファイルと共に実際に入っているものをすべて書き並べたファイルもあるのはなかなか堅牢で考えられているなと思った。

本題とは全く関係ないことで、dataclasses-jsonの最新バージョン0.5.14がPythonの3.7以上3.13未満を要求するのが興味深かった。普通上限は特に決めないようだ。今はまだPython 3.12すら正式リリース前だが、何かの新機能に影響を受けることが確定しているのだろうか、それとも心配性なだけか。

https://pypi.org/project/dataclasses-json/0.5.14/

インスタンススペックを適切に決めるためメモリ使用量の調査をすることになった。しばらくfreeコマンドの結果を記録したい。最初はcronでやろうとしていたが、なぜかファイルへの書き出しがうまくいかなかったのでシェルスクリプトを起動しっぱなしにしておくことにした。

その後はまたずっと週記を書いていたが、途中で筆が止まりカクヨムにのめり込んでしまった。2作品読了。

1作目、「その視聴者、最強につき～推しのダンジョン配信者がピンチになると颯爽と助ける世界一位の探索者～」。主人公が明確に最強なのが良い。推しとやらは正直どうでもいいのでもっと主人公の話を読みたい、という気持ちがある。

kakuyomu.jp

2作目、「陰キャコミュ障ぼっちで影の薄い俺、世界最強のダンジョン探索者です　～世間ではダンジョン配信なるものが流行ってるらしいので、そういうのはよくわかりませんが、流行りには乗りたいと思います～」。主人公最強なのに加えてちゃんと自分で配信もしてくれるのが嬉しい。やはり目立ってなんぼだと思う。

kakuyomu.jp

そんなことをしていたら週記を書き上げられるはずもなく、穴あきだらけのまま日付が変わる直前に投稿。その後ずっと穴埋めに奔走してコンテストの感想をいくつか書き足した。午前7時半就寝。

08/15(火)

午後3時くらいに起きたと思う。二度寝もせずずっと布団でハーメルンを読んでいた。

午後10時くらいになって今日のCFが普段より1時間早いことに気づいた。これはつまり30分後ということで慌てて布団から出て備えたが、そもそもCFが落ちていて参加登録もできない。こういうとき情報が得られなくて困る……と思っていたらTelegramに公式チャンネルがあるらしい。そこを見たら1時間延期と書かれていた。

Codeforces Official – Telegram

そのロスタイムでさらにハーメルンを読み進め、「非科学的な犯罪事件を解決するために必要なものはなんですか？」の最新話に追いついた。今年3月に投稿されたⅡ‐Ⅲ章以降を溜めていたが、なぜすぐ読まなかったのだろうと思うくらい面白く、また好みの展開でもあった。好みの展開というのは主人公の無双である。

syosetu.org

その後何気なく活動報告に目を通したら、つい最近書籍化の情報が出ていてびっくりした。非常に嬉しい。

いつもお付き合い頂きありがとうございます！
この度、私の書いている小説「非科学的な犯罪事件を解決するために必要なものはなんですか？」が書籍化することとなりました！

詳細は以下の通りです！
— 色付きカルテ (@irotukikarute) 2023年8月10日

午後11時半からCF #893 div.2に出た。結局普段と同じ時間。

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

Aは両者が押せるボタンを優先的に押すのがどちらにとっても最善なので、 $c$ を使い切るのがどちらかで場合分け。

Bはちょっと難しい。言われた通りに計算するのは大変なので簡単な方法を考えた。番兵として $s_0=1$ と $s_{m+1}=n+1$ を置き、 $i=0\dots m$ に対し $\lceil(s_{i+1}-s_i)/d\rceil$ を足し合わせると答えになる。こうしてしまえば $s$ を一つ取り除くときの差分更新も自明になる。

Cは $d\le n/2$ であり、実際に $1\dots n/2$ を全部作れる。 $i=1\dots n/2$ に対し $i\leftrightarrow 2i$ という辺を考えると枝分かれがないため何本かのパスに分かれ、一列に並べると必ず $i$ と $2i$ が隣り合っている。

Dは「インデックス $i$ より左だけ抜き出し、そこで高々 $j$ 手使ったときの連続する0の最大個数」のような情報が $O(n^2)$ で計算できるので、 $O(nk)$ で適切にマージすることで各 $l_0$ に対する達成可能な $l_1$ の最大値が求まる。あとは $a$ と $l_0$ を全探索すればよい。一次関数の最大化に見えたのでCHTが頭をよぎるが、何でも全探索できてしまう。

E1は簡単。+と-のクエリを永続stackの操作だと思ってABC273-Eのように木構造で表現すれば、ノードの履歴を記録しておくことでロールバックにも対応できる。木の各ノードに対応する答えを最後にDFSでまとめて計算し、出力クエリに答えればよい。 $k$ が大きい場合に備え祖先への移動をダブリングで行うことにだけ注意。

E2はオンラインクエリなので、+クエリの度に $x$ が $a$ にすでに存在するかどうか判定することで解く。このために $a$ に入っている要素の集合を持っておきたいが、-クエリに対して愚直に更新するのは当然不可能。そこで、更新するタイミングを遅延してみた。

$x$ に対しそれが追加されたときのノードを記録しておく。新たに同じ $x$ が追加された場合、記録していたノードが今のノードの祖先にあるかを判定する。祖先にあれば $a$ に存在しているということになる。そうでない場合今のノードを記録に上書きする。今後上書きされたノードが必要になるのは今の追加がロールバックされたときだけだから、そのとき一緒に上書きもロールバックすればよい。

祖先・子孫関係の判定は、E1の時点ですでに構築していたダブリングテーブルを流用してLCAを計算することで行った。ノードの記録にうっかりmapを使ってしまったが、それでも2sec。配列に書き換えたら1.2secまで高速化された。

全完4位。

www.youtube.com

明日は丸一日家飲みする予定で、さらに今週のセミナーは木曜日に行われる。つまりセミナー準備をできるのは今日が最後だった。余裕を持ってやっておこうと思ってはいたのだが実現できた試しはなく、当然今回もまだ何も準備していない。慌てて取り掛かり朝までかけて何とか形にした。内容は明らかに薄くなってしまった。

午前8時過ぎ就寝。

08/16(水)

正午にディズニーストア前で待ち合わせの予定だったので午前10時半から15分おきに目覚ましをかけていたが、すべて貫通してちょうど正午の目覚ましで起きた。それ以降の目覚ましはかけていなかったので、ここで起きることができたのは不幸中の幸いか。慌てて遅刻するとの連絡を入れ、家を出た。

何とか合流し北京餃子で食事。ドンキに寄ってお菓子とお酒を買い午後2時くらいから家飲みを開始した。今日の相手はホスフィンではなく一昨年院試ゼミを一緒にやった数学科の友人の一人。あまりお酒は飲まないとの話だったので、今買ったほろよい以外には準備していない。

飲酒します pic.twitter.com/iZ9Us8D24K
— こたつがめ (@kotatsugame_t) 2023年8月16日

今日はボドゲ三昧。自分の持っていた「Lemures」「Blade Rondo」「タギロン」「Quarto」「ヨメン」に加え持ってきてくれた「ラブレター」をプレイした。感想はツイートに書いたがここでも述べておく。

「Lemures」は無事クリアできてよかった。やはりソウルブーストはたくさんやっておくべきらしい。逆にそれさえ守ればクリア自体は難しくなさそうに見えるから、エンディングを選ぶ余裕も生まれようというものだ。

「Blade Rondo」は持っている3作を全部プレイしたがずっと負け続き。自分の笑顔は引きつっていなかっただろうか。友人は初見なのに、ちゃんとどうやって勝つかビジョンを持ってデッキを組んでいて上手すぎる。自分はこのカードを使いたいな、とかこのコンボを決めたいな、くらいの局所的な考えしか持てておらず、この違いが終盤ライフポイントを削り切れるかどうかに関わってきた……ように思う。

Lemures：前回の経験を活かし、ひたすらソウルブーストして無事勝利
Blade Rondo：初見プレイの友人に6連敗して顔なくなりかけた。長男でなければ耐えられなかった pic.twitter.com/UBM06DyuLp
— こたつがめ (@kotatsugame_t) 2023年8月16日

「タギロン」はやはり楽しい。縛りプレイも案外成立した。ただしやはり決着ターンは遅くなる。ありうるパターンを全部考えて削っていくということができないので、自分はいつも3枚の和を聞き、他の情報と合わせてそこの数字を特定するところから始めていた。しかしそうすると終盤色がわからなくて困る。

「Quarto」は守りに入るとすぐ引き分けになってしまうのでガンガン攻めてリーチを作っていくのが楽しい。例えば写真に写っている盤面は、右隅に駒を置くと二つリーチが発生して相手に渡せる駒が一つしかなくなる。しかしそれを渡された側は、どこに置き、そして何を相手に渡したとしても確実にクアルトを作らせてしまうため必敗。この必敗状態くらい手が制限されないと読み切れないので、その意味でもリーチがたくさんあるほうがやりやすかった。

「ヨメン」はよくわからない。どんな置き方が強いのかもどんな質問が強いのかもわからない。

タギロン：メモなし・1手30秒でやったら辛い。個人的には制限なしが全力という感じがして心地よい
Quarto：この盤面、黒・高・丸・穴の駒を渡された側が勝つらしいです
ヨメン：相変わらずよくわからないまま勝ったり負けたり負けたりした pic.twitter.com/b1BBVxdpb8
— こたつがめ (@kotatsugame_t) 2023年8月16日

「ラブレター」はほんの少ししかプレイしなかったが、わかりやすいルールだし一瞬で1ゲーム終わるしでかなり手軽だった。

午後11時半に解散。買ってきたほろよいを何とか全部飲み切ることに成功したが、アルコールよりも水分が辛くて腹を壊してしまった。布団に入ってカクヨムを読んでいるうち寝落ち。午前2時くらいだったはず。

08/17(木)

午前10時起床。カクヨムを読み続けていた。2作読了。

1作目、「Ghoti'　前世で読んでたガチ競技系世界に転生してバーチャル配信者達の師匠になった」。主人公のストイックさは非常に好み。しかし文章がクドすぎて読みづらかった。いい感じのシーンの直前に少し溜めがあるのはワクワクするのでもちろん良いが、それが長すぎるように感じた。

kakuyomu.jp

2作目、「ダンジョンで釣りしてたら同じクラスの美少女配信者に見つかってバズった件」。主人公が謎すぎるが、何であっても強いのは大歓迎。ヒロインの配信活動との関わり方も無理なく受け入れられた。自分の地雷がどのあたりにあるのかよくわからない……。

kakuyomu.jp

午後2時から2時間ほど二度寝して、シャワーを浴び大学に向かった。午後5時からセミナー開始。先生が来ないなと思って数分待っていたが、メールを確認したら早くZoomに入ってきてくださいと言われていた。今日はオンラインだったらしい。持ってきているノートPCはマイクが動かないので、非常にまずい。

とりあえず最初2時間、海外の学生の発表を聞いた。先々週の日記に書いた通り春先に読もうとして失敗した論文への再チャレンジだったが、今回もやはり理解できなかった。というかどうやらひたすら場合分けしているらしく、ちゃんと自分で考えないと納得なんてどうやったってできない。まあそういうことが分かっただけでも進歩だと思いたい。これをセミナーで扱うのは間違いだったということで。

休憩を長めに取ってもらい、その間に急いで帰宅して自分の発表を始めた。内容は火曜日から更新なしで薄いままだが、英語による発表なのでそのくらいしか喋られないだろうというのを実は分かっていた。用意した分をしっかり全部扱って終了。買ってからあまり出番のない板タブを久しぶりに使えて嬉しかった。

海外の学生がZoomを抜けてから、さらに先生と修論についてあれこれ話した。次回のセミナー日程や何を発表するかを大まかに決め、午後10時過ぎに解散。

シャワーを浴びて午後11時半からECR153に出た。

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

Aから難しい。どうせギャグだと思って考えると()を繰り返すのが強いことに気づいた。この部分文字列になるような $s$ はどの隣接2文字も異なるため、今度は(((...()...)))の部分文字列にならない。唯一の例外はサンプルにある()だけである。

Bは額面 $1$ の通常コインを使い切るか、少し余らせて額面 $k$ のfancyコインを多く使うかしか考えなくてよい。あとは算数を頑張る。Cは $p_i$ の昇順にそこに置いた人が勝つか負けるかを判定していく。判定は勝ち負けそれぞれ最小の $i$ だけ持てば可能なので、全体で線形時間にできる。Dは0を1に書き換えた回数と1を0に書き換えた回数を持つdp。 $O(|s|^5)$ に見えるがbitsetが使えるし定数倍も非常に良いので爆速。

Eは大変だった。結論から言えばこれは $26\times 26$ 個の超頂点を付け加えたグラフ上の最短距離を求める問題と見なせて、各超頂点からの最短距離を前計算すれば通る超頂点を一つ全探索して前半と後半に分けることで解ける。超頂点を通らない移動方法の距離は簡単にわかる。

コンテスト中はあまり超頂点を意識しないまま実装に移って泥沼にはまり込んでしまった。7ペナ。特に前計算が下手くそで、最終的には超頂点同士の距離をワーシャルフロイドで求めてから超頂点以外だけ見て幅優先探索していた。

Fは結構すぐわかったが実装する時間がなく終了。5完46位。

追加15分でFの実装が完成し一発で通った。 $x=1$ と固定してよい。このときすべての(と)のペアに対し、 $y$ がどの値以上・以下なら(が)の前に来るかわかる。この情報を見ながら $y$ をどんどん大きくしていくと、常に各)に対して「自分より前に並ぶ(の数」を管理できる。

)はこの数の昇順に並んでいると思えるため、管理している数の多重集合を $C$ とおいたとき $k=0\dots n$ について $\#\{c\in C\mid c\le k\}\le k$ が成り立っていることが正しい括弧列となる必要十分条件になる。 $C$ には1要素のインクリメント・デクリメントだけ行えればよいので、例えば $\#\{c\in C\mid c\le k\}-k$ をセグ木に乗せておけば更新も判定もできる。計算量は $O(n^2\log n)$ 。 $y$ の値に関する以上・以下の取り扱いには注意。

www.youtube.com

午前3時から3時間でDMOJのコンテストに出た。タイミングがなかなかなくて、金曜日の午後1時までなのにこんなギリギリでの参加になってしまった。逆にもうすぐ終わるからこそ感想をここに書ける。

Yet Another Contest 7 - DMOJ: Modern Online Judge

P1は基本の不便度が $\lfloor a/2\rfloor$ で、 $a$ が偶数かつ偶数ページから開始するときのみ $a/2-1$ になる、という風に整理できる。

P2はマスを全部辿るパスを取って $1$ から $NM$ まで順に置くのがよい。すると気にするべきは $NM$ の4近傍に $NM$ と互いに素な $NM-1$ 以外の数があるかどうかという話になり、適当にジグザグのパターンを決めて実験したら上手くいっていた。

P3は十分な日数が経過した後に読んでいる本に応じてグループ分けすればよいとわかるから、 $P$ から作ったfunctional graphのループ長の和を最大化する問題となった。これはループに含まれない最長パスを取ってループにするのが最適。

P4はやけに見覚えのある問題設定だったが全然解けず、最終的にはそれっぽい解法で計算量保証を付けずに通した。パパラッチのいる頂点は連結成分をなすからその葉だけを管理する、というもの。沢山あっても操作のたびに合流してすぐ少なくなるだろうと考えた。

管理するのは葉だけだが、パパラッチのいる頂点にはすべてフラグを立てておく。このフラグを更新しながら頂点数もカウントしていく。クエリに対しては頂点 $a$ にパパラッチがいるかどうかで処理を分ける。いるなら、単にその方向に向かって全ての葉から1歩進み、移動前の頂点のフラグを下ろせばよい。

いない場合はやや面倒で、中途半端な位置にいたパパラッチが移動して葉となる可能性がある。そのような頂点は適当な葉一つと $a$ の間を結ぶパスの上で二分探索することで特定でき、あとは先ほどとほぼ同様。ほぼと言ったのは移動前の頂点のフラグを下ろさない場合もあるからである。

最後に葉の重複を除き、また隣接する頂点を舐めて本当に葉であるかをチェックして次の葉とする。ランダムケースでチェックしたら案外すぐ合ってくれた。隣接する頂点を舐めるのは時間的に厳しいかとも思ったが、なぜか十分高速だった。

P5は並列二分探索で移動回数248316回、48点。そこから二分探索の戦略を変えたりちょっとランダム性を入れたりしたが一切改善できなかった。P6は部分点1だけ。遅延セグ木を2本持てばよい。部分点3は小さな $X$ に対しては部分点1と同様のデータ構造、大きな $X$ に対しては愚直に操作することで間に合うと思ったが、REが取れずコンテストが終了してしまった。

結果は463点で10位、レートは2909→2916(+7)。P6は終了数分後に範囲外アクセスを見つけて直したら部分点3が通った。もし間に合っていたら30点増加でなんと2位にまで浮上していたこととなる。非常に残念。

疲れ果てて布団に倒れこみ、カクヨムから「妹の迷宮配信を手伝っていた俺が、うっかりＳランクモンスター相手に無双した結果がこちらです」を読了。タイトル・あらすじを見て惹かれるようなダンジョン配信モノがなくなったので、ランキング最上位から読むことにした。評価されているだけあってまあ面白かったとは思うが、特にこれが好みだという設定やシーンはなかった。

kakuyomu.jp

午前9時就寝。

08/18(金)

午後2時半起床。そのまま布団でラノベを2冊読んだ。

1冊目、「女友達は頼めば意外とヤらせてくれる」2巻。やっぱり官能小説だった。1巻から代わり映えしていないように見えてもう満腹。まあ一般レーベルで描写を過激にできるわけもないし仕方ないのだろう。主人公が下着フェチなのもそういう制限から来ているのだろうか。

2冊目、「FPSゲームのコーチを引き受けたら依頼主が人気VTuberの美少女だった」。面白かった。つい昨日読んだカクヨムと設定が似ていてそちらは文章が合わなかったが、こちらは特にそういうこともなく設定の面白さを十分に楽しめた。主人公が目立つシーンもたくさん用意されていて嬉しい。

今日がMulti-Universities Campの最終回だったらしい。結局招待は来なかったし、自分も思ったより余裕がなく不参加となった。

TweetDeckを開いたらTwitter Blueの購入ページにリダイレクトされた。ついに有料化らしい。7月初めにTweetDeckが新デザイン版となったとき、試用期間は1か月だという話を見聞きした覚えがある。そして実際に1か月、正確には1か月半ほどだが経って締め出されたというわけか。APIの更新はかなりグダグダだったのにこういうところはちゃんとやるんですね～という感想。

新しいTweetDeckはそのうちTwitter Blueに加入しなければ使えなくなる予定だということを知った。
週記（2023/07/03-2023/07/09） - kotatsugameの日記

午後9時からyukicoderのtraP 作問ハッカソンコンテスト 001に参加した。

traP 作問ハッカソンコンテスト 001 - yukicoder

Aはよい。Bはギャグ。Cは $3m\pm 1$ のどちらかが4の倍数で、そちらを選ぶと次2回の割る2で必ず今より小さくなってくれる。Dはやるだけ。Eは問題文に書いてある通り実装するとサンプル2が合わない。しばらく考えて、何か不備があると断定し飛ばすことにした。

Fは満腹度の昇順に達成可能な幸福度の最大値とそれを達成する食べ方の数をdpで計算。Gもdpだがこちらはド典型。Hは感染させる人と日付を優先度付きキューに入れてシミュレート。2度目に感染した日と自分が感染させる日が同じ場合は検疫の前に感染させることに注意。

Iは何も考えず、 $H\times W\times 2^2$ 状態で遷移をシミュレートしループを適切にスキップする方法で解いた。Jは後ろから見て累積MINを更新する・または累積MINと一致する要素を抜き出したとき、その間でのみ分割することができる。ここでEの問題文が修正されたので解いた。Kは各マスの前後 $X$ マスだけ抜き出して圧縮しdp。Lは包除原理＋行列木定理。

Mは結構悩んだ。とりあえず45度回転する。1点固定したとき、マンハッタン距離の最大値はすぐわかる。最小値を具体的に求めるのは難しく、rangefreqを使い $\log$ 二つで「最小値がある値以上か」ということが判定できるとしかわからなかった。

そこで点を順番に見ながら答えをどんどんデクリメントしていくことにした。すると「 $P_i$ は今の答え未満か」を合計 $O(N)$ 回判定すればよくなるが、マンハッタン距離の最大値がわかるのだからこれは先ほどの判定問題に帰着される。

Nは桁dp。11の倍数を扱うので桁の交代和を持つ。自分より上が $f$ 、今置く数字が $d$ 、自分より下が $g$ だったとすると、全体が11の倍数なので $f+d+g\equiv 0\pmod{11}$ となっているはず。符号はうまいこと設定されていることにする。 $d$ を削除しても11の倍数になるなら、符号が少しずれて $f-g\equiv 0$ になっているとわかる。今の2式を連立させることで $f$ から置いてはいけない数字 $d$ が求まるので、それを避けて遷移していけばよい。

solved数を見てOを飛ばし、Pに進んだ。例えばパスグラフなら、各辺に耐えられる個数を乗せてりんごの追加を区間ADDで反映し、二分探索で耐えられなくなった辺のうち根から一番遠いものを見つけるという感じで解ける。今は木だがHLDすれば同じ。頂点数については、辺が破壊される度に除外される頂点を愚直に数えても合計で線形時間になる。

Oは全然解けなかったのでscipy.optimizeに頼ったが当然WA。15完2位。

水曜日に飲んだお酒の缶をゴミに出した後、急激な眠気に襲われて寝た。午前2時から3時の間だったはず。

08/19(土)

午前11時起床。今日も同じようにラノベを2冊読んだ。「VTuberなんだが配信切り忘れたら伝説になってた」の6巻と7巻。

5巻ラストで予告されたように6巻は伝説的VTuberの卒業配信への出演がメイン。表紙もあらすじもそれ一色だったが、読んでみるとそのシーンは最後の20ページ程度で、残りはずっと普段通りのバカ騒ぎが描かれていた。今日の気分だとゲラゲラ笑えるものもやりすぎじゃないかと眉をひそめるものもあり、平均すればまあ楽しめたのではないだろうか。

7巻は1冊丸々使って五期生3人の導入が行われた。非常に面白かった。特に構成が上手いと思う。3人がそれぞれ少しずつ間をあけてデビューしたため、初配信ではそれほど好きになれないどころか苦手ですらあったキャラも、次のデビューまでに既存キャラとの絡みが描かれて評価が上向いた。この既存キャラにはそれまでにデビューを終えた五期生も含まれるから、自然な流れで同期の関係性まで飲み込める。デビュー順も秀逸で、最後のキャラはかなりアクが強かったがそれでも無理なく受け入れられた。実際のデビューでもこういうことは行われていたのだろうか。

午後5時半から午後8時までは二度寝をしていた。シャワーを浴びて午後9時からABC315に参加した。

KEYENCE Programming Contest 2023 Summer（AtCoder Beginner Contest 315） - AtCoder

Aはよい。Bはoff-by-oneに気を付ける。Cは $S$ が最大のものを任意に一つ選んだ時それを使う解が必ずあると直感したので、信じて実装。

Dは難しい。消した行はどの色が揃っていたかという情報を記録しておくと、残っている列は初期状態に比べて何の色がどれだけ少なくなっているかわかる。このようにして印をつけるべき行あるいは列の判定が色の種類数 $\sigma$ に対する線形時間で行えるので、あとは愚直にシミュレートした。繰り返しは高々 $H+W-3$ 回だから $O(\sigma(H+W)^2)$ になり、まあ間に合いそう。

Eは $P_{i,j}\rightarrow i$ というグラフをトポロジカルソートした後、頂点 $1$ から逆辺を辿ってたどり着ける頂点だけ残して出力した。Fは適当に見積もっても $C\lt 30$ なのでdpするだけ。

Gは $k$ を固定するごとに $(i,j)$ に関する問題を定数時間で解いた。まず包除原理で変数の上限を外し、ちょっと値をずらして $Ai+Bj=X$ なる $0\le i,j$ を数えてみる。 $j$ が存在する条件は $Ai\le X$ かつ $Ai\equiv X\pmod B$ であり、後者については $\gcd(A,B)$ で全体を割ってあったことにすると $i\equiv X\cdot A^{-1}$ とできるため容易に数えられる。 $A^{-1}\bmod B$ は前計算しておける。

Exはオンライン畳み込みに見えるが、ABC213-Exと同じようにやろうとして勘違いしできないと思ってしまった。畳み込みする列を長くしなければならないように見えていた。ところが途方に暮れてググったところ以下の記事を見つけた。問題を書いてある形に合わせた後コードをC++に翻訳しつつ実装したら通ってびっくり。

qiita.com

全完10位。Gでしょうもないペナを生やしてしまい賞金を逃した。またAのFAだったらしい。

www.youtube.com

コードゴルフ。AはNibblesで書いてもFAを取ったbashと同じ長さだった。Eは提出されていたPerlの粗探し。BはNibblesの22Bがあって、縮めようとかなりの時間格闘していたが同じく22Bのコードを複数作るだけに終わった。せっかくだから最初にあった22B=0=1`\2+!=2;;$,@~.,$:_の解読結果を記録しておく。自分が作ったコードも方針は全く同じで、zipだったりmapだったりをいろいろ変えていただけだった。

その方針というのは、 $[[1,1],[1,2],\dots,[1,D_1],[2,1],\dots,[M,D_M]]$ という列を作って真ん中の要素を取り出すというもの。列を作った後の処理は読みやすいので先にやっておく。=0=1`\2[arr]で、まず`\2で列を真っ二つに分け、=1で1番目を取り出し、=0で末尾を取り出す。インデックス0はwrapされて末尾になる。

つまり残りの+!=2;;$,@~.,$:_が列を作っている部分。=2;;$が入力の2行目の数列であり、,@は $1\dots M$ を表す。本来入力の一つ目の数 $M$ を表すのは$だが、今はzipWith!の第2引数となっているため一つずれている。次の~より後ろが丸ごと第3引数の関数で、効果としては $D_i$ と $i$ を受け取り $[[i,1],[i,2],\dots,[i,D_i]]$ を返す。それでzipWithを行った後+でconcatすると所望の列が得られるというわけ。

関数.,$:_を読む。$は第1引数 $D_i$ だから,$で $1\dots D_i$ 。これに対しmap.を行う。変換する関数は:_で、_は一つずれてきた外側の関数の第2引数 $i$ だからこれと何かをcons:する形になっている。何かとは暗黙的な引数であり、今は関数の第1引数$が未使用のためそれが補われる。つまり $j\mapsto[i,j]$ となって求める列を作り出す。