AGC051C『Flipper』

サーバルだよ！　AGC051C『Flipper』の解説をするよ！

コンテスト中の考察

なんだかライツアウトっぽいね。
ライツアウトと同じようなことをすれば解けそう。
ライツアウトをmod2での連立方程式だと思って解く方法と同じプログラムを書いて、6×6や7×7で実験をすると、ライツアウトの「解の存在条件」の式と同じようにして、今回の問題の操作での不変条件の式が出てくるんだけど、その式をぐ～～～っと睨むと、次の2つが不変量になってることがわかるよ。
・各列の黒マスの個数の偶奇
・各行の、「mod3で0の列と1の列にある黒マスの個数の合計の偶奇」「mod3で0の列と2の列にある黒マスの個数の合計の偶奇」
あとはこの不変量を崩さない条件も下で黒マスの個数を最小化すればいいね！

行の条件をもうちょっと丁寧に見ておこうかな。各行にあるmod3で0,1,2の列にある黒マスの個数を(x,y,z)で表すことにすると、「mod3で0の列と1の列の黒マスの個数の合計の偶奇」「mod3で0の列と2の列……」が、
・(偶,偶)なら(0,0,0),(1,1,1),……
・(奇,偶)なら(0,1,0),(1,0,1),……
・(偶,奇)なら(0,0,1),(1,1,0),……
・(奇,奇)なら(1,0,0),(0,1,1),……
になるよ。偶奇だけしか見てないから、例えば(偶,奇)なら(4,2,1)とかももちろん作れるね。
ということは、最初の盤面で上の4通りになってる行がそれぞれP,Q,R,S個、列について「黒マスの個数が奇数であるようなmod3で0,1,2の列の個数」をX,Y,Zとすると問題は次のように読み替えられるよ！

問題：
P,Q,R,S,X,Y,Zが与えられたとき、次の条件を満たすような(x,y,z)について、x+y+zの最小値を求めよ。
・(x,y,z)は、(0,0,0)か(1,1,1)をあわせてP個、(1,0,0)か(0,1,1)をあわせてQ個、(0,1,0)か(1,0,1)をあわせてR個、(0,0,1)か(1,1,0)をあわせてS個、(0,0,2),(2,0,0),(0,0,2)を好きな個数、合計したものである
・x≧X かつ y≧Y かつ z≧Z
・x≡X かつ y≡Y かつ z≡Z mod2

(Q,R,S)が考えられる最小なんだけど、x≧Xの条件とかを満たしてないときにどうするかを考えないといけなくて、(0,0,2)はタダで使えるけど+2だから、(1,0,0)を(0,1,1)に変える+1を優先するのが良くて、でも個数制限があって…………
というところで2時間悩んで本番中に結局解けなかったよ…………

コンテスト後の考察

まずQ=R=S=0のときはX+Y+Zが答えになることが少し考えるとわかるね。そうじゃないときを考えよう。
(Q,R,S)をベースに改善することを考えるんだけど、例えば(1,0,0)→(0,1,1)と(0,1,0)→(1,0,1)を両方やるのは(1,1,0)→(1,1,2)だから、(0,0,2)をタダでもらうのと同じになるね。
ということは結局、どの種類を何個変換するかを全探索すればOK！
Submission #19200670 - AtCoder Grand Contest 051 (Good Bye rng_58 Day 2)
うーん、数学でうまく最適解を求めるんじゃなくて、全探索すればよかったんだね……。前半パートがめちゃくちゃ数学だったから、すっかり数学頭になってたよ…………。

前半の考察の数学的な説明

あれ、今日は全部サーバルさんが解説すると思ってたんですが、数学パートは私がやるんですか？　いいですけど。
そういうわけで解説のスナネコです。
不変量を求めるときに登場した方程式が何をやっていたのかをちょっと説明します。

盤面をN×Nとして、各マスが白か黒かを0,1に対応させることで、盤面はのN^2次元ベクトルとみなすことが出来ます。
また、1回の操作も、操作によって変化するマスを1とするベクトルとみなすことで、盤面に対する操作は、ベクトルの足し算だと思うことが出来ます。

