ABC174C Extra

スナネコです。twitterで出した問題について解説します。

問題その１：
高橋君は K の倍数と 7 が好きです。
7,77,777,…という数列の中に初めて K の倍数が登場するのは何項目ですか？
存在しない場合は代わりに -1 を出力してください。

制約：
K\leq 10^{12}

解説：
K が 7 の倍数のときK'=K/7、そうでないとき K'=K とします。
次のように同値変形できます

  • 77...77 (n桁)が K の倍数
  • 11...11 (n桁)が K' の倍数
  • 99...99 (n桁)が 9K' の倍数
  • 10^n = 1 \bmod 9K'

よって、最後の式を満たす最小の n を求めれば良いです。

解法１：離散対数問題
この問題は離散対数問題そのものなので、Baby-Step Giant-Stepなどを用いることで、O(\sqrt{K} \log K) で解くことができます。

解法２：乗法群における位数
明らかに、K が2の倍数か5の倍数のときは答えが-1になることがわかります。
そうでないとき、オイラーの定理から、10^{\phi(9K')}=1 \mod 9K'が成り立ちます。
なので、10^n = 1 \bmod 9K' を満たす最小の n は、\phi(9K') の約数となることがわかります。
（もしそうでなければ、 n'=gcd(n,\phi(9K'))として、より小さい答えが作れるので矛盾します）
\phi(9K')を求め、素因数分解し、約数を全探索することで、O(\sqrt{K})で解くことができます。

128bit整数がないとちょっと計算が大変ですね。





問題その２：
高橋君は K の倍数と 7 が好きです。
7,77,777,…という数列の中に初めて K の倍数が登場するのは何項目ですか？
1\leq K\leq N の全ての K について求めてください。
存在しない場合は代わりに -1 を出力してください。

制約：
N\leq 10^{6}

解説：

10^n=1 \bmod M を満たす最小の n を f(M) と書くことにします。
もし、a,b が互いに素なら、10^n=1 \bmod ab を満たす最小の n は、中国剰余定理から lcm(f(a),f(b)) になることがわかります。
よって、素数べきに対する答えが求めることができれば、それらを組み合わせて一般の場合に答えることができます。
最初に 9N 以下の数の最小素因子テーブルを作っておき、素因数分解が O(\log N) で出来るようにしておきます。（osa_k法というやつですね）
素数 p に対しての答えは、問題その１で説明した方法によって、O(\text{p-1の約数の個数}\times \log N) で求めることが出来ます。
証明は省略しますが、f(p^e) は f(p^{e-1}) か p f(p^{e-1})になります。どちらになるかは実際に計算することで、O(\log N) で確かめられます。
（証明は「f(p^e)\neq f(p^{e-1}) \Longrightarrow f(p^e) = p f(p^{e-1})」を二項定理を使って示します。ちなみに、f(p^e)=f(p^{e-1})になるのは、e=2 のときの 3, 487, 56598313 の3通りしか知られていないようです（A045616））
これらをうまく組み合わせると、全体で O(N\log N) で解くことができます。

埋め込みで解けてしまうのと、O(N\sqrt{N})との区別が難しいのとで、実際のコンテストに出すのは無理ですね。

Nim product

スナネコです。
yosupo judgeのNim productを解きました。
問題

よくわからないですが、Nimber product、Nimber multiplicationみたいな呼び方もあるみたいです。なんて読むんですかこれ？

私に読める言葉で書かれたものが見つからなくて困ったので、丁寧めに解説を書きました。
pdfで4ページくらいなので読んでみてください。
https://drive.google.com/file/d/16g1tfSHUU4NXNTDgaD8FSA1WB4FtJCyV/

無限和を計算するyosupo judgeの問題

スナネコです。yosupo judgeにある \sum_{i=0}^{\infty}r^i i^d を解きました。
問題

d=0の時はただの等比数列の和です。
d=1の時を計算する問題もときどき見ますね。例えば「1の目が出るまでサイコロを振るときの回数の期待値は？」とかです。
…………冗談です。まさかこの問題でそんな計算しませんよね？

さて、dが大きなときでもやることはd=0,1の時と同じで、rを掛けて差を取っていきます。
例えばd=4のときは
\begin{eqnarray} S &=& 1*r &+& 16*r^2 &+& 81*r^3 &+& 256*r^4 &+& 625*r^5 &+& \cdots \\ rS &=& \ &\ & 1*r^2 &+& 16*r^3 &+& 81*r^4 &+& 256*r^5 &+& \cdots \\ (1-r)S &= & 1*r &+& 15*r^2 &+& 65*r^3 &+& 175*r^4 &+& 369*r^5 &+& \cdots \\ r(1-r)S &=&\ &\ & 1*r^2 &+& 15*r^3 &+& 65*r^4 &+& 175*r^5 &+& \cdots \\ (1-r)^2 S &= & 1*r &+& 14*r^2 &+& 50*r^3 &+& 110*r^4 &+& 194*r^5 &+& \cdots \\ r(1-r)^2 S &=&\ &\ & 1*r^2 &+& 14*r^3 &+& 50*r^4 &+& 110*r^5 &+& \cdots \\ (1-r)^3 S &= & 1*r &+& 13*r^2 &+& 36*r^3 &+& 60*r^4 &+& 84*r^5 &+& \cdots \\ r(1-r)^3 S &=&\ &\ & 1*r^2 &+& 13*r^3 &+& 36*r^4 &+& 60*r^5 &+& \cdots \\ (1-r)^4 S &= & 1*r &+& 12*r^2 &+& 23*r^3 &+& 24*r^4 &+& 24*r^5 &+& \cdots \\ r(1-r)^4 S &=&\ &\ & 1*r^2 &+& 12*r^3 &+& 23*r^4 &+& 24*r^5 &+& \cdots \\ (1-r)^5 S &= & 1*r &+& 11*r^2 &+& 11*r^3 &+& 1*r^4 \end{eqnarray}
という感じですね。
なんだか見たことのない数が残りました。こういうときはOEISです。
1,11,11,1 - OEIS
Eulerian Numberというらしいです。d=5の場合も計算すると一致したので多分あってるでしょう。
wikipediaを見てみます。
Eulerian number - Wikipedia
wikipediaに合わせて、Eulerian NumberをA(n,m)と表すことにしましょう。
スナネコは英語は読めませんが、数式を見れば大体の雰囲気はわかりますね。
A(n,m)を表す式は書いてありますが、nを固定したときに全部のmを高速に求める方法は書いてなさそうです。

このEulerian Numberを使って計算できればいいんですけど、うまくいきますかね。ちゃんと式に書いてみましょう。
\displaystyle{ \sum_{m=0}^{d-1}A(d,m)r^{m+1}\\ =\sum_{m=0}^{d-1}\sum_{k=0}^{m} (-1)^k\binom{d+1}{k}(m+1-k)^d r^{m+1}\\ }
愚直に計算するとO(d^2)です。困りました。
正解者の提出をちらっと見てみると、こういう式で計算してました。
\displaystyle{ \sum_{i=0}^d (-r)^{d-i} \binom{d+1}{i+1} \sum_{j=0}^{i} r^j j^d }
スナネコの考えてる式と似たような感じなので、今の方針であってそうです。
二項係数の部分と、(…)^dの部分で変数を分離して、独立に累積和っぽく計算する工夫は面白いですね。これが使えないか試してみます。m+1-kをxと変数変換してみます。
\displaystyle{ \sum_{m=0}^{d-1}\sum_{k=0}^{m} (-1)^k\binom{d+1}{k}(m+1-k)^d r^{m+1}\\ =\sum_{k=0}^{d-1}\sum_{m=k}^{d-1} (-1)^k\binom{d+1}{k}(m+1-k)^d r^{m+1}\\ =\sum_{k=0}^{d-1}\sum_{x=1}^{d-k} (-1)^k\binom{d+1}{k}x^d r^{x+k}\\ =\sum_{k=0}^{d-1} (-1)^k\binom{d+1}{k} \sum_{x=1}^{d-k}x^d r^{x+k}\\ =\sum_{k=0}^{d-1} (-r)^k\binom{d+1}{k} \sum_{x=1}^{d-k}r^x x^d\\ }
うまくできましたね。これで、xのシグマについてはkが大きい方から累積和のように計算していくことができるので、高速に計算できるようになりました。
この計算式の通りにやっても全体でO(d\log mod)ですが、逆元テーブルの線形構築や細かい計算を配列にメモしておくことでいくらか定数倍高速化が効きます。

これでAC……ではありません。d=0の時はそもそも最初の\sum_{m=0}^{d-1}A(d,m)r^{m+1}の時点で空和になって0になってしまいます。仕方がないのでこれだけ場合分けです。

ACは取れましたが、途中で紹介した他の正解者の計算式では場合分けをしてないみたいです。こっちも導出してみましょう。
最後の数式でd-kをyに変数変換します。
\displaystyle{ \sum_{k=0}^{d-1} (-r)^k\binom{d+1}{k} \sum_{x=1}^{d-k}r^x x^d\\ =\sum_{y=1}^{d} (-r)^{d-y}\binom{d+1}{d-y} \sum_{x=1}^{y}r^x x^d\\ =\sum_{y=1}^{d} (-r)^{d-y}\binom{d+1}{y+1} \sum_{x=1}^{y}r^x x^d\\ }
和を取る範囲が違いますね。ここが0から始まっているとd=0のときにも場合分けをしなくて済むようです。
wikipediaをよく見てみると、A(0,0)=1、n>0のときA(n,n)=0、と書いてありました。ということはそもそも一番最初の式の時点でm=dまで和を取ってよくて、そうすると整合性がありそうですね。
\displaystyle{ \sum_{m=0}^{d}A(d,m)r^{m+1}\\ =\sum_{m=0}^{d}\sum_{k=0}^{m} (-1)^k\binom{d+1}{k}(m+1-k)^d r^{m+1}\\ =\sum_{k=0}^{d} (-r)^k\binom{d+1}{k} \sum_{x=0}^{d-k}r^x x^d\\ =\sum_{y=0}^{d} (-r)^{d-y}\binom{d+1}{y+1} \sum_{x=0}^{y}r^x x^d\\ }
確かに同じ式が求まりました。

精進について

サーバルだよ！
競プロの精進について書くよ。
精進の仕方や、精進に対する考え方はいろいろあるから、あくまで私の意見だと思って読んでね。

■3行でまとめて

・復習が大事。解けた問題も解けなかった問題も、解説やいろんな子の実装を見てみる
・典型を身につけるのは大事。ABCは解説ACでもいいので解く
・写経はできればしない。一回自分で書いてみてから他の子の実装をパクる

■モチベーションについて

レートがついて他の子と競う以上、やっぱりレートが下がると面白くないよね……。
私も最近は下がってこそないけど全然上がらなくて面白くないよ……。
f:id:kyopro_friends:20200202161207p:plain

モチベーションが低いときに無理してコンテストに出ても成績は悪くなりがちだから、そういう気分のときはしばらくコンテストに出ないというのももちろんありだよ。
だけど、私には「コンテストに出て悔しい思いをして、解けなかった問題をちゃんと復習する」って方が合ってるから、できるだけコンテストには出るようにしてるんだ。

■パフォーマンスを上げるには

パフォーマンスを上げるためには「簡単な問題をよりはやく解く」「より難しい問題を(どうにか)解く」の少なくともどっちかが必要だよ。
本当に目指すべきは「難しい問題を解く」の方で、「簡単な問題をはやく解く」っていうのは、難しい問題を考える時間を残すために必要なことだね。
・自分の色未満のdiffの問題を、考察も実装も悩まずに解けるようにする
・自分の色のdiffの問題を解けるようにする
あたりを目標にするといいんじゃないかな。
私たちが青の頃は400～600点を埋めてたよ。このあたりの難易度を一通り埋めれば、典型にはだいたい触れられると思う。
水未満なら300点400点あたりかな？



■考察パートについて

一番大事なのは「自分がコンテスト中に解けなかった1問」を解けるようになることだよ。
私が復習するときは
・知識が足りなかったなら覚えて、それを使う関連する問題を(あれば)解く
・知識は足りていたけど、考察できなかったときは、「どうすれば思いつけたか」を考える
ってことを考えながらしてるね。
解説ACについては、ABCの問題で1時間考えて解けないなら、知識が足りない可能性が高いから解説を読んだ方がいいと思うよ。
典型を知らない状態から自分で発明できれば、多分もう忘れることはないと思うけど、時間は有限だからね……。
逆にAGCは、C問題あたりまでなら特別難しい知識はいらない問題が多いから、じっくり考えるのもあり。私はこっちもすぐ解説を読んじゃうけど…………。

■どうすれば思いつくのか？

「どうすれば思いつくか？」にはいろんなアプローチって、例えば私がよく考えるのはこの2つ。
・簡単な部分問題から考える（もし与えられるグラフが木なら解ける。一般のグラフの場合は……）
・愚直解法を考える（O(N^3)のDPはすぐわかるけどN≦2000だから間に合わない。無駄な計算を省くには……）
他にも、計算機科学？に詳しい子は
・解けない問題を考える（もしこの条件がないとNP完全になって解けないから、この条件をうまく使う必要があって……）
みたいな考え方をすることもあるらしいけど、私にはよくわかんないや。

■実装パートについて

AtCoderに限れば実装が大変な問題はそんなに出ないから、「実装が大変そう」って思ったらもっと解法が整理できないか考えてみるのが1つの手だね。
もちろん難しい実装をきっちりやりきる力も大事だけど、難しい実装に手をつけてバグらせたら大変だし、それが嘘解法だった日には目もあてられないよ…………。
私はコンテスト中には「これよりいい解法が思い付けそうになくて、今の難しい実装をバグらせずに通せる自信がある」ってときだけ、難しい実装に手をつけることにしてる……つもりなんだけどな～。

■解説ACと写経について

写経って言葉をみんながどういう意味で使ってるのかよく知らないけど、私は「誰かのコードを横に見ながらコードを書くこと」はほとんどしないよ。
誰かの実装を見たり解説を読んだら、自分の中でよく噛み砕いて、なにをやっているのかを理解してから何も見ずに1から書くのが好きだからね。
解法・アルゴリズムを本当に理解したなら、(少なくとも、理解したはずのその瞬間には)なにも見ずに書けるようになるはずだと私は思ってるし、特に、できれば「なんでこれでうまくいくのか」まで分かるようにしておくと、応用の幅がぐっと広がるはず！
もちろん自分で書ききったあとは、もう1回他の子のコードを参考にしながら、書き直すのは大事だよ。細かい実装のテクニックを身につけるのにも役立つし、「自分はこう書いてしまったけど、こうするともっとスッキリ書ける」っていうのを確かめられる絶好の機会だもんね。（実装のテクニックだと「めぐる式二分探索」が一番有名なのかな？）
他にもACがはやい方から何人かのコードは、びっくりするくらい簡潔なことが多いから参考になるよ！　簡潔すぎてよくわからないこともあるけど……。

■復習について

解けなかった問題だけじゃなくて、解けた問題も復習するのは大事だよ。自分が解いたのよりもっと簡単な方法があったりするかもしれないし。
公式の解説pdfだけじゃなくていろんな解説記事を読むのがいいよ。
ずっと前、ガイドさんが私に勉強の仕方を教えてくれたときに、「よくわからないことがあったら、10種類くらい解説を読んでみると、そのうち1つくらいは自分にとって分かりやすいものがあるはず」って教えてくれたんだ。
10種類……はさすがにできてないかもしれないけど、1つや2つの解説を読んでわけがわからなくても諦めないようにはなれたはず。



そんな感じで私は精進してるよ！
なんだか精進の話とはちょっとズレてる気もするけど、参考になるかな？

EDPC解説 U～Z

EDPC解説目次へ戻る

やー、フェネックだよー。
残りの6問はどれも難しいけど、解説していくよ。
実装例は省略するから自分で考えて書いてみてねー。

U問題 Grouping

N羽のうさぎをいくつかのグループに分ける。
うさぎのペアi,jについて、iとjが同じグループに属していればa[i][j]点を得る。
最高得点を求めよ。
制約：N\leq 16

解説

bitDPっぽいねー。
dp[S]=(集合Sに属するウサギのグループ分けの最高得点)
としてみようか。あとはN問題とほぼ同じで、「どこで切るか」を考えると良さそうだね。
dp[S]=\max(dp[T]+dp[S\setminus T])
ただし、N問題と違って「切らない」っていう選択肢もありだから注意が必要だよ。
実装はメモ化再帰の方が簡単かなあ。
bitDPは0-indexedの方が都合がいいから、入力は0-indexedで与えられているものとするねー。

#define bit(n,k) ((n>>k)&1) /*nのk bit目*/
long long f(int S){
	if(flag[S])return dp[S];
	flag[S]=1;
	//「切らない」場合を計算
	temp=0;
	rep(i,0,N)rep(j,i+1,N)if(bit(S,i)&&bit(S,j))temp+=a[i][j];
	fans=temp;
	//「どこで切るか」を考える
	for(Sの空でない真部分集合Tについて){
		fans=max(fans,f(T)+f(S^T));
	}
	return dp[S]=fans;
}
//ans=dp[(1<<N)-1];

for文で「部分集合T」を動くところが問題なんだけど、すぐに思いつく方法としてはこういうのがあるね。

rep(T,0,S)if((T|S)==S){/* */}

でもこれは状態数O(2^N)、遷移O(2^N)だから全体でO(4^N)になってTLEなんだよねー。
実は「Sの部分集合T」だけをちょうどループ出来るようなこういうテクニックが存在するよ。

for(int T=S;T>=0;T--){
	T&=S;
	/* */
}

この演算は「-1」という操作を「1であるような一番下のbitを0に変えて、それより下のbitを全て1にする」という意味だと思うと納得できるんじゃないかな？
今回は、空集合とS自身を除くからこうだね。

for(int T=S;T>=0;T--){
	T&=S;
	if(T==S || T==0)continue;
	/* */
}

さて、計算量はどうなるかな？
このループは2^{|S|}回されるから、全てのSについて和を考えると
\sum_S 2^{|S|} \\ =\sum_{i=0}^N \sum_{|S|=i} 2^{|S|} \\ =\sum_{i=0}^N 2^i*\#\{S \ | \ |S|=i\}\\ =\sum_{i=0}^N 2^i* {}_N C_i\\ =\sum_{i=0}^N 2^i*1^{N-i} * {}_N C_i\\ =(2+1)^N=3^N
となって、つまり全体でO(3^N)だね。これなら間に合うよ。
今回みたいにbitDPとかで役に立つbit演算のテクニックはこの記事が詳しいねー。
ビット列による部分集合表現 【ビット演算テクニック Advent Calendar 2016 1日目】 - prime's diary

V問題 Subtree

N頂点の木がある。頂点をいくつか選んで黒く塗る。このとき黒く塗られた頂点たちは連結であるようにする。
各頂点について、その頂点を黒く塗るような方法は何通りあるか\mod Mで答えよ。
制約：N\leq 10^5、M\leq 10^9

解説

1つの頂点についてだけ答えればいいんだったら、P問題と同じようにしてO(N)で求められるけど、これを各頂点でやってたらO(N^2)になって間に合わないんだよねー。
この問題みたいに「木の各頂点について～～であるようなものを求めよ」って問題は全方位木DPっていう方法で解けることが多いよ。
こういう感じのアルゴリズムだね。
１．適当な頂点を根にして木DPで問題を解く
２．根を子に移して問題を解く。このとき、今までに求めた情報を使い回す
３．繰り返す
詳しいアルゴリズムについてはこのブログが詳しいよ。
†全方位木DP†について - ei1333の日記
他にもsnukeさんのツイートも参考になるねー。

実はこの問題は、全方位木DPを知ってても"やるだけ"じゃないんだよねー。
まずはこの図を見てもらおうか。
f:id:kyopro_friends:20190112031630p:plain
左側でまず頂点1を根として問題を解いて、次に根を頂点2に移して問題を解くことを考えるよ。
左側の図で頂点1を根として問題を解くときは、頂点1で集める情報は「頂点2、頂点3、頂点4」の部分木に関する情報だね。
だけど右側の図で頂点2を根とするときは、頂点1で集める情報は「頂点3、頂点4」の部分木に関する情報で、頂点2は親だから含まないねー。
同様に頂点3,4を根にすると、頂点1で集める情報は「頂点2,4」「頂点2,3」になるから、毎回情報を集め直してたら、ウニグラフ*1のときに全体でO(N^2)になっちゃうんだよねー。
かといって「頂点2,3,4」に関する情報を集めておいて、そこから「頂点2に関する情報を取り除く」ということも出来ないよ。部分木の答えが\mod Mで0のときにゼロ除算になるからね。
どうすればいいかな？ちょっと問題をまとめ直しておこうか。
問題：頂点vと隣接する頂点の集合をUとする。Uに属する各頂点uに対し、部分木に関する答えdp[u]が求まっている。このとき、各uについて\prod_{w\neq u}dp[w]を高速に求めよ。
これも「累積和」を使うと解くことが出来るんだよね。今回は掛け算だから「累積積」って言った方がいいかな？
こういう手順で求めるよ
１．Uの頂点に順序を付けて1,2,\ldots,kとする。
２．前方1～iの累積積cum1[i]と、後方i～kの累積積cum2[i]を計算しておく
３．各u\in Uについて求める答えはcum1[u-1]*cum2[u+1]
こうすれば前計算O(|U|)、本計算O(1)でできるから、全ての頂点についての答えがO(|U|)で求められるよ。
ここまで工夫すれば全体での計算量はO(N)になって間に合うねー。いやー大変だよー。

…………ちなみに、私は本番ではこれを思いつかなくて、O(N\log N)で解いたんだよねー。詳しくは解説しないけど、こんな感じの方法だよ。
１．Uの頂点に順序を付けて1,2,\ldots,kとする。
２．f(l,r,s)という関数を「区間[l,r)に属する頂点について答えたい。この部分以外に関する積はs」とする
３．区間の長さが1ならsが答え。そうじゃないならm=(l+r)/2として、f(l,m,s'),f(m,r,s'')を再帰呼び出し
こうすると、二分法の要領でO(|U|\log|U|)、全体だとO(N\log N)で求められるねー。やー、競技プログラミングの問題は解ければ正義だから、ゴリ押しも大事だよー？

W問題 Intervals

M個の区間[l[i],r[i]]と値a[i]が与えられる。
長さNの01列に対して次のようにスコアを定めるとき、その最大値を求めよ。
条件：区間[l[i],r[i]]に1が存在すればa[i]点を得る
制約：N\leq 2*10^5、M\leq 2*10^5

解説

やー、DPの問題としては全部の問題のなかでこれが一番難しいんじゃないかな？
この問題をDPで解くためには
dp[i][*]=(*の条件下でi文字目まで決めたときの最高スコア)
みたいな感じにしようと考えるのが自然だよねー。このとき、スコアは「[1,i]に完全に含まれる区間のみ」を考えることにするよ。i+1以降にはみ出す区間は、dp[i+1][*]以降に影響を与えちゃうからね。
DPの状態として持つべき情報は何かを考えてみよう。dp[i][*]を考える時には、dp[i-1][*]の時から新たに[l,i]という形の区間に関するスコアを考慮することになるから、この区間に1があるかどうかがわかる必要がありそうだねー。だから
dp[i][j]=(i文字目まで決めて、最後に1であるのがj文字目であるようなものの最高スコア)
というものを考えてみようか。
dp[i][j]\\ = \left\{ \begin{array}{ll} dp[i-1][j]+(j\in [l,i]となる区間に関するスコアの和) & (j< i) \\ \max \{ dp[i-1][j] | 0\leq j< i\}+([l,i]となる区間に関するスコアの和) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ & (j=i) \end{array} \right.
として一応は計算できるけど、これをこの形のまま実装するとO((N+M)N)かかっちゃうねー。
遷移をよく見ると、これは次の3つのステップに分解できるよ。
１．dp[i][*]にdp[i-1][*]をコピーする
２．dp[i][i]=\max \{ dp[i-1][j] | 0\leq j< i\}とする
３．[l,i]の各区間について、j\in[l,i]なるjの範囲でdp[i][j]にスコアを加える
ステップ１はdp[i][*]とdp[i-1][*]で同じ配列を使い回すことで省略できて、ステップ２は区間maxと1点更新、ステップ３は区間addだから、starry sky treeというものを使うとそれぞれO(\log N)、全体でO((N+M)\log N)にできるよ。
starry sky treeに関する説明は省略するけど、区間addと区間maxができるようにちょっと工夫したセグメント木のことだねー。遅延セグメント木が上位互換になってるから、そっちが使えるならそれでも十分だよ。

X問題 Tower

N個のブロックがあり、i番目のブロックは重さw[i]、丈夫さs[i]、価値v[i]である。
これらのブロックを1列に積み重ねて、次の条件が満たされるような塔を作る。塔に含まれるブロックの価値の和の最大値を求めよ。
条件：塔を構成するどのブロックの丈夫さも、それより上にあるブロックの重さの合計以上である
制約：N\leq 10^3、s[i]\leq 10^4

解説

ナップサックDPみたいに
dp[i][j]=(i番目までのブロックを使って重さj以下で作れる塔の最大価値)
としたいけど、丈夫さに関する条件を考えると、次のブロックが使えるかどうかわからないからうまくいかないねー。
実はこの問題は「ブロックをうまく並び替えることで、塔に使うブロックの順序を決めることができる（＝次に使うブロックは、使うなら一番下）」らしいよ。やー、なんでこんなこと思いつくのかなー？
どういう順序で使えばいいか考えるためにこういうのを考えてみるよ。
f:id:kyopro_friends:20190112002741p:plain
そういうわけでs[i]+w[i]でソートしたら、あとは最初に言ったDPができるね。
ちなみにこれは「s[i]+w[i]が大きいものの方が上になってたら、入れ替えても影響がない」という方針でも証明ができて、その方が簡単なんだけど、「s[i]+w[i]が小さいものが上になったほうがよさそう」ってわかってないと思いつけないから、ちょっと難しいかもねー。
計算量はO(N\max s[i])だよ。

Y問題 Grid 2

2次元のマスを移動する。(i,j)からは(i+1,j)か(i,j+1)に移動できる。
ただしN個の壁があり、そのマスには移動できない。i番目の壁の座標は(r[i],c[i])である。
(1,1)から(H,W)へ移動する場合の数を\mod 10^9+7で求めよ。
制約：H,W \leq 10^5、N\leq 3*10^3

解説

壁は予め辞書順かマンハッタン距離順にソートしておこうか。それから二項係数もでてきそうだから「壁がない時(0,0)から(x,y)まで移動する場合の数＝{}_{x+y}C_x」のことをf(x,y)と書くことにしとくよ。階乗とその逆元をO(H+W)で前計算しておくことで、f(x,y)はO(1)で答えられるとしていいね。（やらなくても間に合うけどねー）
一瞬座標圧縮にも見えるけど、圧縮して無くなったマスだけを通る経路をうまく数えられないからそれはダメそうだねー。
Nが小さければ
dp[i]=(i番目の壁を通って、スタートからゴールまで移動する場合の数)
として包除原理を使うことでも解けるけど、今回は無理だよ。
求めるものの余事象を考えると、「壁のマスを1回以上通って、ゴールまで行く場合の数」になるわけだけど、「1つ以上あるか？」とくれば、W問題と同じように「最後に/最初に〇〇したもののindex」を状態に持てば良さそうだねー。
そこで
dp[i]
=(最初にぶつかる壁がiである場合の数)
=(1～i-1番目の壁を避けてi番目の壁の位置にたどり着く場合の数)
というのを考えるよ。
dp[i]
=f(r[i],c[i])-(i-1番目までの壁に1回以上ぶつかって壁iの位置にたどり着く場合の数)
で、
(i-1番目までの壁に1回以上ぶつかって壁iの位置にたどり着く場合の数)
＝\sum_{j=1}^{i-1}(壁jで初めて壁にぶつかって壁iの位置にたどりつく場合の数)
＝\sum_{j=1}^{i-1} (1～j-1番目の壁を避けてj番目の壁の位置にたどり着く場合の数)\times(j番目の壁の位置からi番目の壁の位置まで壁を無視して移動する場合の数)
＝\sum_{j=1}^{i-1} dp[j]*f(r[i]-r[j],c[i]-c[j])
となるから、遷移はO(N)でできるね。
ゴールまでの場合の数も同様にしてできるから、計算量は全体でO(N^2)だね。

Z問題 Frog 3

N個の足場がある。
足場iからは足場i+1,i+2,\ldots,Nのいずれかに移動でき、足場iから足場jに移動するコストは(h[i]-h[j])^2+Cである。
足場1から足場Nに移動するまでの最小コストを求めよ。
制約：N\leq 2*10^5、C\leq 10^{12}、h[i]\leq10^6

解説

やー、この問題はCHT(Convex Hull Trick)を知ってれば、見た瞬間「CHTだ」ってなる問題だねー。いわゆる「知識ゲー」ってやつかな？
まずはCHTっていうのは、こういうのだねー。

区間[L,R]と直線群Sが与えられたとき、次の2種類のクエリを高速に処理するアルゴリズムをCHTという。
１．直線追加クエリ：Sに直線Ax+Bを加える
２．最小値クエリ：x\in [L,R]に対し\min\{f(x) \ | \ f\in S\}を求める

今回は追加される直線の傾きAと最小値クエリで問われる値xのどちらもが単調だから、dequeを使って書けるんだけど、せっかくだからLi Chao Segment Treeを実装したよ。これはどちらのクエリについても単調性を問わないものだねー。
実装はこのブログを参考にしたよ。
傾きの単調性が要らない Convex Hull Trick - kazuma8128’s blog

Li Chao Segment Tree
N点集合P=\{x_i\}と直線群Sが与えられたとき、次の2種類のクエリをO(\log N)で処理するデータ構造
１．直線追加クエリ：Sに直線Ax+Bを加える
２．最小値クエリ：x\in Pに対し\min\{f(x) \ | \ f\in S\}を求める

元の問題の解説に戻ろうか。
A問題と同じ素直なDPを考えると
dp[i]=(足場iにたどり着くまでの最小コスト)
dp[i]=\min\{dp[j]+(h[i]-h[j])^2+C\ |\ 1\leq j< i\}
となって遷移がO(N)だから全体でO(N^2)になって間に合わないんだけど、遷移式をよく見て変形すると
dp[j]+(h[i]-h[j])^2+C\\ =-2h[j]*(h[i])+(dp[j]+h[j]^2)+(h[i]^2+C)
となって、最後の部分をminの外に出して
dp[i]=\min\{-2h[j]*(h[i])+(dp[j]+h[j]^2)\ |\ 1\leq j< i\}+(h[i]^2+C)
となるねー。
わかりやすくするためにA_j=-2*h[j]、B_j=dp[j]+h[j]^2とおくと、minの部分は
\min\{A_j*(h[i])+B_j\ |\ 1\leq j< i\}
つまり「A_jx+B_jという直線群のx=h[i]における最小値を求めよ」という問題になってCHTで解けるというわけさ。
計算量は、単調性を仮定したdequeを使った実装だとO(N)、単調性を使わないLi Chao Segment TreeだとO(N\log N)だね。


やー、これで26問全部を解説したわけだけど、どうだったかなー？
私たちは本番ではTWXYZの5問を残して21完で、残った5問は主にsnukeさんの解説を参考にして解説ACしたよ。
ꑄ꒖ꐇꌅꏂ🐈 on Twitter: "DPコン、解法全部書いた。 https://t.co/BqSnOQIkbR"
解説AC含めて全問ACすれば黄色くらいの実力になるんじゃないかな？　私たちが黄色になったばっかりだしねー。
それじゃあねー。

EDPC解説目次へ戻る

*1:1つの頂点を中心にして、そこからたくさんの辺が出てるようなグラフ

EDPC解説 M～T

EDPC解説目次へ戻る

カラカルよ。M問題～T問題を解説するわ。
このあたりから計算量を気にして高速化をしないといけない問題が増えてきて大変だけど、ついてこれるかしら？

M問題 Candies

N人の子供にちょうどK個の飴を配る方法は何通りあるか\mod 10^9+7で求めよ。
ただしi番目の子供にはa[i]個以下しか渡すことができない。
制約：N\leq 10^2、K\leq 10^5

解説

dp[i][j]=(i番目までの子供たちにj個の飴を配る場合の数)
ってDPをやるだけね。

dp[0][0]=1;
rep(i,1,N+1)rep(j,0,K+1){
	rep(k,0,a[i]+1)if(j-k>=0)dp[i][j]=(dp[i][j]+dp[i-1][j-k])%MOD;
}

……とはいかないのよねぇ。
これだと計算量がO(NK^2)になって全然間に合わないわ。
そこで状態遷移のところをよくみてみるわ。数式で書くと、これってこういうことよね。
\displaystyle{dp[i][j]=\sum_{k=\max(0,j-a[i])}^j dp[i-1][k]}
これはdp[i-1][*]の区間の和だから、累積和を使えば高速化することができるわね。

dp[0][0]=1;
rep(i,1,N+1){
	cum[0]=0;
	rep(j,1,K+1+1)cum[j]=(cum[j-1]+dp[i-1][j-1])%MOD;
	//cum[j]=dp[i-1][0]+...+dp[i-1][j-1]
	rep(j,0,K+1)dp[i][j]=(cum[j+1]-cum[max(0,j-a[i])]+MOD)%MOD;
}
ans=dp[N][K];

計算量はO(NK)よ。

N問題 Slimes

N匹のスライムが1列に並んでいる。i番目のスライムの大きさはa[i]である。
「隣り合う2匹のスライムを合体させる」という操作を繰り返して1匹のスライムにまとめることを考える。
合体後のスライムの大きさの和と等しいコストがかかる。最小コストを求めよ。
制約：N\leq 400

解説

この問題は逆から考えると簡単ね。つまり問題全体をこう読み替えるわけ。
「
1匹のスライムがいる。大きさは\sum a[i]である。
「スライムを2匹に分解する」という操作を繰り返して、大きさが端から順にa[i]であるようなN匹のスライムを作ることを考える。
分解には分解前のスライムの大きさと等しいコストがかかる。最小コストを求めよ。
」
切るべき箇所は、最終的なスライムの切れ目にあたるN-1箇所のどれかね。
どれが最小になるか分かればいいから
dp[l][r]=(区間[l,r]に相当するスライムが1匹にまとまっているとき、それを分解するために必要な最小コスト)
が分かればいいわね。実装はメモ化再帰が簡単だと思うわ。

int f(int l,int r){
	if(flag[l][r])return dp[l][r];
	flag[l][r]=1;
	if(l==r)return 0;
	//どこで切るか全通り試す
	fans=INF;
	rep(m,l,r)fans=min(fans,f(l,m)+f(m+1,r));
	return dp[l][r]=fans+(a[l]～a[r]の和);//予め累積和を計算しておく
}
//ans=f(1,N);

状態数がO(N^2)、遷移がO(N)だから計算量はO(N^3)ね。

O問題 Matching

男女がN人ずついる。男女からなるペアをN組つくりたい。
男性iと女性jの相性a[i][j]が0か1で与えられ、相性が0であるような2人はペアになることができない。
ペアの作り方は何通りあるか？\mod 10^9+7で求めよ。
制約：N\leq 21

解説

bitDPというテクニックを使う問題ね。
bitDPというのは、集合を数に変換して状態(=添字)として持つようなDPのことよ。
例えば\{0,2,3\}という集合は2^0+2^2+2^3=13という数に変換して、「数iが集合に属しているか」と「i bit目が1か」を対応させるわ。
こうすると、「集合としてS\subset T」⇒「数としてS\leq T」になるから

rep(S,0,1<<N){
	/*処理*/
}

というふうに、DPの遷移が単純なループで書けることが多いのよね。
この問題もこのことを知っていれば簡単よ。
dp[i][S]=(男性はi人目までで、既にペアになった女性の集合がSであるような場合の数)
としてDPするわ。
今まではずっと1-indexedでやってきたけど、bitDPは0-indexedの方が都合がいいから、入力は0-indexedで与えられているものとするわ。

#define bit(n,k) ((n>>k)&1) /*nのk bit目*/
dp[0][0]=1;
rep(i,1,N+1)rep(S,0,1<<N){
	rep(j,0,N)if(bit(S,j)==1&&a[i-1][j]==1){
		dp[i][S]=(dp[i][S]+dp[i-1][S^(1<<j)])%MOD;
	}
}
ans=dp[N][(1<<N)-1];

……とすると、これはO(2^N N^2)でTLEなのよねえ。
少し考えると「既にペアになった女性の集合がS」なら「bitpopcount(S)人目までをチェックした」ってことになるから、iを状態として持つ必要は無いことがわかるわ。

#define bit(n,k) ((n>>k)&1) /*nのk bit目*/
dp[0]=1;
rep(S,1,1<<N){
	i=__builtin_popcount(S);
	rep(j,0,N)if(bit(S,j)==1&&a[i-1][j]==1)dp[S]=(dp[S]+dp[S^(1<<j)])%MOD;
}
ans=dp[(1<<N)-1];

計算量はO(2^N N)よ。

詳しくは説明しないけど、この問題を配るDPで解くときは、次のコードで実はO(2^N N)になるわ。枝刈りが本質的に計算量を改善する例ね。

#define bit(n,k) ((n>>k)&1) /*nのk bit目*/
dp[0][0]=1;
//一見するとO(2^N N^2)だけど……
rep(i,0,N)rep(S,0,1<<N)if(dp[i][S]){//<-ここのif文の枝刈りが効いてO(2^N N)に落ちる
	rep(j,0,N)if(bit(S,j)==0&&a[i][j]==1){
		dp[i+1][S^(1<<j)]=(dp[i][S^(1<<j)]+dp[i][S])%MOD;
	}
}
ans=dp[N][(1<<N)-1];

P問題 Independent Set

N頂点の木が与えられる。頂点を白か黒で塗る。
隣接する頂点どうしをともに黒で塗ることはできない。
塗り方は何通りあるか？\mod 10^9+7で求めよ。
制約：N\leq 10^5

解説

木DPというやつね。部分木に関する情報を集めて元の木に関する問題に答えるようなDPよ。
まず適当な頂点を1つ選んで根とするわ。
各頂点は子が何色かによって塗れる色が決まるから、各部分木について、根が黒/白の塗り方の数がわかればいいわね。
dp[i][j]=(頂点iを(j?黒く:白く)塗ったとき、iを親とする部分木の塗り方の場合の数)
とすると、
\displaystyle{dp[i][0]=\prod_{jはiの子} (dp[j][0]+dp[j][1])}
\displaystyle{dp[i][1]=\prod_{jはiの子} dp[j][0]}
となるわ。
実装は根からたどれるメモ化再帰が簡単じゃないかしら。

void f(int i){
	if(flag[i])return;
	flag[i]=1;
	dp[i][0]=1;
	dp[i][1]=1;
	for(iの子jについて){
		f(j);
		dp[i][0]=dp[i][0]*(dp[j][0]+dp[j][1])%MOD;
		dp[i][1]=dp[i][1]*dp[j][0];
	}
}
//頂点1を根とすると
//f(1);
//ans=(dp[1][0]+dp[1][1])%MOD;

計算量はO(N)ね。

Q問題 Flowers

N本の花が一列に並んでいる。花iは高さh[i]、美しさa[i]である。
左から見て単調増加になるように花を選ぶ時、美しさの最大値を求めよ。
制約：N\leq 2*10^5、h[i]は1～Nで相異なる

解説

i番目までの選び方を決めた時、次の決め方に影響するのは最後に選んだ花だけだから
dp[i][j]=(i番目まで使って最後の高さがjであるようなものの美しさの最大値)
というのを考えるのが自然よね。
dp[i][j]= \begin{cases} \max\{dp[i-1][k]|0\leq k< j\}+a[i] & (h[i]==j\text{のとき})\\ dp[i-1][j] & (\text{それ以外}) \end{cases}
1回あたり更新するのは1箇所だから、iを状態にもつ必要はなくて、配列を使い回すことができるわ。
あとは、区間maxが高速に計算できればいいから、セグメント木を使えばできるわね。
セグメント木の説明は省略するけど、区間に対する操作が高速にできるようなデータ構造のことよ。

rep(i,1,N+1){
	temp=getmax(0,h[i]);//dp[0],...,dp[h[i]-1]のmax
	setvalue(h[i],temp+a[i]);//dp[h[i]]をtemp+a[i]にする
}
ans=getmax(0,N+1);

セグメント木は区間maxの計算と値の変更をどちらもO(\log N)でできるから、計算量はO(N\log N)になるわね。

もしこの問題で全てのa[i]が1なら、これは最長増加部分列と全く同じ問題ね。
つまり最長増加部分列問題もこの解き方で解けるわ。

R問題 Walk

N頂点単純有向グラフGの隣接グラフAが与えられる。
長さKのパスがいくつあるか\mod 10^9+7で求めよ。
ただし同じ辺を複数回通るものも含める。
制約：N\leq 50、K\leq 10^{18}

解法

長さKのパスを考えるのだから、とりあえず始点と終点を状態として
dp[n][i][j]=(頂点iから頂点jへ行く長さnのパスの個数)
というのを考えてみるわ。状態遷移は
dp[n][i][j]=\sum_k dp[n-1][i][k]*a[k][j]
となるわね。ところで、この積の形、よくみると行列の積と同じね！
dp[n][i][j]を(i,j)成分とする行列をDP_nと書くことにすると、さっきの漸化式は
DP_n=DP_{n-1} A
になるわ。
DP_0は明らかに単位行列だから、DP_n=A^nね。
求める答えは\sum_{i,j} dp[K][i][j]だから、A^Kを計算すれば求められるわよ。

matrixpow(A,K,MOD);//Aをmod MODでK乗する
rep(i,1,N+1)rep(j,1,N+1)ans=(ans+A[i][j])%MOD;

行列の積は1回あたりO(N^3)、繰り返し二乗法を使えば積を計算する回数はO(\log K)だから、O(N^3\log K)で求められるわね。

「行列の積と同じ式になってると気づくのは無理じゃない？」
そうね、こればっかりは知ってるかどうかになりそうね。
行列累乗で解く問題は、次の２つのポイントを抑えておくといいわ。どっちも決め手になるほどじゃないけど……
・ポイント１：制約をみる
N\leq 50くらい、Kは10^9とか10^{18}とかの大きな値、みたいな制約の問題は、サイズN\times Nの行列をK乗するかも。
・ポイント２：繰り返し
今回の状態遷移の式を見ると、回数nが遷移に影響しないわね。こういうふうに同じ状態遷移を何度も繰り返すものは、行列累乗かも。

S問題 Digit Sum

1以上K以下の数のうち、十進表記での各桁の数字の和がDの倍数であるものはいくつあるか？
\mod 10^9+7で求めよ。
制約：K\leq10^{10^4}、D\leq 10^2

解説

桁DPね。
桁DPっていうのは本質的に1種類しかなくて、基本的にこの方針で実装することになるわ。
dp[i][f][*]=(上からi桁目まで決めて、Kより小さいことが確定して(f?いて:いなくて)、条件*を満たすようなもの)
場合によっては下の桁から決めることもあるけど、まあ似たようなものね。
今回は桁和がDの倍数であるものの個数を調べたいから、「既に決まっている部分の桁和の\mod D」という状態を追加で持てばいいわよ。
桁DPについてはこのサイトの説明がわかりやすいと思うわ。
桁DP入門 - ペケンペイのブログ
桁DPはもらうDPよりも配るDPの方が圧倒的に書きやすいのよね。実はいままでA問題からR問題までは全部もらうDPで説明してたんだけど、気付いてたかしら？

//K[i]でKの先頭からi文字目の数が得られるとする
dp[0][0][0]=1;
rep(i,0,N)rep(j,0,D){
	rep(dig,0,10)dp[i+1][1][(j+dig)%D]=(dp[i+1][1][(j+dig)%D]+dp[i][1][j])%MOD;
	rep(dig,0,K[i+1])dp[i+1][1][(j+dig)%D]=(dp[i+1][1][(j+dig)%D]+dp[i][0][j])%MOD;
	dp[i+1][0][(j+K[i+1])%D]=(dp[i+1][0][(j+K[i+1])%D]+dp[i][0][j])%MOD;
}
ans=(dp[n][0][0]+dp[n][1][0]-1+MOD)%MOD;//答えに0が含まれるのでそれを除くために-1

計算量は、基数をBとしてO(DB\log_B K)よ。

T問題 Permutation

不等号'<''>'のいずれかからなる長さN-1の文字列sが与えられる。
1～Nの並び替えpであって、次の条件を満たすものは何個あるか？
条件：pの隣接する要素を比較し、順に不等号を書いたとき、それがsと一致する
制約：N\leq 3*10^3

解説

dp[i][j][S]=(i番目まで決めたとき、最後の数がjで、使用済みの数の集合がSであるような場合の数)
というのはすぐ思いつくけど、N\leq 3000だからこれは当然無理ね……。
よく考えると、次に決める数は、前に決める数との大小関係さえわかっていればいいから
dp[i][j]=(i番目まで決めたとき、i番目の数より大きいものがj個残っているような場合の数)
というのを考えればうまくいきそうね。

rep(j,0,N)dp[1][j]=1;
rep(i,2,N+1){
	if(s[i-1]=='<'){
		rep(j,0,N-i+1)rep(k,j+1,N-i+2)dp[i][j]=(dp[i][j]+dp[i-1][k])%MOD;
	}else{
		rep(j,0,N-i+1)rep(k,0,j+1)dp[i][j]=(dp[i][j]+dp[i-1][k])%MOD;
	}
}
ans=dp[N][0]

…………と言いたいところだけど、これもまだO(N^3)なのよね。
M問題と同じように最後の部分で累積和を使うとO(N^2)に出来るわ

rep(j,0,N)dp[1][j]=1;
rep(i,2,N+1){
	cum[0]=0;
	rep(j,1,N-i+3)cum[j]=(cum[j-1]+dp[i-1][j])%MOD;
	if(s[i-1]=='<'){
		rep(j,0,N-i+1)dp[i][j]=(cum[N-i+2]-cum[j+1]+MOD)%MOD;
	}else{
		rep(j,0,N-i+1)dp[i][j]=cum[j+1];
	}
}
ans=dp[N][0];


ふぅ、これで私の担当範囲はおしまいね。最後の6問はフェネックが解説してくれるわ。
……もしかしてフェネックが何かしてくれるなんて珍しいことなんじゃないかしら？

EDPC解説目次へ戻る

EDPC解説 F～L

EDPC解説目次へ戻る

はいはーい、サーバルだよ！
F問題～L問題の解説をしていくよ！　よろしくね。

F問題 LCS

2つの文字列s,tが与えられる。
s,tの共通部分列であって、最長のものを1つ求めよ。
制約：|s|,|t|\leq 3*10^3

解説

いきなり難しい問題だね……。
「求める文字列の長さ」だけを先に求めておいて、実際の文字列はそれを手がかりに構成していくよ。
dp[i][j]=(sをi文字目、tをj文字目までみた時の最長共通部分列の長さ)
とすると、
s[i]==t[j]のときこの文字は使ったほうがいいからdp[i-1][j-1]+1、
そうじゃないときは、どっちかの最後の1文字は使わないから\max(dp[i-1][j],dp[i][j-1])
になるね。

//slenはSの長さ、tlenはTの長さとする
rep(i,1,slen+1)rep(j,1,tlen+1){
	if(s[i]==t[j])dp[i][j]=dp[i-1][j-1]+1;
	else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
//dp[slen][tlen]が求める長さ

具体的に文字列を作るのはDP配列を逆にたどればできるよ。
もしs[i]==t[j]なら、求める最長共通部分列の最後の文字はs[i]で、それより前の部分はdp[i-1][j-1]の結果からわかって、
そうじゃないならどっちかの最後の文字は使わないから、dpの値が減らない方に移動すればいいね。

len=dp[slen][tlen];
i=slen;
j=teln;
while(len>0){
	if(s[i]==t[j]){
		ans[len]=s[i];
		i--;
		j--;
		len--;
	}else if(dp[i][j]==dp[i-1][j]){
		i--;
	}else{
		j--;
	}
}

計算量はO(|s||t|)だよ。
イメージとしてはこんな感じ！

G問題 Longest Path

有向閉路を持たないN頂点M辺の有向グラフGが与えられる。
Gの有向パスの最長経路を求めよ。
制約：N\leq 10^5、M\leq 10^5

解説

これをもらうDP/配るDPで書くのはちょっと難しいね。トポロジカルソートっていうのが必要になるのかな？
こういうときはメモ化再帰で書くといいよ！
f(x)=(xを始点とする最長経路)とすると
f(x) = \begin{cases} 0 & (x\text{が葉のとき}) \\ \max\{f(y)+1|x\text{から}y\text{への辺があるような}y\} \ \ \ \ \ \ \ \ \ \ \ \ \ \ & (\text{そうでないとき}) \end{cases}
として再帰で計算できるよ。答えは\max\{f(x)\}だね。
再帰の深さがO(N)くらいになるけど、スタックオーバーフローはしないみたい。

int f(int x){
	if(flag[x])return dp[x];
	flag[x]=1;
	fans=0;
	for(xからyへの辺があるようなy){
		fans=max(fans,f(y)+1);
	}
	return dp[x]=fans;
}
//ans=0;
//rep(i,1,N+1)ans=max(ans,f(i));

計算量はO(N+M)だよ。

H問題 Grid 1

2次元のマスを移動する。(i,j)からは(i+1,j)か(i,j+1)に移動できる。
ただしa[i][j]が'#'であるマスには移動できない。
(1,1)から(H,W)へ移動する場合の数を\mod 10^9+7で求めよ。
制約：H,W \leq 10^3

解説

(H,W)へ行く場合の数は、(H-1,W),(H,W-1)へ行く場合の数の和だね。だから
dp[i][j]=((1,1)から(i,j)へ移動する場合の数の\mod 10^9+7)
とすれば解けそうだよ。

dp[1][1]=1;
rep(i,1,H+1)rep(j,1,W+1)if(!(i==1&&j==1)){
	if(a[i][j]=='#')dp[i][j]=0;
	else dp[i][j]=(dp[i-1][j]+dp[i][j-1])%MOD;
}
ans=dp[H][W];

計算量はO(HW)だよ。

I問題 Coins

N枚のコインがあり、コインiは確率p[i]で表、1-p[i]で裏が出る。
全てのコインを投げたとき、表が出たコインの数の方が多い確率を求めよ。
制約：N\leq 2999、Nは奇数

解説

dp[i]=(i枚目のコインまで投げたとき、表が出たコインの数の方が多い確率)
だと、次に裏が出たときでもまだ表のほうが多いかどうかがわからないからうまくいかないね。
表が出た枚数がわかってれば大丈夫そうだから
dp[i][j]=(i枚目のコインまで投げたとき、表がj枚でる確率)
で出来そうだよ。
dp[i][j]= \\ (i-1\text{枚目のコインまで投げたとき、表が}j\text{枚でる確率})\times(i\text{枚目のコインが裏である確率})\\ +(i-1\text{枚目のコインまで投げたとき、表が}j-1\text{枚でる確率})\times(i\text{枚目のコインが表である確率})
でちゃんと計算できるね。
答えは\sum_{j=(N+1)/2}^{N}dp[N][j]だよ。

dp[0][0]=1;
rep(i,1,N+1)rep(j,0,i+1){
	if(j>0)dp[i][j]=dp[i-1][j]*(1-p[i])+dp[i-1][j-1]*p[i];
	else dp[i][j]=dp[i-1][j]*(1-p[i]);
}
ans=0;
rep(j,N/2+1,N+1)ans+=dp[N][j];

計算量はO(N^2)だね。

J問題 Sushi

N個の皿があり、皿iには寿司がa[i]個乗っている。
全ての寿司を食べるまで次の操作を繰り返すとき、操作の回数の期待値を求めよ。
操作：皿をランダムに1つ選ぶ。選んだ皿に寿司が乗っていれば、そのうち1つを食べる。
制約：N\leq 300、1\leq a[i]\leq 3

解説

まずは状態をどうやって持つか考えよう。
普通にやるとdp[a0][a1][a2][a3]\ldotsみたいに添字がN個欲しくなっちゃう。
でも例えば「皿1に寿司が2個、皿2に寿司が1個」という状態と「皿1に寿司が1個、皿2に寿司が2個」という状態だと、操作回数の期待値は同じになるよね。
よく考えると、「どの皿に何個あるか」っていうところまでわかる必要はなくて、「1個の皿がいくつ、2個の皿がいくつ、3個の皿がいくつ」だけで期待値は決まることがわかるよ。
そこで
dp[c1][c2][c3]=(1個の皿がc1枚、2個の皿がc2枚、3個の皿がc3枚あるとき、全て食べるまでの操作回数の期待値)
というのを考えるよ。
えーっと、これはループで書くのが難しいからメモ化再帰で書く方がいいね。

dp[c1][c2][c3]=\\ 1\\ +dp[c1-1][c2][c3]*(\text{1個の皿が選ばれる確率})\\ +dp[c1+1][c2-1][c3]*(\text{2個の皿が選ばれる確率})\\ +dp[c1][c2+1][c3-1]*(\text{3個の皿が選ばれる確率})\\ +dp[c1][c2][c3]*(\text{0個の皿が選ばれる確率})

再帰なのに同じ状態に戻ってきちゃう！
けど、これはdp[c1][c2][c3]の項を移項すれば解消できるね。

dp[c1][c2][c3]=\\ 1/(1-(0個の皿が選ばれる確率))\\ +dp[c1-1][c2][c3]*(\text{1個の皿が選ばれる確率})/(1-(0個の皿が選ばれる確率))\\ +dp[c1+1][c2-1][c3]*(\text{2個の皿が選ばれる確率})/(1-(0個の皿が選ばれる確率))\\ +dp[c1][c2+1][c3-1]*(\text{3個の皿が選ばれる確率})/(1-(0個の皿が選ばれる確率)) 

double f(int c1,int c2,int c3){
	if(c1==0&&c2==0&&c3==0)return 0;
	if(flag[c1][c2][c3])return dp[c1][c2][c3];
	flag[c1][c2][c3]=1;
	fans=1/(1-(double)(N-c1-c2-c3)/N);//doubleにキャストしないと整数除算になっちゃう
	if(c1>0)fans+=f(c1-1,c2,c3)*c1/N/(1-(double)(N-c1-c2-c3)/N);
	if(c2>0)fans+=f(c1+1,c2-1,c3)*c2/N/(1-(double)(N-c1-c2-c3)/N);
	if(c3>0)fans+=f(c1,c2+1,c3-1)*c3/N/(1-(double)(N-c1-c2-c3)/N);
	return dp[c1][c2][c3]=fans;
}
//rep(i,1,N+1)c[a[i]]++;
//ans=f(c[1],c[2],c[3]);

計算量はO(N^3)だよ。

K問題 Stones

N個の元をもつ数の集合Aと、石の山があり、二人でゲームをする。
「x\in Aを選び、石の山からちょうどx個の石を取り除く」という操作を交互にして、先に操作できなくなったほうが負けとなる。
最初に石がK個あるとき、どちらが勝つか答えよ。
制約：K\leq 10^5、N\leq 10^2

解説

ゲームの基本的な問題だよ！
石の個数によって勝敗が決まるから、
dp[i]=(石の個数がi個のとき直後の手番の人が勝てるか？)
を考えるよ。これがYesになる状態を「勝ち状態」、Noになる状態を「負け状態」と呼ぶことにするね。
自分の手番の後で残る石の個数としてありえるものについて考えて、どれか1つでも「負け状態」になるなら、それを相手に渡せば良くて、全部「勝ち状態」ならどうやっても相手に「勝ち状態」を渡すことになるから自分は負けだよ。

rep(i,1,K+1){
	rep(j,1,N+1)if(i-a[j]>=0&&dp[i-a[j]]==0)dp[i]=1;
}
//ans=dp[K];

計算量はO(NK)だね。

L問題 Deque

長さNの数列aが与えられ、二人でゲームをする。
「aの先頭か末尾の数を取り除く。取り除いた数と同じ点数を得る」というルールである。
ゲーム終了時の先手の総得点をX、後手の総得点をYとする。 先手はX−Yを最大化しようとし、後手はX−Yを最小化しようとする。二人が最適に行動するとき、X−Yを求めよ。
制約：N\leq 3*10^3

解説

太字で書いてあるところは要するに「(自分の点数)－(相手の点数)を最大化しようとする」だね！
前から取ったほうがいいか後ろから取ったほうがいいかは、残った数を使ってのゲームの結果が分かれば判断できるから、
dp[i][j]=(区間[i,j]が残ってるときの「次の手番の人の得点－そうじゃない方の人の得点」)
とすればよさそうだね。実装はメモ化再帰が簡単かな。

int f(int l,int r){
	if(flag[l][r])return dp[l][r];
	flag[l][r]=1;
	if(l==r)return dp[l][r]=a[l];
	return dp[l][r]=max(a[l]-f(l+1,r),a[r]-f(l,r-1));
}
//ans=f(1,N);

計算量はO(N^2)だね。


ふー、大変だった！　これで私の担当はおしまい。
次はカラカルがM問題からを解説してくれるよ！

EDPC解説目次へ戻る