CodeTON Round 1 (Div. 1 + Div. 2, Rated, Prizes!) 問題文和訳

A. Good Pairs / Хорошие пары (500点)
- 入力
- 出力
- 入出力例
- 注記
B. Subtract Operation / Операция вычитания (1000点)
- 入力
- 出力
- 入出力例
- 注記
C. Make Equal With Mod / Сделай равным по модулю (1500点)
- 入力
- 出力
- 入出力例
- 注記
D. K-good / K-хорошие (2000点)
- 入力
- 出力
- 入出力例
- 注記
E. Equal Tree Sums / Одинаковые суммы деревьев (2500点)
- 入力
- 出力
- 入出力例
- 注記
F. Parametric MST / Параметрическое MST (3000点)
G. Cycle Palindrome / Циклические палиндромы (3250点)
H. Equal LCM Subsets / Одинаковые НОК подмножеств (3750点)
I. Neighbour Ordering / Упорядочивание соседей (4500点)

A. Good Pairs / Хорошие пары (500点)

テストごとの時間制限: 1秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力

正整数配列 $a_1,\,a_2,\,\dots,\,a_n$ が与えられます。全ての $1 \leq k \leq n$ について次の等式が成り立つような $1 \leq i,\,j \leq n$ の添え字の組を良い組と呼びます。

$|a_i - a_k| + |a_k - a_j| = |a_i - a_j|$

ここで $|x|$ は $x$ の絶対値を表します。

良い組を求めて下さい。 $i$ と $j$ は等しくてもよいことに注意してください。

入力

入力は複数のテストケースから成る。1行目には単一の整数 $t$ $(1 \leq t \leq 1000)$ が与えられる、これはテストケースの個数である。以下、テストケースの記述が続く。

各テストケースの1行目には1個の整数 $n$ $(1 \leq n \leq 10^5)$ が与えられる、これは配列の長さである。

各テストケースの2行目には $n$ 個の整数 $a_1,\,a_2,\,\dots,\,a_n$ $(1 \leq a_i \leq 10^9)$ が与えられる、 $a_i$ は配列内の $i$ 番目の要素である。

全てのテストケースでの $n$ の和は $2 \cdot 10^5$ 以下である。

出力

各テストケースについて、良い組を構成する2個の添え字 $i,\,j$ をスペース区切りで単一の行に出力せよ。 $i = j$ の場合も許容される。このようなペアは常に存在することは証明できる。良い組が複数存在する場合、そのいずれかを出力せよ。

入出力例

2 3
1 2
1 1

注記

1つ目のテストケースでは、 $i = 2,$ $j = 3$ の場合、全ての $k$ について等式が成立します。

$k = 1:$ $|a_2 - a_1| + |a_1 - a_3| = |2 - 5| + |5 - 7| = 5 = |2 - 7| = |a_2 - a_3|$
$k = 2:$ $|a_2 - a_2| + |a_2 - a_3| = |2 - 2| + |2 - 7| = 5 = |2 - 7| = |a_2 - a_3|$
$k = 3:$ $|a_2 - a_3| + |a_3 - a_3| = |2 - 7| + |7 - 7| = 5 = |2 - 7| = |a_2 - a_3|$

B. Subtract Operation / Операция вычитания (1000点)

テストごとの時間制限: 1秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力

$n$ 個の整数から成るリストが与えられます。次のような操作を行うことができます: リストから1つの要素 $x$ を選び、リストから $x$ を削除し、残った全ての要素から $x$ の値を引くという操作。そのため、1回の操作でリストの長さはちょうど $1$ だけ短くなります。

整数 $k$ $(k \gt 0)$ が与えられた時、その操作を施した後の、リスト内の唯一の要素が $k$ と等しくなるような $n-1$ 回の操作列が存在するかどうかを判定してください。

入力

入力は複数のテストケースから成る。1行目には単一の整数 $t$ $(1 \leq t \leq 10^4)$ が与えられる、これはテストケースの個数である。以下、テストケースの記述が続く。

