Xmas Contest 2014
Problems

Xmas Contest 2014

2Problem A: A+B Problem
Points: 100

くろうさ「足し算は甘え」
しろうさ「……え？」くろうさ「掛け算と割り算は許してあげる」
しろうさ「えっとえっと」
くろうさ「ゼロと比較して分岐してもいいよ」
しろうさ「引きｚ
くろうさ「というわけでがんばってねっ」

Input
この問題には入力ファイルは存在しない.

Output (Special Judge)
1 以上 100 以下の整数 2 個の足し算を行うプログラムを以下の仕様に従って作成し提出せよ. 後述のように, プログラムの行数が少ないほど高得点を得られる.
プログラムの動作
プログラムは, 英大文字で表される 26 個の変数 A, B, C, D, . . . , Z を扱うことができる. 各変数は 0 以上
322未満の整数を 1 個保持する. 実行開始時に, 変数 A は整数 A, 変数 B は整数 B, 変数 C, D, . . . , Z は 0 で初期化される (A, B は実行ごとに異なる値である). プログラムの終了時に変数 C の値が A + B となっていることが目標である.
プログラムはいくつかの行からなり, 上から下へ実行される. 各行は以下の 4 種類のいずれかである：• z = x * yz は変数, x と y は変数または定数である. この行が実行されると, x と y の積を 232 で割った余りを計算し, z に代入する.

• z = x / yz は変数, x と y は変数または定数である. この行が実行されると, x を y で割った商の整数部分を計算し, z に代入する. ただし, y の値が 0 である場合は実行時エラーとなる.

• if (x) {x は変数または定数である. この行が実行されると, x が 0 でないときは次の行に実行が移り, x が 0であるときは対応する閉じ中括弧に実行が移る (中括弧に囲まれている部分を飛ばす).

• }閉じ中括弧である (この行の実行は何も影響がない).

Xmas Contest 2014

3

プログラムの形式
以下の条件を満たさない提出, あるいは前述の 4 種類のいずれでもない行を含む提出は, “PARSE ERROR”として不正解と判定される.

• 文字コードは ASCII, 改行コードは LF または CR+LF でなければならない.
• プログラムは 999 行以下でなければならない.
• 変数, 定数, =, *, /, if, (, ), {, } の前後には, 0 個以上任意個の空白 (半角空白または水平タブ) を入れることができる. ただし, プログラムの各行は改行文字を除いて 80 文字以下でなければならない.

• 空行があってはならない.
• 定数は 0 以上 232 未満の整数であり, 十進表記で書かれなければならない.
• 開き中括弧と閉じ中括弧は, 適切に対応がとれていなければならない.
採点提出されたプログラムが正しい形式であるとき, プログラムは 1 ≤ A ≤ 100, 1 ≤ B ≤ 100 を満たす各整数の組 (A, B) に対して独立に実行されテストされる.
プログラムが 0 による除算を行った場合, “RUNTIME ERROR” として不正解と判定される.
ある (A, B) に対して, 実行終了時に変数 C の値が A + B でない場合, “WRONG ANSWER” として不正解と判定される.
すべての (A, B) に対して, プログラムが 0 による除算を行わずに終了し, 実行終了時に変数 C の値がA + B である場合, 正解 (“ACCEPTED”) と判定される. プログラムの行数が p である場合, 正解と判定さ⌊⌋1れたときの得点は 100 −p 点となる.
10“PARSE ERROR”, “RUNTIME ERROR”, “WRONG ANSWER”, “ACCEPTED” の判定およびエラーメッセージは, コンテストシステムで提出の詳細から確認できる.
補助

http://hos.ac/contest/xmas2014/aplusb.html にて, JavaScript による簡易インタプリタが利用可能である. ただし, このインタプリタはほとんどのエラーチェックを行わないことに注意せよ.

SampleSample Output
C = A * A
if (D) {D = 2014 * B
if (0) {C = D / 4000000000}}
これは, 形式が正しいプログラムの例である.

Xmas Contest 20144

Problem B: Bad Sort?
Points: 20 + 20 + 60

うさぎは効率の良いソートアルゴリズムを講義で習ったが, 冬休みになったので詳細を忘れてしまった. うさぎががんばって思い出したアルゴリズムは次のようなものであった. 以下に示される関数 Sort は, 入力として受け取った数列 x1 , . . . , xn を非減少列になるように並べ替えた数列を返す.

Sort(x1 , . . . , xn ):n = 0 ならば空の数列を返す.
p を 1, . . . , n からランダムに選ぶ. どの値も確率1で選ばれる.
n空の配列 A, B を用意する.

