02/28(月)

先週は土日分の日記を溜めていたくせに昼までずっとなろうを読んでいたため、週記の投稿が昼過ぎになってしまった。深夜にCodeChefがあるので徹夜は避けたい。今日はインターン先定例会の直前30分にも別のミーティングが予定されているので、さらに睡眠時間が圧迫されている。午後1時に布団に入り、正直ここまで来たら変わらんだろうと思ってしばらくなろうを読んで、午後1時半に就寝。このとき部屋の電気をつけっぱなしにしてみたが、効果のほどは謎。

午後3時に一旦目覚ましで意識を取り戻し、そこから二度寝で30分追加して午後3時半に起床できた。先ほども書いたように午後4時からミーティングを1つ、デプロイに関する作業手順の話を聞いた。次に定例会。先週の進捗はデプロイの話になる。勉強会まで含め、今週も平穏無事に終わった。毎週の進捗がほぼないので、何か想定外のことが起こりようがない、というのが正しいかもしれない。

ABC241-Gが縮んでいた。3項演算子の2項目と3項目の型を揃える（これはあまり正確な言い方ではないかもしれない）ため、数値型を得るためにわざわざ定数を置いていたところがあった。しかしそのようなことをしなくても、このコードでinsertメソッドの返り値はポインタなので、それの指す数値を参照してやればよかったらしい。setのinsertの返り値がポインタとinsertに成功したかどうかのフラグのpairである一方、multisetはポインタのみであるらしい。言われてみれば納得できる仕様である。

atcoder.jp

しばらくなろうを読んでから、CodeChefの前に仮眠を取ろうと思って午後8時半に寝た。

03/01(火)

02/28 午後11時に起きた記憶がある。もう少し寝ていてもいいだろうと思って15分後に目覚ましをかけ二度寝したところ、うっかり爆睡してしまって、次に起きたのは午前2時だった。CodeChefを逃したかと少しがっかり。しかしコンテストサイトを見に行くといつの間にか1日延期されていて、かなり儲けものという気持ちになった。

そこから、時たまYouTube shortsやPixiv小説に浮気しながらも午後1時までずっとなろうを読んでいた。二度寝に失敗し続けていた。昼になったので学食に行って食事し、予約していたラノベを受け取って帰ってきた。毎月25日くらいに出るラノベと1日に出るラノベは、僕が注目しているレーベルということもあっていつもそれなりの冊数を買う。02/25と03/01の間がいつもよりかなり短かったため間で受け取りに行くことができず、今日は11冊買うことになった。

会計を担当した店員さんがバーコードリーダーに本を近づける度、つり銭トレーに貼られているコーティングされたPOPに本の天の部分が突き刺さっていて、さすがに血の気が引いた。急いでトレーを引き離した。実は生協で買った本はそれなりの確率で帯が曲がっていたり、破れていたり、角が潰れていたりする。これらについては輸送時の問題ということも考えられるけど、そこからさらに店頭で傷を付けられるとげんなりしてしまう。細かいことを言えば、本をまとめている輪ゴムを外すときに帯のほうに引っ張るのは避けてほしいし、本を台の上を滑らせて移動させるのも止めてほしい。ただ向こうも本を専門に取り扱っているわけではないし、無意識でそういう扱いをする人間に細かく注文を付けても実行は難しいだろうという感覚があるので、一言カードでクレームを入れるまでには至っていない。

現在支払っているNHKの受信料は、学生ということで家族割引が適用されている。次の4月からそれが終了してしまうというハガキが来たので、続けて適用してもらうための手続きが必要となった。これは残念ながらネット上では行えないようで、コールセンターに電話を掛けた。平日昼間とはいえつながるまで10分程度の待ち時間があり、事情を説明すると書類を送ってもらえることになった。こういう作業をすると改めて受信料の無為さを意識することになる。何もかもスマホに使いもしないワンセグ機能がついているのが悪いので、次買うときはついていないものを選ぶようにしよう。受信料の支払い義務を回避するためにそういう機種が増えているという話は耳にしている。