よって「操作に関する不変量を求めよ」という問題は、「(H-1)(W-2)種類の操作に対応するベクトルで張られる、の部分空間Vの元が満たすべき条件式を求めよ」になります。
(H-1)(W-2)個の操作が独立であることは少し考えるとわかります（ある元を、その元以外の線形結合で作ろうとしても、右下から貪欲に決めるしかなくうまくいかないことがわかります）。
なので、操作が張る部分空間の次元は(H-1)(W-2)であり、この部分空間の元が満たす条件式の個数はHW-(H-1)(W-2)=2H+W-2になります。
あとはサーバルさんがやったように実験をすると不変量っぽいものが見つかりますが、一応これが不変量であることを確認しておきましょう。
・列に関する条件の方は明らかですね。どの操作でも、各列のちょうど2マスが変化するので、黒マスの偶奇は変わりません。
・行に関する条件の方は、mod3で行を塗り分けるとわかります。どの操作でも、赤と青、赤と緑がちょうど2マス含まれるので、赤＋青、赤＋緑の部分にある黒マスの偶奇は変わりません。

列に関する条件式がW個、行に関する条件式が2H個で合わせて2H+W個あるように見えますが、列に関する条件のうち、右端2つの列の分は、他の条件から導くことができるので実質2H+W-2個です。
あとはこれらの条件が独立であることを確認すればよいですが、面倒なので省略します。

AtCoder practice contest B問題 Interactive Sorting

スナネコです。
AtCoderのpractice contestのB問題を解いたので解説を書きます。

問題ページにあるコード例を読むとわかりますが、この問題は「Q回以下の比較で、長さNの数列をソートせよ」と読み替えられます。

(N,Q)=(26,1000)のとき

コード例に書いてあるとおり、バブルソートなど、のソートアルゴリズムを実装すると通ります。
(26,100)のアルゴリズムでも当然解けるので、(26,100)が解けるなら、(26,1000)のためのコードを書く必要はありません。

(N,Q)=(26,100)のとき

最悪計算量がのソートアルゴリズムを書く必要があり、定数倍にも気をつける必要があります。
マージソートをすると、99回の比較でソートできることが証明できます。

(N,Q)=(5,7)のとき

本題です。
7回の質問で得られる情報7bit128パターンから、ありえる数列の並び5!=120通りを特定する必要があります。
この厳しすぎる条件から、毎回の質問は返答がほぼ半々に分かれるようにするしかないことがわかるので、何を質問すればいいか選択肢が絞れます。

1回目

(A,B)を質問し、A<Bと返ってきたとしてよいです。残りの可能性は60通りです。

2回目

質問として(A,C) か (C,D)のどちらかが考えられます。
（例えば(B,C)は数列全体を反転すれば(A,C)と同じですし、(C,E)はDとEを入れ替えれば(C,D)と同じです）
(A,C)を聞いてA<Cと返ってきた場合、ありえる数列が40通り残るので、残りの5回で判別できません。
なので(C,D)を聞きます。C<Dとしてよいです。残りの可能性は30通りです。

3回目

質問として(A,C)、(A,D)、(A,E)の3通りが考えられます。
(A,D)を聞いてA<Dと返ってきた場合、ありえる数列が25通り残るので、残り4回で判別できません。
(A,E)を聞いてA<Eと返ってきた場合、ありえる数列が20通り残るので、残り4回で判別できません。
なので(A,C)を聞きます。A<Cとしてよいです。残りの可能性は15通りです。

4回目

現時点でA<C<D、A<Bがわかっています。ABCDの並び順はABCD,ACBD,ACDBのどれかで、さらにEがどこに入るかで3×5の15通りの可能性があります。
意味のある質問と、最悪ケースを考えると
A>E　12通り
B>C　10通り
B<D　10通り
B>E　9通り
C<E　8通り
D>E　11通り
となるので、(C,E)と質問するしかないことがわかります。

4回目でC<Eになったとき

A<C<(D,E) かつ A<Bがわかっています。DEの順序を確定するのに1回、Bの位置4通りを確定するのに2回の計3回で特定できます。

4回目でC>Eになったとき

意味のある質問と、最悪ケースを考えると
A<E　4通り
B>C　4通り
B>D　5通り
となるので、(A,E) か (B,C)を質問すればよいです。どちらでもあと2回の質問で特定できますが、(B,C)の方があとが簡単です

