05/08(月)

午後4時過ぎに目覚ましで起床。予定がある前の日は布団に横たわる際必ず目覚ましを掛けるようにしているが、自分のこの習慣にはいつも助けられている。

半からインターン先定例会。先週は何もやっていない。大型連休だから休んでいたというよりは、大型連休だから1on1がなくて尻に火が付かなかったというのが正確なメカニズムである。

勉強会はAHC019の1位解法について。この回の問題は複雑すぎて手が出なかったが、それでもTLで感想戦だけ少し見たはず。そのとき知って目から鱗が落ちたテクニックがあった。二組のシルエットのどちらにも入れられるブロックを作る際、両方のシルエットを同時に見ながらブロックを伸ばしていくというもの。すると同時にどこの位置に置けるかも確定して非常に扱いやすそう。1位解法でも当然のように使われていた。

解散した後しばらく先週の週記を書き進め、シャワーを浴びて午後9時からCF #872 div.1に参加した。

Dashboard - Codeforces Round 872 (Div. 1) - Codeforces

Aはタイプ3の人はその中で被らない限り全員座らせるものとしてよい。あとはタイプ1とタイプ2をどうするかで、どちらか片方しか座らせないなら簡単。両方座らせる場合は、タイプ1の人とタイプ2の人が隣り合うシチュエーションがあり得ないので境目にはタイプ3の人がいる。この人を全探索すればよい。

B1は難しかった。 $k=1$ は自明。 $k=2$ は2頂点を結ぶパス上の点が該当するが、これを2頂点の間にある辺の数 $+1$ だと思うことにすれば各辺に対してそれが答えに加わる場合の数を求められる。 $k=3$ の場合もgoodな頂点がパスをなすと思い込んで実装したらWAで、冷静になるとこのケースも $k=1$ と同じく常に1頂点だと分かった。

B2はB1からの自然な発想ですぐ解けた。 $k$ が奇数なら必ず1頂点になる。偶数なら各辺に対しその左右から $k/2$ 頂点ずつ選ぶ場合の数を足し合わせ、 $k=2$ の時と同様 $\binom{n}{k}$ で割って1足すことで答えが求まる。この解法の正当性は、辺の両端点のうちどちらが距離の総和を小さくするか考えることで得られる。これはつまり辺の左右でいくつずつ頂点を選ぶかの話である。

$k$ が奇数なら必ず総和に差が生まれる。さらに各頂点に対し総和を小さくする方向が高々一意のため、それに従ってグラフを辿ることで必ず1頂点に到達し、そこのみがgoodな頂点である。 $k$ が偶数の場合は総和が一致する辺がパスをなし、その上の頂点がすべてgoodであることが言える。

Cは難しかった。まず各部分木とその根に対し、問題のようなXORが0ではないとしても一致する必要があるから、「一致させるのに必要な最小の手数」と「その手数で達成できる値の集合」を考える。集合に入っていない値については根の値を切り替えることで常に $+1$ で達成可能。

木dpで求めてみる。頂点 $u$ を見ているとき、その子それぞれに対して値と集合を計算してあるとする。最も多くの集合に出現した値、に $a_u$ をXORしたものが手数最小のときの値であり、その手数は子で消費した手数の和に「子の数から出現回数を引いたもの」を足した数となる。

とりあえずこれで正しい答えは出て、問題は集合の管理について。マージテクで扱いたいものの、出現回数最大のもの以外を削除したりと集合を舐める操作が発生して計算量が抑えられないように見える。ところが実は上手くいく。

値とその出現回数を管理したいから、情報はsetではなくmapで持つ。ただしある頂点を出ていくときに返り値として持っていくmapは出現回数が全部1になっている必要がある。全体にXORされた値を別に管理したりしておけば、マージテクで全体の出現回数を持ったmapが計算できる。その最大値も計算途中に求められる。ここまでは良い。