2月が終わったので、2月分の読書記録をまとめてツイートした。先月はハーメルンとなろうに時間を吸い取られたタイプの月だった。

2月の集計
買った：18冊
読んだ：10冊
積読：+8冊
積読（累積）：-3冊
— こたつがめ (@kotatsugame_t) 2022年3月1日

4年後期に取った講義のうち、大学院の講義の先行履修については4月にならないと成績が出ないらしい。それ以外はすでに出そろっており、また先行履修も真に何もしなかったのでどうせDか履修放棄扱いだろうと考え、成績報告のツイートを行った。これで1つのリプライツリーに僕の4年間の軌跡を残すことができたことになる。なかなか感慨深い。いろいろ再履修してきたけれど、結局のところ講義にちゃんと取り組むのが単位取得の必要十分条件だったように思う。ちゃんと取り組むというのは、出席を求める講義なら出席する、課題提出を求める講義ならちゃんと提出する、ということ。

単位取得状況 14/16
単位取得率 88%
大学生活、初見クリアです pic.twitter.com/INjYTG0C64
— こたつがめ (@kotatsugame_t) 2022年3月1日

1年：23/57（40%）
2年：61/67（91%）
3年：40/42（95%）
4年：20/22（91%）
合計：144/188（77%）
— こたつがめ (@kotatsugame_t) 2022年3月1日

午後4時から1時間ほど1on1を行い、その前後30分程度でインターンのコーディングを行った。昨日のミーティングで聞いたデプロイのための作業をこなしていく報告のような感じ。正直よくわからない部分があったので少し介護してもらいながら進めていた。

しばらくなろうを読んで、午後6時半に就寝。CodeChefに向けた仮眠である。

03/02(水)

03/01 午後11時起床。午後11時半からFeburary Lunchtime 2022 div.1に出た。

https://www.codechef.com/LTIME105A

MAGNETSORTは極がすべて等しい場合を除けば2手で必ずソートできるので、1手でソートできるかチェックすることになる。動かさなければならない要素の両端を見つけて、その両側に極が異なる2要素が存在するかをチェックすればよい。MAGICMODは解けなかった。1時間半ほど粘って適当に候補を絞り試すコードを提出したが、TLEどころかWAも出てしまい絶望して次の問題に進んだ。

VISEMALLは0と1が前後半で完全に分かれていなければどこからでもループできて、完全に分かれている場合は後半の要素の先頭からスタートした場合のみ前半の要素の末尾まで一筆書きできる。隣接する要素が異なるインデックスをsetやBITで管理して実装した。COOKPERMは、まず $A$ 、 $B$ をそれぞれ置換と見てループのサイズを求める。 $A$ で長さ $a$ 、 $B$ で長さ $b$ のループに属する要素たち $ab$ 個は、実験すると $\gcd(a,b)$ 個のループに分解されるので、これらをソートするためには $ab-\gcd(a,b)$ 回の操作が必要である。この値をすべての組 $(a,b)$ に対して求める。 $a$ 、 $b$ の種類数がそれぞれ $O(\sqrt N)$ 個しかないので、頻度を数えておけば全探索できる。

PERMXORは謎。まず $\bigoplus_{i=1}^N i$ 、つまり $N$ または $N\oplus 1$ で立っているbitはそれぞれどこかのペアでも立っていなければならない。それ以外はできるだけ $(2a,2a+1)$ のようなペアを作りたい。そのようなペアをできるだけ残しつつ $N$ で立っているbitを1つずつ順番に消していこうと思い、 $N$ 以下の最大の2べきを $2^b$ として $(N-2^b,N)$ というペアを作り $N\leftarrow (N-2^b)\oplus 1$ と更新するような手順を繰り返したら通った。これで $N=2^b$ となった場合は $(1,N)$ というペアを作る必要があるが、それ以外は確かに1bitずつ消していけているし、 $1$ 、 $N$ 以外に使う要素は全部 $(2a,2a+1)$ のようなペアを解体した形になっている。

