かんプリンの学習記録

勉強したことについてメモしています. 主に競技プログラミングの問題の解説やってます.

【競プロ】数え上げまとめ

競技プログラミング メモ 数え上げ

数え上げ問題と簡単な解法をまとめる.
「{10^9+7}で割った余りを求めよ」などはいちいち書かないので答えが大きくなるなら余りを求めると考えてもらっていい.

目次


yukicoder No.118 門松列(2)

問題概要

長さ{N}の数列{A}から値がすべて異なる{3}つの要素の選び方の数を求めよ.

{3\leq N\leq 10^5\\ 1\leq A_i\leq 100}

解法

形式的冪級数
{\displaystyle [x^3]\prod_{i=1}^{\max{A}}(1+cnt_i×x)}

({cnt_i}は{A_j=i}となる{j}の数)


yukicoder No.346 チワワ数え上げ問題

問題概要

文字列{S}が与えられる. {S}の部分文字列(連続でなくてもよいが順序は保つ)のうち, "cww"となるものの数を求めよ.

{1\leq |S|\leq 10^5}

解法

文字列から決められた数(今回は{3})取る場合の常套手段として真ん中を固定するものがある.

今回は真ん中の'w'を固定してそれより左の'c'の数と右の'w'の数の積をすべての'w'に対して足し合わせたものが答えとなる.


Educational Codeforces#94 D Zigzags

問題概要

長さ{N}の数列{A}が与えられる. {A_i=A_k,A_j=A_l}となるような{1\leq i < j < k < l\leq N}の組の数を求めよ.

{1\leq N\leq 3×10^3\\ 1\leq A_i\leq N}

解法


真ん中を固定する. {j,k}を固定すると, {i < j}かつ{A_i=A_k}となる{i}の数と{k < l}かつ{A_j=A_l}となる{l}の数の積が答えとなる. 累積和をとっておくことで{O(1)}で求められる. すべての{j,k}について和をとったものが答え.

yukicoder No.584 赤、緑、青の色塗り

問題概要

連続した{N}マスを三色で塗る. 赤は{R}マス, 緑は{G}マス, 青は{B}マス塗る. 塗らないマスがあってもよい. 同じ色は隣り合ったマスに塗ることはできないが, 異なる色であれば連続して2つのマスまで塗っても良い. また, 連続して{3}つ以上のマスに色を塗ることはできない。

{1\leq N\leq 3000\\ 0\leq R,G,B\leq 3000}

解法

各色あと何マス塗ればよいかを持ってDPしても間に合わない.

{2}マス連続して塗るマスの数を固定すると, {1}マス塗る数が決まるのでその並べ方の数を先に求める. 赤を{1}マス塗る部分にどれだけ塗るかを固定すると, どこに何を塗るかがすべて決まるようになる.


yukicoder No.794 チーム戦 (2)

問題概要

{N}個の数{A_i}が与えられる. 2つの数の和が{K}以下になるように完全マッチングする. このような完全マッチングはいくつできるか.

{2\leq N\leq 2×10^5, N}は偶数
{1\leq K\leq 2×10^9}
{1\leq A_i\leq 10^9}

解法

制約が大きいので組み合わせに帰着させるか貪欲になりそう. ソートすれば大きい方から貪欲にマッチングしていける.

yukicoder No.802 だいたい等差数列

問題概要

{D_1\leq A_{i+1}-A_{i}\leq D_2}かつ{1\leq A_i\leq M}となるような長さ{N}の数列{A}の数を求めよ.

{2\leq N\leq 3×10^5\\ 1\leq M\leq 10^6\\ 0\leq D_1\leq D_2\leq M}

解法

形式的冪級数
{\displaystyle [x^{M-D_1-1}]\frac{(1-x^{D_2-D_1+1})^{N-1}}{(1-x)^{N+1}}}

上限・下限付きの重複組み合わせみたいな問題. 包除原理で解ける.


yukicoder No.1044 正直者大学

問題概要

人数が{N,M}である2つのグループ{A,B}がある. これらの人を円状に並べるとき, 隣り合う同じグループの人のペアが{K}個以上となる並べ方の数を求めよ.

