Xmas Contest 2012Solutions

Xmas Contest 2012 – Solutions

練習ラウンドProblem X: Say Yes
問題概要
テストケースの個数だけ YES と出力する.
解答例 (bash)

read tyes YES | head -n $t

Problem Y: Factorization
問題概要
与えられた 2 以上 1018 以下の整数を素因数分解する.
解答例 (bash)

read tfor i in ‘seq 1 $t‘; doread nfactor $n | sed -e ’s/.*: //’done

2

Xmas Contest 2012 – Solutions

3

Problem A: Abundant Dice
手作業による解法

A1.in ではテストケースが 10 個のみであるから, 実際にさいころを組み立ててしまう (あるいはそれを想像する) ことで解くことは難しくない.
解法 1
さいころを回転させた状態は 24 通りである. 始めにそれらの展開図のすべて生成し, 各入力と比較すればよい.
ある状態から始めて 24 通りを生成する方法として, 例えば次が知られている. さいころは xyz 平面で座標軸の向きに置かれているとする.

for i := 1 to 6:
for j := 1 to 4:
さいころの状態を出力する.

z 軸を回転軸として 90◦ 回転させる.
if i が奇数 then:
x 軸を回転軸として 90◦ 回転させる.
else:
y 軸を回転軸として 90◦ 回転させる.

解法 2
まず向かい合う面の和が 7 であるかを確認する. すると作りたいさいころかそれと鏡面対称のものに限られることがわかるので, これを利用して判定する.
例えば, ある頂点に集まる 3 面 (A, B, C) が正しい順に並んでいるかを調べればよい. 正しい順は 24 通りあるが, これらを手作業で列挙することは比較的容易である.
作りたいものであるか鏡面対称のものであるかは, 向かい合う面の目を交換することで入れ替わる. これを利用し, {A, B, C} = {1, 2, 3} の場合に帰着させることで実装を簡潔にすることもできる.

Xmas Contest 2012 – Solutions

4Problem B: Branched DNA
塩基, DNA 鎖を単に文字, 文字列と呼び, 文字 x と貼り合わせられる文字を x′ と書く. A と B を貼り合わせられる最大の長さを K とする (K < L, K < M ). 条件を満たす C は, A と B を k 文字 (1 ≤ k ≤ K) 貼り′′′′′′′ ′合わせたもの C (k) = BM
BM−1 · · · Bk+2 Bk+1 AL−k AL−k−1 · · · A2 A1 で, K 通り考えられる. 以下 K > 0 とする.
解法 1
上記の K 通りを実際に作り, 単純な比較により辞書順最小の文字列を求める. 時間計算量は O(K(L + M ))となり, 実行に長い時間をかければ解くことができる.
解法 2
前計算を行うことで, C (k) の部分文字列の rolling hash は O(1) 時間で求めることができる. 2 個の C (k) に対し, ハッシュが衝突しないと仮定すれば, 最初に異なる文字を二分探索で O(log(L + M )) 時間で求めることができる (長さを決めたとき接頭辞のハッシュ値を比較すればよい). よって比較が O(log(L + M )) 時間で行えるので, 全体で O(K log(L + M )) 時間となる.
解法 3

C (K) , C (K−1) , . . . , C (k+1) , C (k) のうち辞書順最小のものを C ∗(k) とし, C ∗(K) , C ∗(K−1) , . . . , C ∗(2) , C ∗(1)を順次求めることとする (すなわち, 長さが短い順に比較していく).

C (k+1) と C (k) の先頭 M − k 文字は等しいため, C ∗(k+1) と C (k) の先頭 x 文字が等しいならば C ∗(k+1) とC (k) の先頭 min{x, M − k} 文字も等しい, という事実を利用し, 以下のアルゴリズムを考えられる.
C ∗(K) := C (K) .
x := 1.
for k := K − 1 downto 1:
loop:
if x > M − k then:∗(k+1)(k)
if Cx∗(k+1) Cx+1 · · · < Cx(k) Cx+1 · · · then: C ∗(k) = C ∗(k+1) . else: C ∗(k) = C (k) .
break.
else if Cx∗(k+1) ̸= Cx(k) then:if Cx∗(k+1) < Cx(k) then: C ∗(k) = C ∗(k+1) . else: C ∗(k) = C (k) .
break.
else:
x := x + 1.
x は「何文字目まで比較したか」を表すパラメータである. x > M − k となったとき x 文字目以降の文字列をまとめて比較しているが, それらはともに A′L−k A′L−k−1 · · · A′2 A′1 の接尾辞であるため, 事前に suﬃx arrayを構築しておく (O(L(log L)2 ) 時間で十分, O(L) 時間も可能である) ことで O(1) 時間で処理できる. x は減少せず M 以下であるため, 時間計算量は O(K + M ) となっている.

Xmas Contest 2012 – Solutions