各テストケースの1行目には2個の整数 $n,\,k$ $(2 \leq n \leq 2 \cdot 10^5,$ $1 \leq k \leq 10^9)$ が与えられる、それぞれリスト内の整数の個数と目標値である。

各テストケースの2行目には $n$ 個の整数 $a_1,\,a_2,\,\dots,\,a_n$ $(1 \leq a_i \leq 10^9)$ が与えられる。

全てのテストケースでの $n$ の和が $2 \cdot 10^5$ を超えないことは保証されている。

出力

各テストケースについて、 $n-1$ 回の操作で $k$ にすることができるのであればYESと出力せよ。そうでなければNOと出力せよ。

各文字はどのレターケースで出力してもよい(例えば、文字列"YES", "Yes", "yes", "yEs"は肯定とみなされる)。

入出力例

YES
NO
YES
NO

注記

1つ目の入力例では、リストは $\{4,\,2,\,2,\,7\}$ で、目標 $k = 5$ です。この目標を達成する方法の1つは次の通りです。まず、3番目の要素を選び、リストは $\{2,\,0,\,5\}$ となります。次に、1番目の要素を選び、リストは $\{-2,\,3\}$ となります。最後に、1番目の要素を選び、リストは $\{5\}$ となります。

C. Make Equal With Mod / Сделай равным по модулю (1500点)

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力

$n$ 個の非負整数から成る配列 $a_1,\,a_2,\,\dots,\,a_n$ が与えられる。次のような操作を行うことができます。整数 $x \geq 2$ を選び、配列内の各数を $x$ で割った時の余りで置き換えます。即ち、全ての $1 \leq i \leq n$ について、 $a_i$ を $a_i \bmod x$ に置き換えます。

この操作を0回以上行うことで配列の全要素を等しくすることが可能かどうか判定してください。

入力

各テストケースの1行目には1個の整数 $n$ $(1 \leq n \leq 10^5)$ が与えられる、配列の長さである。

各テストケースの2行目には $n$ 個の整数 $a_1,\,a_2,\,\dots,\,a_n$ $(1 \leq a_i \leq 10^9)$ が与えられる、 $a_i$ は配列内の $i$ 番目の要素である。

全てのテストケースでの $n$ の和は $2 \cdot 10^5$ 以下である。

出力

各テストケースについて、操作後のリスト内の全要素を等しくすることができるのであればYESと出力せよ。そうでなければNOと出力せよ。

各文字はどのレターケースで出力してもよい(例えば、文字列"YES", "Yes", "yes", "yEs"は肯定とみなされる)。

入出力例

YES
YES
NO
YES

注記

1つ目のテストケースでは、 $x = 3$ で操作を行うことで、配列 $[2,\,2,\,0,\,2]$ を得、 $x = 2$ で操作を行うことで、配列 $[0,\,0,\,0,\,0]$ を得ます。

2つ目のテストケースでは、全数は既に等しいです。

4つ目のテストケースでは、 $x = 4$ で操作を行うことで、配列 $[1,\,1,\,1,\,1]$ を得ます。

D. K-good / K-хорошие (2000点)

テストごとの時間制限: 3秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力

ある正の整数 $k$ について、 $k$ で割ったときに異なる $k$ 個の余りとなる $k$ 個の正整数の和として $n$ を表すことができるとき、正整数 $n$ は $k$ -goodであるといいます。

正整数 $n$ が与えられたとき、 $n$ が $k$ -goodであるような $k \geq 2$ を求めて下さい、もしくは、そのような $k$ が存在しないことを判別してください。

入力

入力は複数のテストケースから成る。1行目には単一の整数 $t$ $(1 \leq t \leq 10^5)$ が与えられる、これはテストケースの個数である。

各テストケースは1行から成り、1個の整数 $n$ $(2 \leq n \leq 10^{18})$ が与えられる。

出力

