Xmas Contest 2017

A - Compressor

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 100 点

問題文

うなぎは DTM (パソコンを用いた音楽制作) に挑戦しています。

音を変化させるエフェクターには様々な種類がありますが、その中でも コンプレッサー というエフェクターは非常に使いこなすのが難しいとされています。

うなぎはコンプレッサーをマスターするため、同じ音に対して音量が著しく変化しないようにコンプレッサーを適用したものと、全くコンプレッサーを適用していないものの両方を用意して聴き比べることにしました。

うなぎは 15 個のテストを、すなわち合計 30 個の音楽ファイルを用意し、それらに 01_A.wav, 01_B.wav, 02_A.wav, ..., 15_B.wav と名前をつけました。ファイル名の先頭 2 文字が楽曲番号を表し、A, B のうちどちらか片方のみにコンプレッサーが適用されています。

早速うなぎは聴き比べてみようと思いましたが、それぞれの楽曲について A と B のどちらにコンプレッサーを適用したか忘れてしまいました。

うなぎの用意したファイルから、15 個の楽曲それぞれについて、どちらにコンプレッサーがかかっているかを判定してください。

入力データの詳細

うなぎの用意した zip ファイルを解凍すると、input というディレクトリと 2 個の wav ファイルが出てくる。

2 個の wav ファイル (sample_mono_comp.wav と sample_mono_dry.wav) はコンプレッサーの適用例を示す楽曲データである。sample_mono_dry.wav に対して (例示のため、本番用のデータよりも強めに) コンプレッサーをかけた結果が sample_mono_comp.wav となっている。これらのデータを解く際の参考として使って構わない。

input というディレクトリの中にはうなぎの作った 30 個の音楽ファイルが入っている。これら 15 種の楽曲に対し、A, B のどちらにコンプレッサーが適用されているかを正しく当てることができればこの問題は正解となる。

すべての wav ファイルは以下の制約を満たす。

リニア PCM 形式 (非圧縮で量子化された波形データがそのまま格納されている)
チャンネル数 1 (モノラル音源)
サンプリングレート 44.1 kHz (1 秒あたり 44\,100 サンプル)

入力

この問題では入力は与えられない。

出力

1 行目に 15 文字の A または B のみからなる文字列を出力せよ。

出力する文字列の i 文字目 (1 \leq i \leq 15) は、i 番目の楽曲について、コンプレッサーが適用されている側のファイル名についているアルファベットでなければならない。

たとえば 01_A.wav にコンプレッサーが適用されており 01_B.wav には適用されていない場合は 1 文字目は A となる。

B - Hello, Xmas Contest 2017

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 100 点

問題文

うさぎが Xmas Contest 2017 の看板を作ろうとしています。看板はマス目が長方形のグリッド状に並んだもので、それぞれのマスには 1 文字だけ文字を書くことができます。文字を書かないマスがあっても構いません。

うさぎが書ける文字の種類は、英大文字 (A-Z)、英小文字 (a-z)、数字 (0-9)、飾りの星マーク (*) のいずれかです。

うなぎが看板を読む時には、以下のようにして看板から文字列を読みとります:

上の行から順に一行ずつ見ていく。
それぞれの行に対し、その行のいずれのマスにも文字が書かれていなければ、その行は無視する。
その行に文字の書かれているマスがあれば、そのうち最も左のマスに書かれている文字を読みとる。

うさぎは、うなぎが看板を読んだときに読みとる文字列から星マーク (*) を除いたものがちょうど XmasContest2017 となるように看板を作ろうとしています。

それだけでなく、看板の向きを間違えて 90 度、180 度、270 度いずれの角度に回転した状態で看板をかけることになった場合でも、うなぎが (* を除いて) XmasContest2017 という文字列を読みとるようにしたいと考えています。

この条件を満たす看板の例をひとつ求めてください。文字を書くインクが節約できるとうれしいので、文字を書くマスの個数が少ないほど高得点が得られます (詳細は採点方法の項を参照)。

入力

この問題では入力は与えられない。

出力

次のようなフォーマットで出力せよ。

H W
S_1
S_2
:
S_H

ここで H は看板を表すグリッドの行数、W は列数である。

S_1 から S_H はそれぞれ W 文字からなる文字列である。これらの文字列は英大文字 (A-Z)、英小文字 (a-z)、数字 (0-9)、アスタリスク (*)、ピリオド (.) のみからなる。

文字列 S_i (1 \leq i \leq H) の j 番目 (1 \leq j \leq W) の文字はグリッドの上から i 行目、左から j 列目のマスの情報を表す。その文字が . のときマスには何も書かれておらず、そうでないときはその文字がマスに書かれている。

