問題文

うさぎが Xmas Contest 2019 に向けて看板を作ろうとしている．

今年は巨大な看板を作ろう．そう思ってうさぎはデザイン案の検討を始めようとした．

ところが，困ったことにうさぎの手元にはあまり大きな紙がない．そこで，ノートの紙を貼り合わせることで大きな紙を作り，そこにデザイン案を描いていくことにした．

――――――

膨大な時間をかけ，うさぎはようやく会心のデザイン案を描きあげた！

長く苦しい戦いだった．うさぎが一息つこうと部屋の窓を開けたとき，なんたる運命のイタズラか，一陣の風が吹き込み……！

気がつくとそこには，無情にもバラバラの紙片が散らばっていた．せっかくの会心のデザインが……．

別の紙にうろ覚えでさきほどのデザインを描きなおしてみたが，どうもしっくりこない．バラバラの紙片をもう一度つなぎ合わせるしかないのだろうか？

うろ覚えデザイン

問題

バラバラになった紙片をうまく並べることで，うさぎの考えた会心のデザインを復元せよ．

紙片は全部で 64 枚あり，1 から 64 までの番号が振られている．これを 8 \times 8 のグリッド状に並べることでデザインを復元したい．

紙片たちの情報と，うさぎがうろ覚えで描き直したデザインをまとめた zip ファイルがこちらからダウンロードできる．zip 内には以下のファイルが入っている．