5回目でB<Cになったとき

A<B<C<D、E<Cがわかっているので、Eがどこに入るか3通りを2回で確定できます

5回目でB>Cになったとき

(A,E)<C<(B,D) となるので、AE,BDの順序をそれぞれ2回で特定すれば良いです。

以上でこの問題が解けました。
最後の何回かの質問の部分の場合分けがちょっと大変ですが、他に選択肢はないので、頑張って場合分けを実装するしかなさそうです。

ABC174C Extra

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

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

制約：

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

• 77...77 (n桁)が の倍数
• 11...11 (n桁)が の倍数
• 99...99 (n桁)が の倍数
• 

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

解法１：離散対数問題
この問題は離散対数問題そのものなので、Baby-Step Giant-Stepなどを用いることで、 で解くことができます。

解法２：乗法群における位数
明らかに、 が2の倍数か5の倍数のときは答えが-1になることがわかります。
そうでないとき、オイラーの定理から、が成り立ちます。
なので、 を満たす最小の は、 の約数となることがわかります。
（もしそうでなければ、として、より小さい答えが作れるので矛盾します）
を求め、素因数分解し、約数を全探索することで、で解くことができます。

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

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

制約：

解説：

を満たす最小の を と書くことにします。
もし、 が互いに素なら、 を満たす最小の は、中国剰余定理から になることがわかります。
よって、素数べきに対する答えが求めることができれば、それらを組み合わせて一般の場合に答えることができます。
最初に 以下の数の最小素因子テーブルを作っておき、素因数分解が で出来るようにしておきます。（osa_k法というやつですね）
素数 に対しての答えは、問題その１で説明した方法によって、 で求めることが出来ます。
証明は省略しますが、 は か になります。どちらになるかは実際に計算することで、 で確かめられます。
（証明は「」を二項定理を使って示します。ちなみに、になるのは、 のときの 3, 487, 56598313 の3通りしか知られていないようです（A045616））
これらをうまく組み合わせると、全体で で解くことができます。

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

Nim product

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

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

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

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

スナネコです。yosupo judgeにある を解きました。
問題

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

さて、dが大きなときでもやることはd=0,1の時と同じで、rを掛けて差を取っていきます。
例えばd=4のときは

という感じですね。
なんだか見たことのない数が残りました。こういうときは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を使って計算できればいいんですけど、うまくいきますかね。ちゃんと式に書いてみましょう。

愚直に計算するとO(d^2)です。困りました。
正解者の提出をちらっと見てみると、こういう式で計算してました。

スナネコの考えてる式と似たような感じなので、今の方針であってそうです。
二項係数の部分と、(…)^dの部分で変数を分離して、独立に累積和っぽく計算する工夫は面白いですね。これが使えないか試してみます。m+1-kをxと変数変換してみます。

うまくできましたね。これで、xのシグマについてはkが大きい方から累積和のように計算していくことができるので、高速に計算できるようになりました。
この計算式の通りにやっても全体でですが、逆元テーブルの線形構築や細かい計算を配列にメモしておくことでいくらか定数倍高速化が効きます。

これでAC……ではありません。d=0の時はそもそも最初のの時点で空和になって0になってしまいます。仕方がないのでこれだけ場合分けです。

ACは取れましたが、途中で紹介した他の正解者の計算式では場合分けをしてないみたいです。こっちも導出してみましょう。
最後の数式でd-kをyに変数変換します。

和を取る範囲が違いますね。ここが0から始まっているとd=0のときにも場合分けをしなくて済むようです。
wikipediaをよく見てみると、A(0,0)=1、n>0のときA(n,n)=0、と書いてありました。ということはそもそも一番最初の式の時点でm=dまで和を取ってよくて、そうすると整合性がありそうですね。

確かに同じ式が求まりました。

精進について

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

■3行でまとめて

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

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

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

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

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

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

コノハ「これでA[BRGP]Cの500点問題も全て解き終わりましたね」
ミミ「自力AC率は19/23で82.6%ですか。微妙な数字ですね、博士」
コノハ「そうですね。次の難易度に進むべきかどうか聞いてみるですよ」

次に解くべきは

— 競技プログラミングをするフレンズ (@kyopro_friends) March 31, 2018