最大値が1だった場合、作ったmapに変更を加えずそのまま返り値としてもよいのが重要。最大値が2以上だった場合は集合を舐めて出現回数が最大値と一致する値だけ取り出し返り値用のmapに入れるが、この時見ることになる値の個数が全部合わせても葉の数で押さえられる。出現回数の総和は葉においてのみたった1だけ増え、値を一つ見るごとに必ず1以上減るからである。

Dはあっけなかった。まず $g(\ast,j)$ の求め方を考える。 $j$ から左に見て行って新しく出現した値の位置にマークしておくと、 $g(i,j)$ は $i$ より右でマークされている最も近い位置を表す。 $g(\ast,j)$ が分かっている状態で $g(\ast,j+1)$ を計算してみると、値が変化するのは $g(j+1,j+1)$ と、 $a_{j+1}$ の出現によって消えたマークの前いくつかであることがわかる。

つまり $g(\ast,j)$ から $g(\ast,j+1)$ への変化は高々2個の区間ADDで表現でき、ひいては $g(\ast,ast)$ のテーブルが矩形ADD $O(n)$ 個で作成できる。クエリはもともとテーブルの矩形和。この2種のオフラインクエリを処理するライブラリに見覚えがあり、窃盗して出したら4secで通った。制約の10⁶とTL 7secは $\log$ 一つと二つを区別しているのだろう。

Point/Rectangle Add Rectangle Sum - ei1333の日記

のこり40分弱真面目にEに取り組んだがほとんど何もわからなかった。システスは全部通って5完15位、2772→2883(+111)。

www.youtube.com

日付が変わる前に先週の週記を投稿した後はネット小説、主になろうを読んでいた。

ハーメルンの「輝かせたくて」が完結した。面白かったのは確かだが終わり方が唐突に見える。これまで読んだ同作者の他作品も同様だったから、今回はそういう人なのだと心の準備はできていた。

syosetu.org

朝方に「【電子書籍＆POD化】神様のドＳ!!～試練だらけのやり直しライフは今日もお嬢様に手厳しい～」を読了。先週日曜日から読み始めて一気読み。そのくらい非常に面白かった。

https://ncode.syosetu.com/n9239ex/

主人公の周りの男子が主人公に向ける感情や上流階級の暮らしぶりの描写が読んでいて楽しい。たまにシリアスな話があると先が気になり、読み進める手を止められなかった。人間関係的ないざこざは中等部の間に一段落した印象で、その後は恋愛描写に紛れ日常生活で度々人の悪意に触れるシーンがある。これは予想もつかないところから飛び込んできたりして強烈なアクセントだった。そういうものを完璧な笑顔と正論で跳ね返す主人公が爽快。

その後もなろうを読み続け、午前8時半就寝。

05/09(火)

午後0時半に起きて大学に向かった。今日は弊研究室への進学を考えている他大学の学生が訪問してくるそうだ。午後1時から集まり、2時間ほど話していた。

まず自分や同級生が勉強している内容について少し喋り、残りの時間は先生が課題として出していたDiestel 1章の演習問題について発表してもらった。演習問題のうちマイナスがついたものは簡単なので課題として適切ではないか、とどこかのタイミングで先生に進言した記憶がある。今日はそれらの問題だった。簡単とは言っても見てみるとなるほどと思わされるものもあって面白い。

購買に寄りつつ帰宅し、荷物を準備して1時間ほどでまた外出した。一泊二日で帰省する。何やら実家でやってほしいことがあるらしい。仙台駅に行って切符を購入し、立ち食いそばを食べて乗車。車内では寝たりなろうを読んだりしていた。

「【本編電子書籍＆POD化】神様のドＳ!!　番外編置き場」を読了。主人公以外が視点人物の話が並んでいて嬉しい。本編にはほんの少ししかなかった。

https://ncode.syosetu.com/n0908fo/

今日は新幹線駅までは迎えに来られる人がいないとのことで富山駅からさらに電車に乗り、午後9時頃に到着した。夕食を摂ってからテレビ番組「笑わない数学」の「無限」回と「四色定理」回の録画を見せてもらった。