i = 1, . . . , n に対して, 順に以下を行う：
i = p のとき, 何もしない.
そうでないとき,xi < xp ならば, A の末尾に xi を加える.
そうでなければ, B の末尾に xi を加える.
Sort(A), (xp ), Sort(B) をこの順に連結して返す.
果たしてこれは効率が良いものであろうか. アルゴリズムの性能を見積もるため, うさぎは関数 Sort の呼び出しが発生する度に時間がかかると考え, 入力の長さが n のときのその時間を n 単位であると考えた. 例
えば, 数列 (2, 3, 1) をソートするために Sort(2, 3, 1), Sort(2, 1), Sort(), Sort(2), Sort(), Sort(), Sort() という呼び出しが発生したとすると, 時間は 3 + 2 + 0 + 1 + 0 + 0 + 0 = 6 かかったと考える.
入力として数列 (X1 , . . . , XN ) が与えられたとき, かかる時間の期待値を求めたい. ただし, 誤差などの問題を避けるため, 後述の出力形式に対応したプログラムを作成せよ.

Input
入力の 1 行目にはテストケースの個数 T が書かれている. その後次の形式で各テストケースが与えられる.

N
X1 · · · XN
N および X1 , . . . , XN はすべて整数である.

Outputaと表したとき, a − br が P でb割り切れるような 0 以上 P 未満の整数 r を 1 行に出力せよ. 制約によって, 出力すべき r がちょうど 1 個存
P = 10 007 とする. 各テストケースに対して, 求める期待値を既約分数で在することが証明できる.

Xmas Contest 2014

5Constraints
すべての入力において, 以下の制約が満たされる.

• 1 ≤ Xi ≤ N (1 ≤ i ≤ N ).
さらに, 各入力において, 以下の制約が満たされる.

B1.in (20 点)• T = 10.
• 1 ≤ N ≤ 10.

B2.in (20 点)• T = 20.
• 1 ≤ N ≤ 200.

B3.in (60 点)• T = 40.
• 1 ≤ N ≤ 5 000.

SampleSample Input

Sample Output

5326677

1 2801838018

2 3 18018

51 2 3 4 555 4 2 1 354 3 2 5 1

それぞれのテストケースに対して, かかる時間の期待値を既約分数で表すと,

3 17 62 62 62,,,,となる.
1 3 5 5 5

Xmas Contest 2014

6Problem C: Count Your Ways
Points: 20 + 80

うさぎの国には, 1, . . . , N の番号がついた N 個の街がある. M 本の一方通行の道があり, i 番目の道は始点が街 Ai , 終点が街 Bi である. うさぎは長旅が好きである. ある街から出発し, 道をちょうど 2 014 122 419
回使い, 出発した街へ戻ってくる旅程は何通りあるだろうか. 2 個の旅程は, 使う道の列が一致するとき同じと考える (通る街が同じでも, 異なる道を使っていれば異なる旅程と考える). 答えが非常に大きくなる予感を抱えたうさぎは, 旅程の個数を 2 014 122 419 で割った余りを求めることにした.

Input
入力の 1 行目にはテストケースの個数 T が書かれている. その後次の形式で各テストケースが与えられる.

N M
A1 B1..
.
AM BM
N , M および A1 , . . . , AM , B1 , . . . , BM はすべて整数である.

Output
各テストケースに対して, 条件を満たす旅程の個数を 2 014 122 419 で割った余りを 1 行に出力せよ.

Constraints
すべての入力において, 以下の制約が満たされる.

• 1 ≤ Ai ≤ N , 1 ≤ Bi ≤ N (1 ≤ i ≤ M ).
さらに, 各入力において, 以下の制約が満たされる.

C1.in (20 点)• T = 10.
• 1 ≤ N ≤ 100.
• 1 ≤ M ≤ 100.

C2.in (80 点)• T = 20.
• 1 ≤ N ≤ 10 000.
• 1 ≤ M ≤ 10 000.

Xmas Contest 2014

7SampleSample Input

Sample Output

502 101 202 201 201 23 31 22 33 13 61 21 32 12 33 13 25 81 22 12 12 11 33 53 5
5 1
5 番目のテストケースにおいては, 例えば, 街 1 から出発し, 5 番目, 6 番目, 8 番目の道を使い, その後 1 番目の道と 3 番目の道を交互に 1 007 061 208 回ずつ使って街 1 に戻ってくる, という旅程が条件を満たす.

Xmas Contest 2014

8Problem D: Distinguished Furry Animals
Points: 30 + 70

