A - 幾何問題を解こう

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

A君は今日も幾何の問題を解いている。 幾何の問題を解く時は浮動小数点誤差に気をつけることが大事である。

浮動小数点誤差とは、2進法の有限小数で数を表す際におこる丸めによって起きる誤差である。 例えば、10進法での 0.1 は2進法では 0.00011001100110011 ... という無限小数になるが、 これを有限の桁で丸める際に誤差が発生してしまう。

正の整数 p, q が10進法で与えられる。 有理数 p / q を有限桁数の小数で表現することができるような b 進法（b は2以上の整数）を求めよ。 複数ある場合は最も小さいものを出力せよ。

Constraints

  • 0 < p < q < 10^9

Input Format

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

Output Format

答えを一行に出力せよ。

Sample Input 1

1 2

Sample Output 1

2
1/2 は 2 進法で 0.1 です

Sample Input 2

21 30

Sample Output 2

10
21/30 は 10 進法で 0.7 です
B - 監獄

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

無限人の囚人たちがいる。はじめ、囚人たちは 0,\ 1,\ 2,\ ... と番号が振られている。

次の操作を N 回行う。

  • 0 番目の囚人を釈放し、k,\ 2k,\ 3k,\ ... 番目の囚人たちを処刑する。
  • その後、残った囚人たちに番号を振り直す。このとき、元の番号が小さい囚人から順に 0,\ 1,\ 2,\ ... と番号を振る。

N 回目の操作で釈放される囚人がはじめに振られていた番号を求めよ。

Constraints

  • 1\leq N\leq10^5
  • 2\leq k\leq10^5
  • 答えは 10^{18} 以下である。

Input Format

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

N k

Output Format

答えを一行に出力せよ。

Sample Input 1

4 2

Sample Output 1

7

Sample Input 2

1 3

Sample Output 2

0

Sample Input 3

100000 100000

Sample Output 3

99999
C - ABC Gene

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

文字列 ABC で表される遺伝子配列がある。あなたは次の操作を何回か行い、この遺伝子配列を書き換えていくことができる。

  • 文字 A，B，C のうち 1 つを選ぶ。これを x とおく。遺伝子配列に含まれるすべての x をそれぞれ ABC へ同時に置き換える。

A，B，C だけからなる文字列 S が与えられる。遺伝子配列を S に一致させられるか判定せよ。

Constraints

  • 1\leq|S|\leq5,000
  • S は A，B，C だけからなる。

Input Format

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

S

Output Format

遺伝子配列を S に一致させられるならば Yes を、一致させられないならば No を一行に出力せよ。

Sample Input 1

ABC

Sample Output 1

Yes

遺伝子配列ははじめから ABC である。

Sample Input 2

AABCC

Sample Output 2

Yes

B を選んで操作を行うと ABC → AABCC となる。

Sample Input 3

AABCABC

Sample Output 3

No

例えば、C を選んで操作を行っても AABCC → AABCABC とはならない。すべての C をそれぞれ ABC へ同時に置き換えるので、実際は AABCC → AABABCABC となる。

D - 真っ暗な部屋

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

目を覚ますと、A君は真っ暗な部屋の中にいた。 どうやらA君は N 個の部屋から構成されたダンジョンに迷い込んでしまったようだ。 あなたはA君がどの部屋に迷い込んだのかを知ることはできなかったが、幸いにもダンジョンのマップを手に入れることができた。 A君の進むべき道を示し明るい部屋に導こう。

N 個の部屋のうち M 個の部屋が真っ暗な部屋であり、それぞれ D_1, D_2, ..., D_M 番目の部屋が真っ暗な部屋であることが分かっている。 また、全ての部屋からちょうど K 本の一方通行の道が順に並んでおり、i 番目の部屋から出る道はそれぞれ v_{i,1}, v_{i,2}, ..., v_{i,K} 番目の部屋に繋がっている。 あなたは、A君に対し今いる部屋から a_1, a_2, ..., a_l 番目の道を順に進ませることができる。 ただし、A君は明るい部屋に到達したらそれ以降の指示は無視する。 あなたは、指示の前後においてA君が今いる部屋の情報を知ることはできないため、A君がどの部屋にいたとしても明るい部屋に辿り着けるような指示列を伝えなければならない。

