2024-04-28

ABC209-F Deforestation O(N log^2 N)解

atcoder.jp
が $O(N \log^2 N)$ で解けるよという話です。特に何か面白いと言ったことはなくて、ただの土木ですが、一応。

必要十分条件は
各 $i=1,2,\dots,N-1$ について
・ $H_i < H_{i+1}$ なら $P_i > P_{i+1}$
・ $H_i > H_{i+1}$ なら $P_i < P_{i+1}$
となっていることです。

ここで、 $H_i = H_{i+1}$ であるような $i$ について $i,i+1$ で区切って、それぞれの列について問題を解いてからその積に適切な多項係数をかければよいことを考えると、結局各 $i$ について $P_i > P_{i+1}$ または $P_i < P_{i+1}$ という条件が設定されていて、その条件を満たすような順列を数え上げれば良いです。これはEDPC-Tなわけですが、これは包除原理を考えると、分割統治+FFTで $O(N \log^2 N)$ で解くことができます。
詳しくは、Nachiaさんの裏EDPCなどを参照してください :

www.mathenachia.blog

実装例だけ載せておきます:

atcoder.jp

2024-02-06

JOI2023/2024本選参加記

2024/1/28,2/4に開催されたJOI 2023/2024本選に参加しました。その参加記です。

2/3以前

今年のJOIの自己紹介動画はなんか期限が去年よりもかなり早く設定されていて、今年は同学年の競プロerでやる新年会でロシアンたこ焼きやるのでは間に合わなくて、ネタに困ってしまった。ずるずる引きずってたらついに期限の大晦日になってしまった。家の事情で忘年会に行っていて、普通に諦めて夏撮った自分の写真に言葉を添えて提出した。

本選競技については、今年は春合宿に行きたいと思っていたのだけれども、普段からJOIサボる人はずっとサボるらしく、結局本選競技の週になってようやくJOIの過去問に触り始めた。でも結局触ったものといえば、去年の本選と一昨年の本選だけで、結局数問しか追加では解いてなくて、JOI本選には
難易度7 : 8/51 AC
難易度8 : 3/33 AC
難易度9 : 4/60 AC
難易度10 : 1/48 AC
難易度11 : 0/59 AC
難易度12 : 1/41 AC
という悲惨な状況で挑んだ。

海外OIも、同学年の競プロer数人でバチャで手をつけようとしたが、自分は通した人に解法は正しいと言われたのに、実装が下手すぎて永遠に通せなくて、萎えて結局1問も解けていない。2/3にtatyamさんがJOI本選模擬を立ててくれていたが、自分はちょうどその時間にUniversal Cupをしおむすびと走っていた(途中で17も合流した)ので出れず、結局本選当日も起きてもJOIの過去問すら全然できてないのに海外OIを触る気持ちにはなれなくてぼーっと今年の二次予選の問題を眺めていた。

1/28 開会式/交流会

開会式、せっかくの開会式ではあるのだけれどもなんかその時間帯は鬱になっていたのか、全く開会式の映像を見る気が起きず、JOIの過去問をぼーっと眺めていた。

夜は双子によるチューター企画/交流会があって、今年もヒューリスティックなのかなあと絶望していたところ(ヒューリスティックが全くできないため)、今年のチューター企画は、10問の暗号化された問題文から問題文を復元してその問題に答えるというのをはや解きするというものだったので救われた。チューター企画のチームメイトはhiikunZとかめで、チームメイトが強くて色々上手く行って、結果としては最速提出でunique全巻できて、自分のチーム的にはアツかった。hiikunZとかめありがとう！

チューター企画後、DiscordのVCでGartic Phoneをやったのだけれども、今まで見たことのない人数が通話に入ってるのを見て、少しビビった。

2/3

Universal Cupに出るところまでは上に書いた。21:00からABCに出た。全完したのだがパフォーマンスが黄色ギリギリで順位も300+で、どういうこと？になってしまった。問題は配点の割に簡単だったし、どうやらEは既出でGはLibrary Checkerから貼れば解決したらしい。Eの既出は、覚えてなくてもまあありうる話だったが、Gを解くときLibrary Checkerの存在が完全に頭から抜けていて、それはまずいですねという感じ。そんなこんなでGは永続セグ木で解く問題に見えたので、永続セグ木で解いた。Fで大変なことになった結果、全完が遅くなる+ペナがいっぱいつくなどでこんな感じに。

