Xmas Contest 2013
SolutionsXmas Contest 2013 – Solutions

2Problem A: Random Trip
解法 1
確率が整数パーセントで与えられているので, スタート地点となる確率が 0 でない町は高々 100 個しかな
い. そのそれぞれに対し, 他の各町までの距離を (深さ優先探索などで) O(N ) 時間で求めることができる.
解法 2
確率の値の制約を用いない O(N ) 時間解法の概略を紹介する.
与えられる木の辺集合を E とし, 辺 e ∈ E を通る確率を pe , 辺 e, e′ ∈ E をともに通る確率を qe,e′ とすると, 求める期待値は∑pe +e∈E∑qe,e′e,e′ ∈E, e̸=e′であることがわかる (期待値の線形性を用いよ).

pe は, e で分けられる 2 個の部分木にスタート地点とゴール地点が 1 個ずつある確率である. 各部分木にスタート地点あるいはゴール地点がある確率を動的計画法によって求めておくことで計算できる.

e に対し,∑qe,e′ を考える. e で分けられる 2 個の部分木を T , T ′ とし, e′ としての T ′ に含まれるもe′ ∈E, e′ ̸=eのを動かすとき, qe,e′ は, T と, e′ で分けられる 2 個の部分木のうち e を含まない方にスタート地点とゴール地点が 1 個ずつある確率である. T にスタート地点 (ゴール地点) がある確率は e′ の選び方によらないので,T ′ 内の各辺 e′ に対する, e′ で分けられる 2 個の部分木のうち e を含まない方にスタート地点 (ゴール地点) がある確率の和を求めればよい. これもやはり動的計画法で, 今度は「各部分木にスタート地点あるいはゴール地点がある確率」の和を求めておけば全体で O(N ) 時間で計算できる.

Xmas Contest 2013 – Solutions

3Problem B: Rotating Coin
N = 1 の場合
一円玉を長さ 2πR1 の線分に沿って転がすと R1 回転する. よって一円玉は「円周に対して」R1 回転するが, 円周自体の向きが 1 回転しているため, 一円玉自身は R1 + 1 回転していることになる.
一般の場合同様にして, 一円玉を半径 R のコインの円周のうち割合 t だけに沿って転がした場合, 一円玉自身は t(R+1)
回転することがわかる. よって, 一円玉が各コインの円周のどれだけの割合に触れるかを求め, 回転数を合計すればよい.
一円玉より小さいコインがないことから, 一円玉はすべてのコインに接する. i 番目のコインと i + 1 番目のコインの両方に接する時点での興味ある角度は, 3 辺の長さが Ri + Ri+1 , Ri + 1, Ri+1 + 1 の三角形に余弦定理を用いて求めることができる.

Xmas Contest 2013 – Solutions

4Problem C: Really Long Sequences
長さ M , N の列の最長共通部分列を求める計算量 O(M N ) のアルゴリズムが知られているが, 本問では,I = {(i, i′ ) | ai = bi′ } とするとき O(M + N + |I| log |I|) 時間で求める方法を用いる. 問題文で書かれた数列の生成法で |I| が小さくなるかは後ほど検討するが, 値がランダムに選ばれていれば |I| が M N よりずっと小さくなるのでよさそう, とおおよそ考えられる.
各値 x に対し {i′ | bi′ = x} を記録しておけば, I は O(M + N + |I|) 時間で具体的に求めることができる.
長さ k の共通部分列は, I の k 個の元 (i1 , i′1 ), . . . , (ik , i′k ) で i1 < · · · < ik , i′1 < · · · < i′k を満たすものに対応している. さらにこれは, I の元を第 1 成分の小さい順に, 第 1 成分が等しい場合は第 2 成分が大きい順に並べたものを考えたとき, その列から第 2 成分を取り出した数列の狭義単調増加部分列に対応している.
例えば, a = (11, 22, 11, 22, 33), b = (22, 22, 33, 11, 11, 33) に対し,

