Codeforces #403(Div. 2) E: Underground Lab

解法

k人のクローンがいてそれぞれceil(2n/k)個の頂点を訪れることができるので、訪れることができる頂点の数の合計Sは

S = ceil(2n/k)*k >= 2n

与えられたグラフは連結グラフなので全域木が存在する。与えられたグラフのある全域木Tについて考える。

TでDFSした時、頂点を見る順番は

頂点v(初めて訪れた)=>頂点vの子w=>...=>頂点v(wから戻ってきた)

のようになる。

このとき、順番が隣り合う場合は必ず２頂点はある辺で結ばれていることがわかる。よって、DFSの探索順で頂点を訪れればすべての頂点を訪れることができる。この頂点の探索順を配列Aで表すとする。

|A|<=S

であれば、Aの順に頂点を訪れていけばよい。

全域木の辺の数は

n-1であり、各辺は2回ずつ訪れてその度に訪れた頂点の数は増えていく。また最初の1頂点(根)も考慮すれば

|A| = 2(n-1)+1=2n-1

であり|A|<S

思いつき方

連結グラフ→全域木

k人が訪れることのできる頂点数の合計は?→2n

Codeforces #403 (Div. 2) C: Andryusha and Colored Balloons

解法

木の問題は、根付き木にすると見通しが立てやすくなることが多い。

根から再帰的に色を塗っていく。

ある頂点vの色をcur_col, 親の色をpar_colとする。また、部分木vのうち色が決まっているのはvだけとする。子の色を決めたい。問題文中の色を塗る条件をわかりやすく言い換えると、距離2以内の頂点の色は異なるということになる。あるvの子c[i]の色に対して、距離2以内に来る頂点ですでに色が決まっている、または一緒に色を決めなければならない頂点は以下の通り。

(1) 頂点v(cur_col)

(2) 頂点vの親(par_col)

(3) 別のvの子c[j] (i!=j)

つまり、下の図のように塗れば良い。

根の処理だけ特殊になるが、根を実際には存在しない頂点0の子とし、頂点0の色を実際には存在しない色0で塗っておけば、頂点0の子として色を塗れる。

思いつき方

根付き木にして描いてみる。

Codeforces #403 (Div. 2) D: Innokenty and a Football League

解法

各チームについてshort nameの付け方は2通りある。

また、それぞれのチームのshort nameの関係は、いくつかの包含関係で表せる。

2値変数Aが真であることをa、偽であることを¬aのように表すと

(x[1]=>x[2])∧(x[2]=>x[3])∧(x[3]=>x[1])∧(¬x[3]=>x[2])∧(¬x[1]=>¬x[2])∧(¬x[2]=>¬x[1])

のような複数の包含関係を「かつ」でつないだような論理式全体を真にするような各変数の値の割り当てはImplication graphの強連結成分分解で知ることができる。Implication graphはa=>bのような包含関係をそのまま有向辺として持つグラフのこと。各強連結成分の真偽値が等しくなるような2値の割り当てが解になる。ただし、aと¬aの連結成分が等しい場合、aと¬aの値が等しいことになり明らかに矛盾。この時は解なし。また、対偶関係も辺として加えられるので注意。

これを実際の問題に当てはめてみよう。

(1)異なるチームS,TについてSの名付け方sとTの名付け方¬tが等しい場合

チーム名の重複は許されないから

s=>t

かつ

¬t=>¬s

この2条件は対偶関係になっている。

(2)名付け方sと名付け方tが等しい場合

つまり、問題文で与えられているように

Sの名付け方が(DIN, DIB), Tの名付け方が(DIN, HOGE)

のような場合

SをDIBと名付けた場合はTはDINとは名付けられないのであった。

よって

¬s=>¬t

同様に

¬t=>¬s

これらに対偶関係を加えてまとめると

¬s<=>¬t

かつ

s<=>t

思いつき方

知識

SRM 708 DIV1 Medium: PalindromicSubseq

X[i]の値を具体的に求めていこう。

各文字S[i]についてそれぞれX[i]を求める。S[i]がある回文に含まれる場合、S[i]と一致するようなもじS[j]がある。ただし、i=jでS[i=j]が奇数長回文の中心である場合も含む。iとjを総当りで固定した場合、それだけでO(N^2)もかかる。しかし、i,jを固定した場合、事前に計算をしていれば各(i,j)についてO(1)でS[i],S[j]を含むような回文を数えられる。

