Codeforces Global Round 4
反省会場
A - Prime Minister
問題：
1．過半数の席が欲しい
2．連立政権ができるが、Aliceの政党の半分以下の議席の党だけしかできない。
3．連立する党の数を最小化したということがわかる
考察：
・Aliceの議席の半分以下の政党をまとめてソート。大きい順にいれて、全体の半分を超えたところが答え。
・最後まで超えないときはNO
B - WOW Factor
問題：Wを連続するV2つで代用してWOWを作りたい。VとOの文字列が与えられる。連続するVVをWとして使うことで、連続しなくてもよい部分文字列WOWがいくつ作れるか。
考察：
・典型
・Oを固定してそれぞれのOで考える。
・左右のVVの数の積が、そのOを使うときの場合の数
・累積和でOK
・長さが10^6なのでLLじゃないとオーバーフローする…。これに気づかず2時間頭抱えてました(やばすぎ)
C - Tiles
問題：W*Hにななめに黒白にわかれたタイルを置く。黒も、白も隣接しないような置き方はいくつあるか
考察：
・左上を決めるとその横は2通り、その下も2通り。
・その右下は1つに決まる
・左上は4通りなので、4*2^(h-1)*2^(w-1)=2^(w+h)
黒だけ隣接してはいけないと誤読してて2時間頭抱えてました(ちゃんと読もう)
D - Prime Graph
問題：以下の条件を満たすN頂点の連結単純グラフを求めよ
１．辺の数Mが素数
２．各頂点の次数が素数
考察：
・貪欲に考えると、最小の素数で構成できるかを考える
・まず連結なので、N-1本以上は枝が必要である。
・また各頂点の次数が素数なので、2以上。端点が２N個なので枝はN以上必要
・そうするとN以上の最小の素数で構成できるかを考えればよい。
・難しいのでグラフのほうを考える。
・二重辺にならないように辺を増やす。次数が2から3、5と増やす。
・3までで、N/2個増やせる。
・神様が1000までのNはN以上1.5*N以下に素数が存在することを教えてくれる。調べるとあってる。
・次数2か3で良いことがわかれば簡単。
・素数判定はN*sqrt(N)でよいので間に合う
これ爆速で通したの良かった。
E - Archaeology
問題：a,b,cで構成された文字列Sが与えられる。長さS/2以上の対称な(連続でなくてもよい)部分文字列を求めよ
実は、隣り合う文字が違うことが保証されてる
考察：
・先頭と最後尾を2文字ずつ見ると、必ず一致する文字がある。
・なぜならab…cdとするa!=b、c!=dは保証されている。もしa!=c、a!=dなら、3種類出てるので、bがc、dのどちらかと一致する。
・同じ文字を取っていって長さ半分くらい＋１文字出力するとうまくいく
隅々まで問題を読もうね…
F1 - Short Colorful Strip
問題：N個のマス目をN色で塗る。塗る色が指定される。各色1マス。以下のルールで塗って、与えられる列と一致させたい。何通りあるか。
・色1から順番に塗る。
・重ね塗りするときは、はみ出してはいけない。
考察：全く分からん
解説：
・ある範囲の塗り方DP[l][r]通りとする
・ある色で塗られた範囲[l,r]を考える
・次に塗るのはその中で最小の色ｃ、場所ｋである。
・色ｃを塗る範囲を[a,b]とすると、a,bの全通りに対して
DP[l][r]=sum(DP[l][a-1]*DP[a][k-1]*DP[k+1][b]*DP[b+1][r]
という遷移になる。l、r、a。bで調べるので配列N^2、遷移Ｎ^2のO(N^4)である
・工夫するとO(N^3)にできる←これはなに
コード見ればわかるかもしれないけど放置中
ＤＰっぽさあったけどわからなかった。範囲ＤＰは計算ドリル感あるし解きたかった
※ベンツヨしたんで追記します
まず解説を読み解くとこから
1．DP[l][r]：ある範囲が1色で塗られているとき、その範囲だけを考えたときの塗り方の場合の数
[l,r)の範囲がなにかしらの色(無色でもよい)で塗られているとします。
このときl-1やrは、別の色の必要があります。また、その色を示すマスが含まれないとします。
このあと、その範囲はどの色で塗られるでしょうか。
ちょっとわかりづらいのでSample2の例で考えてみましょう。
4 5 1 6 2 3 7
というマスがあります。
はじめに４，５，１，６，２を色1で塗るとしましょう
4 5 1 6 2 3 7
ここでDPを考慮する場所は
4 5 と 6 2 と 3 7
の3つの区間です。[0,2) と [3,5)、[5,7)です。
左側を塗る通りはDP[0][2]です
右側を塗る通りはDP[3][5]*DP[5][7]です。これは別の色で塗られている区間は独立だからです。
4から2までを色1で塗った時の場合の数はDP[0][2]*(DP[3][5]*DP[5][7])で求まることがわかりました。
色1で塗る方法は左側の境目が0,1,2,3で、右側の境目が4,5,6,7です。
この全てで計算して足せば色1の塗り方が求まります。
次に、ある区間で次に調べる色を考えます。
例えば区間[0,2)であれば、4 5なので、小さい方4で塗ることになります。
つまり、区間の最小値を求めればよいです。自分は雑にセグ木を使いました。もっと手軽な方法があるかもしれません。
まとめます
・最後にDP[0][n]を求めたい
・DP[l][r]を求めるには
1.[l,r)の最小値cと場所kを求める
2.[l,a)、[a,k)、[k+1,b)、[b,r)をあり得るa,b全てで調べる
ここでa,bは独立に考えてよいです。なので
DP[l][r]=ΣΣ( DP[l][a-1]*DP[a][k] * DP[k+1][b]*DP[b+1][r] )
=Σ( DP[l][a]*DP[a][k] ) * Σ( DP[k+1][b]*DP[b][r] )
となりO(N)での計算が可能です。
・DP配列は、ｌとｒでN^2個なので遷移がO(N)より、全体でO(N^3)で求めることができます。
・実装についてですが、再帰で大丈夫でした。再帰にしないなら区間が短い順、左側からとかで求めていく感じだと思います。なんかバグりそう
感想
誤読というか問題文読めてないの多すぎる
とりあえずＬＬ使っておいたほうがいいですね
ＡＢＣあとで疲れていたのもあったのでまあ仕方ないかなと思います
もうちょっとで水色落ちしちゃうので、明日のエデュフォは頑張りたいなー。
まあ水に落ちたらＤｉｖ３に出れるというメリットがある(?)