採点方法

採点は以下のように行われます。

出力がフォーマットに従っていない場合は WA と判定される。
1 \leq H \leq 100 および 1 \leq W \leq 100 を満たしていない場合は WA と判定される。
出力された看板を 0 度、90 度、180 度、270 度それぞれの角度に回転させたとき、うなぎの読み取る文字列から * を除いたものがちょうど XmasContest2017 になっていない場合があれば WA と判定される。

以上の判定で WA とならなかった場合 AC となりますが、そのとき得点は以下のように決まります。

出力された看板に書かれた文字の数 (出力の文字列に含まれる . 以外の文字の文字数) を C としたとき、
- C \leq 32 ならば 100 点
- 32 < C \leq 100 ならば 100 × (100-C) / 68 点
- 100 < C ならば 0 点

出力例1

6 7
Welcome
*...to.
.......
.*Xmas*
Contest
...2017

この場合、うなぎが読み取る文字列はそれぞれ以下のようになります。

(時計回りに) 0 度回転した場合: W**C2
(時計回りに) 90 度回転した場合: Con2017
(時計回りに) 180 度回転した場合: 7t*oe
(時計回りに) 270 度回転した場合: emocleW

C - Revenge of Kurousa

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 100 点

ストーリー

くろうさ「足し算は甘え」

しろうさ「あっこれって」

くろうさ「ビット演算は許してあげる」

しろうさ「えっとえっと」

くろうさ「ほんとにちょっとだけなら足し算してもいいよ」

しろうさ「何回ぐｒ

くろうさ「というわけでまたまたがんばってねっ」

(元ネタ: Xmas Contest 2015 Problem E: Esolang?, 元ネタの元ネタ: Xmas Contest 2014 Problem A: A+B Problem)

入力

この問題では入力は与えられない。

出力

0 以上 255 以下の整数をインクリメントする (値を 1 増やす、ただし 255 は 0 にする) プログラムを以下の仕様に従って作成し提出せよ。ジャッジ方法の項で詳細を記述するが、プログラム中で加算操作を行った回数が少ないほど高得点が得られる。

プログラムの動作

プログラム中では a, b, c, ..., z の 26 個の変数を扱うことができる。各変数は 0 以上 255 以下の整数を保持することができる。プログラム開始時に a の値がある整数値に設定されており、そのほかの 25 個の変数はすべて 0 に設定されている。

提出するプログラムは各行に「操作」が 1 つずつ記述される形式をとる。すべての操作は Z = X op Y という書式に従う。ここで、X, Y, Z は変数名を表す英小文字であり、op は演算を表す文字列 (後述) でなければならない。各操作は X と Y の示す変数の保持する値に対し op で示される演算を行った結果を Z に格納するという動作をする。

演算として使うことができるのは 16 種のビットごとの論理演算と、加算の計 17 種類である:

ビットごとの論理演算を行うとき、op は 0 と 1 のみからなる 4 文字の文字列である。この文字列は、各ビットに対して行われる論理演算の真理値表を表しており、入力が (0, 0), (0, 1), (1, 0), (1, 1) の場合に対応する出力を順に並べたものである。
- たとえば、ビットごとの論理和 (OR) 演算を表す文字列は 0111 であり、論理包含 (→) を表す文字列は 1101 となる。
加算を行うとき、op は + である。加算の結果が 256 以上になる場合、その和を 256 で割った余りが変数 Z に格納される。

以下に示すのはプログラムの記述例である (内容には特に意味がない)。

b = a + a
c = b 0101 a
a = a 1101 b

ジャッジ方法

ジャッジは以下のように行われます。

提出されたプログラムの形式が正しくない場合 (各行に「操作」を表す正しい書式の文字列が 1 つずつ書かれていない場合)、ジャッジ結果は WA となる。
提出されたプログラムが 1\,000 個以上の「操作」を含む場合、ジャッジ結果は WA となる。
0 以上 255 以下のすべての整数 A に対し、プログラム実行開始時の a の値を A に設定したうえで、提出されたプログラムを実行する。プログラムの実行が終了した時点で、変数 a の値が A+1 (ただし A=255 の場合は 0) になっていないような A が存在すれば、ジャッジ結果は WA となる。

以上のプロセスで WA と判定されなかったプログラムは AC と判定されますが、その得点は以下のように決まります。

プログラム中に存在する加算操作の回数 を P とする。また、上述の条件を満たしたプログラムのうち、P としてありうる値の最小値 (加算操作の最小の必要回数) を P_0 とする。このとき、得点は
- P = P_0 ならば 100 点
- P_0 < P \leq 2P_0 ならば 30 点
- 2P_0 < P ならば 0 点