各テストケースについて、1行に $n$ が $k$ -good $(k \geq 2)$ となるような $k$ の値を出力せよ、あるいは、どのような $k$ に対しても $n$ が $k$ -goodでない場合は $-1$ と出力せよ。有効な $k$ の値が複数存在する場合は、そのいずれをも出力してももよい。

入出力例

注記

$6$ は次のように $3$ で割った時の余りが異なる $3$ 数の和として表せるため $3$ -goodです: $6 = 1 + 2 + 3$ 。

$15 = 1 + 5 + 9$ であり、 $1,\,5,\,9$ は $3$ で割った時、異なる余りを与えるため、 $15$ は $3$ -goodです。

$20 = 2 + 3 + 4 + 5 + 6$ であり、 $2,\,3,\,4,\,5,\,6$ は $5$ で割った時、異なる余りを与えるため、 $20$ は $5$ -goodです。

E. Equal Tree Sums / Одинаковые суммы деревьев (2500点)

テストごとの時間制限: 1秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力

根なしの無向木、即ちサイクルなしの連結無向グラフが与えられます。

次の条件を満たすように、各頂点に非零整数の重みを割り当てる必要があります: 木の任意の頂点を削除した時、残りの連結成分の各頂点の重みの和が等しい。

入力

入力は複数のテストケースから成る。1行目には単一の整数 $t$ $(1 \leq t \leq 10^5)$ が与えられる、これはテストケースの個数である。以下、テストケースの記述が続く。

各テストケースの1行目には1個の整数 $n$ $(1 \leq n \leq 10^5)$ が与えられる、木の頂点数である。

続く $n-1$ 行の各行には2個の整数 $u,\,v$ $(1 \leq u,\,v \leq n)$ が与えられる、頂点 $u$ と $v$ の間に辺があることを表す。与えられる辺が木を構成することは保証されている。

全てのテストケースでの $n$ の和は $10^5$ 以下である。

出力

各テストケースについて、1行に $n$ 個の空白区切りの整数 $a_1,\,a_2,\,\dots,\,a_n$ を出力せよ、ここでの $a_i$ は頂点 $i$ に割り当てられた重みである。重みは $-10^5 \leq a_i \leq 10^5$ かつ $a_i \neq 0$ を満たさなければならない。

これらの制約を満たす解が必ず存在することは証明できる。解が複数存在する場合は、そのいずれかを出力せよ。

入出力例

-3 5 1 2 2
1 1 1

注記

1つ目のテストケースでは、頂点 $1$ を削除した時の残りの連結成分の和は全て $5$ であり、頂点 $3$ を削除した時の残りの連結成分の和は全て $2$ となります。他の頂点を削除した場合は、残りの連結成分は1個であるため、連結成分の和は全て等しくなります。

F. Parametric MST / Параметрическое MST (3000点)

テストごとの時間制限: 1秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力

$n$ 個の整数 $a_1,\,a_2,\,\dots,\,a_n$ が与えられます。任意の実数 $t$ について、頂点 $i$ と $j$ 間の辺の重みを $w_{ij}(t) = a_i \cdot a_j + t \cdot (a_i + a_j)$ とする $n$ 頂点の完全重み付きグラフ $K_n(t)$ を考えてください。

$f(t)$ を $K_n(t)$ の最小全域木 *1のコストとします。 $f(t)$ が上に有界であるかどうかを判別し、そうである場合、その最大値を出力して下さい。

入力

入力は複数のテストケースから成る。1行目には単一の整数 $T$ $(1 \leq T \leq 10^4)$ が与えられる、これはテストケースの個数である。以下、テストケースの記述が続く。

各テストケースの1行目には1個の整数 $n$ $(1 \leq n \leq 10^5)$ が与えられる、これはグラフの頂点数である。

各テストケースの2行目には $n$ 個の整数 $a_1,\,a_2,\,\dots,\,a_n$ $(1 \leq a_i \leq 10^9)$ が与えられる。