2/4

ABC後、通話で虚無のABCの話は終えて、kemuniku鯖でBGAでアグリコラをしてる人たちに合流し、自分は一回オリフラムをして寝たが、時間が1:30くらいをまわっていて、起床が少し心配だった。無事10時前に起きると、それから朝ご飯食べるなど支度をしてJOIの過去問を眺めていた。本選開始直前にAtCoderのコードテストが不穏な動きを見せて、これは愛しのpaiza.ioの出番か？と思いきや復活したのでAtCoderのコードテストで行くことにする。ヤシの実サイダーを用意して競技に臨んだ。(ちなみに適当に手に取ったヤシの実サイダーは御坂美琴缶だった。きっと味方してくれるだろうと信じて競技に臨んだ。)

競技パート

とりあえずkaichou243伝統芸能の問題順を無視して解くをやろうと思っていて、まずB問題を開いた。割といつもので少し心が落ち着いた。満点解法を実装して提出。(13:10, 合計100点)
一旦A問題をやろうかと思って見てみると、ぱっと見わからなくて結構ビビる、最大値の最小化なので二分探索か？とか血迷って言い始めたけど、冷静さをなんとか取り戻して全然そうじゃないことに気づき、満点解法を実装して提出したが、一回実装ミスをして満点が取れず、A問題にして2回もビビる羽目に。実装ミスに気づいて直して提出。(13:30, 合計200点)
次にDを読んでみると、完全マッチングの判定をすることを要求されていることがわかり、一旦Dに粘着する気分になる。絶対Hallの定理だなと思いつつも、一旦興味本位で適当に書いた嘘貪欲を投げてみると落ちた。それはそう。Hall条件を書き出して一旦そのままをコードに起こして50点を獲得。(時間不明, 合計250点)
絶対その先の小課題や満点解法へのキーは掴んでいるはずなので、このまま粘着してより高い点数を狙おうとして、少し考察して条件を整理すると一個次の8点課題が定数倍が厳しそうだがMo's algorithm + lazy seg treeでできるかなと思い、かなり時間をかけて実装するもTLEだったので、かなり参った。(15:00くらい)
流石にちょっとまずいと思って、定数倍高速化を試みるかと思いコードと睨めっこするが、全然ダメで結局一旦撤退する。(15:30)
急いで小課題だけ回収しようと思い、パッと見えたCの24点コードを提出。(時間不明, 合計274点)
かなり焦っていて、Cの続きが全然見えなくて、一旦Eに移るとなんかとりあえずいつもので16点が取れそうなので、コードを書いて提出。(時間不明, 合計290点)
Eの続きも見えず、やっぱりDに粘着しようと思い、定数倍高速化でやり損ねた、std::set→64分木とlazy seg tree→starry sky treeの書き換えをやり損ねていたことに気づいて、大急ぎで両方書いてみるんだけど、ダメだった。もう終了間際で、あまりできることがなかったので、一旦Mo's + lazy seg treeを捨てるつもりになって考察を巻き戻して終了後にでも解法を理解するつもりになって考察を始めたところで終了。

終わった後、自分が取った部分点から考えて290点だと結構怪しい気がしていて、春合宿落ちたかもしれんと思って本当に怖かったが、Cyanmondに通りそうと言われたのできっと大丈夫だろうと信じ始める。お祈り。

終了後Dをかなり考えても、Mo's + lazy seg treeよりまともな計算量の解法が全然生えなくて、だけど満点を取った人たちと同じ条件を考えているので方針は間違ってないらしくて困った.... 典型練習不足。結局Dは理解したが、50点止まりだったのが本当に情けなかった。Cも後でしばらく考えてみるとともういくつかの小課題が見えて、本当にDの8点課題でMo's + lazy seg treeをしようとしていたのが時間の無駄だったなと感じた。反省。

一つ思うことがあるとすれば、本選競技中に4回もトイレに駆け込んでいて、本当に何？みたいな気持ちだった。

2/5

去年に倣えばこの日の午前中に成績優秀者発表があるので、朝からかなりそわそわしていた。
学校に行って、1限が始まろうとしていた時TwitterでtatyamさんがJOIボーダーが載ってるリンクを貼っていて、見てみるとJOI春合宿通ってるぽくてよかった。本当によかった。