D - Inversion Number

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 100 点

問題文

要素数 N の順列とは、1 から N までの N 個の整数 (1, 2, ..., N) を並べ替えたものです。

要素数 N の順列 A に対し、A の転倒数 (inversion number) とは、A_i > A_j を満たす組 (i, j) (1 \leq i < j \leq N) の個数です。

要素数 N の順列のうち、その転倒数を K で割った余りが m になるようなものの個数を 10^9+7 で割った余りを求めてください。

制約

1 \leq N \leq 10^{18}
0 \leq m < K \leq 10

入力

N K m

出力

要素数 N の順列のうち、その転倒数を K で割った余りが m になるようなものの個数を 10^9+7 で割った余りを出力せよ。

入力例 1

3 10 2

出力例 1

要素数 3 の順列の転倒数は高々 3 なので、このケースでは転倒数が 2 のものを数えればよいです。

転倒数が 2 の順列は (3, 1, 2), (2, 3, 1) の 2 通りあります。

入力例 2

7 9 1

出力例 2

入力例 3

100 1 0

出力例 3

437918130

10^9+7 で割った余りを出力してください。

E - String Problem

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 100 点

問題文

2 つの文字列 S, T が与えられます。以下のような操作を好きな順番で好きなだけ行うことで S を T にできるかどうかを判定してください。

操作 A：S に含まれる文字 A を 1 つ削除する。
操作 B：S の好きな位置に文字 B を 1 つ挿入する。

制約

1 \leq |S|, |T| \leq 1000
S, T は大文字アルファベットのみからなる

部分点

|S| \leq 10 を満たすデータセットに正解した場合は、50 点が与えられる。
追加制約のないデータセットに正解した場合は、上記とは別に 50 点が与えられる。

入力

入力は以下の形式で標準入力から与えられる。

S
T

出力

可能な場合は YES を、不可能な場合は NO を出力せよ。

入力例 1

XMAS
XBMS

出力例 1

YES

例えば XMAS → XBMAS → XBMS のように操作すれば良いです。

入力例 2

AABABA
BABBABAB

出力例 2

YES

例えば AABABA → ABABA → BABABA → BABABAB → BABBABAB のように操作すれば良いです。

入力例 3

AB
AA

出力例 3

NO

入力例 4

ATCODER
CONTEST

出力例 4

NO

F - Tree Disassembly

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 100 点

問題文

クリスマスツリーを持った青いうさぎと赤いうなぎがぶつかってしまい、二つのツリーがこんがらがってしまいました。

N 頂点からなるグラフが与えられます。頂点には 1 〜 N の番号がつけられています。辺は N*2-2 本あり、i 番目の辺は頂点 A_i と頂点 B_i を繋いでいます。

このグラフの辺を赤と青に塗り分ける方法であって、赤い辺のみからなるグラフも青い辺のみからなるグラフも木になるようなものは何通りあるでしょうか？

答えは非常に大きくなることがあるので、10^9+7 で割ったあまりを求めてください。

制約

4 \leq N \leq 104
1 \leq A_i,B_i \leq N
自己ループや多重辺は存在しない
問題文中の条件を満たす塗り分け方が少なくとも 1 通り以上存在する

採点

テストケースは 01.txt 〜 10.txt の 10 個あり、テストケースに 1 つ正解するごとに 10 点が与えられます。

この問題ではテストケースが公開されており、こちらからダウンロードすることができます。

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 B_1
A_2 B_2
:
A_{N*2-2} B_{N*2-2}

出力

答えを 10^9+7 で割った余りを出力せよ。

入力例 1

出力例 1

このケースでは以下の 12 通りの塗り分け方があります。

図：塗り分け方の一覧

G - Maze

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 100 点

問題文

下図の迷路のうち、スタート（左上）からゴール（右下）にたどり着けるものを全て見つけてください。

入力

この問題では入力は与えられない。

出力

スタートからゴールにたどり着ける迷路の横にあるアルファベットを順番に出力せよ。

例えば、A,T,C,O,D,E,R のみであった場合は以下のように出力すれば良い。

ACDEORT

H - Ango

Time Limit: 15 sec / Memory Limit: 256 MB

配点 : 100 点

問題文

うさぎとあなたは暗号ごっこをしようとしています。暗号ごっこは以下のように行われます。

最初に、あなたは N 個の 0 以上 M 以下の整数をうさぎに教えておく。このうち i 番目の整数を x_i とする。
うさぎは Q 回、以下のような方法であなたに暗号を送ってくる。
- 2 つの整数 a, b (1 \leq a < b \leq N) をランダムに選び、x_a + x_b の値をあなたに伝える。
あなたは x_a + x_b の値が送られてくるたびに a, b の値を当てなければならない。