「うさみみの館」は, 現在建設中の謎の施設である. 館は 1 から n までの番号のついた n 個の部屋をもち,それぞれの部屋の床にはうさぎの絵が描かれている. 部屋 i のうさぎの絵の左耳の部分に乗ると, 部屋 li に描
かれたうさぎのしっぽの上にテレポートする. 同様に, 部屋 i のうさぎの絵の右耳の部分に乗ると, 部屋 ri に描かれたうさぎのしっぽの上にテレポートする.
こんな不思議な館であるが, 部屋の個数 n とテレポートの設定方法 l1 , . . . , ln , r1 , . . . , rn を具体的にどのような値にするかは未定である. ただし, n が正の整数であることと, 1 ≤ i ≤ n に対し 1 ≤ li ≤ n, 1 ≤ ri ≤ nであることは決まっている.
うさぎたちは, 館の完成記念パーティーに, ねこときつねを招くことにした. まずは館の御披露目として, ねこときつねにテレポートを体験してもらうというイベントがある. ねこときつねはそれぞれ部屋 1 からスター
トし, 耳に乗ってテレポートすることを何回か繰り返す.
実は, ねこもきつねも耳への乗り方を既に決めているらしい. 耳への乗り方は文字 L, R からなる文字列で表される. 文字列の長さはテレポートの回数を表し, i 文字目が L であれば i 回目に左耳に乗ること, i 文字目がR であれば i 回目に右耳に乗ることを表す. ねこの計画は文字列 C で, きつねの計画は文字列 F で表される.
例えば C が RRL であれば, ねこは, 部屋 1 からスタートし,1. 右耳に乗って部屋 r1 にテレポートし,2. 右耳に乗って部屋 rr1 にテレポートし,3. 左耳に乗って部屋 lrr1 にテレポートし,最終的に部屋 lrr1 に辿り着く.
さて, 面白いテレポートの設定にするため, ねこときつねが最終的に辿り着く部屋が異なるようにしたい. そのために必要な館の部屋の個数 n の最小値はどのくらいだろうか.

Input
入力の 1 行目にはテストケースの個数 T が書かれている. その後次の形式で各テストケースが与えられる.

C FC, F は文字 L, R からなる文字列である.

Output
各テストケースに対して, ねこときつねが最終的に辿り着く部屋が異なるようにできるような n の最小値を1 行に出力せよ. そのような n が存在しない場合には代わりに −1 を出力せよ.

Xmas Contest 2014

9Constraints
各入力において, 以下の制約が満たされる. |w| は文字列 w の長さを表す.

D1.in (30 点)• T = 100.
• C, F は文字 L のみからなる.
• 1 ≤ |C| ≤ 1 000, 1 ≤ |F | ≤ 1 000.

D2.in (70 点)• T = 100 000.
• 1 ≤ |C| ≤ 18, 1 ≤ |F | ≤ 18.

SampleSample Input

Sample Output

62L LL3

LL LLLL

2

LRLL LLR

3

LRRL RLRL2RLRRL LRLRR

3LRL LLLRL
6 番目のテストケースにおいて, 例えば, 部屋の個数を n = 3, テレポートの設定を l1 = 2, l2 = 3, l3 = 1,r1 = 1, r2 = 2, r3 = 3 とする. ねこは, 部屋 1 からスタートし,1. 左耳に乗って部屋 l1 = 2 にテレポートし,
2. 右耳に乗って部屋 r2 = 2 にテレポートし,3. 左耳に乗って部屋 l2 = 3 にテレポートし,最終的に部屋 3 に辿り着く. 一方きつねは, 部屋 1 からスタートし,1. 左耳に乗って部屋 l1 = 2 にテレポートし,
2. 左耳に乗って部屋 l2 = 3 にテレポートし,3. 左耳に乗って部屋 l3 = 1 にテレポートし,4. 右耳に乗って部屋 r1 = 1 にテレポートし,5. 左耳に乗って部屋 l1 = 2 にテレポートし,最終的に部屋 2 に辿り着く. このようにして, ねこときつねが最終的に辿り着く部屋が異なるようにできる.

Xmas Contest 2014

10Problem E: Economic Plan
Points: 20 + 80