総評

もちろん春合宿通れたのは嬉しかったが、本選競技はやり残したことがいっぱいあるように感じられて、悔しい。
しっかり精進して春合宿では成功したい。
今年はzhoukangyangがIOIに来るらしいので、なかなかに厳しいが今年IOI日本代表になりたいものだ。

2024-02-04

ABC221-H Counting Multiset ヤング図形で考察する

atcoder.jp
を解きたいです。整数の分割の数え上げですね。問題の条件を満たす整数の分割に対し、ヤング図形の転置を考えると、以下の条件を満たす整数 $N$ の分割 $(\lambda_1,\lambda_2,\dots,\lambda_l) \ (\lambda_1 \geq \lambda_2 \geq \dots)$ の数え上げになります。
・ $\lambda_1=k$
・ $\lambda_i-\lambda_{i+1} \leq M$
これの数え上げはdp[i][j] := $\lambdaの総和がi,\lambda_1=j$ として解くことができます。明らかな漸化式から累積和dpを導出することもできますが、 $\lambda_1=j-1$ である分割をとり $\lambda_1$ を $j$ に書き換えることを考えると、 $\lambda_2=j-M-1$ であるようなものを余分に数えていて、逆にこれを除けば $\lambda_1=j$ かつ $\lambda_2 \neq j$ であるような分割を全て数えられているので、漸化式
dp[i][j]=dp[i-1][j-1]-dp[i-j][j-M-1]+dp[i-j][j]
を得ることができ、累積和なしでも解けます。(上記の漸化式は、noshiさんのユーザー解説やkanpurinさんのユーザー解説に載っているものと同じです)

2024-01-31

奇点の個数をパラメータにしたグラフの数え上げ

先に関連したものを紹介します：
mathlog.info
atcoder.jp

この記事の目標は、頂点ラベル付きグラフを奇点の個数ごとに数えることです。

最初に、次を考えます：
偶数 $d$ に対し、 $n$ 頂点 $m$ 辺のラベルなし根付き頂点ラベル付き偶グラフ(???)であって根の次数が $d$ であるようなものを数えます。
日本語がむずかしいです。参考文献にはこんな感じのことを書いてあったので一回こう書きましたが、要するに頂点ラベル付きの $n$ 頂点 $m$ 辺偶グラフであって、頂点nの次数がdであるようなもののことを指しています。

さて、結論から述べると、この答えは
$[x^dy^m]\frac{1}{2^{n-1}}(1+y)^{\binom{n-1}{2}}(1-xy)^{n-1}\displaystyle\sum_{p=1}^{n}\binom{n-1}{p-1}\left(\frac{1+xy}{1-xy}\right)^{p-1}\left(\frac{1-y}{1+y}\right)^{(p-1)(n-p)}$
です。(以降、この数を $w_{n,m,d}$ とします)

この事実の証明は、 $S=\{(\epsilon_1,\dots,\epsilon_n):\epsilon_n=+1 \land \epsilon_i=\pm 1 \ (\forall i \in [1,n-1])\}$ 、グラフ $g=(V,E)$ と符号ベクトル $\mathbf{\epsilon}$ に対して $\sigma_{\epsilon}(g)=\displaystyle\prod_{e=(i,j) \in E} \epsilon_i\epsilon_j,a_{\epsilon}(g)=(負の符号が付けられた頂点の次数の総和),b_{\epsilon}(g)=(\epsilon_i\epsilon_j=-1であるようなe=(i,j) \in Eの個数)$ として、
$\displaystyle\sum_{\epsilon \in S} (-1)^{a_{\epsilon}(g)}$
を考えることによりできます。上の式は $g$ が偶グラフであるとき $2^{n-1}$ となり、そうでないとき $0$ となります。したがって上の式を $n$ 頂点 $m$ 辺の頂点ラベル付きグラフであって頂点 $n$ の次数が $d$ であるようなグラフ $g$ 全てについて和をとると(このような $g$ の集合を $\mathcal{L}_{n,m}^{d}$ とします)、求めたい個数の $2^{n-1}$ 倍になります。ところで、これは明らかに
$\displaystyle\sum_{\epsilon \in S} \sum_{g \in \mathcal{L}_{n,m}^{d}} (-1)^{b_{\epsilon}(g)}$
と等しいです。これを頑張ってゴリゴリ計算すれば上の式になることがわかります。(これは数え上げに熱心な読者への課題とします。すみません....)