{1\leq N,M\leq 10^5\\ 0\leq K\leq N+M}

解法


連続した同じグループの人を{1}組と考える. グループ{A,B}の人を{k}組に分割すると固定すると, 「区別できない{N}人({M}人)を区別できる{k}組に分ける(各組には{1}人以上入る)」ことにし, あとから{N}人({M}人)の並べ方を決めるようにすると二項係数を用いて簡単に表すことができる. ただし, 円順列であるので{k}で割ることが必要. {k}組に分割するとき, 隣り合う同じグループのペアは{N-k+M-k}となるので, {k}の動く範囲は{1}以上{\lfloor\frac{N+M-K}{2}\rfloor}以下となる.

{\displaystyle \sum_{k=1}^{\lfloor\frac{N+M-K}{2}\rfloor}N!×{}_{N-1}{\rm{C}}_{k-1}×M!×{}_{M-1}{\rm{C}}_{k-1}}


yukicoder No.3046 yukicoderの過去問

問題概要

{K}段の階段を{1}回で{A_i(1\leq i \leq N)}段昇ることができるとき, ちょうど{K}段昇る昇り方は何通りあるか.

{1\leq K\leq 10^5\\ 1\leq N\leq 10^5\\ 1\leq A_i < A_{i+1}\leq 10^5 }

解法


形式的冪級数

{\displaystyle [x^K]\sum_{i=0}^{\infty}(x^{A_1}+x^{A_2}+\cdots +x^{A_N})^i=[x^K]\frac{1}{1-x^{A_1}-x^{A_2}-\cdots -x^{A_N}}}


ABC180 F - Unbranched

問題概要

自己ループを持たずすべての頂点の次数が{2}以下であり, 連結成分のサイズの最大値が{L}であるようなラベル付き{N}頂点, ラベル無し{M}辺のグラフの数を求めよ.

{2\leq N\leq 300\\ 1\leq M\leq N\\ 1\leq L\leq N}

解法