4完41位で2762→2634(-128)。人生終了。MAGICMODは $\sum_i A_i-\sum_i i$ を割り切るような $X$ しか候補にならないので、全探索できるらしい。天才すぎる。この問題は列を好き勝手に並び替えられるという点で非常に自由度が高い操作を行うので、その並び替えで弄れないもの、すなわち総和に着目するべきだった、と言える。別に初めて見るようなタイプでもないものの、ドハマりしてしまった。

3月ぶんの新刊ラノベを注文した。17冊。新刊チェックについては、2月の中旬にラノベを注文したときから更新がなかった。そのときは以下のような理由で3月発売のラノベを予約していなかったが、大学生協の3月の営業時間が公開されて昼間だけとは言え普通に営業してくれることが分かったので安心して注文できた。

ラノベの新刊チェックと予約をした。とりあえず03/01発売までの19冊。3月に入ってからは大学生協の営業時間がどのようになるのかわからないし、自分の帰省がいつになるかも決まっていないので、確実に受け取れそうな発売日のラノベだけ予約したということ。
週記（2022/02/07-2022/02/13） - kotatsugameの日記

なろうを読みつつテスター作業をした。ふと開いてみたvalidatorに間違いがあって冷や汗が出た。ところで、最近のテスター作業では問題文や解説の文章表現にもいろいろ口を出している。曖昧な表現を厳密なものにするだけにとどまらず、単に文章として読んだときに違和感を得るものも結構遠慮なく書き直している。一応、そういう文章は他の人の創作物であるという認識だから元の表現を尊重しようとは考えているものの、実際書いてみるとどうしても自分の好みが入る。そこまで行くとちょっと微妙な気がしてきているが、伊達にたくさん問題を解いているわけではないのだから、自分の感覚は正しいだろうと信じてそのような修正を行っている。独り善がりな行為に終わらないことを願う。

昼過ぎ布団に入り、さらに1時間ほどなろうを読んでから寝た。午後1時半だった。

03/03(木)

03/02 午後10時半起床。なろうを読んだりYouTubeを見たりしていた。

「ダンダス」というYouTuberがいる。ちょっと前に音割れASMRでバズっていた。他の動画も勢いがあって面白く、いくつか眺めていた。特に好きなものを貼っておく。

ASMR動画を撮ったけど
音量設定間違えてとんでもない動画になった。

フル動画→ https://t.co/m18Gx8o4jj pic.twitter.com/X0aDQ4s38i
— ダンダス (@Dandas315) 2022年1月17日

www.youtube.com

午前4時半に再度寝て、次に午前8時に目を覚ました。YouTubeを開くと「科学の力使いまくって隠居生活」シリーズに更新が来ていたので、視聴した。さらになろうを読んで午前11時半ごろに布団から出た。

www.youtube.com

午後6時までICPC横浜大会のチーム紹介ドキュメントを作成していた。これについては別にメイキング記事を書いて公開する予定だ。昨年のものよりパワーアップしたと自負しているので、ぜひ探して見てほしい。参考までに、昨年のもののメイキング記事はこれだ。

kotatsugame.hatenablog.com

2022/03/10追記：公開した。

kotatsugame.hatenablog.com

自転車を出して外出。まず夕食としてラーメンを食べた。最近TLで故・仙台レジャーランド一番町店の近くに新しいゲーセンができたような話を聞いたのでちょっと探してみたが、見つからず、結局いつものセガ仙台で閉店まで5時間ほどチュウニズムをプレイした。アプデの日だったため待ちがいて、最初1時間ほどは交代しつつのプレイだった。