f[l][r]:=S[l,r)を使った空の文字列も含む回分の個数

g[l][r]

:= Sから得られる回分のうち、偶数長でかつ対になる文字がそれぞれg[0,l)とg(r,n]から得られるものの個数

とする。

l=min(i,j), r=max(i,j)+1とすれば半開区間が得られ、

[l,r)の内側だけでペアになっている回文と、両端だけでペアになっている回文を作れればよく、これは

f[l+1][r-1]*g[l][r]

で求まる。

和をとればX[i]が求まり、Y[i]も求まる。

g[l][r]の求め方は

SRM 708 DIV2 Hard: PalindromicSubseq2 - parukiのブログ

と同様。

f[l][r]はもっと簡単で

f[l][r] = f[l+1][r]+f[l][r-1]-f[l+1][r-1] + (s[l]==s[r-1]ならばf[l+1][r-1]、そうでなければ0)

Codeforces #402 (Div. 1) B: Bitwise Formula

解法

AND, OR, XORのいずれもビットごとに独立に計算されることに注目する。ボブの選ぶm桁の数値(仮にxとする)は、各桁独立に求められる。各桁は0か1の2通り。それぞれ試して各変数のm桁目を求めて和をとり、最小値、最大値に対してそれぞれ適切なほうを選ぶ。

時間: O(nm)

ミス

誤読。ボブの選んだ数値まで和に含めてしまっていた。入力例まで読めば間違えなかったはず。

SRM 709 DIV1 Medium: Softmatch

http://codeforces.com/blog/entry/49911?#comment-344869

↑の理解

|patterns|<=5なのでこれの最大ケース|patterns|=5の場合だけ考えてみよう。以下のような愚直なDPはすぐに思いつく。

dp[i][p[0]][p[1]][p[2]][p[3]][p[4]]

:= Sのi番目まで確定していて、pattenrs[j]についてはp[j]文字まで一致している。このときの単語の出現個数の最大値。

しかし、これでは間に合わないから、DPテーブルの次元を減らしたい。

p[0]>=p[1]の場合を考えてみよう。ただし、p[1]の値は具体的にはわかっていないとする。

p[0]の値によって、Sの確定部分のうち直前p[0]文字は求まる。このSの直前p[0]文字、S[i-p[0],i)によって、p[1]の値を具体的に求めることができる。つまり、pattenrs[1]のprefixとS[i-p[0],i)のsuffixが最大何文字一致しているかがわかる。同様に

p[0]>=p[j], (j!=0)ならば p[j]の値をすべて求めることができる。

p[0]が最大とは限らないが、あるp[x]が最大でありその値がわかっているならば他のp[j](j!=x)は求めることができる。よって、先のDPは以下のように変換できる。

dp[i][j][k]

:= Sのi番目まで確定していて、patterns[j]が一致文字数が最も多く、その文字数はkである。このときの単語の出現個数の最大値。

これを解けば良い。

思いつき方？

とりあえず愚直なDPを考えてみる。そのDPの次元のとり方に無駄がありそうなら、次元を減らそうと試みる。p[i]は何に畳み込めるか。逆に考えるとわかりやすい？p[i]をすべて求めるのに必要最小限の情報は何か。

SRM 709 DIV1 Easy: Xscoregame

|A|<=15で順列で最小とあり、ビットDPっぽい。しかし、

X+(X^Y) の後半xorパートが怪しい。

の値が大きければ良いというわけでもない。

そこでA[i]<=50に注目する。A[i]<=50<64=2^6である。つまりA[i]の下位6ビット以外はすべて0。それに対してXの値は当然1であったほうが良い。つまり、下位6ビット以外に関しては、大きければ大きい方がいい。よって普通にXの最大値がわかれば十分。他方、下位6ビットに関してはYとのxorで影響を受けるので、ありうるすべての値について最大値を計算する。したがって以下のようなDPを計算する。

dp[used][lower_bits]

:= Aのうち使用したものがused、下位6ビットがlower_bitsであるときのXの最大値

WA

dp[used]:=Xの最大値

をやらかした。

証明しようと試みなかったし、直感的に正しいわけでもないのに、あまり考えずに提出してしまった。

これがExamplesで落ちないのは厳しい。

思いつき方

ビットDPっぽい。

A[i]<=50

=> 下位6ビットを見る