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

Codeforces Round #177 (Div. 1)

codeforces.com

 

受験終わって初回virtual。3完。辛い。

 

A. k種類の小文字アルファベットから成るちょうど長さnの文字列であって、隣り合う文字が全て異なるものの内、辞書順最小のものは何か。

流石にaから始まるのが辞書順最小で、次は隣り合う文字は異なってないといけないからbで、次はaでと考えると、ababab...となる。後は末尾にk-2種類の文字、それも辞書順最小なので当然'c' ~ 'c'+k-3を登場させると良いけど、ちょっと実装がだるい。k=1とかに気をつける

 

B. σはS={1,..., n}のS→Sな写像であって、「∀t(1 <= t <= k)について∃x(x∈N)が存在して、σ^x(t)=1」∧「∀t(k < t <= n)についてσ^x(t)=1を満たすxが存在しない」を満たす。σは何通りあるか。

こういった写像はdirected pseudoforestと対応するので、自明に1個のdirected pseudotreeと、{k+1, .. , n}→{k+1, .., n]の任意の写像1つの数え上げ。後者は自明に(n-k)^(n-k)。いちおうdirected pseudotreeと書いたけど、実はこの場合は有向辺と無向辺が一対一に対応して数え上げられるので、pseudotreeでいいはず。なんかpseudotreeといえば、閉路の各頂点に、0個以上の木がくっついてる形をしているわけだけれども、道しかくっついていないという嘘想定を何故かしてしまって死んだ。この良く分からん勘違い、春合宿でもやってしまったけどマジで意味が分からん。

結局やることとしては、σ^x(1)=1となるxが存在するわけだから、pseudotreeの閉路上に頂点1は存在する。後は、どうにでも出来ると思うけど、例えば閉路がt個の頂点から構成されるとすると、閉路上にある頂点は残りt-1個に関しては自由なので(n-1)C(t-1)通り。そしてt-1個の並びは自由なので(t-1)!通り。

後は木をこの閉路につけるわけだけど、ここで、一般に、無向グラフにおいて、十分に大きいnについて、n個の互いに非連結な成分C1 ~ Cnをn-1本の辺で連結にする時、異なる連結のさせ方は(π[i=1..n]Ci) × {(Σ[1..n] |Ci|)^(n-2)}通りある。これは∀iで|Ci|=1のとき、cayleyの公式と一致する。

以上から答えは、(n-k)^(n-k) × [Σ[t=1..k-1]{(t-1)! × (k-1)C(t-1) × t × k^(t-k-1)} + (k-1)!] となる(t == kのとき、t-k-1 = -1なことに注意する)。

 

C. 0~nの順列P0~Pnについて美しさを Σ[i=0..n] (i⊕Pi)で定義する(⊕はXOR)。可能な美しさの最大値と最大値を与える順列1つを出力せよ。

等式 A⊕B = A+B - ((A&B) << 1)を用いると(ここで&はAND)、Σ[i=0..n] (i⊕Pi) ≦ Σ(i+Pi) = n(n+1)であって、上界がn(n+1)であることが分かる。

貪欲に順列を構成すると、上界を達成することが出来ることを示す。

まず

  • 2進数でnがk桁で表されるとすると、k桁で表される全ての整数tについて、t⊕x = 2^k-1となるようなxがただ1つ存在する。これはt&x = 0となるようなxがk-1桁以下で表される整数にただ1つ存在することによる。
  • t1⊕x1 = 2^k-1, t2⊕x2 = 2^k-1の時、t1≠t2 ⇒ x1≠x2である
  • 上記の条件でt⊕x = 2^k-1となる時、A&B = 0 ⇔ A+B = A⊕Bを考えるとt+x = t⊕x = 2^k-1である。

ここで、n以下でかつk桁で表される全ての整数の集合、すなわち、”離散な"閉区間(面倒くさいのでこう呼ぶ)S = [2^(k-1), n]に対して、T = {x | t∈S, t⊕x = 2^k-1}とすれば、t+x = t⊕xより、Tは離散な閉区間[2^k-1-n, 2^(k-1)-1]であり、S∩T=∅かつS∪T = [2^k-n-1,  n]であるから、これらを全て消費すると、離散な閉区間[0, 2^k-n-2]が残るので、残った離散な閉区間に対して、同じ問題を再帰的に解いていくと良い。

こうして構成された順列は、全ての項について、i⊕Pi = i+Piが成り立っているので、上の考察からこれは上界を与えている。

なんか実装力が衰えすぎていたのと、この考察中々にややこしいのでめちゃくちゃなバグが発生しまくった。反省。

 

自分向けメモ: 貪欲の下界上界を先に意識するパターン忘れない。一回やったら流石にcombinatoricsは解けて...