うさぎの国には N 個の空港があり, 1 から N までの番号がついている. 現在, 1 ≤ a < b ≤ N を満たすすべての整数の組 (a, b) に対して, 空港 a と空港 b を双方向に結ぶ航空便がある. したがって, 全部で1N (N − 1) 便がある.
2
航空便が多すぎて手に負えないと判断したうさぎの国の政府は, この度, 維持費節約のために航空便を一部廃止することになった. まず, 利用者が極端に少ない M 便があったため, それらの廃止を決定した. M 便のうち i 番目は空港 Ai と空港 Bi を結んでいた (1 ≤ i ≤ M ). これら M 便の廃止後も, どの空港に対しても,その空港と他の空港を結ぶ航空便が N − 1 便のうち半分は残ることがわかっている.
うさぎの王様は, さらなる航空便の廃止を行いたい. 政府の事情に詳しくない王様は, 政府に対して「追加であと k 便を廃止せよ」という命令を出し, 具体的にどの k 便を廃止するかは政府に一任することにした. ここでk は0≤k≤1
N (N − 1) − M を満たす整数である.
2

王様は, どの空港からどの空港へも何本かの航空便を乗り継いで行くことができる状態を保ちたい, と考え

1
N (N − 1) − M 便のうちどの k 便を廃止するかわからない. 政府がどんな横暴に及んでも2この状態が必ず保たれるような k の最大値はどれくらいだろうか.
た. 政府は, 残る

Input
入力の 1 行目にはテストケースの個数 T が書かれている. その後次の形式で各テストケースが与えられる.

N M
A1 B1..
.
AM BMN , M および A1 , . . . , AM , B1 , . . . , BM はすべて整数である.

Output
各テストケースに対して, どの空港からどの空港へも何本かの航空便を乗り継いで行くことができる状態が必ず保たれるような k の最大値を 1 行に出力せよ. そのような k が存在しない場合には代わりに −1 を出力せよ.

Xmas Contest 2014

11Constraints
すべての入力において, 以下の制約が満たされる.

• 1 ≤ Ai < Bi ≤ N (1 ≤ i ≤ M ).
• (Ai , Bi ) ̸= (Aj , Bj ) (1 ≤ i < j ≤ M ).
• 各整数 c (1 ≤ c ≤ N ) に対し, Ai = c または Bi = c となる i (1 ≤ i ≤ M ) の個数は1(N − 1) 未満
2である.
さらに, 各入力において, 以下の制約が満たされる.

E1.in (20 点)• T = 10.
• 1 ≤ N ≤ 100.
• 1 ≤ M ≤ 100.

E2.in (80 点)• T = 20.
• 1 ≤ N ≤ 10 000.
• 1 ≤ M ≤ 10 000.

SampleSample Input

Sample Output

214 2

2

1 3
2 46 6
1 22 33 44 55 6
1 6
1 番目のテストケースにおいては, もし k = 2 としてしまうと, 例えば, 空港 1, 4 を結ぶ便と空港 2, 3 を結ぶ便を政府が追加で廃止した場合に, 空港 1 から空港 4 へ航空便を乗り継いで行くことができなくなってしまう.

Xmas Contest 2014

12Problem F: Fake Distribution
Points: 30 + 70

うさぎたちの間では, クリスマスプレゼントとして乱数列を交換するのが流行である. しかし, 実数の開区間(0, 1) に一様分布する乱数の生成器 (R と呼ばれる) は誰もが持っているので, もっと面白い分布をする乱数列をプレゼントするのが乙である.
しろうさは, s, t を R で独立に生成した 2 個の値とするとき, 値√− log s · sin(2πt)の分布が綺麗だと考えた.
くろうさは, u1 , u2 , u3 , u4 , u5 , u6 を R で独立に生成した 6 個の値とするとき, 値

u1 + u2 + u3 + u4 + u5 + u6 − 3の分布がかっこいいと考えた.
さて, しろうさの考えた分布とくろうさの考えた分布は似ているという噂が立っているらしい. テストケー
スごとに, しろうさの分布とくろうさの分布のうち一方が選ばれ, その分布に従った N 個の値 X1 , . . . , XN が与えられる. 果たしてどちらの分布が選ばれたか判定できるだろうか.

Input
入力の 1 行目にはテストケースの個数 T が書かれている. その後次の形式で各テストケースが与えられる.

N
X1 · · · XN
値の個数 N は整数である. X1 , . . . , XN は実数であり, 小数点以下 10 桁まで書かれている.

Output (Special Judge)
各テストケースに対して, X1 , . . . , XN がしろうさの分布のものからと判断した場合は文字列 White を, くろうさの分布のものからと判断した場合は文字列 Black を 1 行に出力せよ.
すべてのテストケースに対して White または Black と答えていて, かつ,しく答えた場合, 正解と判定される.

4
T 個以上のテストケースに正5Xmas Contest 201413

Constraints
すべての入力において, 以下の制約が満たされる.

• T 個のテストケースのうち,り, 残りの1T 個においては X1 , . . . , XN はしろうさの分布から生成された値であ
2

1
T 個においては X1 , . . . , XN はくろうさの分布から生成された値である.
2