「無限」回で紹介された $\mathbb{Z}_{\gt 0}$ の濃度と $\mathbb{Q}_{\gt 0}$ の濃度が等しいことの証明に納得できる人は、元から知っていた人だけではないだろうか。斜めに取っていけばOKですと図だけ見せて終わりにするのはとんちで煙に巻いているだけにも思えてしまいそう。自分は $(p,q)\mapsto(p+q-1)(p+q-2)/2+p$ という $\mathbb{Z}_{\gt 0}^2$ から $\mathbb{Z}_{\gt 0}$ への全単射を構成して初めて飲み込めた記憶がある。

「四色定理」は面白かった。グラフへの帰着やその説明を省略するためグラフが徹底的に避けられていて、ずっと地図に色を塗りながら話をしていた。テレビなので図がたくさん用意されておりむしろ見やすい。特にケンペ鎖の話は、ぐるっとループができて内と外を隔てる様子がはっきり分かって綺麗だった。

実家でやってほしいこととは書類への記名捺印だった。ほんの数文字書くために交通費として往復4万円近く出してもらったと思うとびっくりだが、4月の帰省はドタバタしていたから改めて顔見せできたのはよかった。今回も来た次の日に帰るということでドタバタはしている。

しばらく父と話した後日付が変わる前に布団に入った。しかしその後朝までなろうを読み続けてしまった。午前7時半就寝。

05/10(水)

午後2時に起こされた。昼食を取って実家を出発。電車で富山駅に向かった。

AMAZING TOYAMA pic.twitter.com/SaFrxYkeEP
— こたつがめ (@kotatsugame_t) 2023年5月10日

切符を買った後、1時間弱時間が空いたので駅前のゲーセンでチュウニズムをプレイした。素手だったのでスコアなどは考えず適当に触っていたが、一発プレイで「Calamity Fortune」のAJが出た。

Calamity Fortune AJ pic.twitter.com/FKEZLgPt2w
— こたつがめ (@kotatsugame_t) 2023年5月10日

新幹線の中ではずっとなろうを読んでいた。仙台の部屋を出るときに本を2冊掴んできたので行きと帰りでそれぞれ読もうかと考えていたが結局全てをなろうに捧げてしまった。仙台駅に着いてからゲーセンに行こうとして、その道中にあるアンパンマン像の写真を久しぶりに撮った。

仙台駅を庇い石にされてしまったアンパンマン pic.twitter.com/7NroMntXsF
— こたつがめ (@kotatsugame_t) 2023年5月10日

ゲーセンで1クレだけプレイ。これが04/01から数えて100クレ目となり、初めて全国解禁ポイントを貯めて楽曲を解禁することに成功した。期間内にチュウニズムデュエルをほぼ2回分走り切った結果こんなにプレイ回数が多くなったようだ。

初めて期間内に100クレプレイした pic.twitter.com/nYVX7RPbYc
— こたつがめ (@kotatsugame_t) 2023年5月10日

丸亀製麺で食事して午後9時前に帰宅した。その後シャワーも浴びずになろうを読み耽り、いつの間にか寝落ちしていた。ブラウザの閲覧履歴によれば午前6時過ぎのはず。

05/11(木)

午後3時に目を覚ましてまたなろうを読んでいた。午後4時半になって布団から這い出し、30分だけインターン関連の作業を行って1on1に突入した。

カスみたいな進捗しかないので報告する内容がない。今日も作業メインになってしまった。一つ変な挙動が見つかっているのでそれの調査をしようとしたところ、自分が受け取ったデータがすでに間違っていたことが判明。自分の埋めたバグではなさそうということだけ分かって、以降の調査はデータ作成部に詳しい方に託すことになった。1時間半ほどで終了。

その後もなろうを読み続け、午後11時くらいに「謙虚、堅実をモットーに生きております！」を読了した。火曜日に読み始めて一気読み。さすが累計ランキング上の古典というべきか、信じられないくらい面白かった。

https://ncode.syosetu.com/n4029bs/

