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

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

hamayanhamayan's blog

Codeforces Round #403 問題と解説

競技プログラミング

http://codeforces.com/contest/782

A. Andryusha and Socks

http://codeforces.com/contest/782/problem/A
1~N番のN組の靴下がある。
左右合わせて2N個の靴下をある順番で受け取る。
もう片方の靴下を受け取るまで机の上にもう片方の靴下を置いておき、もう片方が来たらどちらも片付ける。
机の上に最大何個の靴下が置かれることになるか。

B. The Meeting Place Cannot Be Changed

http://codeforces.com/contest/782/problem/B
N人いる。
それぞれ位置X[i]で歩く速さはV[i] m/秒である。
どこか一箇所に集まる時に最短何秒かかるか。

C. Andrysha and Colored Balloons

http://codeforces.com/contest/782/problem/C
N頂点の木がある。
各頂点に色をつけるが、a - b - cと連結している場合はa,b,cは違う色で塗る必要がある。
つまり、2頂点先までで同じ色があるとダメ。
必要な色数の最小数と、その場合の塗り方を答えよ。

D. Innokenty and a Foodball League

http://codeforces.com/contest/782/problem/D
N個のクラブ名(三文字)と町の名前の組がある。
以下のルールで全ての組に対して三文字の名前を決めることができるかを判定せよ。
できるならば、そのパターンを示せ。
1. 「全てクラブ名にする」か「クラブ名の先頭2文字と町の名前の先頭1文字を合わせる」
2. クラブ名が同じ他のクラブが存在する場合は「全てクラブ名にする」ことで命名ができない

E. Underground Lab

http://codeforces.com/contest/782/problem/E
N頂点M辺の無向グラフがある。
長さfloor(2N/K)以下のパスをK本用意することで全ての頂点を通るようにする。
そのパスの構成を答えよ。

F. Axel and Marston in Bitland

http://codeforces.com/contest/782/problem/F
N頂点M辺の有向グラフがあり、辺には0か1が書かれている。
これに対しPとBから成るパターン文字列を考える。

S[0] = P
S[i] = S[i - 1] + inv(S[i - 1])
inv関数はPとBを反転させる関数
つまり、S = {P, PB, PBBP, PBBPBPPB, PBBPBPPBBPPBPBBP}

Pは0にBは1に対応している。
頂点1からスタートしてパターン文字列に沿って頂点を移動していく時、移動できる距離の最大値を答えよ。
もし、移動距離が10^18を越える場合は-1と出力せよ。
















以下、解説

A. Andryusha and Socks

http://codeforces.com/contest/782/problem/A
bool on[N]を用意しておき、順番に処理しながら、机の上に最大何個ある状態があるかチェックする。
http://codeforces.com/contest/782/submission/25246539

B. The Meeting Place Cannot Be Changed

http://codeforces.com/contest/782/problem/B
t秒で全員が一箇所に集合できるかを判定する関数chkを用意して、二分探索で解く。
判定の時は区間で考える。
i人目がt秒で移動できる範囲は[X[i] - t * V[i], X[i] + t * V[i]]
これを全員分求めて、皆が被っている範囲があるかを判定する。
http://codeforces.com/contest/782/submission/25250029

C. Andrysha and Colored Balloons

http://codeforces.com/contest/782/problem/C
必要な色数の最小値は(次数の最大値+1)。
あとは、dfsをしながら塗っていくが、その際に2頂点先まで色が被らないようにしないといけないので、自分の色を塗るために、自分の親の色(ca)と自分の親の親の色(cb)を伝搬させながら色塗りをしていく。
http://codeforces.com/contest/782/submission/25253035

D. Innokenty and a Foodball League

http://codeforces.com/contest/782/problem/D
2-SATで解く。
hamayanhamayan.hatenablog.jp
各クラブについて「全てクラブ名にする」か「クラブ名の先頭2文字と町の名前の先頭1文字を合わせる」の2通りの選択肢があるので、2-SATに帰着できる。
「同じクラブ名であればどちらも同じクラブ名にできない」と「クラブ名が被らない」という条件を加えてSATsolverに通す。
http://codeforces.com/contest/782/submission/25256585

E. Underground Lab

http://codeforces.com/contest/782/problem/E
頂点1からdfsをして、無向グラフを探索していく。
無向グラフだが、木として扱いながらdfsをする感じ。到達済みの頂点には行かないようにする感じ。
探索する過程でオイラーツアーを構築していく。
オイラーツアーはhttp://www.npca.jp/works/magazine/2015_5/が例もあって分かりやすい。
オイラーツアーの要素数は2N - 1でこれをK個に分割してパスとして答えるとそのまま答え。
http://codeforces.com/contest/782/submission/25278138

F. Axel and Marston in Bitland

http://codeforces.com/contest/782/problem/F
まだ自分は解いてないけど、解法はなんとなく分かった。
ダブリングの要領で解く。
bool dp[i][c][from][to] := パターンS[i]をc(=0:正転, =1:反転)させたもので頂点fromから頂点toへ到達可能か
これの計算量を落とすために最後の要素はbitsetで代用する
bitset dp[i][c][from]
ここで dp[i][c][A][C] == 1となるのは dp[i - 1][c][A][B] & dp[i - 1][c - 1][B][C] == trueのとき。
これをbitsetでor計算とかで上手いこと計算していく。
あとは、これを使って頂点1から最大パスを計算していく。