I = {(1, 5), (1, 4), (2, 2), (2, 1), (3, 5), (3, 4), (4, 2), (4, 1), (5, 6)}であり, 下線で示した共通部分列は, 数列 5, 4, 2, 1, 5, 4, 2, 1, 6 の下線で示した狭義単調増加部分列に対応している.
長さ |I| の数列の最長増加部分列を O(|I| log |I|) 時間で求める方法はよく知られている (動的計画法の高速化) ので, これで数列 (ai )i と (b′i )i′ の最長共通部分列が O(M + N + |I| log |I|) 時間で求まった.
残るは |I| についての考察である. 数列 (ai )i は ai ≡ 103ai−1 + R (mod 1 000 003) のように定められている. 1 000 003 が素数であるから, α ≡ 103α + R を満たす α がとれるので, ai − R ≡ 103(ai−1 − α), よって ai − R ≡ 103i (P − α) がわかる. (103i )i は基本周期が 333 334 であることが確認できるので, P − α ̸≡ 0であれば数列 (ai )i も基本周期 333 334 をもつ. このとき数列 (ai )i は同じ値を高々 3 回しか含まないので,|I| ≤ 3N が得られる. 一方 P − α ≡ 0 のとき数列 (ai )i は定数である. 数列 (b′i )i′ に対しても同じ考察が成り立ち, (b′i )i′ が定数でなければ |I| ≤ 3M である.
以上をまとめると, 数列 (ai )i , (b′i )i′ のいずれかでも定数でないときは, |I| は O(M + N ) である. 両方の数列が定数であるときは, 最長共通部分列は容易に求まる.

Xmas Contest 2013 – Solutions

5Problem D: Rabbit Pairs
グリッドグラフの各辺が赤か黒に塗られており, 赤い辺を高々 K 本用いた完全マッチングの個数を mod p(p は素数) で求める問題を解けばよい. 平面的グラフの完全マッチングの個数を数えるアルゴリズムとして,
FKT algorithm (Fisher, Kasteleyn, Temperley) が知られている. これを二部グラフに適用した形を示す：
平面的二部グラフ G = (U ∪ V, E), U = {u1 , . . . , un }, V = {v1 , . . . , vn }, E ⊂ U × V に対し, 各辺の向き付けであって, G の任意の閉路 (二部性より長さ偶数) が各向きの辺を奇数本もつようなものが存在する. そのような向き付けに対し, 行列 A = (ai,j )1≤i,j≤n を
+1 (ui vj ∈ E, ui から vj への向き)
ai,j = −1 (ui vj ∈ E, vj から ui への向き)0(ui vj ∈/ E)で定めると, G の完全マッチングの個数は det A の絶対値に等しい.
これは, {1, . . . , n} の置換 σ に対しn∏()ai,σ(i) ̸= 0 であることが完全マッチング ui vσ(i) i に対応すること, どi=1の完全マッチングに対してもその符号が一致することが向き付けの条件から従うことを考えると示される.
本問のグリッドグラフの場合には適切な向き付けを直接得られる. また, 完全マッチング (ui vi )i が存在しui から vi への向きであるように頂点の番号付け・辺の向き付けを行うことで, det A ≥ 0 とすることができる. 例えば, N が偶数であるとして以下に示すようにすればよい.

u1v1u2v2

u3v3v6u6v5

u5v4

u4

u7v7u8v8

u9v9v12 u12 v11 u11 v10 u10u13 v13 u14 v14 u15 v15
この方法を応用する. 赤い辺 ui vj に対し, ai,j を ±1 の代わりに ±X と定めた行列 A(X) を考える. 赤い辺()を k 本含む完全マッチング ui , vσ(i) i に対しn∏ai,σ(i) = X k となるから, 赤い辺をちょうど k 本含む完全i=1k