そのような指示のうち、最も短いものの長さを答えよ。

Constraints

  • 2 \leq N \leq 100
  • 1 \leq M \leq min(16, N-1)
  • 1 \leq K \leq N
  • 1 \leq D_i \leq N
  • D_i は全て異なる
  • 1 \leq v_{i, j} \leq N
  • 全ての暗い部屋は少なくとも1つの明るい部屋に到達可能である

Input Format

入力は以下の形式で標準入力から与えられる。 
N M K
D_1 D_2 ... D_M
v_{1,1} v_{1,2} ... v_{1,K}
v_{2,1} v_{2,2} ... v_{2,K}
...
v_{N,1} v_{N,2} ... v_{N,K}

Output Format

答えを一行に出力せよ。

Sample Input 1

4 2 2
1 2
2 4
3 1
4 2
1 3

Sample Output 1

2

1, 1 という指示を出すと
  • A君の初期位置が部屋1である場合、2つ目の移動で部屋3に到達する
  • A君の初期位置が部屋2である場合、1つ目の移動で部屋3に到達する

Sample Input 2

3 2 2
1 2
2 3
1 2
2 1

Sample Output 2

3

2, 1, 2 という指示を出すと
  • A君の初期位置が部屋1である場合、1つ目の移動で部屋3に到達する
  • A君の初期位置が部屋2である場合、3つ目の移動で部屋3に到達する

Sample Input 3

6 3 3
1 2 3
4 1 1
2 5 2
3 3 6
4 4 4
5 5 5
6 6 6

Sample Output 3

3

非連結であるケースや、自己辺、多重辺があるケースに気をつけよう
E - 坑道数式

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

ある日廃坑を探検していたあなたは、坑道に長い数式 S が書かれているのを発見した。大きな数が好きなあなたは、チョークを取り出し、数式を計算した結果ができるだけ大きくなるように(または)を書き加えることにした。書き加えた後も数式になっていなければならないとすると、最大でいくつにできるか。

文字と文字の間は十分広く空いていて、(または)であればいくつでも書き加えることができる。最終的に数式になっていれば、最初のかっこの対応が崩れるように(または)を書いてもよい（Sample 2参照）。 また、ここでは以下のBNFで定義される<expr>を数式と呼ぶ。数式中の数は全て一桁である。 

<expr>  ::= "(" <expr> ")"
         | <term> "+" <term>
         | <term> "-" <term>
<term>  ::= <digit> | <expr>
<digit> ::= "0" | "1" | "2" | "3" | "4"
          | "5" | "6" | "7" | "8" | "9"

Constraints

  • 3 \leq |S| \leq 200
S は数式を表す。

Input Format

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

Output Format

答えを整数で出力せよ。

Sample Input 1

1-(2+3-4+5)

Sample Output 1

5

1-(2+3-(4+5))が最大となる。

Sample Input 2

1-(2+3+4)

Sample Output 2

0

(1-(2+3)+4)が最大となる。

Sample Input 3

1-(2+3)

Sample Output 3

-4

1-(2)+(3)はここでいう数式ではないことに注意。

F - ほぼ周期文字列

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

文字列 S が与えられる。この文字列 S に対し、Q 個のクエリに答えよ。 i 番目のクエリでは、S[l_i,\ r_i] から1文字まで変えてよいとき、S[l_i,\ r_i] を周期 t_i の文字列にできるかどうかを判定せよ。S[l,\ r] は文字列 S の l 文字目から r 文字目までの部分文字列を表す。