全てのテストケースでの $n$ の和は $2 \cdot 10^5$ 以下である。

出力

各テストケースについて単一行に $f(t)$ の最大値(整数であることは証明できる)を、もしくは $f(t)$ が上に有界でない場合はINFを出力せよ。

入出力例

INF
-1
INF
-6
-18

G. Cycle Palindrome / Циклические палиндромы (3250点)

テストごとの時間制限: 1秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力

全ての $1 \leq i \leq n$ について $a_i = a_{n-i+1}$ が成立するとき、 $n$ 個の整数の列 $a_1,\,a_2,\,\dots,\,a_n$ は回文であるといいます。 $n$ 個の整数の列 $a_1,\,a_2,\,\dots,\,a_n$ が与えられた時、列 $a_{\sigma(1)},\,a_{\sigma(2)},\,\dots,\,a_{\sigma(n)}$ が回文であるような周期順列 $\sigma$ が存在するかを判別してください。

$1,\,2,\,\dots,\,n$ の順列とは $\{1,\,2,\,\dots,\,n\}$ から $\{1,\,2,\,\dots,\,n\}$ への全単射函数のことです。 $1,\,\sigma(1),\,\sigma^2(1),\,\dots,\,\sigma^{n-1}(1)$ が相異なる数であるとき、順列 $\sigma$ は周期順列であるといいます。ここで $\sigma^m(1)$ は $\underbrace{\sigma(\sigma(\ldots \sigma}_{m \text{個}}(1) \ldots))$ を表します。

入力

入力は複数のテストケースから成る。1行目には単一の整数 $t$ $(1 \leq t \leq 3 \cdot 10^4)$ が与えられる、これはテストケースの個数である。以下、テストケースの記述が続く。

各テストケースの1行目には1個の整数 $n$ $(2 \leq n \leq 2 \cdot 10^5)$ が与えられる、これは列の大きさである。

各テストケースの2行目には $n$ 個の整数 $a_1,\,a_2,\,\dots,\,a_n$ $(1 \leq a_i \leq n)$ が与えられる。

全てのテストケースでの $n$ の和は $2 \cdot 10^5$ 以下である。

出力

各テストケースについて、周期順列が存在する場合、YESと出力せよ、そうでなければNOと出力せよ。

答えがYESである場合、追加の1行に順列である $n$ 個の整数 $\sigma(1),\,\sigma(2),\,\dots,\,\sigma(n)$ を出力せよ。順列が複数存在するならば、いずれを出力してもよい。

入出力例

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

YES
3 1 4 2 
NO
YES
5 3 7 2 6 4 1

H. Equal LCM Subsets / Одинаковые НОК подмножеств (3750点)

テストごとの時間制限: 10秒
テストごとのメモリ制限: 512 MB
入力: 標準入力
出力: 標準出力

正整数の集合が2つ $A,\,B$ が与えられます。 $S_A$ の要素の最小公倍数(LCM)と $S_B$ の要素の最小公倍数(LCM)が等しくなるように、空でない二つの部分集合 $S_A \subseteq A,$ $S_B \subseteq B$ を求めなければなりません。

入力

入力は複数のテストケースから成る。1行目には1個の整数 $t$ $(1 \leq t \leq 200)$ が与えられる、これはテストケースの個数である。

各テストケースについて、2個の整数 $n,\,m$ $(1 \leq n,\,m \leq 1000)$ から成る1行が与えられる、それぞれ集合 $A$ と $B$ の大きさである。

次の行には $n$ 個の相異なる整数 $a_1,\,a_2,\,\dots,\,a_n$ $(1 \leq a_i \leq 4 \cdot 10^{36})$ が与えられる、これらは $A$ の要素である。

次の行には $m$ 個の相異なる整数 $b_1,\,b_2,\,\dots,\,b_m$ $(1 \leq b_i \leq 4 \cdot 10^{36})$ が与えられる、これらは $B$ の要素である。

全てのテストケースでの $n$ の和と $m$ の和は $1000$ 以下である。