あなたは暗号ごっこを無事成功させることができるでしょうか？

部分点

N = 300, M = 10^{18}, Q = 200000 を満たすテストケースに正解した場合は、20 点が与えられる。
N = 200000, M = 10^{18}, Q = 200000 を満たすテストケースに正解した場合は、上記とは別に 50 点が与えられる。
N = 200000, M = 10^{12}, Q = 200000 を満たすテストケースに正解した場合は、上記とは別に 30 点が与えられる。

入出力

整数 N, M が空白区切りで標準入力に与えられる。
あなたのプログラムは N 個の整数 x_i (1 \leq i \leq N) を空白区切りで出力しなければならない。
整数 Q が標準入力に与えられる。
以下を Q 回繰り返す。
1. 2 つの整数 a, b (1 \leq a < b \leq N) がランダムに選ばれ、x_a + x_b の値が標準入力に与えられる。
2. あなたのプログラムは整数 a, b を正しく予測し、整数 a, b を空白区切りで出力しなければならない。

入出力例も参考にせよ。

注意点

答えを出力した後、あなたのプログラムは直ちに終了しなければならない。 終了しなかった場合のジャッジ結果は不定である。また、正しくない出力をした場合の結果も不定である（必ずしも WA になるとは限らない）。

あなたのプログラムが正しい答えを出力して終了した場合、正答とみなされる。

出力した後に、出力をflushしなければならないことに注意せよ。flushしなかった場合、TLEとなることがある。

各言語での入出力の方法は過去の AtCoder で出題されている問題 (リンク: ABC 019 D: 高橋くんと木の直径) を参考にするとよい。

入出力例

N=3,\ M=4,\ Q=2 ときの入出力例を示す。

入力	出力	説明
`3` `4`		`N, M` が与えられている。
	`0` `2` `4`	`x_i` を出力している。
`2`		`Q` が与えられている。
`6`		`a=2,b=3` が選ばれ、`x_2 + x_3` の値が与えられている。
	`2` `3`	`a, b` を予測し、出力している。
`4`		`a=1,b=3` が選ばれ、`x_1 + x_3` の値が与えられている。
	`1` `3`	`a, b` を予測し、出力している。

I - SAT Puzzle

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 100 点

問題文

以下のパズルをSATで解いてください。

6*6 のマス目が与えられる。いくつかのマスは黒マスであり、それ以外は白マスである。
白マスをいくつか黒マスに変え、以下の条件を満たすようにせよ。
- 白マスの連結成分がちょうど 4 つ存在し、いずれもサイズは 4 である。

下図の例題も参考にしてください。

図１：例題

後々のためにマスには以下のように番号をつけておきます。

図２：マスの番号付け

解答方法

あなたはこのパズルを解くための以下のようなCNFを提出してください。

論理変数は x_1, x_2, ..., x_{1000} のみを用いる。
式を充足する真偽値の割り当てに対し、x_i (1 \leq i \leq 36) がパズルの解答の盤面におけるマス i の色を表す。x_i が真の場合マス i は黒であり、偽の場合は白である。

ジャッジ方法

ジャッジは以下のように行われます。

提出のCNFに以下のような節を追加する。
- テストケースのパズルの初期盤面でマス i が黒く塗られているとき、(x_i) という節を追加する。（これにより、x_i は必ず真となる。）
CNFの充足可能性を判定する。充足不可能であった場合ジャッジ結果は WA となる。また、この判定に 30 秒以上かかった場合は IE となる。
充足可能な場合は真偽値の割り当てを 1 つ見つけ、各 i (1 \leq i \leq 36) について、x_i が真の場合マス i を黒マスにし、偽の場合は白マスにする。
得られた盤面がパズルの解として正しいかどうかを判定する。正しければジャッジ結果は AC となり、正しくなければ WA となる。

テストケースは 10 ケースあり、全てに正解すると AC となります。

こちらのgist にジャッジのソースコードをuploadしてあるので、デバッグ等にご利用ください。

入力

この問題では入力は与えられない。

出力

i 行目に i 番目の節の情報を出力し、最後の行に 0 を出力せよ。各節の出力方法は minisat を参考にせよ。

例えば (x_1 \lor x_2) \land (\lnot x_1 \lor x_2 \lor \lnot x_3) というCNFの場合は以下のように出力すれば良い。

1 2 0
-1 2 -3 0
0

注意点

以下の点に注意せよ。

リテラルには x_1 から x_{1000} までしか使ってはいけない
空の節を入れてはならない。（0 のみが行に出力され、出力の終端だと判定されてしまうため）