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

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces Round #360 (Div. 1)

http://codeforces.com/contest/687

A. NP-Hard Problem

問題

グラフが与えられる。頂点を A か B かに分類する。このとき A も B も点カバーになっている必要がある。このような分類ができるか判定し、可能ならその一例を示せ。

解法

辺 (u,v) が A にも B にも覆われる必要があるため、隣接する頂点同士はかならず別の集合に属する必要がある。

A に入れる頂点を一個決めると、その頂点に隣接する頂点はクラス B になり、さらにその頂点に隣接する頂点はクラス A になり、というように連鎖的に定まる。 なので、実際に連鎖させて矛盾が起きないか調べればいい。

ちなみに、やっていることは二部グラフ判定と同じ。

gist.github.com

B. Remainders Game

問題

x mod c[i] の情報を用いて x mod k を特定できるか判定せよ。

解法

  • x mod a と x mod b が分かれば x mod LCM(a, b) が特定できる(中国剰余定理)
  • x mod a が分かれば x mod a' (a' は a の約数)が特定できる

まず 1 つ目の事実を使って x mod LCM(c[1],...,c[n]) を特定する。もし k が LCM の約数であれば 2 つ目の事実を使って特定できる。逆にこれ以外は特定できないことは直感的に明らか。

gist.github.com

C. The Values You Can Make

  • dp[ i 番目まで見た ][ 総和が j ][ 一部の総和が k ]:=可能かどうか

という DP ができる。500*500*500 の配列はちょっと怖いので、500*500 の配列を使い回した。bitset で高速化しないと解けないタイプかと思ったが、普通に O(n3) やるだけっぽい。なんだこれ。

gist.github.com

D. Dividing Kingdom II

時間が 6 sec もあるので O(qmα) が通るみたい(αはアッカーマンの逆関数)。クエリ一回あたり O(mα) でやる方法を考えてみよう。

まず辺を重みで降順ソートしておく。そしてその順番で辺を繋いでいく。

一番重い辺は違うグループにした方がいい。8 を繋ぐ(8が[l,r]の中で一番大きかった)。

f:id:pekempey:20160630081759p:plain

8 はうまく無視できたので、解は 8 以下であることが保証された。次に 6 を繋ぐ。

f:id:pekempey:20160630081955p:plain

6 もうまく無視できたので、解は 6 以下であることが保証された。次に 5 を繋ぐ。

f:id:pekempey:20160630082057p:plain

塗り方を変えたけど、これも無視できた。解は 5 以下。次に 4。

f:id:pekempey:20160630082314p:plain

次に 3 を繋ぐ。

f:id:pekempey:20160630082431p:plain

3 はどう頑張っても無視できない。したがって 3 が最小である。

これは結局、上位 k 本を使ったグラフの二部グラフ判定をすればいい。A 問題のように dfs で塗っていく方法は難しそうなので union-find を使う。黒い u と白い u の 2 つを用意しておいて、辺(u,v) があったら(白u, 黒v)と(黒u, 白v) を繋いでおけばいい。もし u と u+n が連結していたら白u→黒→白→…→黒uみたいなループがあることになるので二部グラフではない。

gist.github.com

実はゴリ押せる系の問題、モヤッとする。