マッチングの個数は det A(X) の X の係数である. det A(X) を効率よく計算するためには, これが高々 n 次の多項式であることを用い, X = 0, 1, . . . , n を代入したときの値を (体 Fp 上の計算で) 求め, 連立方程式を解いて (あるいは補間法を用いて) 多項式を復元すればよい. 時間計算量は O(n4 ) となる (本問では n =MN).
2

参考
グリッドグラフは bandwidth が小さいので, 行列の疎性を用いて行列式計算の計算量を落とせる.
また, n + 1 通りの値を代入する必要があるため, n + 1 > p の場合を解くためには, 標数 p の有限体で十分大きいものをとって計算することになる.

Xmas Contest 2013 – Solutions

6Problem E: Range Composition
解法 1

segment tree を用いると, O(N ) 時間 O(N ) メモリの前計算により, a, b が与えられたとき合成関数
Fb ◦ Fb−1 ◦ · · · ◦ Fa+1 ◦ Fa を O(log N ) 時間で計算できる.
具体的には, 区間 [1, 1], [2, 2], [3, 3], . . . ; [1, 2], [3, 4], [5, 6], . . . ; [1, 4], [5, 8], [9, 12], . . . ; . . . 内の関数を合成したものを保持しておけばよい. 任意の区間はこれらの O(log N ) 個に分割される.
解法 2

segment tree は区間 [1, N ] を 2 分割していくことで管理したが, 次の条件を満たすように 3 分割以上も許した構造を factorization forest は呼ばれる：区間 I を I1 , . . . , Ik に分割できる条件は,• k=2• I1 , . . . , Ik 内の関数を合成したものはいずれも等しい関数 e となり, さらに e ◦ e = e を満たすのいずれかである.

N によらない定数高さの factorization forest を構成できることが知られており, クエリごとに O(1) 時間で答えることができる (ただし, 定数倍は大きい).
解法 3下の図は関数適用の様子を矢印で表している.

RABBIT

111111122222223333333

これらのうちいくつかを取り出して, 交わらないパスの和集合として管理することを考える.

R1⃝12⃝23⃝3A2⃝123B12⃝23⃝3BI1123⃝323⃝3T12⃝21332

これらは次のように構成されている：r = 1, 2, 3 に対し, 次を行う. 左端で値 r を選んでから順に関数を適用していきパスを辿る. ただし途中で今まで訪れた点に到達する場合はパスを切り (図中破線), その関数の値域に含まれない値を選び新たなパスを開始する. これらのパスにはラベル r をつける.
すると, どの場所から矢印を辿っても, 破線は高々 2 本しか通らない. これは通るパスのラベルが減少するためである. よって, 各パスに対してその終点の位置, および, 場所とラベルからパスへのポインタを管理することで, 前処理にかかる計算量は O(N ) で, 矢印を辿る操作を O(1) 時間で実現できる (演算回数は非常に少な
いが, segment tree 解よりメモリアクセスは悪くなってしまう).

Xmas Contest 2013 – Solutions

7Problem F: Replacing Batteries
N = 1 の場合
d(1 − a−t ) = a−t log a であるから, 型が a の電dt
池と型が b の電池を同時に使い始め, 型 a の電池が先に切れる確率は,型が a の電池が切れるまでの時間の確率密度関数は t 7→

∫ ∞(a−t log a)b−t =0log alog a=log ablog a + log bである.
一般の場合
電池が切れるまでの時間の分布は指数分布であるが, 指数分布のもつ重要な性質として「無記憶性」がある.
すなわち, 電池が切れていない任意の時点において, その後電池が切れるまでの時間は, これまでその電池をどれだけの時間使ったかに依存しない. このことは, 既に t0 時間使った型が c の電池がこれから t 時間以上持つ

c−(t0 +t)= c−t となることからわかる.
c−t0
よって, 「2 匹がそれぞれ今何番目の電池を使っているか」のみを状態として保持すれば, その後の情報につ確率がいて得るために十分であることがわかる. 以下の計算量 O(M N ) の単純なアルゴリズムによって答えを求めることができる.