5Problem C: Colorful Lights
特殊な制約があるグラフの頂点彩色数とその彩色数で頂点を塗り分ける方法を数え上げる問題である. この問題は一般のグラフでは NP 困難である.
指数時間解法グ ラ フ の 頂 点 の 部 分 集 合 S と 整 数 k に 対 し, S を k 色 で 塗 り 分 け る 方 法 が「1 通 り 以 上 あ る か 」「mod 20 122 224 で何通りか」を動的計画法で求めることができる. ある 1 色で塗ることができる頂点集合は独立集合であり, それらは O(2N N 2 ) 時間で最初に列挙することができる.
時間計算量は, 単純な方法では O(4N N ) となり, 部分集合を効率的に列挙する方法により O(3N N ) に高速化することが可能である.
多項式時間解法
この問題のグラフに対する制約は, cograph であることと同値である. cograph には同値な定義が数多くあるが, 詳細は割愛する*1 .

cograph の重要な性質として, 2 頂点以上の任意の誘導部分グラフに対し, それまたはその補グラフが非連結である, というものがある. このことを利用し, 頂点集合 S で誘導される部分グラフの彩色数 f (S) と, 各 kに対しちょうど k 色で塗り分ける方法 g(S, k) を, 以下のように再帰的に求めることができる.

• |S| = 1 のとき
f (S) = 1 であり, g(S, 1) = 1, g(S, k) = 0 (k ̸= 1) である.
• |S| = 2 のとき– S が連結のとき (S の補グラフは非連結となる)
S の補グラフの連結成分の 1 つを T とし, T ′ = S \ T とすると,
f (S) = f (T ) + f (T ′ ),g(S, k) =k ( )∑kg(T, i)g(T ′ , k − i)ii=0である.

– S が非連結のときS の連結成分の 1 つを T とし, T ′ = S \ T とすると,
f (S) = max{f (T ), f (T ′ )},g(S, k) =( )(kk∑∑ki=0 j=k−iである.
この方法の時間計算量は O(N 4 ) である.

*1 例えば http://hos.ac/slides/20110504_graph.pdf を参照.

i)ig(T, i)g(T ′ , j)i+j−k

Xmas Contest 2012 – Solutions

6Problem D: Drastic Sokoban
片づけが不可能な非自明な例としては, 以下のような場合が典型的である.

兎荷

片づけが可能かどうかは, 以下の手順で判定できる.

1. 片づけ先のマスの集合を G とする. すべての荷物が既に G にあれば, 片づけは可能.
2. 荷物をすべて取り除いたとき, うさぎが到達できるマスの集合 S を求める. S にも G にも属さないマスに荷物があれば, 片づけは不可能.

3. 以下のいずれかを満たすならば片づけは可能, そうでなければ不可能.
i) |G| = B であり, ある隣接する 2 マス x ∈ S \ G, y ∈ S \ G が存在.
ii) |G| = B + 1 であり, ある隣接する 2 マス x ∈ S \ G, y ∈ S が存在.
iii) |G| ≥ B + 2 であり, ある隣接する 2 マス x ∈ S, y ∈ S が存在.
1. と 2. の場合の正当性は明らかであるから, 3. の場合の正当性を示す. まず |G| = B のときを考える.
片づけが可能であると仮定する. 1. の場合を除外したので, 片づけが終了する直前の状態を考えることができる. このときにうさぎがいるマスも最後に動かされる荷物があるマスも S \ G に属すため, 隣接する 2 マスx ∈ S \ G, y ∈ S \ G が確かに存在する.
逆に, ある隣接する 2 マス x ∈ S \ G, y ∈ S \ G が存在すると仮定する. 片づけが可能であることを, B に関して帰納的に示す. まず, うさぎは箱を適切に動かすことで S の任意のマスに移動できることに注意する.
すべてのマスの個数が |G| + 2 = B + 2 以上なので, 移動したいマスに荷物があっても動かせるからである.

S = {x, y} の場合, それらはうさぎがいるマスと荷物があるマスであり, |G| = B = 1 より片づけ先のマスが存在し, それは x, y でないから荷物を動かして片づけは完了する. そうでない場合, z ∈ S \ {x, y} であって,z を固定家具のマスに変えたとしても, 荷物をすべて取り除いたとき, うさぎが S \ {z} の任意のマスに到達できるようなものを 1 つとる (例えば, 頂点が S のマス, 辺が隣接関係を表す連結グラフの全域木を考え, x, y でない葉をとればよい). うさぎは以下の手順を行う.