直前に読んだ「神様のドＳ!!」と同じ（投稿日時ではこちらが先）現実世界における上流階級の話。そういうものを探して読んでいる。いつ恋愛要素が出てくるんだろうなと思ったらどこまで読んでもそんな雰囲気は一切なく、そのうちコメディがメインになった。これがまた面白い。出てくるキャラがみんないい人ばかりで、別の作品ならシリアスな展開になるところも何事もなく進行するためストレスフリーで読めた。

主人公の中身はポンコツだが外面は完璧に保たれているというのが良い。それを存分に活用して権力を振りかざすシーンも楽しいが、やはり視点人物が主人公以外だとギャップをより一層感じられて嬉しい。ほんの数話しかなかったもののどれも格別だった。

シャワーを浴びてセミナー準備を開始。次回は6.4章の内容を話す。ここで扱う証明のメインはどれも構築だったから、アイディアだけ説明すれば細部の議論はもはや作業となってしまう。あんまり時間をかけるべきではなさそうだなと思いながら読み進め、朝までかけて最後まで準備できた。

ゴミを出して布団に入り、午前7時から1時間ほどなろうを読んで寝落ちした。

05/12(金)

午前11時半に起きて登校し、正午から1時間ほどホスフィンと会って話していた。

解散して数学棟の教室に移動。今日のセミナーは参加者の都合で遅い時間に始まるので、それまで寝たりなろうを読んだりして過ごした。

午後5時にセミナー開始。最初1時間は4月初めにもあった海外の学生の発表で、内容は火曜日と同じ演習問題だった。いくつかしょうもない構築問題があるので聞く側としては何度もやりたいところではない。

次の2時間は同級生の発表。教科書に主張だけ載っていた定理について先生から紹介された論文の解説だった。これも構築。非現実的なサイズになってしまうもののアイディアがとても面白かった。

自分が発表を聞く態度は良くなかった。詰まり気味なのを見てイライラするのはともかく、それを高圧的な口調などで態度に出すのは厳に慎むべきである。さらに悪いことに、ちょっとした失敗を思わず鼻で笑ってしまった。これは人をいたずらに不快にする・あるいは委縮させるだけである。本当に気を付けたい。

最後に残った1時間で自分の発表をした。前提の説明などに時間を取られてほぼ自明な部分しか説明できなかったが、最初に挙げた例が最後に紹介した命題で扱うケースになっていたりと伏線回収が上手くいった感触がある。

急いで帰宅し、午後9時20分からyukicoder 388に参加した。

yukicoder contest 388 - yukicoder

Aは $N\bmod 3$ で場合分け。Bはyukicoderが重なって出現できないので前から貪欲に取れる。Cは $P_1$ と $P_N$ だけ決めて後は $(N-2)!$ を掛けておけばよい。Dはbitごとにそのbitが立っていない $f(L,R)$ の数を数える。

Eはなもりグラフのループ部分を一方向に向き付け、残りをループに向かう方向に向き付ける。ループ上の辺を順に辿る部分の実装で少し手間取った。Fは数の桁和を求める関数 $f$ について $f(a+b)=f(a)+f(b)-9X$ となるような $(a,b)$ を数え上げればよい。下の桁から $f(a)+f(b)-f(a+b)$ を持ちつつ桁dpした。

Gは軸ごとに独立に。 $i$ が増える方向に $h$ 回、もう一方向に $w$ 回ジャンプしたとすれば、その方法は $\binom{h+w}{h}\times\binom{h}{2h-H}\binom{w}{2w-W}$ 通りとなる。 $(h+w)!$ をいったん取り除くと $h$ と $w$ に分けて畳み込める形になるので、そうやって計算した後戻せばよい。畳み込んだ時のインデックスが $h+w$ に対応している。

Hはかなり苦労した。 $A$ をソートした列に $\pm 1$ の操作を繰り返して狭義単調増加にすればよい。あらかじめ $-1,-2,\dots$ をしておくことで広義単調増加に書き直せるので、同じ値にする区間を考える問題になる。区間とそこに出現する要素、揃える先の値の組をstackで管理しつつ先頭から順に見ていった。