文字列 W が周期 t の文字列であるとは、 i\ =\ 1,\2,\... ,\ |W|-t に対し、 W_{i} = W_{i+t} となることとする。

Constraints

  • 1 \leq |S| \leq 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq l_i \leq r_i \leq |S|
  • 1 \leq t_i \leq r_i-l_i+1
  • Sはアルファベットの小文字のみからなる

Input Format

入力は以下の形式で標準入力から与えられる。 
S
Q
l_1 r_1 t_1
...
l_Q r_Q t_Q

Output Format

Q 行にわたって出力せよ。 i 行目には、i 番目のクエリの答えを Yes または No で出力せよ。

Sample Input 1

abcabcaxcabc
4
1 9 3
8 12 3
1 4 2
2 3 2

Sample Output 1

Yes
Yes
No
Yes

Sample Input 2

isuruu
4
3 6 1
3 6 2
3 6 3
2 4 1

Sample Output 2

Yes
Yes
Yes
No
G - Escape

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

(13:35) Input format の記述を一部修正しました

頂点に正の値を持つ無向グラフが与えられる。 頂点には 1 から N の番号がついており、i 番目の頂点は w_i の値を持っている。 1 番目の頂点からスタートし、直前に通った辺を通ることができないという制約のもとでグラフ上を移動することができる。 各頂点では，初めて訪れた時に限りその頂点が持つ値の点数を得られる。

取得できる点数の総和の最大値を求めよ。

Constraints

  • 1 \leq N \leq 100000
  • N-1 \leq M \leq 100000
  • 1 \leq w_i \leq 1000
  • 1 \leq u_i, v_i \leq N
  • 多重辺・自己辺は存在しない
  • グラフは連結である

Input Format

入力は以下の形式で標準入力から与えられる。 
N M
w_1 w_2 ... w_N
u_1 v_1
u_2 v_2
...
u_M v_M

1 行目にはグラフ(修正 13:36:00)の頂点数 N と辺の数を表す整数 M が入力される。
2 行目には各頂点が持つ値 w_i が入力される。
さらに続けて M 行に、各辺により繋がれる 2 頂点の番号が入力される。

Output Format

答えを1行に出力せよ。

Sample Input 1

6 6
1 2 3 4 5 6
1 2
2 3
3 4
1 4
4 5
5 6

Sample Output 1

21

頂点 1→2→3→4→5→6 と進むことで全ての頂点の点数を集めることができます。

Sample Input 2

7 8
1 3 3 5 2 2 3
1 2
2 3
3 1
1 4
1 7
1 5
1 6
5 6

Sample Output 2

16

頂点 1→2→3→1→5→6→1→4 と進むことで16点を集めることができます。
H - Bit Operation Game

Time Limit: 2 sec / Memory Limit: 256 MB

(13:43:00) Sample Input 1 の図を修正しました

Problem Statement

N 頂点の根付き木が与えられる。 頂点には 0 から N-1 の番号がついており、0番目の頂点が根を表す。 根には T = 0 が、それ以外の頂点には

  • T=T&X
  • T=T&Y
  • T=T|X
  • T=T|Y
  • T=T^X
  • T=T^Y
のいずれかの操作が書かれている。 ここでの演算子 &, |, ^ はそれぞれビット演算子 and, or, xor, を意味する。

A君とB君はこの木を使って以下のゲームを M 回行った。 二人は根からスタートし、子頂点を選び進むという操作を、A君から始め葉に到達するまで交互に行う。 通ったノードに書かれている操作を、通った順に適用した時の、最終的な T の値がスコアになる。 B君はできるだけスコアを小さくしたいと考えており、またA君は大きくしたいと考えている。 M回のゲームの X, Y の値が与えられるので、二人が最適な選択をした時の各ゲームのスコアを出力せよ。

Constraints

  • 1 \leq N \leq 100000
  • 1 \leq M \leq 100000
  • 0 \leq X, Y < 2^{16}