■考察パートについて

一番大事なのは「自分がコンテスト中に解けなかった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

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

解説

bitDPっぽいねー。
集合に属するウサギのグループ分けの最高得点
としてみようか。あとはN問題とほぼ同じで、「どこで切るか」を考えると良さそうだね。

ただし、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文で「部分集合」を動くところが問題なんだけど、すぐに思いつく方法としてはこういうのがあるね。

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

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

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

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

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

さて、計算量はどうなるかな？
このループは回されるから、全てのについて和を考えると

となって、つまり全体でだね。これなら間に合うよ。
今回みたいにbitDPとかで役に立つbit演算のテクニックはこの記事が詳しいねー。
ビット列による部分集合表現 【ビット演算テクニック Advent Calendar 2016 1日目】 - prime's diary

V問題 Subtree

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

解説

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

全方位木DP、有向辺に関するDPだと思うのが分かりやすい。
1. 青い矢印は普通の木DPで下から順に求まる
2. 根から出る矢印は全部求まっているので、根に入る矢印も求められる（ここの計算量改善に総和とって引き算とか左右からの累積和とかが出てくる）
3. 同様に赤い矢印を上から順に求めていく pic.twitter.com/p4bl6rXzGn

— ꑄ꒖ꐇꌅꏂ🐈 (@snuke_) 2019年1月6日

実はこの問題は、全方位木DPを知ってても"やるだけ"じゃないんだよねー。
まずはこの図を見てもらおうか。

左側でまず頂点1を根として問題を解いて、次に根を頂点2に移して問題を解くことを考えるよ。
左側の図で頂点1を根として問題を解くときは、頂点1で集める情報は「頂点2、頂点3、頂点4」の部分木に関する情報だね。
だけど右側の図で頂点2を根とするときは、頂点1で集める情報は「頂点3、頂点4」の部分木に関する情報で、頂点2は親だから含まないねー。
同様に頂点3,4を根にすると、頂点1で集める情報は「頂点2,4」「頂点2,3」になるから、毎回情報を集め直してたら、ウニグラフ*1のときに全体でになっちゃうんだよねー。
かといって「頂点2,3,4」に関する情報を集めておいて、そこから「頂点2に関する情報を取り除く」ということも出来ないよ。部分木の答えがで0のときにゼロ除算になるからね。
どうすればいいかな？ちょっと問題をまとめ直しておこうか。
問題：頂点と隣接する頂点の集合をとする。に属する各頂点に対し、部分木に関する答えが求まっている。このとき、各についてを高速に求めよ。
これも「累積和」を使うと解くことが出来るんだよね。今回は掛け算だから「累積積」って言った方がいいかな？
こういう手順で求めるよ
１．の頂点に順序を付けてとする。
２．前方～の累積積と、後方～の累積積を計算しておく
３．各について求める答えは
こうすれば前計算、本計算でできるから、全ての頂点についての答えがで求められるよ。
ここまで工夫すれば全体での計算量はになって間に合うねー。いやー大変だよー。

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

W問題 Intervals

個の区間と値が与えられる。
長さの01列に対して次のようにスコアを定めるとき、その最大値を求めよ。
条件：区間に1が存在すれば点を得る
制約：、

解説

やー、DPの問題としては全部の問題のなかでこれが一番難しいんじゃないかな？
この問題をDPで解くためには
の条件下で文字目まで決めたときの最高スコア
みたいな感じにしようと考えるのが自然だよねー。このとき、スコアは「に完全に含まれる区間のみ」を考えることにするよ。以降にはみ出す区間は、以降に影響を与えちゃうからね。
DPの状態として持つべき情報は何かを考えてみよう。を考える時には、の時から新たにという形の区間に関するスコアを考慮することになるから、この区間に1があるかどうかがわかる必要がありそうだねー。だから
文字目まで決めて、最後に1であるのが文字目であるようなものの最高スコア
というものを考えてみようか。

として一応は計算できるけど、これをこの形のまま実装するとかかっちゃうねー。
遷移をよく見ると、これは次の3つのステップに分解できるよ。
１．にをコピーする
２．とする
３．の各区間について、なるの範囲でにスコアを加える
ステップ１はとで同じ配列を使い回すことで省略できて、ステップ２は区間maxと1点更新、ステップ３は区間addだから、starry sky treeというものを使うとそれぞれ、全体でにできるよ。
starry sky treeに関する説明は省略するけど、区間addと区間maxができるようにちょっと工夫したセグメント木のことだねー。遅延セグメント木が上位互換になってるから、そっちが使えるならそれでも十分だよ。