• z ∈ G かつ z に荷物がないとき, ある荷物に隣接するまで移動し, その箱を z に動かす.
• z∈/ G かつ z に荷物があるとき, z まで荷物を動かしながら移動したのち, z に隣接するマスに移動する.
• その他の場合, 何もしない.
すると「z ∈ G かつ z に荷物がある」「z ∈/ G かつ z に荷物がない」のいずれかの状態になり, 片づけは完了す
るか, z を固定家具のマスと考えることで, 荷物 B − 1 個で片づけが可能な場合に帰着される.
以上より |G| = B の場合の正当性は確認された. |G| > B の場合, G のうち実際の片づけ先として使う Bマス以外を G から除いて考えられるので, それぞれの必要十分条件が従う.

Xmas Contest 2012 – Solutions

7Problem E: Experience Point
経験値 Ci 点とボーナス Di 点を得られる道の扱いを,• 経験値 Ci 点を得て, ボーナスは無視する• 経験値 Ci + Di 点を得るが, ゴールするまでに休憩地点を通らなければならないのいずれか, として言い換えることができる. すると, チェックポイントと「ゴールするまでに休憩地点を通らなければならないかどうか」の組を頂点としたグラフを考えることができ, このグラフ上での最長経路を求めればよいことになる. グラフにサイクルがあり, そこで経験値をいくらでも多く得ることができる場合があり,そのときは 999 999 999 を出力することになる.
閉路がない場合すべての辺が頂点番号が増える向きである場合, 頂点番号の順に, その頂点まで到達した状態で得られる経験値の最大値を動的計画法で順次計算することができる. 時間計算量は O(N + M ) となる.

O(N M ) 時間解法
Bellman-Ford 法により, 正閉路検出および正閉路が存在しない場合の最長経路を求めることができる.
O(N + M ) 時間解法
グラフを強連結成分に分解することで, 閉路がない場合に帰着できる. ある強連結成分内に得られる経験値が正の辺が 1 本でも含まれる場合, その強連結成分を通った場合は経験値をいくらでも多く得られる, として扱うことができる.
注意点
閉路があっても, 経験値が全く得られないもの, あるいはスタートから到達できない・ゴールに到達できないものがあり得ることに注意を要する.
また, 経験値をいくらでも多く得ることができない場合でも, 経験値を 999 999 999 を超えて得られる場合がある ((30 000 − 1) × (30 000 + 30 000)).

Xmas Contest 2012 – Solutions

8Problem F: Frill Wreath2√()2 ()2
P1E1 · · · PNENXY 上の格子点 (x, y) の個数を求める問題である. こ円周 x −+ y−=MMM
EN
れは x′2 + y ′2 = P1E1 · · · PN, (x′ , y ′ ) ≡ (X, Y ) (mod M ) を満たす整数の組 (x′ , y ′ ) の個数と等しく, さらに√√√z = x′ + y ′ −1 とおけば条件は zz = P1E1 · · · PNEN , z ≡ X + Y −1 (mod M ), z ∈ Z[ −1] と同値である.
√√
環 Z[ −1] は UFD (一意分解整域) であり, Z の素数 p は以下のように Z[ −1] で素元分解される：√√• p = 2 のとき, 2 = − −1(1 + −1)2 .

