読者です 読者をやめる 読者になる 読者になる

はまやんはまやんはまやん

hamayanhamayan's blog

Codeforces Round #405 問題と解説

http://codeforces.com/contest/790
http://codeforces.com/contest/791

A. Bear and Big Brother

http://codeforces.com/contest/791/problem/A
2つの数A,Bがある。
一回の操作でAは3倍、Bは2倍される。
最小何回の操作でA > Bとなるか。

B. Bear and Friendship Condition

http://codeforces.com/contest/791/problem/B
N頂点,M辺の無向グラフがある。
このグラフが以下の性質を満たすか判定せよ。
「全ての独立した3頂点(X,Y,Z)について(X,Y)と(Y,Z)間に辺があるとき(X,Z)間にも辺がある」

C. Bear and Different Names / A. Bear and Different Names

http://codeforces.com/contest/790/problem/A
http://codeforces.com/contest/791/problem/C
N人の兵士がいる。
この兵士の名前について、N-K+1個の情報が与えられる。
i番目の情報は[i, i+K-1]の範囲の兵士に名前がダブっている兵士のペアがあるなら"NO"、皆異なる名前であれば"YES"。
ありうる兵士の名前(10文字以内の英語大文字小文字)を出力せよ。

D. Bear and Tree Jumps / B. Bear and Tree Jumps

http://codeforces.com/contest/790/problem/B
http://codeforces.com/contest/791/problem/D
N頂点の木がある。
f(s,t) := 頂点sから頂点tへの最短距離/Kの切り上げ
全てのs<tを満たす頂点のペア(s,t)についてf(s,t)の総和は?

E .Bear and Company / C. Bear and Company

http://codeforces.com/contest/790/problem/C
http://codeforces.com/contest/791/problem/E
文字数Nの文字列Sがある。
この文字列に対して、隣り合う文字をスワップする操作を行う。
"VK"という連続文字列が出てこないようスワップするときの最小スワップ数は?

D. Bear and Rectangle Strips

http://codeforces.com/contest/790/problem/D
縦2横Nの配列がある。
各マスには整数が書かれている。
このマスから内部の和が0となる長方形を最大何個被らず作れるか


以下、解説
























A. Bear and Big Brother

http://codeforces.com/contest/791/submission/25631907
シミュレーションするだけ。
条件を満たすまで回すシミュレーションはwhileでやるとよい。

B. Bear and Friendship Condition

http://codeforces.com/contest/791/submission/25632038
この考察に至るまでが難しいのだが、今回の条件は以下のように言い換えることができる。
「各連結成分について完全グラフであるか」
これを計算する方法は

  • UnionFindで連結成分に分けて全ての頂点間に辺があるかを見る
  • DFSで連結する頂点の頂点数と辺数を計算して判定する

があるが、上記のコードは後者である。
口で説明するより、コードを見てもらった方が早い。
dfsの戻り値のsecondを割る2しているのは、次数の総和/2=辺数となる(握手補題)を使っている。

C. Bear and Different Names / A. Bear and Different Names

http://codeforces.com/contest/790/submission/25632507
考察をしっかりすると、解ける。
まず、全部の名前を別々に生成する。
情報が"NO"ならばどこかがダブっているが、ans[i+K-1]をans[i]に更新する。
これはans[i+K-1]とans[i]が同じ区間に属するのは情報が"NO"となるその区間だけになるので同じ名前にしてしまっても、他の"YES"に影響しないためである。
あとは出力するだけ。
http://codeforces.com/contest/790/submission/25606141
1位の人のコードを見た。早すぎ

D. Bear and Tree Jumps / B. Bear and Tree Jumps

全方位木DPをする
hamayanhamayan.hatenablog.jp

まず、全方位木せず全ての頂点について木DPをするパターン
http://codeforces.com/contest/790/submission/25634428
こっちが全方位木パターン
http://codeforces.com/contest/790/submission/25635846
全方位木のパターンとしては典型チックだけど、頭がこんがらがる。

E .Bear and Company / C. Bear and Company

http://codeforces.com/contest/790/submission/25644066
dp[v][k][x][isLastV] := 先頭から'V'をv個、'K'をk個、他の文字をx個使って並べて、最後が'V'である(=isLastV)ときのswap最小回数
としてdpを作る。以下にどういう選択なのか、詳しく書く。

例えば"VVKXXVKVV"を考える(公式Editorialと同じ)。
これでdp[4][1][1][0]とすると、先頭からVを4つ、Kを1つ、他の文字を1つ取ったことになるので、
VVKXXVKVV
↓
XKV
が残った文字列となる。ここで最小スワップ数で取ってきたとすると残る文字の順番は同じになるので、
どのような順番でとってもその後の展開は同じとなる。
つまり、それ以前の状態を1つにまとめあげることができる。

更新処理としては、毎回文字列を先頭からチェックしていって選択済みなら飛ばして、選択できるようになったらDP更新していく。