今日はアプデで追加・通常開放された譜面を埋めるだけで終わり、とはいえ好みの曲だったりちょうどよい難易度だったりしてかなり楽しめた。成果としては追加された14を5つ（全部）AJ、14+を2つAJ、15を2つ（全部）SS。プラチナポゼッションは保たれた。14+について、妖々跋扈は定数14.5と旧基準では13なのでそれほど難しくなかった一方、Elemental Ethnicはさすが旧基準で13+といったところか、単純な譜面に見えたもののかなり苦労させられた。どんどん癖がついて絶望したが何とか捻り出せた。TECHNOPOLIS 2085は譜面動画を何度も見たので余裕だと思っていたはずが、見るのとやるのとでは大違いということで終盤の難しさを思い知った。

妖々跋扈AJ！！！Demetoriかっこよすぎ！！！！！ pic.twitter.com/o1tvGNYyGp
— こたつがめ (@kotatsugame_t) 2022年3月3日

Elemental Ethnic AJ pic.twitter.com/z8SD3QySba
— こたつがめ (@kotatsugame_t) 2022年3月3日

どこが難しい年と思っていたけど見るのとやるのとでは大違い pic.twitter.com/r9Y0Fuc9Ax
— こたつがめ (@kotatsugame_t) 2022年3月3日

立ち食い蕎麦を食べて帰宅。しばらく日記を書いて、午前4時半就寝。

03/04(金)

午前11時半くらいに一瞬起きていた形跡がある。その後またすぐ寝て、次に午後4時起床。東北大学から卒業判定についてのお知らせが来ていて、無事卒業が確定した。別紙学生とあるが、その別紙に自分の学籍番号があったということ。

【理学部】卒業判定について

４年次学生　各位

　　　　　卒業判定について

このことについて，別紙学生は，令和４年３月４日開催の教授会において卒業が承認されましたので，お知らせします。
— こたつがめ (@kotatsugame_t) 2022年3月4日

布団でずっとなろうを読んでいて、午後7時半ごろにまた寝た。次に午後11時に起床。30分後からのCF div.2は、なろうを読むのが止められず見送った。

生活リズムが乱れているので、週末のコンテスト予定を確認しておこうと思ってチェックしていたら、日曜日にOpenCupがあることに気づいた。先週以下のようなことを書いたが、この5月というのは3月の間違いだった。Mar（ch）とMayを取り違えたらしい。

今日は久しぶりのOpenCup……と思ったら、いつの間にか5月に延期されていた。
週記（2022/02/21-2022/02/27） - kotatsugameの日記

そのままずっとなろうを読み続け、午前4時就寝。

03/05(土)

午前7時半起床。なろうを読んだりYouTubeを見たりしていた。

今は「flat-工房」というデュエマを主に扱うYouTuberの動画にハマっている。ありえないくらいテンポがよくて、高速で繰り出される暴言もやたらリズムに乗っていて耳に残る。3分程度の動画をポコポコ出すスタイルのようだけど、ある一定のテーマで作られた動画をまとめたものも投稿されていて、そちらは20分以上あるにも関わらず気づいたら終わっているくらい引き込まれてしまった。もともとが3分だからほぼ無編集でつなぎ合わせるだけでも十分見られる動画になり、最初から最後まで延々高速トークが聞ける。特に好みだったものを貼っておこう。

www.youtube.com

「『バトルゾーンにある自分のクリーチャーを、自分のマナゾーンにあるかのようにタップしてもよい。』と書かれていますが、そんなこといいわけがありません」で説明が放棄されているが、それだけぶっ壊れたカードだったということだろう。どうぶっ壊れているのかについては、このカードに巻き込まれて殿堂入りした他のカードを解説する動画のほうで説明されていた。通常、クリーチャーのコストをいくら軽減しても、文明を支払うために1未満にはならないようカードの効果で定められている。ところがこのとき、出したカードが新たにマナとして扱えることで、1コストでマナ+1、つまり疑似的に0コストでクリーチャーを召喚できるのがヤバいらしい。これでクリーチャーを大量に展開する戦略が猛威を奮ったそうだ。