さて、目標に戻りたいのですが、 $n$ 頂点 $m$ 辺の頂点ラベル付きグラフであって $d$ 頂点の奇点を持つものの個数は
$w_{n+1,m+d,d}$
と等しいです。これは、先ほど数えたもののからラベルなし根の頂点(=ラベルが最も大きい頂点)とその頂点に接続する辺を除いたグラフと一対一対応を取れるからです。

一応一つだけ系を書き残しておきます：

$n$ 頂点 $m$ 辺の偶グラフの個数は
$[y^m]\frac{1}{2^n}(1+y)^{\binom{n}{2}}\displaystyle\sum_{p=0}^{n} \binom{n}{p}\left(\frac{1-y}{1+y}\right)^{p(n-p)}$ .

最後に関連項目に見える関連項目ではないものを紹介します(最悪)：
qoj.ac
全く関連していないとは言えないかもしれません

参考文献：
https://www.amazon.co.jp/グラフの数え上げ-―母関数を礎にして-田澤-新成/dp/4320110862

2023-12-01

AtCoder Grand Contest 019 Problem F Yes or No,備忘録(別解？),O(N log^2 N)

atcoder.jp

解いた。解説がよくわからなかったので(読む努力を怠りすぎでは？)おそらく違う解法を取ったとみて、自分の解法を適当に説明します。

まず最適な行動について考える。残りのマルの数を $x$ ,バツの数を $y$ として、 $x \geq y$ ならマル、そうでないならバツを答えるのが最適。で、最後に $\binom{n+m}{m}$ で割るものとして、残り $(x,y)$ のとき最適な行動をとったとき正解になるマルバツの列の数の和を取れば良い。

お絵描きしてみると、 $N$ 行 $M$ 列のグリッドを $y=x$ の線で分けてそれぞれ計算すると良さそう。とりあえず片方を立式してみると、

$\displaystyle\sum_{0 \leq a \leq n,1 \leq k \leq m,a \leq k} \binom{a+k-1}{k-1}\binom{n-a+m-k}{m-k}$ .

これを高速に計算したいんだけど、一旦binomを全部バラしてみると

$\displaystyle\sum_{0 \leq a \leq n,1 \leq k \leq m,a \leq k} \frac{(a+k-1)!(n-a+m-k)!}{a!(n-a)!(k-1)!(m-k)!}$

なので、畳み込みっぽい。 $a \leq k$ が邪魔っぽいけど、これは分割統治+畳み込みで計算できるやつなので、いける。

$y=x$ のもう片方の領域も同じ要領でできるので解けた。計算量心配だけど、早めの畳み込み使っておけばACが取れそう。

提出:
atcoder.jp

2023-07-30

AGC060 Same Descent Setを解く

少し雑目です。

問題

atcoder.jp

Descent Setを固定した時の順列の数え上げは包除原理でできます。

$S \subseteq [N-1]$ がDescent Setの順列の個数は

$\displaystyle\sum_{A \subseteq S} (-1)^{|S|-|A|} \binom{N}{A_1,A_2-A_1,\dots,N-A_k}$

なので、求める答えは

$(N!)^2 \times \displaystyle\sum_{S \subseteq [N-1]} \left\{ \sum_{A \subseteq S} (-1)^{|S|-|A|} \frac{1}{A_1!(A_2-A_1)!\cdots(N-A_k)!} \right\} ^2$

です。これを高速に計算したいです。

$\displaystyle\sum_{S \subseteq [N-1]} \left\{ \sum_{A \subseteq S} (-1)^{|S|-|A|} \frac{1}{A_1!(A_2-A_1)!\cdots(N-A_k)!} \right\} ^2$

は、 $2$ 乗の部分を展開し、 $\displaystyle\sum$ を交換すると

$\displaystyle\sum_{A,B \subseteq [N-1]} \sum_{A \cup B \subseteq S} (-1)^{2|S|-|A|-|B|} \frac{1}{A_1!(A_2-A_1)!\cdots(N-A_k)!B_1!(B_2-B_1)!\cdots(N-B_l)!}$