Input Format

入力は以下の形式で標準入力から与えられる。 
N M
o_1
o_2
...
o_{N-1}
u_1 v_1
u_2 v_2
...
u_{N-1} v_{N-1}
X_1 Y_1
X_2 Y_2
...
X_M Y_M

1 行目には木の頂点数 N と、行われるゲーム数を表す整数 M が入力される。
2 行目から N 行目にかけて、1 ～ N-1 番目の頂点に書かれている操作が入力される。
さらに続けて N-1 行に、各辺により繋がれる 2 頂点の番号が入力される。
最後に M 回のゲームにおける X, Y の値が M 行に渡り入力される。

Output Format

各ゲームでの最終的な T の値をそれぞれ M 行に出力せよ。

Sample Input 1

6 3
T=T|X
T=T|Y
T=T|Y
T=T^Y
T=T&X
0 1
0 2
1 3
1 4
2 5
5 6
3 5
0 0

Sample Output 1

4
6
0

(13:43:00) 図を修正しました
X = 5, Y = 6 の場合、頂点 0 -> 2 -> 5 と進み、T = 5 & 6 = 4 になります
X = 3, Y = 5 の場合、頂点 0 -> 1 -> 4 と進み、T = 3 ^ 5 = 6 になります
X = 0, Y = 0 の場合、どこを通っても T は 0 から変化しません
I - ツインリバース

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

要素数 N の配列 A が与えられる。ただし、A は (1,\ 2,\ ...,\ N) の順列である。

次の操作を 0 回以上 10,000 回以下の任意の回数行い、A を (1,\ 2,\ ...,\ N) へソートしたい。

  • 整数 i (1\leq i\leq N) を 1 つ選び、区間 A[1,\ i-1] の要素を逆順にし、区間 A[i+1,\ N] の要素を逆順にする。

ただし、区間 A[l,\ r] とは A の l,\ l+1,\ ...,\ r 番目の位置のことである。

A を (1,\ 2,\ ...,\ N) へソートできるか判定せよ。ソートできるならば、操作の例を一つ出力せよ。

Constraints

  • 1\leq N\leq 3,000
  • A は (1,\ 2,\ ...,\ N) の順列である。

Input Format

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

N
A_1 A_2 ... A_N

Output Format

A を (1,\ 2,\ ...,\ N) へソートできないならば、-1 とだけ一行に出力せよ。

ソートできるならば、操作の例を一つ次のように出力せよ。

  • 1 行目には、操作の回数を表す整数 M (0\leq M\leq10,000) を出力せよ。
  • 2 行目からの M 行のうち k 行目には、k 回目の操作で選ぶ整数 i (1\leq i\leq N) を出力せよ。

Sample Input 1

5
5 1 4 2 3

Sample Output 1

2
3
1

例えば、次のように 2 回の操作を行えばよい。

  • i=3 を選ぶと (5,\ 1,\ 4,\ 2,\ 3) → (1,\ 5,\ 4,\ 3,\ 2)
  • i=1 を選ぶと (1,\ 5,\ 4,\ 3,\ 2) → (1,\ 2,\ 3,\ 4,\ 5)

Sample Input 2

2
2 1

Sample Output 2

-1

Sample Input 3

3
1 2 3

Sample Output 3

0
J - 連結

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

N 個の頂点からなるグラフがある。頂点は 1,\ 2,\ ...,\ N と番号が振られている。i (1\leq i\leq N) 番目の頂点は非負整数の重み a_i をもつ。

はじめ、グラフには辺がない。あなたはグラフに無向辺を追加していくことができる。グラフに追加できる辺の候補は M 本ある。辺は 1,\ 2,\ ...,\ M と番号が振られている。i (1\leq i\leq M) 番目の辺は、頂点 x_i と y_i を端点とし、非負整数の重み z_i をもつ。