マナコストを支払うためタップしているので、1ターン待ってから殴るのかななど思っていたが、それですら悠長すぎるらしい。実際に使われた勝ち方としては、他のカードと組み合わせてループすることで何らかのクリーチャーを無限回召喚して、その効果で相手の山札を削ってライブラリーアウトで勝利するというものがあるようだ。

なろうを読み続けて、午後3時半くらいに再度就寝。午後7時に起床。またなろうを読んで、午後9時からABC242に出た。

AtCoder Beginner Contest 242 - AtCoder

AはAWKで書いた。フィールド番号を間違えてWA、しかもページの反応が遅くて提出ボタンを2連打してしまったらしく2ペナついた。BはRakuで書いたらTLEしてしまい、BashでAC。このあたりはジャッジが詰まっていたので、とりあえず両方投げておいてよかったという感じ。以降はC++。Cはdp。Dは非常に難しい。実験すると、 $t$ としては $\bmod 3$ が等しく60をギリギリ超える値まで減らして問題ないことが分かったので、そうした後に $t$ 回のループを回して答えを求めた。Eはどこで辞書順が確定するかを全探索。

Fが合わなくて1時間くらい苦しんでいた。占有する行と列の数を全探索するところまでは良いが、そのあとの包除原理が間違っていた。公式解説で言うところの $f(n,m,x)$ について、 $f(n,m,x)=\binom{nm}{x}-n\binom{(n-1)m}{x}-m\binom{n(m-1)}{x}+nm\binom{(n-1)(m-1)}{x}$ が成り立つと思って実装していた。今日記を書きながら試してみたところ重複の扱いが全くもってダメ。一体どこから出てきた式だっただろうか。しかもこのような計算が軽い嘘包除を考えていたため、黒白それぞれで占有する行と列の数を全探索する $O(N^2M^2)$ のループの中で $f$ の値を計算しようとしており、正しく計算するループがTLEに思えてなかなか思いつけなかった。最終的には解説の動的計画法による計算を4次元それぞれで行うことで解いた。定数倍軽めの $O(N^2M^2(N+M))$ で1200ms。

GはMo。瞬殺だったはずがRE。クエリのソート関数について、ブロックの番号block_numの偶奇によって $r$ 昇順・降順に切り替えようと思ってr[i]<r[j]^block_num%2のようなコードを書いたのが悪かった。これはblock_numが奇数のときr[i]>=r[j]と等しく、このような等号付き不等号を表す関数でソートすると壊れる。配列サイズばかり気にしていて、ランダムケースを試してようやく気づけた。Exは解けず、7完110位。

コードゴルフ。Aはdcで、頑張ってみたら結構うまく縮んだ。 $X$ の値によって $B-A$ 、 $C$ 、 $0$ のどれかを得て、それを $B-A$ で割ったものを答えとする方針。 $A\lt X$ のときは $B\lt X$ を見るのではなく $B-A\lt X-A$ を見ることで、答えとして用意した $B-A$ が流用できてお得。さらに、それらの比較の際引き算してvコマンドに与えることで負かどうかを見るという方法をとると、 $A\lt X$ の時に作った $A-X$ もまた流用できるのでさらにお得になった。BはVimの20Bが早さで負けてあ～と言っていたらPerlの18Bが出てひっくり返った。コンテスト中sort{$a cmp$b}など書きながらなかなか見ない形だなと思っていたが、見ないのは当たり前で、cmpでソートする際はそのようなコードブロックを書く必要がない。

CはRubyがVimで縮むやつで、負け。DもRuby。 $k-1$ の2進数で下 $t$ 桁のpopcountを知りたいとき、digits(2)で得られた配列の先頭 $t$ 要素を切り出すという書き方をすると $t$ が非常に大きくても動いてくれるらしい。その後入力読み込みの改善で取った。EもRuby。文字列の前半分だけ見てbytesでループを回すと、メソッド適用後の値もそのまま文字列になっているので、直接reverseして文字列の後ろ半分と比較することで答えをインクリメントするかどうかが容易にわかる。以降は手付かず。