となります。ここで、 $g(S) := (-1)^{|S|} \frac{1}{S_1!(S_2-S_1)!\cdots(N-S_k)!}$ とすると、 $2|S|-|A|-|B|$ と $|A|+|B|$ の偶奇が一致していることから、上の式は

$\displaystyle\sum_{A,B \subseteq [N-1]} g(A)g(B)2^{N-1-|A \cup B|}=\sum_{A,B \subseteq [N-1]} g(A)g(B)2^{N-1-|A|-|B|+|A \cap B|}$

と等しいことがわかります。ここで、困るのがこの式に $|A \cap B|$ が含まれていることですが、これがなければ簡単です。総和を寄与に分解する典型に想いを馳せると、 $2^{|A \cap B|}$ をかけて総和を取る代わりに $A \cap B$ の部分集合全てに対して $g(A)g(B)2^{N-1-|A|-|B|}$ を割り当てて総和を取ることを考えれば良いことがわかります。

つまり、以下の式が答えということです。

$(N!)^2 \times \displaystyle\sum_{C \subseteq [N-1]} \sum_{C \subseteq A,B} g(A)g(B)2^{N-1-|A|-|B|}$

$\displaystyle\sum_{C \subseteq A,B} g(A)g(B)2^{N-1-|A|-|B|}$ は、 $C_i$ で区切って問題を考えることにより、 $f=(-1) \times 2^{-1} \times (\exp(x)-1)$ として、

$\left( [x^{C_1}]\frac{f}{1-f} \right) ^2 \left( [x^{C_2-C_1}]\frac{f}{1-f} \right) ^2\cdots \left( [x^{N-C_k}]\frac{f}{1-f} \right) ^2 \times 2^{N+1}$

と等しいことがわかります。これを $C \subseteq [N-1]$ についての総和が取りたいので、 $[x^n]g= \left( [x^n]\frac{f}{1-f} \right) ^2$ を満たす形式的冪級数 $g$ を用いると答えは

$(N!)^2 \times 2^{N+1} \times [x^N] \frac{g}{1-g}$

と書けます。この式の通りに計算すれば $O(N \log N)$ 時間で答えを求めることができます。

2022-11-19

ABC180-F Unbranchedを高速に解く

問題:

atcoder.jp

問題の条件より，各連結成分は $2$ 頂点以上のサイクルまたは線グラフです．

特に， $N$ 頂点 $M$ 辺であることから線グラフが $N-M$ 個含まれていることが言えます．

連結成分のサイズの最大値が $L$ 以下の上の条件を満たすグラフの個数から連結成分のサイズの最大値が $L-1$ 以下の上の条件を満たすグラフの個数を引けば答えは求まります

したがって，以下では問題の3つ目の条件を「連結成分のサイズの最大値が $L$ 以下」という条件に変えた問題を考えます．

$f_n:=n$ 頂点のグラフのうち $2$ 頂点以上 $L$ 頂点以下のサイクルのみからなるものの個数，

$g_n:=n$ 頂点のグラフのうち $1$ 頂点以上 $L$ 頂点以下の線グラフ $N-M$ 個からなるものの個数

とすると，答えは，

$\displaystyle\sum_{k=0}^{N} \binom{N}{k}f_kg_{n-k}$

です．よって $f_n,g_n$ が $n=0,1,2,\dots,N$ について求まれば良いです．

天下り的になりますが， $2$ 頂点以上 $L$ 頂点以下のサイクルの個数の指数型母関数を $c(x)$ ， $1$ 頂点以上 $L$ 頂点以下の線グラフの個数の指数型母関数を $l(x)$ とすると，

$f$ の指数型母関数は $\exp(c(x))$ ， $g$ の指数型母関数は $\frac{l(x)^{N-M}}{(N-M)!}$ です．

$c(x),l(x)$ は $n(>3)$ 頂点のサイクル，線グラフの個数がそれぞれ $\frac{(n-1)!}{2},\frac{n!}{2}$ であることに留意すれば $O(N)$ の時間計算量で求まるため， $\exp(c(x)),\frac{l(x)^{N-M}}{(N-M)!}$ の計算がボトルネックとなり，全体で $O(N \log N)$ の時間計算量で答えの計算が可能です

実装例:

atcoder.jp