for i := 1 to M + 1:
for j := 1 to N + 1:
pi,j := 0.
p1,1 := 1.
for i := 1 to M :for j := 1 to N :log Aipi,j .
log Ai + log Bjlog Bjpi,j+1 := pi,j+1 +pi,j .
log Ai + log Bjn∑
returnpM +1,j .
pi+1,j := pi+1,j +j=1

参考1である (積分で求まる). これと無記憶性を用いると, 型
log cが a の電池と型が b の電池を同時に使い始め, 型 a の電池が先に切れる確率を次のようにも求められる：型が型が c の電池が切れるまでの時間の期待値は

a の電池と型が b の電池をそれぞれ切れる度に新しいものに交換して連続して使っていると考えると, 単位時
log aである.
間ごとにそれぞれ log a 回, log b 回切れるので, 次に型が a の電池が切れる確率はlog a + log b

Xmas Contest 2013 – Solutions

8Problem G: Rumor with Primes
まず (−1)f (1) , (−1)f (2) , . . . を求めてから, g(n) を順次計算しながら入力中の N の値を小さい順にみてg(N ) (の符号) を答えていくことを考える. 素因数を効率的に調べるために, Eratosthenes の篩が有効である.
始め x1 = x2 = · · · = +1 とし, 各素数 p ごとに, p の倍数である n について, (n > p なら n が素数でないことを記録し) n が p で奇数回割り切れるとき xn := −xn としていく. この方法の時間計算量は, n ≤ N の範囲を調べるとき O(N log log N ) である.
空間計算量が O(N ) であることに注意を要する. 1 つの省メモリ法は, 各 n に対してちょうど 2 ビットのみを使うように実装することである (例えば C++ の bitset). もう 1 つの方法として, 始めに√N 以下の素因数√をすべて求めたうえで (O( N log log N ) 時間), 区間 [1, N ] をいくつかに分割しそれぞれで区間篩のアルゴリ(√ )N NN個に分割した場合, 時間計算量は O N log log N +,ズムを適用する方法がある. 長さ L の区間
LL log N
空間計算量は O(L) となる. 例えば L = 10 000 000 を選べば十分である.
参考(−1)f (n) は Liouville 関数と呼ばれている. g(n) > 0 となる n は, n = 1 の次に小さいものは n =906 150 257 である.
g(n) = 0 となる n は 1 ≤ n ≤ 1 000 000 000 の範囲では実際には非常に少なく (252 個), それらは知られている*1 . その値を利用し, N に対して g(n) = 0 となる n が N 以下に偶数個あるか奇数個あるかで g(n) の符号を決定する解法も考えられる.

*1 http://oeis.org/A028488/b028488.txt

Xmas Contest 2013 – Solutions

9

Problem H: Read the Input
解法 1
知られている英語の各文字の出現頻度, あるいはさらに隣接 2 文字の出現頻度を用い, S の長さ 30–60 程度の部分文字列に得点づけを行い上位を出力することで, 問題文になっている箇所を発見できる. 得点づけは, 単に出現に対して頻度の和をとるだけでも良い精度となる.
解法 2
問題文に出現しそうな単語を考えて, 検索を行う. 例えば問題文に整数 N は数列 (Ri ) の長さを表す. 数列の各要素 Ri (1 ≤ i ≤ N ) は整数である.
とあるが, 単語 “integer”, “sequence”, “element” が実際に問題文中に現れるテストケースがある. 各入力
ファイル内で問題の形式はほぼ同じである (ことが予想できる) ので, 検索すべき単語を徐々に増やしていくことができる.
ただし, H2.in の 18 個目のテストケースで若干工夫・ひらめきを要する. 他のケースから類推して, 文字列“est” を検索して発見した, といった解法が見られた (ある 3 文字が S 中に現れる回数の期待値は 1 より小さい点に注目せよ).