午後11時半からMarch Cook-Off 2022 div.1に出た。

https://www.codechef.com/COOK139A

ALTERNATEDIVは $(i,2i)$ を $i=N$ から降順に並べた。NANDXORはいつだかのオンサイトのA問題で見たやつで、この制約下でpopcountは高々30種類しかないので、同じ要素を使ったペアが被りまくるとしても $30N$ 回くらい探索すれば見つかることが期待できる。ただし無思考で配列に出現したペアを保存していくだけでは、チェックに時間がかかってしまい解けない。ここで丁寧に考えると、ペアとしては出現した順番に先頭3個を保存しておけばよいことがわかる。同じpopcountのペアが3個出現したとして、まだ答えが見つかっていないなら、それらは $\{(A,B),(A,C),(B,C)\}$ または $\{(A,B),(A,C),(A,D)\}$ のような形をしている。前者の場合は次出現したペアが何であれ被りがない相方が見つかるので良い。後者の場合は、 $A$ を含むようなペアがこの後何個見つかっても無意味な一方、 $A$ を含まないペアはこれまた3つのうちどれかと被りがないことが言える。

A - Equal Weight

SECRETREEは面白かった。 $(1,i,j)$ を聞くと、 $1$ を根としたときに $j$ が $i$ の部分木内にあるかどうかがわかる。これを全部聞くと木の状態が復元できる。復元の方法は、頑張って直接の親を見つけるなどということを考えずとも、トポロジカルソートを行うと入次数が0になった瞬間の辺が木に含まれる辺であることが言える。

PO2は面倒。基本的に値が大きいほうから貪欲に取ってよい。ある要素を選ばないことによって新たに最大2つの要素を選べるようになる可能性があるが、その2つの要素がどちらも選ばないことにした要素より小さければ、問題設定から2つ合わせても選ばない要素に勝てないため。つまり、 $\max P$ だけ取り出して見たとき、奇数個連続しているような箇所の選び方が決まる。偶数個連続している箇所は左右にずらす自由度があって先ほどの性質が成り立たないが、よく考えてみるとこの場合はその連続している箇所を削除した状態で考えてもよいことがわかる。結局その箇所の両隣を2つとも選べることはないからだ。以上のことを $P$ の値の降順に行っていけばよい。ただ実装が面倒だった。削除した箇所はどこまで削除したかを双方向連結リストの要領で管理して、選び方が決まった場所はその両隣も使えないようチェックを入れた。サンプルを合わせて祈るように投げたら1発で通ってくれた。フルフィードバックじゃないと絶対にやりたくないタイプの実装だった。

PO2で苦しんでいる間にその次の2問のsolvedのほうが多くなっていた。まあたくさん解かれているので簡単。FLIPOINTSはflipしたい点を全探索して、ちゃんと選べるかチェックした。これは点の凸包2つが重ならないかで決まる。そうして選び出した遷移を使ってBFSを行う。どうせ遷移の種類は少ないだろうとエスパーして、特に工夫なく探索した。凸包2つが包含関係にある場合でミスして1WA。遷移の種類は高々 $N^2$ 個らしい。OH1DCAREは列をflipするかどうかで2-SATが作れて、辺数 $O(NM^2)$ のところをABC210-Fのようにすることで $O(NM)$ に減らす。

math.stackexchange.com

F - Coprime Solitaire

6完6位で2634→2744(+110)。水曜日の傷が深すぎてhighestに戻れていない。

ABC242-Cについて。この数列はOEISにある。FORMULAの部分を見ると母関数が書かれていて、分母を見ることで数列の漸化式が得られる。なぜか外に出ている負号を入れると $(1-x)(1-4x+x^2+6x^3+x^4)$ で、 $1-x$ で割るのは累積和を取ることだから、逆に差分の漸化式が $a_n=4a_{n-1}-a_{n-2}-6a_{n-3}-a_{n-4}$ だとわかる。ただし先頭の数項では成り立たないようで、しばらく首を捻っていた。 $1-x$ も掛けると今度は直接値が出る漸化式も得られるが、どちらにしてもdpで計算するよりコードは長くなった。dcでもTLEして通らないのでダメ。