さらに, 各入力において, 以下の制約が満たされる.

F1.in (30 点)• T = 20.
• N = 10 000.

F2.in (70 点)• T = 100.
• N = 2 000.

SampleSample Input

Sample Output

2White3Black0.1207533857 -0.0740957678 -0.5254538066
30.3057030458 0.7705966469 -0.0639899533

Xmas Contest 201414

Problem G: Geometry Lover
Points: 30 + 70

うさぎは幾何の問題が大好きなので, クリスマスの飾り付けで余ったゴムひもで遊んでいた.
直方体状の部屋があり, 3 本の非常によく伸びるゴムひもがある. うさぎはこれから, 各ゴムひもの一方の端を左の壁に, もう一方の端を右の壁に固定しようとしている. ゴムひもを固定する点は相異なる. ゴムひも同士は絡み合っているかもしれない. 各ゴムひもを左の壁から右の壁まで辿るとき, 常に左から右へ進む (右から左へ進む部分はない).
うさぎは, 2 通りのゴムひもの配置を考えた. これらを天井から見た様子がアスキーアート S1 , S2 として入力に与えられる. これら 2 通りは実は同一の配置かもしれない. すなわち, ゴムひもの端を固定した後, ゴムひもを伸ばしたり縮めたり絡ませたり解いたりして一方から他方を得ることができるかもしれない. たとえば,以下に示される 2 通りは同一の配置である.

-------------------------\ /\ /\ /\\\/ \/ \/ \--

----

--

=--------\ /\ /\ /\\\/ \/ \/ \-------------------------というわけで, 与えられた 2 通りのゴムひもの配置が同一かどうか判定してほしい.

Input
入力の 1 行目にはテストケースの個数 T が書かれている. その後次の形式で各テストケースが与えられる.

N1 N2
S1
S2
Ni (i = 1, 2) は整数である. Si (i = 1, 2) は長さ Ni の文字列 9 行であり, 文字 . (半角ピリオド), - (半角ハイフン), \ (半角バックスラッシュ), / (半角スラッシュ) からなる.

Output
各テストケースに対して, 与えられた 2 通りのゴムひもの配置が同一ならば文字列 YES を, そうでない場合は文字列 NO を 1 行に出力せよ.

Xmas Contest 201415

Constraints
すべての入力において, 以下の制約が満たされる.

• S1 , S2 は, 以下の 5 種類のブロックを横に並べたものである.
--...--...-----------.

.\./.

.\./.

.....

.....

.

..\..

../..

.....

.....

.

./.\.

./.\.

.....

.....

--...--...--...--...-

.

.....

.....

.\./.

.\./.

.

.....

.....

..\..

../..

.

.....

.....

./.\.

./.\.

------------...--...-

文字 . は空白の代わりである. 右の 4 種類は, 天井から見たときのゴムひもが交差する様子を表す. 3行目または 7 行目の 3 文字目は, 上側に見えるゴムひもの進行方向を示す.
さらに, 各入力において, 以下の制約が満たされる.

G1.in (30 点)• T = 20.
• 1 ≤ Ni ≤ 50 (i = 1, 2).

G2.in (70 点)• T = 40.
• 1 ≤ Ni ≤ 5 000 (i = 1, 2).

Xmas Contest 201416

SampleSample Input

Sample Output

2YES

17 17

NO

--...-------...-..\./.......\./..
...\.........\...
../.\......./.\..
--...--...--...-.......\./.......
........\........
......./.\.......
-------...-------------...------.......\./.......
........\........
......./.\.......
--...--...--...-..\./.......\./..
...\.........\...
../.\......./.\..
--...-------...-10 20---------..........
..........
..........
---------..........
..........
..........
--------------...----...----.....\./....\./.....
....../....../......
...../.\..../.\.....
-----...----...----....................
....................
....................
--------------------

Xmas Contest 2014

17Problem H: Hack Me
Points: 10 + 90

Input
あるテキストファイルを, ある秘密の方法で暗号化したファイルが与えられる.
本問に限り, 入力はテキストファイルではなくバイナリファイルである (ただし実行可能ファイルではない).

Output元のテキストファイルを出力せよ.

Constraints
各入力において, 以下の制約が満たされる.

H1.in (10 点)• 元のテキストファイルは, Xmas Contest 2014 の A, B, C, D, E, F, G 問題のいずれかの Sample
Output である.

H2.in (90 点)• 元のテキストファイルは 32 行からなり, 各行には 1 個の整数のみが不要な先頭の 0 のない十進表記で書かれている. 各整数は 0 以上 232 未満である.