ラベル付き頂点を複数の集合に分ける方法を考えるとき, ラベル番号が小さい頂点から連結成分を決めていくことで重複なく数え上げることができる.
{dp[i][j]:=}{i}頂点{j}辺を決めたときのグラフの数として.
{\begin{equation} \left \{ \begin{array}{l} dp[i+1][j]+=dp[i][j] &孤立点\\ \displaystyle dp[i+k][j+k-1]+=dp[i][j]×{}_{N-i-1}{\rm{C}}_{k-1}×\frac{k!}{2} &頂点数kのパス\\ dp[i+2][j+2]+=dp[i][j]×(N-i-1) &頂点数2のサイクル\\ \displaystyle dp[i+k][j+k]+=dp[i][j]×{}_{N-i-1}{\rm{C}}_{k-1}×\frac{(k-1)!}{2} &頂点数kのサイクル\\ \end{array} \right. \end{equation}}

ABC172 E - NEQ

問題概要

{1\leq A_i, B_i\leq M}である長さ{N}の数列{A,B}で{A_i\neq B_i}かつ{A_i\neq A_j}かつ{B_i\neq B_j}となるものの個数を求めよ.

{1\leq N < M\leq 5×10^5}

解法


{A_i\neq A_j, B_i\neq B_j}の条件は簡単だが, {A_i\neq B_i}の条件が難しい. {A_i=B_i}の条件だと簡単になるので包除原理が使える.
{\displaystyle\sum_{K=0}^{N}(-1)^K×{}_{N}{\rm{C}}_{K}×{}_{M}{\rm{P}}_{K}×({}_{M-K}{\rm{P}}_{N-K})^2}

ABC167 E - Colorful Blocks

問題概要

{N}個のマスの各マスを{M}色のいずれかで塗る方法で, 隣り合うマスが同じ色で塗られている組が{K}組以下である者の数を求めよ.

{1\leq N,M\leq 2×10^5\\ 0\leq K\leq N-1}

解法


同じ色が隣り合うマスを決めると, そのマスを一つのマスとして考えると同じ色が隣り合わないような塗り方を求める問題と同等になる.
{\displaystyle\sum_{i=0}^{K}{}_{N-1}{\rm{C}}_{i}×M×(M-1)^{N-1-i}}

ABC163 F - path pass i

問題概要

{N}頂点の木に色が塗られている(色は{1}以上{N}以下の整数で表され, 重複もある). {k=1,2,\cdots ,N}に対して, 色{k}が塗られている頂点を一度以上通る単純パスの数を求めよ.

{1\leq N\leq 2×10^5}

解法


{k}を一つ以上通るパスの数＝全てのパスの数ー{k}を一つも通らないパスの数
色が{k}の頂点を削除したグラフの連結成分{C}毎に{\frac{|C|*(|C|-1)}{2}}を計算し足せばいい.
適当な根からDFSをすればいい. 詳しい解説

ABC158 E - Divisible Substring

問題概要

0から9までの数字からなる文字列{S}の空でない連続部分文字列のうち十進表記の整数とみなしたときに素数{P}で割り切れるものの個数を求めよ. 先頭に余分な0があってもよいもののとする.

{1\leq |S|\leq 2×10^5\\ 2\leq P\leq 10^4}

解法


{S_1}から{S_i}まででできる数字を{T_i}とする. {S_i}から{S_j}まででできる数字が{P}の倍数になるのは,
{T_{j}-T_{i-1}×10^{j-i+1}\equiv 0{\rm{mod}}P\\ T_{j}×10^{-j}\equiv T_{i-1}×10^{-(i-1)}{\rm{mod}}P}
となるので{\frac{T_{i}}{10^i}}を計算しておけばよい.

ABC160 F - Distributing Integers

問題概要

{N}頂点の木の各頂点{k=1,\cdots ,N}に対して{k}に{1}を書き, {2,\cdots ,N}を順番に「まだ整数が書かれていない頂点であって,整数が書かれた頂点に隣接している頂点」に書くときの整数の書き方として考えられるものの数を求めよ.

{1\leq N\leq 2×10^5}

解法


{k}を根とする根付き木を考えると, ある根付き部分木の答えは根の各子{C_i}を根とする根付き部分木{T_{C_i}}の答えを{A_{C_i}}として,
{\displaystyle\frac{(\displaystyle\sum_{i}|T_{C_i}|)!}{\displaystyle\prod_{i}(|T_{C_i}|)!}×\prod_{i}A_{C_i}}が答えとなる.
これを{k=1,\cdots ,N}に対して求めるには全方位木DPを用いればよい.

ABC147 F - Sum Difference

問題概要

長さ{N}の初項{X}公差{D}の等差数列{A}がある. {A}からいくつかの要素をいくつか選び, その和を{S}, 選ばなかった要素の和を{T}とするとき, {S-T}として考えられる値は何通りあるか.

{1\leq N\leq 2×10^5\\ -10^8\leq X,D\leq 10^8}

解法


数列の総和を{U}とするとき{S-T=2S-U}となるので, {S}として考えられる値の数を数えればよい.
数列から選ぶ個数を{k}とすると, {S=k×X+D×(0以上N-1以下の整数のうちk個の和)}となる.
「{0}以上{N-1}以下の整数のうち{k}個の和」で表される整数は{\displaystyle\sum_{n=0}^{k-1}n}以上{\displaystyle\sum_{n=N-k}^{N-1}n}以下の整数すべてである.
{S}の取り得る値は{D}おきなることからすべての{k}について{k×X}を{D}で割った余り毎に考えると, 少なくとも一つの区間に含まれるような値の個数を数えればよいことになる.

ABC146 E - Rem of Sum is Num

問題概要

長さ{N}の正整数列{A}の空でない連続部分列の要素の和を{K}で割った余りが要素の数と等しくなるものの数を求めよ.

{1\leq N\leq 2×10^5\\ 1\leq K\leq 10^9\\ 1\leq A_i\leq 10^9}

解法


{S_i}を{i}番目までの要素の和とすると, {i}番目から{j}番目までの部分列が条件を満たすのは
{S_j-S_{i-1}\equiv j-i+1{\rm{mod}}K}かつ{j-i+1 < K}
変形すると
{S_j-j\equiv S_{i-1}-(i-1){\rm{mod}}K}かつ{j-i+1 < K}
となるので, {B_j=S_j-j{\rm{mod}}K}を計算し, {B_j=B_i,j-K+1 < i < j}を満たす{i}の数を数えればよい.

ABC138 F - Coincidence

問題概要

{L\leq x\leq y\leq R}かつ{y}を{x}で割った余りが{y{\rm{XOR}}x}と等しい{(x,y)}の個数を求めよ.

{1\leq L\leq R\leq 10^{18}}

解法


条件を満たすとき, {y}を{x}で割った余りは{y-x}と表せる. 結局これは{y-x}の計算において繰り下がりが発生しないことと同値となる. {L\leq x}と{y\leq R}と{x,y}の最上位ビットの位置が等しいという情報をもって桁DPすればよい.

ABC135 D - Digits Parade

問題概要

各文字が{0}～{9,?}である文字列{S}の各{?}を{0}～{9}のいずれかに置き換えてできる整数のうち, {13}で割って{5}余る数は何通りか. 先頭に余分な{0}があってもよいものとする.

{1\leq |S|\leq 10^5}

解法


{13}で割った余りを情報としてもってDP

ABC134 F - Permutation Oddness

問題概要

{\displaystyle\sum_{i=1}^{N}|i-P_i|=K}となるような{1,...,N}の順列{P}の個数を求めよ.

{1\leq N\leq 50\\ 0\leq K\leq N^2}

解法


前から何番目まで見たか, そのうち何個決めたか, そのとき確定している和の値をもってDP

ABC133 E - Virus Tree 2

問題概要

ラベル付き{N}頂点の木の頂点それぞれに対して{K}色のうちいずれか{1}色で塗るとき, 二つの異なる頂点の距離が{2}以下ならば, その二つの頂点の色が異なるように塗る方法の数を求めよ.

{1\leq N,K\leq 10^5}

解法


適当な頂点を根とする. ある根以外の頂点の子を塗る方法は子の数を{C}として, {{}_{K-2}{\rm{P}}_{C}}通りとなる(その頂点とその親の色以外の色で塗る方法の数). これを根から順番に求めていけばよい.

ABC132 F - Small Products

問題概要

長さ{K}の正整数列のうちどの隣り合う要素の積も{N}以下となるものの数を求めよ.

{1\leq N\leq 10^9\\ 2\leq K\leq 100}

解法


{dp[i][j]=i}番目まで決めて最後の整数が{j}であるようなものの数とすると{O(NK)}となるが, {\displaystyle\lfloor \frac{N}{j}\rfloor}の値が同じであるような{j}をまとめることができるので{O(\sqrt{N}K)}で解くことができる.

ABC130 E - Common Subsequence

問題概要

整数列{S,T}の部分列の組のうち整数列として等しいような組の数を求めよ.

{1\leq |S|,|T|\leq 2×10^3\\ 1\leq S_i,T_i\leq 10^5}

解法


{dp[i][j]=S}の{i}番目までと{T}の{j}番目まででの等しい整数列の数としてDP

ABC129 E - Sum Equals Xor

問題概要

正整数{L}が二進数表記で与えられる. 以下の条件を満たす非負整数{a,b}の組の数を求めよ.

  • {a+b\leq L}
  • {a+b=a\bigoplus b}

{1\leq L < 2^{100001}}

解法


2つの条件は

  • {a\bigoplus b\leq L}
  • {a \& b=0}

と言い換えられるので上位の桁から{L}以下が確定してるかという情報をもってDP


ABC110 D - Factorization

問題概要

{A_1×A_2×\cdots ×A_N=M}となる正整数からなる長さ{N}の数列{a}として考えられるものの数を求めよ.

{1\leq N\leq 10^5\\ 1\leq M\leq 10^9}

解法


{M}の素因数ごとに{A}のどの要素にいくつその素因数がかけられるかを考えると解ける.

ABC104 D - We Love ABC

問題概要

{A,B,C,?}からなる文字列{S}の{?}を{A,B,C}のいずれかに変更することによって得られる文字列全てにおいて, 部分列として含まれる{ABC}の数の和を求めよ.

{1\leq |S|\leq 10^5}

解法


{B}の位置を固定すると, それより左にある{A}の数×それより右にある{C}の数が求めるものとなる. {?}を変更することによってできる文字列の数も考慮すると解くことができる.

ABC098 D - Xor Sum 2

問題概要

長さ{N}の数列{A}の連続部分列のうちその連続部分列に含まれるすべての要素のXORとすべての要素の和が等しいような連続部分列の数を求めよ.

{1\leq N\leq 2×10^5\\ 0\leq A_i < 2^{20}}

解法


XORと和が等しくなるのはbitごとにそのbitが1である要素が高々1つしかないとき. bitごとにそのbitが1であるかどうかの情報をもって尺取り法などをしてやればよい.

ABC077 D - 11

問題概要

{1}以上{N}以下の各整数を1つ以上含む長さ{N+1}の数列{A}が与えられる({A}の要素のうち1つだけ重複がある). {K=1,\cdots,N+1}について長さ{K}の部分列の数を求めよ. ただし, 数列として同じものは{1}通りと数える.

{1\leq N\leq 10^5\\ 0\leq A_i \leq N}

解法


数列に2つ含まれる数の位置のみが重要であり, その位置を{L,R}とする. 部分列の数は{{}_{N+1}{\rm{C}}_{k}}であり, そのうち{A_L}と{A_R}のどちらか一方のみを含み, {A_{L+1},\cdots,A_{R-1}}を含まないものを重複して数えているので, その分の{{}_{N-R+L}{\rm{C}}_{k}}を引いたものが答え.

ABC050 D - Xor Sum

問題概要

ある非負整数{a,b}が存在して{a\,\mbox{XOR}\, b=u, a+b=v}となるような{0\leq u,v\leq N}の組が何通りあるか求めよ.

{1\leq N\leq 10^{18}}

解法


任意の{k}bit目において{a}の{k}ビット目と{b}の{k}ビット目の組として{(0,0),(1,0),(1,1)}であるという制約をつけると{u,v}の数え上げを{a,b}の数え上げに変更できる. 「何bit目まで決めたか」と「そこまでで{N-a-b}の値({2}以上なら{2})」という情報をもって桁DP

ARC110 D - Binomial Coefficient is Fun

問題概要

長さ{N}の非負整数列{A}が与えられる. 長さ{N}で和が{M}以下である任意の非負整数列{B}について, {\displaystyle\prod_{i=1}^{N}\binom{B_i}{A_i}}の値の総和を求めよ.

{1\leq N\leq 2000\\ 1\leq M\leq 10^9\\ 0\leq A_i\leq 2000}

解法


{\displaystyle f_i=\sum_{k=A_i}^{\infty}\binom{k}{A_i}x^k}として{\displaystyle[x^M]\frac{\prod_{i=1}^{N}f_i}{1-x}}が答え.
負の二項定理を考えると{\displaystyle f_i=\frac{x^{A_i}}{(1-x)^{A_i+1}}}となるので{\displaystyle S=\sum_{i=1}^{N}A_i}として{\displaystyle[x^M]\frac{\prod_{i=1}^{N}f_i}{1-x}=[x^M]\frac{x^S}{(1-x)^{S+N+1}}=\binom{M+N}{S+N}}

ARC106 D - Powers

問題概要

長さ{N}の整数列{A}がある. {1\leq X\leq K}を満たす{X}それぞれについて, {\displaystyle\sum_{L=1}^{N-1}\sum_{R=L+1}^{N}(A_L+A_R)^X}を求めよ.

{1\leq N\leq 2×10^5\\ 1\leq K\leq 300\\ 0\leq A_i\leq 10^8}

解法


{\displaystyle\sum_{L=1}^{N-1}\sum_{R=L+1}^{N}(A_L+A_R)^X=\frac{\sum_{L=1}^{N}\sum_{R=1}^{N}(A_L+A_R)^X-\sum_{i=1}^{N}(2A_i)^X}{2}}となるので{\displaystyle\sum_{L=1}^{N}\sum_{R=1}^{N}(A_L+A_R)^X}を求める.
{\begin{align} \displaystyle\sum_{L=1}^{N}\sum_{R=1}^{N}(A_L+A_R)^X&=\sum_{L=1}^{N}\sum_{R=1}^{N}\sum_{k=0}^{X}\binom{X}{k}A_L^kA_R^{X-k}\\ &=\sum_{L=1}^{N}\sum_{R=1}^{N}\sum_{k=0}^{X}X!\frac{A_L^k}{k!}\frac{A_R^{X-k}}{(X-k)!}\\ &=X!\sum_{k=0}^{X}\left(\sum_{L=1}^{N}\frac{A_L^k}{k!}\right)\left(\sum_{R=1}^{N}\frac{A_R^{X-k}}{(X-k)!}\right)\\ \end{align}}
{\displaystyle\sum_{i=1}^{N}\frac{A_i^k}{k!}}の値を前計算すれば解ける.

ABC173 F - Intervals on Tree

問題概要

与えられる{N}頂点のラベル付き木に対して{f(L,R)}を「{L}以上{R}以下の頂点とそれを両端に持つ辺からなる部分グラフの連結成分の個数」と定義したとき, {\displaystyle\sum_{L=1}^{N}\sum_{R=L}^{N}f(L,R)}を求めよ.

{1\leq N\leq 2×10^5}

解法


できるグラフは森になる. 森の連結成分数を{C}, 辺数を{E}, 頂点数を{V}とするとき{C=V-E}が成り立つので, 各{L,R}に対する頂点数を{V(L,R)}, 辺数を{E(L,R)}とすると{\displaystyle\sum_{L=1}^{N}\sum_{R=L}^{N}V(L,R)-E(L,R)=\sum_{L=1}^{N}\sum_{R=L}^{N}V(L,R)-\sum_{L=1}^{N}\sum_{R=L}^{N}E(L,R)}を求めることとなる.
{V(L,R)=R-L+1}であり, {\displaystyle\sum_{L=1}^{N}\sum_{R=L}^{N}E(L,R)}は{E(L,R)}を直接求めるのではなくてすべての辺についてその辺が含まれるような{L,R}の数を求めればよいので解くことができる.

ABC169 F - Knapsack for All Subsets

問題概要

長さ{N}の正整数列{A}と{S}が与えられる. {\{1,2,\cdots,N\}}の空でない部分集合{T}について{f(T)}を次のように定義する.

  • {T}の空でない部分集合{\{x_1,x_2,\cdots,x_k\}}であって, {A_{x_1}+A_{x_2}+\cdots+A_{x_k}=S}を満たすものの個数.

{T}として考えられる集合すべてに対して{f(T)}の和を求めよ.

{1\leq N\leq 3000\\ 1\leq S\leq 3000\\ 1\leq A_i\leq 3000}

解法


{A_{x_1}+A_{x_2}+\cdots+A_{x_k}=S}となるような集合{U=\{x_1,x_2,\cdots,x_k\}}を部分集合として持つ{T}の数は{2^{N-|U|}}個ある({U}に含まれないものそれぞれに対して含むか含まないかの2択).
{\displaystyle[x^S]\prod_{i=1}^{N}(2+x^{A_i})}

ABC162 E - Sum of gcd of Tuples (Hard)

問題概要

{1}以上{K}以下の整数からなる長さ{N}の数列{A}すべてについて{\gcd (A_1,\cdots,A_N)}の和を求めよ.

{2\leq N\leq 10^5\\ 1\leq K\leq 10^5}

解法


{\displaystyle\sum_{g=1}^{K}\sum_{\gcd (A_1,\cdots,A_N)=g}g=\sum_{g=1}^{K}g\sum_{\gcd (A_1,\cdots,A_N)=g}1}となるので約数版の高速ゼータ変換・高速メビウス変換をすれば解ける.

ABC159 F - Knapsack for All Segments

問題概要

長さ{N}の正整数列{A}と{S}が与えられる. {f(L,R)}を次のように定義する.

  • {L\leq x_1 < x_2 < \cdots < x_k\leq R}かつ{A_{x_1}+A_{x_2}+\cdots+A_{x_k}=S}を満たすような整数列{(x_1,x_2,\cdots,x_k)}の個数.

{1\leq L\leq R\leq N}を満たす{(L,R)}の組全てに対する{f(L,R)}の和を求めよ.

{1\leq N\leq 3000\\ 1\leq S\leq 3000\\ 1\leq A_i\leq 3000}

解法


「前から何番までまで見たか」,「現在の和」,「現在の状態(左端を決めてない/左端は決めたが右端は決めてない/右端まで決めた)」をもってDP

形式的冪級数解法


ABC158 F - Removing Robots

問題概要

数直線上に, {N}個の大きさの無視できるロボットがある. ロボット{i}は座標{X_i}に存在し, 起動すると{D_i}だけ正の方向に毎秒1で移動し, 移動を終えると同時に数直線上から取り除かれる. ロボットを一つ起動する操作を0回以上行うとき数直線上に残っているロボットの組み合わせとして考えられるものは何通りあるか. ロボット{i}が移動する過程で, 数直線上の座標{X_i}以上{X_i+D_i}未満の範囲に残っている別のロボット{j}と接触したら, ロボット{j}も起動される.

{1\leq N\leq 2×10^5\\ -10^9\leq X_i\leq 10^9\\ 1\leq D_i\leq 10^9\\ X_i\neq X_j}

解法


{N}頂点の空グラフを用意する. {X_i}の大きい方から順にそのロボット{i}を起動したときロボット{j}が起動される場合頂点{i}から{j}に有向辺を張る. ただしすでに入次数が{1}以上の頂点には辺は張らないものとする. このようにしてできたグラフは森となる. 各木ごとに葉(入次数{0}の頂点)から求めていけばいい.

ABC154 F - Many Many Paths

問題概要

{r_1\leq i\leq r_2}かつ{c_1\leq j\leq c_2}に対して2次元平面上で{(0,0)}から{x}軸正の方向に1もしくは{y}軸正の方向に{1}移動することを繰り返して{(i,j)}まで移動する経路の数の和を求めよ.

{1\leq r_1\leq r_2\leq 10^6\\ 1\leq c_1\leq c_2\leq 10^6}

解法


{i,j}に対する答えは{\displaystyle\binom{i+j}{i}}
{\displaystyle\sum_{i=r_1}^{r_2}\sum_{j=c_1}^{c_2}\binom{i+j}{i}=\binom{r2+c2+2}{r2+1}-\binom{r2+c1+1}{r2+1}-\binom{r1+c2+1}{r1}+\binom{r1+c1}{r1}}

ABC150 E - Change a Little Bit

問題概要

{0,1}からなる長さ{N}の異なる2つの数列{S,T}に対し, 関数{f(S,T)}を以下のように定義する.

  • {S}に対し以下の操作を繰り返して{T}と等しくすることを考える. このとき行う操作のコストの和として考えられる最小値が{f(S,T)}である.
    • {S_i}を({0}から{1}, もしくは{1}から{0}に)変更する. この操作のコストは, 変更直前に{S_j\neq T_j}であったような整数{j}の個数を{D}として, {D×C_i}である.

すべての{(S,T)}の組について{f(S,T)}の和を求めよ.

{1\leq N\leq 2×10^5\\ 1\leq C_i\leq 10^9}

解法


{C_i}の降順に変更するのが最適. {C}を降順に並べ替える. {i}番目を変更するときに{D=k}となる{(S,T)}の組の数は{\displaystyle\binom{i-1}{k-1}×2^k×2^{i-1-k}×4^{N-i}}であるので答えは
{\displaystyle 4^{N-1}×\sum_{i=1}^{N}C_i*(i+1)}

ABC140 E - Second Sum

問題概要

{\{1,2,\cdots,N\}}の順列{P}が与えられる. すべての{1\leq L < R\leq N}について{P_L,\cdots,P_R}の中で{2}番目に大きい数の総和を求めよ.

{2\leq N\leq 10^5}

解法


{P_i}が{2}番目に大きい数となるような{(L,R)}の数はstd::setで{P_i}の降順に位置を管理することで求めることができる.

ABC136 F - Enclosed Points

問題概要

{2}次元平面上の{N}個の点(どの{2}点の{x}座標も{y}座標も異なる)が与えられる. 全点集合の空でないすべて部分集合{T}に対して, 各辺が座標軸と平行であって{T}の点をすべて含むような最小の長方形に含まれる点の個数の総和を求めよ.

{2\leq N\leq 2×10^5\\ -10^9\leq x_i, y_i\leq 10^9}

解法


ある点が含まれる長方形を作るような部分集合の数を求める. その点より右上, 左上, 左下, 右下にある点の数をBITなどを用いて求めることで解くことができる.

ABC127 E - Cell Distance

問題概要

{N}行{M}列のマス目のうち{K}マスに駒を{1}つずつ置く. 全ての配置について全ての駒のペアのマンハッタン距離の和の総和を求めよ.

{2\leq N×M\leq 2×10^5\\ 2\leq K\leq N×M}

解法


ある{2}マスに駒が置かれているような置き方の数は{\displaystyle\binom{NM-2}{K-2}}個あるので, すべての{2}マスのペアにおけるマンハッタン距離の和を求めればよいが, {x}座標と{y}座標について独立に求めることができ, {x}座標の差が{d}となるような置き方の数は{(N-d)×M^2}あるので解くことができる.

ABC127 E - Cell Distance

問題概要

{2}次元平面上に{x}軸と平行な直線({y=y_i})が{M}本と{y}軸と平行な直線({x=x_i})が{N}本引いてある. この中に存在しているすべての長方形についてその面積を求めよ.

{2\leq N×M\leq 2×10^5\\ 2\leq K\leq N×M}

解法


{\displaystyle \sum_{L_1=1}^{N-1}\sum_{R_1=L_1+1}^{N}\sum_{L_2=1}^{M-1}\sum_{R_2=L_2+1}^{M}(x_{R_1}-x_{L_1})(y_{R_2}-y_{L_2})\\ \displaystyle=\left(\sum_{L_1=1}^{N-1}\sum_{R_1=L_1+1}^{N}(x_{R_1}-x_{L_1})\right)\left(\sum_{L_2=1}^{M-1}\sum_{R_2=L_2+1}^{M}(y_{R_2}-y_{L_2})\right)\\ \displaystyle=\left(\sum_{i=1}^{N-1}(x_{i+1}-x_i)×i×(N-i)\right)\left(\sum_{i=1}^{M-1}(y_{i+1}-y_i)×i×(M-i)\right)}

ARC102 E - Stop. Otherwise...

問題概要

区別できない{K}面サイコロを{N}個振る. 各{i=2,3,\cdots,2K}に対し, どの異なる{2}つのサイコロの出目の和も{i}にならないような出目の組の場合の数を求めよ.

{1\leq K\leq 2000\\ 2\leq N\leq 2000}

解法


{a+b=i(1\leq a\leq b\leq K)}となる{(a,b)}の数は{\displaystyle t=\min\left(\left\lfloor\frac{i}{2}\right\rfloor ,K-i+\left\lfloor\frac{i}{2}\right\rfloor +1\right)}となる. {a+b=i}となる{(a,b)}一つに対して{a,b}のどちらの目も一つ以上出るような出目の数は{\binom{N+K-1-2}{K-1}}であり, このようにして包除原理を用いて解くことができる.

ARC101 E - Ribbons on Tree

問題概要

{N}頂点({N}は偶数)の木の頂点を{\displaystyle \frac{N}{2}}組のペアに分け, どのペア間の最短パスにも含まれない辺がないようなペアの分け方は何通りあるか.

{1\leq N\leq 5000}

解法


包除原理を用いると, {\displaystyle\sum_{F\subseteq E}(-1)^{|F|}(F\mbox{のどの辺も最短パスに含まれないペアの分け方の数})}となる. 「今の部分木」,「今の連結成分の頂点数」,「これまでに取り除いた辺の本数の偶奇」をもって木DPをする.

yukicoder No.1321 塗るめた