出力

各テストケースについて、最小公倍数が等しい2つの部分集合が存在しない場合、1行にNOで出力せよ。

そうでない場合、1行にYESと出力し、続く行に2個の整数 $|S_A|,\,|S_B|$ $(1 \leq |S_A| \leq n,$ $1 \leq |S_B| \leq m)$ を出力せよ、これらはそれぞれ部分集合 $S_A,\,S_B$ の大きさである。

次の行には $S_A$ の要素である $|S_A|$ 個の整数 $x_1,\,x_2,\,\dots,\,x_{|S_A|}$ を出力し、その次の行には $S_B$ の要素である $|S_B|$ 個の整数 $y_1,\,y_2,\,\dots,\,y_{|S_B|}$ を出力せよ。あり得る部分集合の組が複数存在する場合、いずれを出力してもよい。

入出力例

4
3 4
5 6 7
2 8 9 10
4 4
5 6 7 8
2 3 4 9
1 3
1
1 2 3
5 6
3 4 9 7 8
2 15 11 14 20 12

NO
YES
1 2
6
2 3
YES
1 1
1
1
YES
3 2
3 7 4
12 14

I. Neighbour Ordering / Упорядочивание соседей (4500点)

テストごとの時間制限: 5秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力

無向グラフ $G$ が与えられた時、 $G$ の各頂点について、全ての隣接頂点の順序付きリストを隣接順序といいます。 $G$ の隣接順序と、 $v$ が $u$ と $w$ の隣接頂点であるような3頂点 $u,\,v,\,w$ を考えてください。 $v$ の隣接リスト内で $u$ が $w$ の後に来る時、 $u \lt_v w$ と書きます。

グラフの各単純サイクル $v_1,\,v_2,\,\dots,\,v_c$ について、以下のいずれかを満たすとき、隣人順序は良いといいます。

$v_1 \lt_{v_2} v_3,\,v_2 \lt_{v_3} v_4,\,\dots,\,v_{c-2} \lt_{v_{c-1}} v_c,\,v_{c-1} \lt_{v_c} v_1,\,v_c \lt_{v_1} v_2$
$v_1 \gt_{v_2} v_3,\,v_2 \gt_{v_3} v_4,\,\dots,\,v_{c-2} \gt_{v_{c-1}} v_c,\,v_{c-1} \gt_{v_c} v_1,\,v_c \gt_{v_1} v_2$

与えられた $G$ について、そのグラフに良い隣接順序が存在するかどうかを判別し、存在する場合はそれを構築して下さい。

入力

入力は複数のテストケースから成る。1行目には1個の整数 $t$ $(1 \leq t \leq 10^4)$ が与えられる、これはテストケースの個数である。以下、テストケースの記述が続く。

各テストケースの1行目には2個の整数 $n,\,m$ $(2 \leq n \leq 3 \cdot 10^5,$ $1 \leq m \leq 3 \cdot 10^5)$ が与えられる、グラフの頂点数と辺の本数である。

続く $m$ 行の各行には2個の整数 $u,\,v$ $0 \leq u,\,v \leq n)$ が与えられる、これは頂点 $u,\,v$ 間をつなぐ辺があることを表す。グラフには自己辺も同一頂点間の多重辺も存在しないことは保証されている。

全てのテストケースでの $n$ の和と $m$ の和は $3 \cdot 10^5$ 以下である。

出力

各テストケースについて、1行に、良い隣接順序が存在する場合はYESと、そうでなければNOと出力せよ。各文字はどのレターケース(大文字/小文字)で出力してもよい。

答えがYESである場合、さらに、良い隣接順序について記述した $n$ 行を出力せよ。 $i$ 行目には、頂点 [tex;i] の隣接頂点を順番に出力せよ。

良い隣接順序が複数存在する場合は、そのいずれかを出力せよ。

入出力例

*1:原文では英語/ロシア語の、全域木ではなく最小全域木のWikipediaのページへのリンク