見ている要素が直前の要素を揃える先より大きいなら、その要素は独立する区間になる。そうでない場合直前の区間に必ず入れることにした。するとその区間を揃える先の値が小さくなるかもしれない。小さくなる場合はそれを実行し、さらに前の区間とマージするかどうかを考える。これを繰り返した。 $A$ はソートしてあるからそんな急激に小さくなることがなく、デクリメントを1ずつ行っても間に合いそう。

出現する要素をmapでカウントし、揃える先の値より大きい・小さい要素の個数と和を持った。これでデクリメントが実行でき、マージもマージテクで十分高速になる。証明を何もしていないものの出したら通った。

全完13位。Hは $\mathrm{dp}_x$ を最後の値が $x$ である場合のコストとすると、要素 $a$ を追加したときの遷移が累積MINと $|x-a|$ の加算になって、slope trickで典型的に扱える形になるらしい。このテクニックを完全に忘却していた。一時期流行ったが最近見ていない気がする。

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

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

書く

撮った動画はアップロードだけしておいた。ここにリンクを張っておくが、公開はopen hacking phaseが終わってからだった。

www.youtube.com

朝方までずっとなろうを読み、少し日記を書いた後午前8時就寝。

05/13(土)

午後1時半起床。昨日のECRの提出が落ちていないのを確認してから動画を公開した。

午後2時からUniversal Cup 16回目。今日はGomelセット、というよりtouristセットだった。Muscatキャンプ5日目でも使われた問題たちで、これでキャンプで回避した分をすべて回収できたことになる。

Universal Cupで将来的に使われるらしい。回避。
Hello Muscat 2023 参加記 - kotatsugameの日記

Petrozavodsk Winter 2023. Day 7: Gennady Korotkevich Contest 7 - Dashboard - Contest - QOJ.ac

書く

食事して午後9時からABC301。

パナソニックグループプログラミングコンテスト2023（AtCoder Beginner Contest 301） - AtCoder

AはAとTの個数が一致するケースが面倒。これは一番後ろの文字でないほうを答えればよいが、なんにしても少し場合分けする必要がありそうなのでC++で書いた。

Bは適当に。CはABC003-Bを彷彿とさせる問題設定。文字種ごとにカウントして足りない分を@で埋めていき、足りなくならないことをチェックした。

B - AtCoderトランプ

Dは桁dpでできそうだなと思いつつ場合分けと全探索で押し切った。まず $N$ が、最上位桁が1の2進数で表記してあるとする。 $|N|\gt|S|$ なら $T$ のどれでもよい。 $|N|\lt|S|$ なら $N$ にない桁は全部0にして無視する。以上より、以降 $|N|=|S|$ として考えてよい。

まず $N\in T$ か調べる。そうでない場合 $N$ より真に小さい値を見つける必要があるので、大小関係が確定する桁が存在する。これを下から全探索。それより上の桁で $N$ と一致させられるか、その桁で大小関係を確定させられるかの二つをチェックすればよい。見つかった瞬間に出力する。

EはS、G、oを取り出して互いの距離を求め、どの点に訪れたかbitで持ってdpした。oの個数を $n$ として $O(2^nn^2)$ で解けるが、SもGも特別扱いせず計算に含めたため正確に書けば $2^{n+2}(n+2)^2$ になってしまった。

Fは難しい。DDoS型文字列を含むものを数え上げることにした。2文字目として最も左にある位置を固定した場合、それより右は小文字と大文字が順に現れればいいだけだから簡単に計算できる。よって位置を固定し、そこが大文字で、かつ先頭から見て初めて同じ大文字が2回出現した位置であるという条件を満たそうとした。

固定した位置に初めから大文字があった場合、それが以前に出現しているかどうかで場合分けするが、やることはほぼ変わらない。どちらも?を埋めるために使える大文字の集合というのが定まるので、そのうち何文字を使うか全探索し、組合わせと26のべき乗を掛け合わせたものが場合の数になる。固定した位置が?でも同様。どちらも高々26回しかループが回らないので十分高速である。