√• p ≡ 1 (mod 4) のとき, ある素元 π ∈ Z[ −1] に対し p = ππ.
√• p ≡ 3 (mod 4) のとき, p ∈ Z[ −1] は素元.
()()
∏ f∏ gE1ENjeipi(pi ≡ 1, qj ≡ 3 (mod 4)), pi = πi πi とよって, Z での素因数分解を P1 · · · PN = 2qjijEN
E1
すると, zz = P1 · · · PN を満たす z はすべての gj が偶数のときに限り存在し,z = u(1 +√(−1)e∏πifi −xi πi xiiと表される 4)()∏ g /2√jqj(u ∈ {±1, ± −1}, 0 ≤ xi ≤ fi )j∏
(fi + 1) 個である.
ik, a, b に対し,∏√πifi −xi πi xi ≡ a + b −1 (mod M ) となる x1 , . . . , xk の選び方が何通りあるか, を求1≤i≤kめる動的計画法によって条件を満たす z を数えることができる. 素朴な方法では, 各 i について, xi = 0, . . . , fi(f −xに対し πi i i πi xi mod M を計算する.

時間計算量は O∑

fi log fi + Mif −xi

時間を使わないためには, a, b に対し πi i2∑)fiとなる. fi に比例するi√πi xi ≡ a + b −1 (mod M ) なる xi が何個あるかの分布を求める. これで動的計画法の部分の計算量は O(M 4 ) となる.
解法 1()πiπi 2=より pi が M と互いに素ならば mod M でも等比数列
πipi0≤xi ≤fiでありよって周期的であることに注目する. pi が M と互いに素でない場合でもこれらはおおよそ周期的であ)(πifi −xi πi xiは等比数列であり,f −xiは周期的である (πil πi l = pli でl≤xi ≤fi −lf −xの商を考えよ). よって xi ≤ l + M 2 までを調べれば周期が見つかり, πi i i πi xi mod M の分布がわかる. 各i に対し O(M 2 log fi ) 時間となる. なお本問の制約では M < 53 より l ≤ 2 である.
り, 正確には, M が pi でちょうど l 回割り切れるとき, πi iπi x i

解法 2πifi −xi πi xi mod M の分布を fi に対して再帰的に求める. fi > 0 とする. fi が偶数の場合, πifi −1−xi πi xi のfi −1分布に πi をかけたものと πi fi を考えればよい. fi が奇数の場合, πi 222けたものを考えればよい. 各 i に対し O(M (log fi ) ) 時間となる.

−xifi +1πi xi の分布に πi 2 , πifi +12をかXmas Contest 2012 – Solutions

9Problem G: Galaxy View
どの 3 点も同一直線上にない平面上の 5 点の位置関係は, 凸包が三角形, 四角形, 五角形のいずれであるかで3 通りの場合がある. 5 点が星形をなすためには, 凸包が五角形であることが必要十分であることがわかる.
凸包が三角形, 四角形, 五角形である 5 点の組合せがそれぞれ a 通り, b 通り, c 通りであるとする. これらを区別するための点の配置として,(i) 三角形とその内部の 1 点である 4 点の組合せ(ii) 三角形とその内部の 2 点である 5 点の組合せを考える. これらがそれぞれ d 通り, e 通りであるとする.

(i) の 4 点に残りの N − 4 点のうち 1 点を加えることを考えると, その 1 点が三角形の内部にある場合は凸包が三角形である 5 点, 外部にある場合は凸包が四角形である 5 点が生じる. 凸包が三角形である 5 点は (i) のような 4 点 4 通りから, 凸包が四角形である 5 点は (i) のような 4 点 2 通りから生じるから, (N − 4)d = 4a + 2b( )Nがわかる. また, (ii) は凸包が三角形である 5 点であるから, e = a である. これらと a + b + c =をあわ5( )N
1せると, c =− (N − 4)d + e として c を d, e から求めることができる.
52d, e を効率よく求める方法を考える. 3 点の組合せそれぞれに対し, それらがなす三角形の内部の点の個数が求まれば十分である. 3 点の組 (A, B, C) であって, (x 座標, y 座標) が辞書順最小のものが A であり,A, B, C はこの順に正の向きであるようなものを考えることにする. 点 D が三角形 ABC の内部にあることは, ∠BAD < ∠BAC かつ ∠ABD < ∠ABC と言い換えられる. よって, A, B を固定し, 残りの点をC として ∠BAC の小さい順に見ていくことを考えると, 各 C に対し「その時点で既に見た点 D であって∠ABD < ∠ABC を満たすもの」が数えられればよい. これは例えば binary indexed tree を用いて O(log N )時間で問い合わせることができる (A, B を決めたとき残りの点を角度でソートしておけばよい). この方法の全体の時間計算量は O(N 3 log N ) となる.

Xmas Contest 2012 – Solutions

10

Problem H: Hidden Problem
実行に時間がかかる C 言語のプログラムの出力を求める問題である.

H1.in
20121224i∑ ∑i=11 を計算するプログラムである.

j=1

代わりに,20121224∑i を計算すればよい. 元のプログラム通り, 32-bit 整数をオーバーフローさせなければな

i=1らないことに注意する.

H2.in
整数の組 (x, y) を引数として受け取る関数が, x > 0, y > 0 の場合は (x + 1, y − 2), (x − 1, y − 1),(x − 3, y + 2) に対して再帰呼び出しを行っている.
x + y の値が常に減少するためこの再帰呼び出しは必ず停止する. メモ化を行えばよい.
H3.in
整数 n (2 ≤ n ≤ 40), n 個の整数 ai,j (0 ≤ i < n, 0 ≤ j < n, 0 ≤ ai,j < 100 000) が与えられたとき, n 個の整数 zi (0 ≤ i < n) であって z0 = 1, z1 = 4, 1 ≤ zi ≤ 4 を満たすものをうまく選んだときの,S=∑ai,j (zj − zi ) の最小値を求めるプログラムである.

zi <zj

全探索で書かれたプログラムに適切な枝刈りを入れることで解くこともできるが, 入力の多項式時間で答えを求める解法を紹介する.
まず, S の最小値は zi ̸= 2 としてもとれることがわかる. これは, zi = 2 であるすべての zi を同時に 1 または 3 に変化させることで, 少なくとも一方は S の値が減少しないからである. 同様に zi ̸= 3 としてよいこともわかる. つまり S =∑ ∑3ai,j である. したがって, この問題は v0 , v1 , . . . , vn−1 を頂点とし, 頂点 vi かzi =1 zj =4

ら頂点 vj へコスト 3ai,j の辺があるグラフの最小 v0 -v1 カット問題に帰着される.