X問題 Tower

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

解説

ナップサックDPみたいに
番目までのブロックを使って重さ以下で作れる塔の最大価値
としたいけど、丈夫さに関する条件を考えると、次のブロックが使えるかどうかわからないからうまくいかないねー。
実はこの問題は「ブロックをうまく並び替えることで、塔に使うブロックの順序を決めることができる（＝次に使うブロックは、使うなら一番下）」らしいよ。やー、なんでこんなこと思いつくのかなー？
どういう順序で使えばいいか考えるためにこういうのを考えてみるよ。

そういうわけででソートしたら、あとは最初に言ったDPができるね。
ちなみにこれは「が大きいものの方が上になってたら、入れ替えても影響がない」という方針でも証明ができて、その方が簡単なんだけど、「が小さいものが上になったほうがよさそう」ってわかってないと思いつけないから、ちょっと難しいかもねー。
計算量はだよ。

Y問題 Grid 2

2次元のマスを移動する。からはかに移動できる。
ただし個の壁があり、そのマスには移動できない。番目の壁の座標はである。
からへ移動する場合の数をで求めよ。
制約：、

解説

壁は予め辞書順かマンハッタン距離順にソートしておこうか。それから二項係数もでてきそうだから「壁がない時(0,0)から(x,y)まで移動する場合の数＝」のことをと書くことにしとくよ。階乗とその逆元をで前計算しておくことで、はで答えられるとしていいね。（やらなくても間に合うけどねー）
一瞬座標圧縮にも見えるけど、圧縮して無くなったマスだけを通る経路をうまく数えられないからそれはダメそうだねー。
が小さければ
番目の壁を通って、スタートからゴールまで移動する場合の数
として包除原理を使うことでも解けるけど、今回は無理だよ。
求めるものの余事象を考えると、「壁のマスを1回以上通って、ゴールまで行く場合の数」になるわけだけど、「1つ以上あるか？」とくれば、W問題と同じように「最後に/最初に〇〇したもののindex」を状態に持てば良さそうだねー。
そこで

最初にぶつかる壁がである場合の数
番目の壁を避けて番目の壁の位置にたどり着く場合の数
というのを考えるよ。

番目までの壁に1回以上ぶつかって壁の位置にたどり着く場合の数
で、
番目までの壁に1回以上ぶつかって壁の位置にたどり着く場合の数
壁で初めて壁にぶつかって壁の位置にたどりつく場合の数
番目の壁を避けて番目の壁の位置にたどり着く場合の数番目の壁の位置から番目の壁の位置まで壁を無視して移動する場合の数

となるから、遷移はでできるね。
ゴールまでの場合の数も同様にしてできるから、計算量は全体でだね。

Z問題 Frog 3

個の足場がある。
足場からは足場のいずれかに移動でき、足場から足場に移動するコストはである。
足場から足場に移動するまでの最小コストを求めよ。
制約：、、

解説

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

区間と直線群が与えられたとき、次の2種類のクエリを高速に処理するアルゴリズムをCHTという。
１．直線追加クエリ：に直線を加える
２．最小値クエリ：に対しを求める

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

Li Chao Segment Tree
点集合と直線群が与えられたとき、次の2種類のクエリをで処理するデータ構造
１．直線追加クエリ：に直線を加える
２．最小値クエリ：に対しを求める

元の問題の解説に戻ろうか。
A問題と同じ素直なDPを考えると
足場にたどり着くまでの最小コスト

となって遷移がだから全体でになって間に合わないんだけど、遷移式をよく見て変形すると

となって、最後の部分をminの外に出して

となるねー。
わかりやすくするために、とおくと、minの部分は

つまり「という直線群のにおける最小値を求めよ」という問題になってCHTで解けるというわけさ。
計算量は、単調性を仮定したdequeを使った実装だと、単調性を使わないLi Chao Segment Treeだとだね。

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

EDPC解説目次へ戻る

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