Gもかなり難しかった。人 $i$ がいる点を $P_i$ と書くことにする。人 $i$ の陰に人 $j$ が隠れる場合、点 $p$ は直線 $P_iP_j$ 上にある。よって「直線を列挙し、1本の直線に乗る最大の人数を求める」「直線の交点を列挙し、そこを $p$ の候補として全探索する」ことができれば解ける。ここで考える直線は $X\lt 0$ の領域を通っているもののみである。

前者については、直線に乗る人のうち $X$ 座標が最小の人 $i$ を固定して考えた。それ以外の人 $j$ （ただし $X_i\lt X_j$ ）について直線 $P_iP_j$ を考え、等しいものをまとめる。直線 $P_iP_j$ と $YZ$ 平面の交点を考えれば、直線が一致することと交点が一致することが同値なので、これでまとめることができる。

後者で直線の交点を列挙するのには、直線を媒介変数表示し二つの変数を持つ一次方程式を座標軸3本分連立させて解くしかない。ただし今直線の方向ベクトルの $X$ 成分がゼロでないとわかっているため、ここを見ることで直ちに変数を一つにまとめられて、場合分けはそれほど多くなかった。

あとは固定した $p$ に対しての計算方法。 $pP_i$ という直線と $YZ$ 平面の交点を求めることで、 $p$ から見て一直線に並ぶ点を列挙できる。一つの $p$ に対し計算量 $O(N\log N)$ 。直線が $O(N^2)$ 本あるので交点は $O(N^4)$ 個であり、間に合う。

等しい点をまとめる部分で誤差の扱いに失敗して5WA。mapやsetを使っている場合使われる比較関数は<であり、==ではない。<の実装でちゃんとEPSを使わず値を比較していたため落ち続けていた。 $O(N^5\log N)$ の実行時間は全く問題なかった。

Exにはほとんど時間が残せなかった。クエリについて、辺 $A$ の重みを $W$ とすると、「 $W$ 以下の重みを持つ辺のみで $S$ から $T$ に行ける」「そこから辺 $A$ を取り除くと行けなくなる」の2条件を満たす場合のみ答えが1になる。なので辺の重みでソートしておけばdynamic connectivityで解ける形になっている。10分ちょっと遅れて実装が終わったがハチャメチャにTLEしてダメだった。

7完、Gの代わりにExを解いた人に負けて16位。コードゴルフはABDのみ。

AはVimで非常にうまく書けた。まず末尾の文字を削除してレジスタに入れる。次にATまたはTAという文字列が存在する限り削除し続ける。最後にカーソル下にある文字を削除してレジスタに入れ、ファイル全体をレジスタにある文字で置き換える。これがうまくいくことを確認しておきたい。

ATまたはTAを削除し続けるので、最後にはAとTの一方しか残らない。最初 $S$ にAが $a$ 文字、Tが $t$ 文字あり、末尾の文字がAであった場合を考えよう。 $a-1\gt t$ なら最後にAが残り、答えもAである。 $a-1\lt t$ なら最後にTが残り、 $a=t$ と $a\lt t$ どちらのケースでも答えはTなのでOK。

$a-1=t$ の場合答えはAである。「最後にカーソル下にある文字を削除」する際、文字が存在しないため最初に削除した文字Aがレジスタに残るのがポイント。これでファイル全体を置き換えるのだから、確かにAを書き込めている。

BはRaku。...という演算子は単純な範囲生成に比べ強力で、例えば3...1と書くと降順のリスト(3,2,1)を生成してくれる。これを使えたらいいなと思って試していたら1...4...2が(1,2,3,4,3,2)になることに気づいた。どうやら繋げられるらしい。入力をこの演算子でreduceするだけで事が済んでしまった。

Dは解説の「楽な実装」をPerlで書いた。?を検索し最も先頭にあるものにヒットさせ、文字列の置換先として1にするか否かの判定コードを置いておく。オプションを付け、置き換える前に置換先文字列をPerlコードとして評価するようにすればよい。

www.youtube.com