あなたの目標は、すべての頂点を連結にすることである。そのために、まだグラフに追加していない辺のうちちょうど 1 本を選んでグラフに追加する、という操作を任意の回数行うことができる。ただし、どの瞬間においても次の条件が成り立っていなければならない。

  • グラフのどの連結成分についても、(頂点の重みの総和)\geq(辺の重みの総和) である。

すべての頂点を連結にできるか判定せよ。できるならば、グラフに辺を追加していく方法を一つ出力せよ。

Constraints

  • 2\leq N\leq10^5
  • a_i は整数，0\leq a_i\leq10^9
  • 1\leq M\leq10^5
  • 1\leq x_i<y_i\leq N
  • z_i は整数，0\leq z_i\leq10^9

Input Format

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

N M
a_1 a_2 ... a_N
x_1 y_1 z_1
x_2 y_2 z_2
:
x_M y_M z_M

Output Format

すべての頂点を連結にできないならば、-1 とだけ一行に出力せよ。

すべての頂点を連結にできるならば、グラフに辺を追加していく方法を一つ次のように出力せよ。

  • 1 行目には、グラフに追加する辺の本数 m (1\leq m\leq M) を出力せよ。
  • 2 行目からの m 行のうち k 行目には、k 番目にグラフに追加する辺の番号 i_k (1\leq i_k\leq M) を出力せよ。

Sample Input 1

4 3
50 0 0 50
1 2 0
2 3 100
3 4 0

Sample Output 1

3
1
3
2

2 番目の辺を追加するのは最後でなければならない。

Sample Input 2

2 3
50 50
1 2 100
1 2 101
1 2 102

Sample Output 2

1
1

多重辺が含まれている。

Sample Input 3

3 1
50 50 50
1 2 100

Sample Output 3

-1

すべての辺をグラフに追加しても、すべての頂点を連結にできない。

K - Leapfrog

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

N 個のマスが円状に並んでいる。マスは時計回りに 1,\ 2,\ ...,\ N と番号が振られている。各 i (1\leq i\leq N-1) について、i 番目のマスと i+1 番目のマスは隣り合う。また、N 番目のマスと 1 番目のマスは隣り合う。

これらのうち M 個のマスには、互いに区別できない駒が 1 個ずつ置かれている。はじめ、x_1,\ x_2,\ ...,\ x_M 番目のマスに駒が置かれている。次の操作を何回か行い、y_1,\ y_2,\ ...,\ y_M 番目のマスに駒が置かれているようにしたい。

  • 時計回りまたは反時計回りに連続する 3 個のマスを選び、順に A,\ B,\ C とおく。A と B にそれぞれ駒があり C に駒がないならば、A の駒を C へ移動する。

y_1,\ y_2,\ ...,\ y_M 番目のマスに駒が置かれているようにできるか判定せよ。できるならば、必要な操作の回数の最小値を求めよ。

Constraints

  • 3\leq N\leq 3,000
  • 1\leq M\leq N
  • 1\leq x_1<x_2<...<x_M\leq N
  • 1\leq y_1<y_2<...<y_M\leq N

Input Format

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

N M
x_1 x_2 ... x_M
y_1 y_2 ... y_M

Output Format

y_1,\ y_2,\ ...,\ y_M 番目のマスに駒が置かれているようにできるならば、必要な操作の回数の最小値を一行に出力せよ。できないならば、代わりに -1 を一行に出力せよ。

Sample Input 1

7 2
1 2
5 6

Sample Output 1

3

次のように 3 回の操作を行えばよい。

  • 2 番目のマスの駒を 7 番目のマスへ移動する。
  • 1 番目のマスの駒を 6 番目のマスへ移動する。
  • 7 番目のマスの駒を 5 番目のマスへ移動する。

Sample Input 2

3 1
1
2

Sample Output 2

-1

Sample Input 3

2999 3
1 2 3
2 3 4

Sample Output 3

4491004