A126363 - OEIS

朝方はなろうを読みつつ日記を書いていた。明日は午後1時から模擬地区予選ということで、午前8時くらいには布団に入ったはずが、うっかりなろうを読み続けてしまい午前10時就寝。

03/06(日)

正午の目覚ましで意識は取り戻したものの起きられるはずがなく、結局午後1時にハッと目覚めた。Slackで起床確認されており申し訳のなさがある。またこのとき、OpenCupがさらに延期されていたことに気づいた。

食事もせずにコンテスト開始。コンテスト中の様子は参加記を書いた。

kotatsugame.hatenablog.com

午後6時に終了。前述のとおり今日はOpenCupがないので、食事して午後7時ちょっと前からCF #775 div.1に参加した。

Dashboard - Codeforces Round #775 (Div. 1, based on Moscow Open Olympiad in Informatics) - Codeforces

Aはよい。Bは $\lfloor y/x\rfloor$ をいろいろ調べるとき、 $y$ でループを回すと商列挙で $O(N\sqrt N)$ かかるところを、 $x$ でループを回すと調和級数で $O(N\log N)$ になるというやつ。 $x\mid y$ なるペアを調べるときに同じ現象が発生するほうが典型的か。具体的に $x$ でどうループを回すのかが思いつかず、しばらく迷走していた。数列に存在する値 $x$ と存在しない値 $k$ によって作られた区間 $[kx,(k+1)x)$ に、数列に存在する値が含まれているとアウト。判定は出現したかどうかのbool値配列の累積和で行える。

Cは昨日のABC242-Eみたいに先頭から決めていくやつ。 $s$ のヒストグラム $cnt$ を作っておくと、まずすべての並び替えが $C=\frac{n!}{\prod cnt_i!}$ と書ける。先頭の要素として $1\le i\lt t_1$ を選ぶと、残りの並び替えは $cnt$ の差分を考えて $C\times\frac{cnt_i}{n}$ と書ける。 $cnt$ の累積和をBITで管理しておけば、この値をすべての $i$ に対して求めた和が得られる。先頭要素を $t_1$ に固定して次に進むときは、 $C\leftarrow C\times\frac{cnt_{t_1}}{n}$ 、 $cnt_{t_1}\leftarrow cnt_{t_1}-1$ 、 $n\leftarrow n-1$ と更新して次に進む。次に進んで $n=0$ だった場合は答えをインクリメントしてbreak、 $cnt_{t}=0$ だった場合はそのままbreakして出力。 $C\times\frac{cnt_i}{n}$ の式を勘違いして1WA。

Dは難しかった。眠気も強くフラフラしながら考察していたが何とか解けてよかった。 $a_1$ 、 $a_2$ 、 $a_3$ の累積和を取ったりして整理すると、移動経路のマスの総和が下に移動するときの列を $i,j$ （ただし $i\le j$ ）として $L_i+R_j$ という形で表せる。まず区間を一つだけ使う場合を考えると、 $(\max L,\max R,\max L_i+R_j)$ のようなデータをセグ木に乗せることで計算できる。次に区間を複数使う場合について、 $L$ の値のみ考えた場合はdpができる。区間を $r$ の昇順に並べて、 $dp_r\leftarrow \max(\max_{l-1\le i\le r-1}dp_i,\max_{l\le i\le r}L_i)-k$ という更新をすればよい。最終的に選ばれる区間は包含関係にはないので、このように $r$ の位置にdpの値をセットしておいても次の区間で必ずその値を参照できるからだ。この計算をした後、新たに $L_i\leftarrow\max(L_i,dp_{i-1})$ と定めると、先ほどの区間を一つだけ使う場合に帰着できる。