• signboard_t1/design.png : うさぎがうろ覚えで描き直したデザイン．
• signboard_t1/pieces/*.txt : 紙片たちの情報．たとえば番号 10 の紙片に描かれているものは 10.txt として与えられる．
• signboard_t1/pieces/p_*.png : 対応する *.txt を画像化したもの．

幸いにも，元々の紙にあった模様から紙片の向きは特定できているので，各紙片の回転を考える必要はない．

問題文

正整数 N と，(不)等号 \mathrm{op} (<, =, > のうちいずれか) が与えられる．

以下のすべての条件を満たす集合 X が存在するか判定し，存在するならば 1 つ構成せよ．

• X の各要素は 0 以上 10^9 以下の非負整数である．
• |X| = N． (ただし |X| で集合 X の要素数を表す)
• S = \{ a + b \mid a, b \in X \}, D = \{ a - b \mid a, b \in X \} としたとき |S|\ \mathrm{op}\ |D| が成り立つ．
  • すなわち，S, D はそれぞれ X の要素どうしの和/差としてありうる値の集合である．上の定義では a = b の場合も含むことに注意せよ．(以下の例も参考にせよ)

たとえば X = \{2, 0, 1, 9\} のとき S = \{0, 1, 2, 3, 4, 9, 10, 11, 18\} および D = \{-9, -8, -7, -2, -1, 0, 1, 2, 7, 8, 9\} なので，|S| < |D| である．

制約

• 1 \leq N \leq 2\,019．
• \mathrm{op} は <, =, > のうちいずれか．

入力例 1

4 <

出力例 1

2 0 1 9

問題文に書かれている例である．

入力例 2

4 >

出力例 2

Merry Christmas!

問題文

うさぎの部屋は H \times W の長方形のマス目状になっている．部屋の各マスは，「通常のマス」「片づけ先のマス」「固定家具のマス」の 3 種類のいずれかである．最初，うさぎと何個かの荷物が，固定家具でない相異なるマスに位置している．上から i 行目 (1 \le i \le H)，左から j 列目 (1 \le j \le W) のマスの情報は文字 A_{i,j} で表され，以下を意味する．

• .：通常のマス
• R：通常のマスであり，うさぎがいる
• a：通常のマスであり，荷物がある
• O：片付け先のマス
• @：片付け先のマスであり，荷物がある
• #：固定家具のマス

うさぎは，以下のいずれかの行動を何回か，何らかの順番で行い，すべての荷物が片づけ先のマスに配置されている状態にしたい．

• 今いるマスと上下左右に隣接している空きマスに移動する．
• 今いるマスと上下左右に隣接しているマスにある荷物を，移動方向に 1 つ先の空きマスに押して動かし，動かした荷物があったマスに移動する．

ただし，「空きマス」とは，固定家具のマスでなく，荷物もない状態のマスのことである．

必要な行動回数の最小値を求めよ．なお，この問題では，すべての入力ファイルが公開される (「採点」を参照のこと)．

制約

• 5 \le H \le 400．
• 5 \le W \le 400．
• A_{i,j} は ., R, a, O, @, # のいずれかである (1 \le i \le H，1 \le j \le W)．
• A_{i,j} のうちちょうど 1 個が R である．
• A_{i,j} のうち a の個数と O の個数は等しく，1 個以上である．
• i = 1 または i = H または j = 1 または j = W のとき，A_{i,j} は # である．
• 問題文で示された行動により，すべての荷物が片づけ先のマスに配置されている状態にすることが可能である．

採点

• テストケースは 01.txt, 02.txt, 03.txt, 04.txt, 05.txt の 5 個あり，それぞれ正解すると 7 点，11 点，17 点，25 点，40 点が与えられる．
• 入力ファイルはこちらからダウンロードできる．
• 実際の入力ファイルに対して部屋の片づけをこちら (または zip 同梱の html) で手で遊べる．

入力例 1

6 7
#######
#R....#
#..@..#
###a###
###O###
#######

出力例 1

10

例えば，以下の 10 回の操作で片づけることができる．

1. 下に移動する．
2. 右に移動する．
3. 右に荷物を押しながら移動する．
4. 下に荷物を押しながら移動する．
5. 上に移動する．
6. 上に移動する．
7. 右に移動する．
8. 右に移動する．
9. 下に移動する．
10. 左に荷物を押しながら移動する．

この入力例も，こちらで手で遊べる．

問題文

正の整数 n に対し，f(n) を n が持つ素因数を重複を込めて数えた個数とする．例えば，200 = 2^3 \times 5^2 なので，f(200) = 5 となる．

正の整数 N が与えられるので，\sum_{n=1}^N (-1)^{f(n)} を求めよ．

制約

• 1 \le N \le 10^{11}．

部分点

• N \le 10^{10} を満たすデータセットに正解した場合は，45 点が与えられる．
• 追加制約のないデータセットに正解した場合は，上記とは別に 55 点が与えられる．

入力例 1

6

出力例 1

0

f(1) = 0，f(2) = 1，f(3) = 1，f(4) = 2，f(5) = 1，f(6) = 2 なので，答えは (-1)^0 + (-1)^1 + (-1)^1 + (-1)^2 + (-1)^1 + (-1)^2 = 0 である．

入力例 2

2019

出力例 2

-25

入力例 3

906150257

出力例 3

1

問題文

正の整数 n に対し，f(n) を n が持つ素因数を重複を込めて数えた個数とする．例えば，200 = 2^3 \times 5^2 なので，f(200) = 5 となる．

正の整数 N が与えられるので，\sum_{n=1}^N f(n) を求めよ．

制約

• 1 \le N \le 10^{11}．

部分点

• N \le 10^{10} を満たすデータセットに正解した場合は，45 点が与えられる．
• 追加制約のないデータセットに正解した場合は，上記とは別に 55 点が与えられる．

入力例 1

6

出力例 1

7

f(1) = 0，f(2) = 1，f(3) = 1，f(4) = 2，f(5) = 1，f(6) = 2 なので，答えは 0 + 1 + 1 + 2 + 1 + 2 = 7 である．

入力例 2

2019

出力例 2

6028

入力例 3

906150257

出力例 3

3660251364

問題文

うさぎは H \times W の長方形のマス目を持っている． マス目の上から i 行目 (1 \le i \le H)，左から j 列目 (1 \le j \le W) のマスをマス (i,j) と呼ぶ．

マス (i,j) の初期状態は文字 S_{i,j} で表され，# は黒く塗られていること，. は塗られていないことを意味する．

うさぎはクリスマスプレゼントとしてスタンプをもらった．

このスタンプを 1 回押すと縦 H/2 マス横 W/2 マスの大きさの長方形を黒く塗りつぶすことができる． すなわち，整数 i_0,j_0 を選んだとき，i_0 \le i \lt i_0+H/2 かつ j_0 \le j \lt j_0+W/2 を満たすようなマス (i,j) を全て黒く塗ることができる．

うさぎはこのスタンプを使って全てのマスを黒く塗ろうとしている． 最小で何回スタンプを押せば良いだろうか？

制約

• 2 \le H,W \le 1000
• H,W はいずれも偶数
• S_{i,j} は . または #

入力例 1

4 4
#..#
#.#.
..##
..##

出力例 1

3

例えば，下図の通りに押すと 3 回で全てのマスを黒く塗ることができる．

入力例 2

2 6
######
######

出力例 2

0

問題文

うさぎは H \times W の長方形のマス目を持っている． マス目の上から i 行目 (1 \le i \le H)，左から j 列目 (1 \le j \le W) のマスをマス (i,j) と呼ぶ．

マス (i,j) の初期状態は文字 S_{i,j} で表され，# は黒く塗られていること，. は塗られていないことを意味する．

うさぎはクリスマスプレゼントとしてスタンプセットをもらった．

このスタンプセットには 2 種類のスタンプが入っており，それぞれ下図のようなマスの集合を一度に黒く塗ることができる．

すなわち，

• 左のスタンプを 1 回押すと，整数 i_0,j_0 を選んだとき，i = i_0+5a+2b, j = j_0-2a+5b となる整数 a,b が存在するようなマス (i,j) を全て黒く塗ることができる．
• 右のスタンプを 1 回押すと，整数 i_0,j_0 を選んだとき，i = i_0+2a+5b, j = j_0-5a+2b となる整数 a,b が存在するようなマス (i,j) を全て黒く塗ることができる．

うさぎはこのスタンプセットを使って全てのマスを黒く塗ろうとしている． 最小で何回スタンプを押せば良いだろうか？

制約

• 1 \le H,W \le 300
• S_{i,j} は . または #

入力例 1

8 8
.####.##
########
.####.##
########
########
##.####.
########
##.####.

出力例 1

3

入力例 2

50 50
######################.#.##.######################
##############.########################.###..#####
####.###############..############################
###################.###########.####.#############
########.#.#####################.##########..#####
###.###.#####.######.######.##############.###.##.
.########.###.###############..#######.###.####.#.
.#.###############.######.#####.###############..#
####.########################.###.##.#############
################.#####.#.#########.#.#############
..#########.############.#########.#####.######.##
######.###############.#####.###########..########
###.##########.#.##########..################.####
################.###########################.##.##
#####.############.....#####.####..###############
#.#####################.####.#.######..##########.
#########.#.########.#.###.############.##.#######
########.####.####################.#######.#..####
##.#####.####.################.#######.#######.###
..#######.#.#################.###.##############..
#.######.####.#####.#.####.#####.##.#####..#######
################.#######..#####.##################
########.###..#########..###.########.###.######.#
#############################.######.###########.#
##..#############.#############..#########.####.##
############.###########.###.##############..#####
.#####..###############.#########.#.#########.####
#.########.############.#########.############.###
###.#.####################..###########.#..#######
#####.###.##############.##.##########.#####.#####
#######.##.#####.##########.###############.######
.#########.################.#####.#########.######
##.############.###..###########.###.#.##.######.#
##############..#######.#############.######.#####
###.################.###..######.##..#########.###
#.##################.########.########..##########
.#.#########.#####################################
#######.###########.#########.#####.############..
#.####################.##..###.###.###############
###########.############.####..###################
.###########.#########.#################.#########
##############.#..##############..#########.######
###..##.##########################.###########.###
#########.##########.#.#####.####.################
#.######.##.################.#.######.#.#####.####
#########.######.###.#.###.######.###.#.#####.####
###############.##################.#######.#..####
#.######.#######..#############..#########.##.####
#########.###########.####.###########.#########.#
######.#.###########.#####.###.##.#######..######.

出力例 2

15

入力例 3

1 1
#

出力例 3

0

問題文

うさぎは H \times W の長方形のマス目を持っている． マス目の上から i 行目 (1 \le i \le H)，左から j 列目 (1 \le j \le W) のマスをマス (i,j) と呼ぶ．

マス (i,j) の初期状態は文字 S_{i,j} で表され，# は黒く塗られていること，. は塗られていないことを意味する．

うさぎはクリスマスプレゼントとしてスタンプセットをもらった．

このスタンプセットには 10^{10} 種類のスタンプが入っており，スタンプ k\ (1 \le k \le 10^{10}) は，p_k マスおきに横一列に並んだマスの集合を一度に黒く塗ることができる． ただし，ここで p_k は k 番目に小さい奇素数とする． すなわち，スタンプ k を 1 回押すと，整数 i,j_0 を選んだとき，j = j_0+a*p_k となる整数 a が存在するようなマス (i,j) を全て黒く塗ることができる．

うさぎはこのスタンプセットを使って全てのマスを黒く塗ろうとしている． 最小で何回スタンプを押せば良いだろうか？

制約

• 1 \le H,W
• H*W \le 10^5
• S_{i,j} は . または #

入力例 1

2 15
.#.##.##.#..##.
########.#.####

出力例 1

4

例えば以下のように押せばよい． 2 は奇素数でない点に注意せよ．

• スタンプ 1 (p_1 = 3) を i = 1, j_0 = 3 として押す．
• スタンプ 2 (p_2 = 5) を i = 1, j_0 = 1 として押す．
• スタンプ 4 (p_4 = 11) を i = 2, j_0 = 0 として押す．
• スタンプ 4 (p_4 = 11) を i = 2, j_0 = -2 として押す．

入力例 2

5 1
.
.
#
.
.

出力例 2

4

入力例 3

20 19
#.#.##..#.###.#.#.#
.#.###..#.##.##.##.
#.##..#.##..#..#..#
######.######.####.
.#########.####.###
..###.##..#####.##.
#########.#########
.##.##.#####.##.###
##.#####.#####.##.#
.##.#..##.##.###.##
#.##.##.#..##..#.##
#.##.###.##########
#.######..####.####
.##.##.##..#.##.##.
########.##########
##.########.##.#..#
#.##.##.#####.##.##
#############..####
..#.##..##..#..#.#.
.##.#..#####.##.##.

出力例 3

37

問題文

うさぎは H \times W の長方形のマス目を持っている． マス目の上から i 行目 (1 \le i \le H)，左から j 列目 (1 \le j \le W) のマスをマス (i,j) と呼ぶ．

初め，いくつかのマスは黒く塗られている． マス (i,j) の情報は文字 S_{i,j} で表され，# は黒く塗られていること，. は塗られていないことを意味する．

うさぎはクリスマスプレゼントとしてスタンプをもらった．

このスタンプを 1 回押すと下図のようなマスの集合を全て黒く塗ることができる． 下図についてより詳細に説明すると，赤枠で囲われた 19 \times 31 のパターンを斜め一直線に無限につなげたものである． ただし，スタンプは下図を 1 マス単位で平行移動させて押すことしかできず，回転・反転させることや 0.5 マスずらして押すこと等はできない．

うさぎはこのスタンプを使って，まだ塗られていないマスを全て黒く塗ろうとしている． 最小で何回スタンプを押せば良いだろうか？

制約

• 1 \le H,W \le 1000
• S_{i,j} は . または #

入力例 1

19 31
..#############################
#...###########################
###..##########################
####...########################
######...######################
########..#####################
#########...###################
###########...#################
#############..################
##############...##############
################..#############
#################...###########
###################...#########
#####################..########
######################...######
########################...####
##########################..###
###########################...#
#############################..

出力例 1

1

入力例 2

5 5
###.#
##..#
##.##
#..##
#.###

出力例 2

4

入力例 3

20 19
###.###########.###
##.########...##.##
###.##############.
###################
######.############
##############.#.##
#########.#########
#######.#########.#
##########.#######.
#########.#.#.#.###
#######.###########
#####.#############
.#.##.#############
###.#######.####.#.
.########.#.#######
##.################
#.####.############
########.#.########
###################
#.#.########.######

出力例 3

13

問題文

N 種類のカードが，それぞれ 2019^{2019} 枚ずつある．

i 種類目のカードには，上側に文字列 A_i が，下側に文字列 B_i が書かれている．

これらのカードから 1 枚以上を選び，好きな順で一列に並べることを考える．このとき，並べられた各カードの上側に書かれている文字列を繋げたものを s，下側に書かれている文字列を繋げたものを t とする．

次の条件を満たすようにカードを選んで並べることはできるだろうか？

• 条件: s から 0 文字以上の好きな箇所の文字を選んで消すことで t に一致させることができる．

制約

• 1 \leq N \leq 16．
• 1 \leq |A_i|, |B_i| \leq 10^5．
• A_i, B_i は英小文字のみからなる文字列である．

入力例 1

2
cab ac
acba ab

出力例 1

YES

たとえば，2 種類目，2 種類目，1 種類目の順にカードを並べると，s = acbaacbacab, t = ababac となり，これは条件を満たす．

入力例 2

1
xmas contest

出力例 2

NO

問題文

根付き木を，「根付き木のある多重集合について，それらの根を新たな 1 個の頂点と辺で結びその頂点を根としたもの」として再帰的に定義する (繋ぐときの並べ方を区別しないことに注意せよ)． 特に，1 頂点のみからなる木は空集合に対応する． この問題では，頂点数が有限の根付き木のみを考える． 根付き木 T_1, \ldots, T_k を新たな根に繋いだ根付き木を \{\!\!\{T_1, \ldots, T_k\}\!\!\} と書く． 例えば以下の図のようになる．

根付き木は根付き木の多重集合

根付き木 T, T' の順序を，「T_1 \ge \cdots \ge T_k,\, T'_1 \ge \cdots \ge T'_l によって T = \{\!\!\{T_1, \ldots, T_k\}\!\!\},\, T' = \{\!\!\{T'_1, \ldots, T'_l\}\!\!\} と表したとき， 列 s = (T_1, \ldots, T_k),\, s' = (T'_1, \ldots, T'_l) を辞書式順序で比較して， s < s' ならば T < T'，s = s' ならば T = T'，s > s' ならば T > T'」として再帰的に定義する (T \ge T' は T > T' または T = T' を表す)． 例えば以下の図のようになる．

根付き木の順序

くろうさとしろうさがゲームを行う． 盤面には根付き木がいくつかある． 最初，頂点は合計で N 個あり，1 から N までの番号がついている． P_i = 0 のとき頂点 i は盤面の根付き木のうち 1 個の根であり，P_i > 0 のとき頂点 i と頂点 P_i が辺で結ばれている． 先手くろうさと後手しろうさは交互に次の行動を行う：盤面にある根付き木を 1 個選び，上で定めた順序でそれより真に小さい根付き木に書き換える (すなわち，選んだ根付き木を T とするとき，T > T' なる根付き木 T' を 1 個選んで，選んだ部分を T' に変化させる)． 行動できなくなった側が負けであり，相手が負けたら勝ちである．

くろうさもしろうさも，以下に従う．

• 必ず勝つことができるならば，勝つように行動する．
• 必ず勝つことはできないが必ず負けないようにできるならば，負けないように行動する．

このときどちらが勝つか，あるいはゲームが無限に続くかを決定せよ．

制約

• 1 \le N \le 201912．
• 0 \le P_i \le i - 1 (1 \le i \le N)．

部分点

• N \le 2019 を満たすデータセットに正解した場合は，45 点が与えられる．
• 追加制約のないデータセットに正解した場合は，上記とは別に 55 点が与えられる．

入力例 1

8
0 0 0 1 2 2 3 7

出力例 1

Black

くろうさは，初手で頂点 3 を根とする部分木を図のように書き換えることで勝つことができる．

入力例 1

入力例 2

14
0 1 2 2 1 5 5 0 8 8 10 10 9 9

出力例 2

White

問題文

うさぎは Xmas Contest 2019 の看板デザインに苦闘していた．

少しは休憩が必要だ．いまデザインを検討している紙の裏側でも使って，パズルを作って息抜きをしよう．ついでに，出来上がったパズルを Xmas Contest の参加者に解いてもらえば，もっと喜んでもらえるかもしれない．

そう思ったうさぎは，看板デザインを検討する傍ら，その紙の裏側を使ってスケルトンの制作も行っていた．

しかし，紙がバラバラになってしまった (Signboard 1 参照) 今となっては，せっかく完成したスケルトンも泡沫の夢……．

なんとか盤面の形状だけは思い出したものの，肝心の単語リストはバラバラになった紙片にしか残っていない．なんとかしてこのスケルトンを再び完成させられないだろうか？

スケルトンの盤面

問題

バラバラになった紙片の情報とスケルトンの盤面が与えられるので，紙に書かれた単語のみを使ったスケルトンの解を求めよ．

紙片は全部で 64 枚あり，1 から 64 までの番号が振られている．

紙片たちの情報をまとめた zip ファイルがこちらからダウンロードできる．zip 内には以下のファイルが入っている．

• signboard_t2/pieces/*.txt : 紙片たちの表面の情報．たとえば番号 10 の紙片に描かれているものは 10.txt として与えられる．
• signboard_t2/pieces/p_*.png : 対応する *.txt を画像化したもの．
• signboard_t2/pieces_back/*.txt : 紙片たちの裏面の情報．たとえば番号 10 の紙片に描かれているものは 10.txt として与えられる．
• signboard_t2/skeleton.txt : うさぎが思い出した盤面の情報．. は文字が入らないマス，* は文字が入るマスを表す．

紙片にはパズルを解くのに必要な単語がすべて書かれているが，パズル考案段階のメモ書きも残されているので，不要な単語が書かれていることもありうる．