日記を書いたりなろうを読んだりして午前8時就寝。

05/14(日)

午後6時起床。1時間半ほど布団でなろうを読んでいた。食事してシャワーを浴び午後9時からARC160。

AtCoder Regular Contest 160 - AtCoder

Aは先頭の項から決めていく。もともとの $A$ と違う値を持ってきたいなら使える $(L,R)$ は一通りしかないので、そこで答えが決まってしまう。 $L=R$ で操作できるのがちょっと面倒だが、とりあえず実装してサンプル1の $K$ を $1\dots 6$ に変えてチェックし、出したら通った。

Bは一旦 $x\le y\le z$ として数え上げ、等号4パターンそれぞれ係数を掛けて足した。この大小関係だと条件は $yz\le N$ と書ける。制約から $1\le y\le\sqrt N$ を全探索できて、 $y$ を固定すると $x$ と $z$ の範囲はすぐ求まる。

Cは値 $x$ が $c$ 個あるという状態を持って $x$ の昇順にdpした。 $A=x+1$ となる個数を $k$ とすると、 $(x,c)$ から $(x+1,k)\dots(x+1,k+\lfloor c/2\rfloor)$ に遷移できる。このままだと $O(N\max A)$ に見えるが、値が存在する $c$ の最大値を管理しつつその範囲だけ見るようにすれば十分高速なはず。証明はしていない。 $x\le\max A+\log_2 N$ まで見なければならないことに注意。

Dは操作を逆に見て、 $(0,\dots,0)$ から作れる列を数え上げる。 $A_i$ に $K$ 足すのを操作 $i$ 、 $A_i,\dots,A_{i+K-1}$ に $1$ 足すのを操作 $N+i$ とする。明らかに操作 $N+1$ から $2N-K+1$ はそれぞれ $K-1$ 回までしかしなくてよい。逆にこの場合作れる列が一意であることを実験で確かめた。

証明はコンテスト後に行った。操作 $i$ の回数を $c_i$ とし、そこから得られる数列が $A$ だったとする。まず $A_1=Kc_1+c_{N+1}$ であるから、 $c_{N+1}\le K-1$ より $c_1$ と $c_{N+1}$ が特定できる。 $c_{N+1}$ の寄与を残りの $A$ から引くと、今度は $A_2$ を使って同様のことができる。こうして得られた操作回数の列 $c$ は $A$ を生成したものと一致する。

よって数え上げるべきは操作回数の列 $c$ で、 $c_i\ge 0$ 、 $N+1\le i\le 2N-K+1$ で $c_i\le K-1$ 、 $\sum c_i=M/K$ を満たすもの。上限の制限を違反する個数に関して包除することで制限を無視することができ、この場合単なる重複組み合わせになる。 $M/K$ が非常に大きいので前計算はできないものの、毎回 $O(N)$ かけて愚直に計算してよい。また明らかに、 $M/K$ が整数でない場合答えは0。

Eは最近UCで見た気がしないでもない。二重頂点連結なら次数は2以上なので、葉には辺を追加する必要がある。特に葉の数 $k$ が偶数なら、それらをペアにして辺を張るだけで全体を二重頂点連結にする方法がある。

重心分解の要領で「すべての部分木が葉を高々 $k/2$ 個しか持たない」状態を作ると、異なる部分木から選んだ葉をペアにし続けてすべての葉を取り尽くせる。これは答えとしてvalid。根を通るサイクルがたくさんできることや、どの頂点もそこを通るサイクルが十分な数あることから、間接点が存在しないことが確かめられる。

$k$ が奇数の場合、余った葉を $W$ 最小の頂点とペアにするのが得。 $k$ 偶数の場合と同様、「葉を高々 $(k-1)/2$ 個しか持たない」部分木のみになるよう根を決める。 $W$ 最小の頂点が根でない場合、その頂点が存在する部分木以外から一つ葉を選んでペアにする。根だった場合、葉を二つ以上持つ部分木があればそこの一つとペアにする。どちらも残りは上と同様にマッチングすることで適する。