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

Codeforces 競技プログラミング Codeforces 和訳 CodeTON 和訳

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 の場合も許容される。このようなペアは常に存在することは証明できる。良い組が複数存在する場合、そのいずれかを出力せよ。

入出力例

3
3
5 2 7
5
1 4 2 2 3
1
2
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"は肯定とみなされる)。

入出力例

4
4 5
4 2 2 7
5 4
1 9 1 3 4
2 17
17 0
2 17
18 18
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行目には単一の整数 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) が与えられる、a_i は配列内の i 番目の要素である。

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

出力

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

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

入出力例

4
4
2 5 6 8
3
1 1 1
5
4 1 7 0 8
4
5 9 17 5
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 の値が複数存在する場合は、そのいずれをも出力してももよい。

入出力例

5
2
4
6
15
20
-1
-1
3
3
5

注記

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 を満たさなければならない。

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

入出力例

2
5
1 2
1 3
3 4
3 5
3
1 2
1 3
-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を出力せよ。

入出力例

5
2
1 0
2
-1 1
3
1 -1 -2
3
3 -1 -2
4
1 2 3 -4
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] の隣接頂点を順番に出力せよ。

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

入出力例

3
5 6
0 1
0 2
1 2
2 3
3 4
4 1
2 1
0 1
6 10
0 1
2 0
0 3
0 4
1 2
1 4
2 3
2 5
3 5
4 5
YES
1 2 
4 2 0 
0 1 3 
2 4 
3 1 
YES
1 
0 
NO

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

Educational Codeforces Round 124 問題文和訳

Codeforces 競技プログラミング Codeforces 和訳 Educational Codeforces Round 和訳

A. Playoff / Плей-офф

テストごとの時間制限: 2秒
テストごとのメモリ制限: 512 MB
入力: 標準入力
出力: 標準出力
2^n 人の選手が出場するプレーオフトーナメントを考えます。選手には 1 から 2^n の番号が振られています。

トーナメントは n ラウンドで行われます。各ラウンドでは、各選手が、ちょうど1つの組に属するように組み分けを行います。それぞれの組で選手が競い合い、どちらかが勝ちます。勝者は次のラウンドに進み、敗者はトーナメントから脱落します。

組み分けは次のように行われます。

  • 第1回戦では、選手 1 と選手 2、選手 3 と選手 4、選手 5 と選手 6、…というように戦います。
  • 第2回戦では、1-2 の試合の勝者と 3-4 の試合の勝者、5-6 の試合の勝者と 7-8 の試合の勝者、…というように戦います。
  • その後のラウンドも同じルールで行われます。

選手 x と y が戦ったとき、勝者は次のように決まります。

  • x+y が奇数の場合、番号が小さい選手が勝つ(つまり、x \lt y なら x が勝ち、そうでないなら y が勝つ)
  • x+y が偶数の場合、番号が大きい選手が勝つ

次図は、n=3 の時のトーナメントの様子です。
f:id:Flkanjin:20220311134131p:plain
ここでの課題は、「整数 n が与えらえれたとき、優勝する選手の番号を判別すること」です。

入力

1行目には単一の整数 t (1 \leq t \leq 30) が与えられる、これはテストケースの個数である。

各テストケースは1行から成り、1個の整数 n (1 \leq n \leq 30) が与えられる。

出力

各テストケースについて、1個の整数を出力せよ、その数とはトーナメントの勝者の番号である。

入出力例

2
3
1
7
1

注記

n=3 の場合は、問題文中の図に示されています。

n=1 の場合、選手 1 と 2 の試合1回だけが行われます。1 + 2 = 3 は奇数であるため、番号の小さい方の選手が勝ちます。よって、選手 1 が勝者となります。

B. Prove Him Wrong / Докажи, что он не прав

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
最近、貴方の友人は整数の配列 a についてある興味深い操作を発見しました。

  1. 2つのインデックス i,\,j (i \neq j)
  2. a_i = a_j = |a_i - a_j| とする*1

この操作でしばらく遊んでいたら、彼は次のような結論に達しました。

  • 1 \leq a_i \leq 10^9 である n 個の整数のどのような配列 a に対しても、操作後に a の総和が減少するようなインデックスの組 (i,\,j) が見つけることができる*2

この文は疑わしいと思っているため、与えられた n について反例を見つけたいと思っています。反例を見つけ、彼が間違っていると証明できるでしょうか?

言い換えると、どのようなインデックスの組 (i,\,j) に対しても操作後に総和が減少しない(増加、または変化なし)ような n 個の整数 a_1,\,a_2,\,\dots,\,a_n (1 \leq a_i \leq 10^9) からなる配列 a を見つけてください。

入力

1行目には単一の整数 t (1 \leq t \leq 100) が与えられる、これはテストケースの個数である。その後、t 個のテストケースが続く。

各テストケースの1行目にして唯一の行には、単一の整数 n (2 \leq n \leq 1000) が与えられる、これは配列 a の長さである。

出力

各テストケースについて、反例である大きさ n の配列 a が存在しない場合、NOと出力せよ。

そうでない場合、YESと出力し、その後、配列 a 自身 (1 \leq a_i \leq 10^9) を続けて出力せよ。反例が複数存在する場合、そのうちにいずれかを出力せよ。

入出力例

3
2
512
3
YES
1 337
NO
YES
31 4 159

注記

1つ目のテストケースでは、有効なインデックスの組は (1,\,2), (2,\,1) のみです。

インデックス (1,\,2)(または (2,\,1))に対して操作を行うと、a_1 = a_2 = |1-337| = 336、つまり、配列 [336,\,336] を得ます。どちらの場合も操作が増加するため、この配列 a は反例となります。

C. Fault-tolerant Network / Отказоустойчивая сеть

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
コンピュータが2列に並んでいる教室があります。各列には n 台のコンピュータが置かれていて、各コンピュータはそれぞれ等級で分類されている。1列目のコンピュータの等級は a_1,\,a_2,\,\dots,\,a_n であり、2列目のコンピュータの等級は b_1,\,b_2,\,\dots,\,b_n です。

初期状態では、各列の隣接するコンピュータの組(全ての 1 \leq i \lt n について組 (i,\,i+1))はワイヤーでつながれていて、2列が2つの独立したコンピュータネットワークを形成しています。

ここでの課題は、「1つ以上の異なる列のコンピュータの組を繋ぐことで1つの共通ネットワークに結合する」ことです。1列目の i 台目のコンピュータと2列目の j 台目のコンピュータを繋ぐには |a_i - b_j| のコストがかかります。

1台のコンピュータを他の複数のコンピュータと接続することはできますが、少なくとも基本的な障害耐性(フォールトトレランス)を確保する必要があります、即ち、1台のコンピュータが故障しても、ネットワークがつながったままになるようにコンピュータを接続する必要があります。言い換えれば、1台のコンピュータが故障しても(それがどのコンピュータであっても)、ネットワークが2つ以上に分かれないようにするということです。

障害耐性ネットワークを構築するために必要は最小コストはいくつでしょう?

入力

1行目には単一の整数 t (1 \leq t \leq 10^4) が与えられる、これはテストケースの個数である。その後、t 個のテストケースが続く。

各テストケースの1行目には、単一の整数 n (3 \leq n \leq 2 \cdot 10^5) が与えられる、これは各列のコンピュータの台数である。

各テストケースの2行目には、n 個の整数 a_1,\,a_2,\,\dots,\,a_n (1 \leq a_i \leq 10^9) が与えられる、これらは1列目のコンピュータの等級である。

各テストケースの3行目には、n 個の整数 b_1,\,b_2,\,\dots,\,b_n (1 \leq b_i \leq 10^9) が与えられる、これらは2列目のコンピュータの等級である。

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

出力

各テストケースについて単一の整数を出力せよ、その数とは障害耐性ネットワークを構築するために必要は最小コストである。

入出力例

2
3
1 10 1
20 4 25
4
1 1 1 1
1000000000 1000000000 1000000000 1000000000
31
1999999998

注記

1つ目のテストケースでは、4組のコンピュータを接続するのが最適です。

  • 1列目のコンピュータ 1 と2列目のコンピュータ 2: コスト |1-4| = 3
  • 1列目のコンピュータ 3 と2列目のコンピュータ 2: コスト |1-4| = 3
  • 1列目のコンピュータ 2 と2列目のコンピュータ 1: コスト |10-20| = 10
  • 1列目のコンピュータ 2 と2列目のコンピュータ 3: コスト |10-25| = 15

合計で、3+3+10+15=31 です。

2つ目のテストケースでは、1列目の 1 と2列目の 1、1列目の 4 と2列目の 4 を接続するのが最適です。

D. Nearest Excluded Points / Ближайшие точки

テストごとの時間制限: 4秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
平面上の相異なる n 個の点が与えられます。i 番目の点の座標は (x_i,\,y_i) です。

各点 i について、与えられた n 点に含まれない、(マンハッタン距離で)最も近い整数座標の点を求めて下さい。そのような点が複数存在する場合、どれを選んでもいいです。

2点 (x_1,\,y_1), (x_2,\,y_2) 間のマンハッタン距離は |x_1-y_1| + |x_2-y_2| です。

入力

1行目には単一の整数 t (1 \leq t \leq 10^4) が与えられる、これはテストケースの個数である。その後、t 個のテストケースが続く。

続く n 行は点についての説明である。その i 行目には2個の整数 x_i,\,y_i (1 \leq x_i,\,y_i \leq 2 \cdot 10^5) が与えられる、これは i 番目の点の座標である。

入力内の全ての点が相異なることは保証されている。

出力

n 行出力せよ。i 行目には与えられた n 点に含まれない、i 番目の点から(マンハッタン距離で)最も近い整数座標の点を出力せよ。

出力する座標は範囲 [-10^6;\,10^6] 内でなければならない。どのような最適解もこれらの制約を満たすことは証明することができる。

答えが複数存在する場合、どれを出力してもよい。

入出力例

6
2 2
1 2
2 1
3 2
2 3
5 5
1 1
1 1
2 0
3 1
2 4
5 4
8
4 4
2 4
2 2
2 3
1 4
4 2
1 3
3 3
4 3
2 5
2 1
2 5
1 5
4 1
1 2
3 2

E. Sum of Matchings / Сумма паросочетаний

テストごとの時間制限: 4秒
テストごとのメモリ制限: 512 MB
入力: 標準入力
出力: 標準出力
グラフ G の最大マッチングの大きさを MM(G) とします。

2部グラフが与えられます。第1部の頂点には 1 から n までの、第2部の頂点委は n+1 から 2n までの番号が振られています。各頂点の次数は 2 です。

1 \leq l \leq rleq n かつ n+1 \leq L \leq R \leq 2n を満たす整数4つ組 (l,\,r,\,L,\,R) について、区間 [l,\,r] または区間 [L,\,R] に含まれる与えられたグラフの全ての頂点と、端点がこれらの区間どちらかに属する与えられたグラフの辺から成るグラフを G’(l,\,r,\,L,\,R) と定義します。即ち、元のグラフから G’(l,\,r,\,L,\,R) を得るには、i \notin [l,\,r] かつ i \notin [L,\,R] を満たす全ての頂点 i と、これらの頂点にくっついている全ての辺を削除しなければなりません。

1 \leq l \leq r \leq n かつ n+1 \leq L \leq R \leq 2n を満たす全ての整数の組 (l,\,r,\,L,\,R) に対する MM(G(l,\,r,\,L,\,R))*3 の和を計算してください。

入力

1行目には単一の整数 n (2 \leq n \leq 1500) が与えられる、これは各部の頂点数である。

2n 行が続き、各行はグラフの辺を表す。i 行目には2個の整数 x_i,\,y_i (1 \leq x_i \leq n; n+1 \leq y_i \leq 2n) が与えられる、これらは i 本目の辺の端点である。

与えられるグラフには多重辺はなく、各頂点はちょうど2本の接続辺を持つ。

出力

各テストケースについて単一の整数を出力せよ、その数とは、1 \leq l \leq r \leq n かつ n+1 \leq L \leq R \leq 2n を満たす全ての整数の組 (l,\,r,\,L,\,R) に対する MM(G(l,\,r,\,L,\,R)) の和である。

入出力例

5
4 6
4 9
2 6
3 9
1 8
5 10
2 7
3 7
1 10
5 8
314

F. Tower Defense

テストごとの時間制限: 4秒
テストごとのメモリ制限: 512 MB
入力: 標準入力
出力: 標準出力
Монокарп(Monocarp)*4はタワーディフェンスゲームをプレイしています。このゲームのレベルはOX軸で表すことができ、その軸上の 1 から n までの各格子点には塔が立っています。

i 番目の地点の塔のマナ容量は c_i でマナ再生率は r_i です。初期状態 0 秒時点では、各塔のマナは最大値です。ある秒数立った時点で i 番目の塔のマナ量が x である場合、その 1 秒後には min(x+r_i,\,c_i) マナになります。

1 つのレベルにはモンスターが q 体登場します。j 体目のモンスターは t_j 秒後に体力 h_j で地点 1 にスポーンします。各モンスターは、座標が増加する方向に毎秒 1 ポイントずつ移動します。

モンスターが塔を通過するとき、塔はモンスターに min(H,\,M) ダメージを与えます、ここでの H はモンスターの現在体力で、M はタワーの現在マナ量です。この値をモンスターの体力とタワーのマナ量から差し引きます。

残念なことに、塔を全て通過してしまうモンスターがいることもあります。Монокарпは、全ての塔を通過した後のモンスターの体力の総和を知りたいと思っています。

入力

1行目には単一の整数 n (1 \leq n \leq 2 \cdot 10^5) が与えられる、これは塔の個数である。

続く n 行の i 行目には、2個の整数 c_i,\,r_i (1 \leq r_i \leq c_i \leq 10^9) が与えられる、これらは i 番目の塔のマナ容量とマナ再生率である。

次の行には単一の整数 q (1 \leq q \leq 2 \cdot 10^5) が与えられる、これはモンスターの数である。

続く q 行の j 行目には、2個の整数 t_j,\,h_j (0 \leq t_j \leq 2 \cdot 10^5; 1 \leq h_j \leq 10^{12}) が与えられる、これらは j 体目のモンスターのスポーン位置と体力である。

モンスターはスポーン時間の昇順に並んでいるため、全ての 1 \leq j \leq q -1 について t_j \lt t_{j+1} が成立する。

出力

単一の整数を出力せよ、その数とは全ての塔を通過した後のモンスターの体力の総和である。

入出力例

3
5 1
7 4
4 2
4
0 14
1 10
3 16
10 16
4
5
2 1
4 1
5 4
7 5
8 3
9
1 21
2 18
3 14
4 24
5 8
6 25
7 19
8 24
9 24
40

*1:正確には a_i と a_j に |a_i - a_j| を代入

*2:\forall a; \exists (i, j) s.t. … という形式

*3:恐らく MM(G'(l,\,r,\,L,\,R) ) の間違い

*4:モノカルプ、モノカープ: ロシア男性名Поликарп(Polycarp)をもじった名前であると思われる。英単語としては一巡植物を意味する

Codeforces Round #776 (Div. 3) 問題文和訳

Codeforces 競技プログラミング Codeforces 和訳 Codeforces Div. 3 和訳

A. Deletions of Two Adjacent Letters / Удаления двух соседних букв

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
文字列 s が与えられます。その文字列の長さは奇数で、ラテン文字の小文字から成ります。

文字列の長さが 1 よりも大きい限り、次の操作を行うことができます: 文字列 s 内の任意の隣接する2文字を選び、それを文字列から削除するという操作です。例えば、文字列"lemma"に操作を一度行うと、次の4つの文字列のいずれかを得ることができます: "mma", "lma", "lea", "lem"。具体的には、1回の操作で、文字列の長さは 2 だけ短くなります。

形式的にが、文字列 s を s = s_1s_2\dots s_n (n \gt 1) という形で表されるとします。1回の操作で、任意のインデックス1 (1 \leq i \lt n) を選び、s = s_1s_2\dots s_{i-1}s_{i+2}\dots s_n に置き換えます。

与えられた文字列 s と文字 c について、最終的に等式 s=c が成立するような一連の操作が可能であるか判別して下さい。即ち、文字 c から成る長さ 1 の文字列で処理が終了するような一連の操作は存在するでしょうか?

入力

入力データの1行目には1個の整数 t (1 \leq t \leq 10^3) が与えられる、これは入力のテストケース数である。

t 個のテストケースの説明が続く。各テストケースは2行で表される。

  • 1 から 49 までの奇数長で、ラテンアルファベットの小文字で構成される文字列 s
  • ラテンアルファベットの小文字1文字 c から成る文字列

出力

各テストケースについて、別々の行に次を出力せよ。

  • 文字列 s を s = c が真となるように変換できる場合、YES
  • そうでない場合、NO

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

入出力例

5
abcde
c
abcde
b
x
y
aaaaaaaaaaaaaaa
a
contest
t
YES
NO
NO
YES
YES

注記

1つ目のテストケースでは、s = "abcde"です。s = "c"にしなければなりません。1回目の操作では、最初の2文字を消し、s = "cde"となります。2回目の操作で最後の2文字を消し、期待される値 s = "c"を得ます。

3つ目のテストケースでは、s = "x"で、s = "y"にしなければなりません。明らかに、これを実現することはできません。

B. DIV + MOD

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
少し前、Влад*1が面白い函数を思いつきました。

  • \displaystyle f_a(x) = \left\lfloor \frac{x}{a} \right\rfloor + x \bmod a; ここでは \displaystyle \left\lfloor \frac{x}{a} \right\rfloor は \displaystyle \frac{x}{a} の切り捨てを、x \bmod a は x を a で割った余りを表す。

例えば、a = 3, x = 11 とすると、\displaystyle f_3(11) = \left\lfloor \frac{11}{3} \right\rfloor + 11 \bmod 3 = 3+2 = 5 という値になります。

数 a は固定で、Владにとって既知です。x が l から r までの両端を含む l \lt x \lt r 任意の整数を取りえる場合、f_a(x) の最大値をВладが求められるよう手助けをしてください。

入力

入力データの1行目には1個の整数 t (1 \leq t \leq 10^4) が与えられる、これは入力のテストケース数である。

t 行が続く、そのそれぞれの行には3個の整数 l_i,\,r_i,\,a_i (1 \leq l_i \leq r_i \leq 10^9, 1 \leq a_i \leq 10^9) が与えられる、これらは区間の左右の境界と固定値 a である。

出力

各テストケースについて、単一行に1個の整数を出力せよ、その数とは与えられた a について与えられた区間上での函数の最大値である。

入出力例

5
1 4 3
5 8 4
6 10 6
1 1000000000 1000000000
10 12 8
2
4
5
999999999
5

注記

1つ目のテストケースでは

  • \displaystyle f_3(1) = \left\lfloor \frac{1}{3} \right\rfloor + 1 \bmod 3 = 0 + 1 = 1
  • \displaystyle f_3(2) = \left\lfloor \frac{2}{3} \right\rfloor + 2 \bmod 3 = 0 + 2 = 2
  • \displaystyle f_3(3) = \left\lfloor \frac{3}{3} \right\rfloor + 3 \bmod 3 = 1 + 0 = 1
  • \displaystyle f_3(4) = \left\lfloor \frac{4}{3} \right\rfloor + 4 \bmod 3 = 1 + 1 = 2

答えとしては、自明として、f_3(2) と f_3(4) が適切です。

C. Weight of the System of Nested Segments / Вес системы вложенных отрезков

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
数直線上に m 点が存在し、i 個目の点の座標は x_i で、重み w_i を持ちます。全ての点の座標は異なり、点には 1 から m までの番号が振られています。

各組 i,\,j (1 \leq i \lt j \leq n) について条件 l_i \lt l_j \lt r_j \lt r_i を満たすとき、n 個の区間の列 [l_1,\,r_i], [l_2,\,r_2], \dots, [l_n,\,r_n] は入れ子区間と呼ばれます。言い換えると、2番目の区間は1番目の区間の厳密な内側にあり、 3番目の区間は2番目の区間の厳密な内側にある、という具合に成り立っているというものです。

与えられた数 n について、次を満たす入れ子区間を求めて下さい。

  • 各区間の両端が、与えらえた m 個の点の1つである
  • 区間の端点として用いられる 2 \cdot n 個の点の重みの合計が最小である

例えば、m = 8 とします。与えられた点が、図中に示され、重みは赤で、座標は青で書かれています。次のような3つの入れ子区間のシステムを構築します。

  • 1つ目の区間の重み: 1 + 1 = 2
  • 2つ目の区間の重み: 10 + (-1) = 9
  • 1つ目の区間の重み: 3 + (-2) = 1
  • システム内の全ての区間の重みの和: 2 + 9 + 1 = 12
f:id:Flkanjin:20220309230248p:plain
3つの入れ子区間のシステム

入力

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

各テストケースの前には空行が書かれている。

各テストケースの1行目には2つの正整数 n (1 \leq n \leq 10^5), m (2 \cdot n \leq m \lt 2 \cdot 10^5) が与えられる。

続く m 行には整数の組 x_i (-10^9 \leq x_i \leq 10^9), w_i (-10^4 \leq w_i \lt 10^4) が与えられる、これらはそれぞれ番号 i の点の座標と重みを表す。全ての x_i は相異なる。

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

出力

各テストケースについて、n+1 行出力せよ。その1行目には構築したシステムの重みを出力し、続く n 行にはちょうど2個の整数を出力せよ、2つの整数とはi 個目の区間 (1 \leq i \leq n) の端点のインデックスである。区間の端点を出力する順番は重要ではなく、先に左端点のインデックスを出力し、次に右端点の番号を出力してもよく、その逆でもよい。

最小の重みで入れ子区間のシステムを構築する方法が複数ある場合は、そのうちのどれかを出力せよ。

入出力例

3

3 8
0 10
-2 1
4 10
11 20
7 -1
9 1
2 3
5 -2

3 6
-1 2
1 3
3 -1
2 4
4 0
8 2

2 5
5 -1
3 -2
1 0
-2 0
-5 -3
12
2 6
5 1
7 8

10
1 6
5 2
3 4

-6
5 1
4 2

注記

1つ目のテストケースでは、問題文の例と一致します。構築されたシステムの重みが最小であることは証明できます。

2つ目のテストケースでは、6 個の点しかないため、それぞれを用いて 3 個の区間を構成する必要があります。

D. Twist the Permutation / Петя и циклические сдвиги

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
Петя*2は 1 から n の数の配列 a を持っていて、a[i] = i となっていました。

彼は n 回の操作を順次に行いました。そして最後に、彼は新しい状態の配列 a を受け取りました。

i 回目の操作では、Петяは配列の最初の i 個の要素を選び、それらを右にに似の回数循環シフトさせました(i+1 以上のインデックスの要素はそのままです)。1回の右への循環シフトは、配列 a = [a_1,\,a_2,\,\dots,\,a_n] を配列 a=[a_i,\,a_1,\,a_2,\,\dots,\,a_{i-2},\,a_{i-1},\,a_{i+1},\,a_{i+2},\,\dots,\,a_n] にするような変換です。

例えば、a=[5,\,4,\,2,\,1,\,3] で i = 3(つまり、3回目の操作)の場合、この操作の結果として、彼は次の3つの配列のいずれかを得ることができます。

  • a = [5,\,4,\,2,\,1,\,3] (0 回の循環シフト、もしくは 3 で割り切れる回数)
  • a = [2,\,5,\,4,\,1,\,3] (1 回の循環シフト、もしくは 3 で割ると 1 余る回数)
  • a = [4,\,2,\,5,\,1,\,3] (2 回の循環シフト、もしくは 3 で割ると 2 余る回数)

また、別の例を見てみましょう。n = 6、即ち 初期状態で a = [1,\,2,\,3,\,4,\,5,\,6] とします。考えられるシナリオの1つは次の通りです。

  • i = 1: Петяが何回循環シフトを行っても配列 a は変化しない
  • i = 2: Петяが 1 回循環シフトを行うとすると、配列は a = [\textbf{2},\,\textbf{1},\,3,\,4,\,5,\,6] となる
  • i = 3: Петяが 1 回循環シフトを行うとすると、配列は a = [\textbf{3},\,\textbf{2},\,\textbf{1},\,4,\,5,\,6] となる
  • i = 4: Петяが 2 回循環シフトを行うとすると、配列は a = [\textbf{1},\,\textbf{4},\,\textbf{3},\,\textbf{2},\,5,\,6] となる
  • i = 5: Петяが 0 回循環シフトを行うとすると、配列は変化しない
  • i = 6: Петяが 4 回循環シフトを行うとすると、配列は a = [\textbf{3},\,\textbf{2},\,\textbf{5},\,\textbf{6},\,\textbf{1},\,\textbf{4}] となる

n 回の操作を行った後の配列 a の最終状態が与えられます。この結果になるような操作方法が存在するか判別してください。答えが存在する場合、n 回の操作のそれぞれで行った循環シフトの回数を出力して下さい。

入力

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

テストケースについての記述が続く。

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

次の行には配列 a の最終状態である n 個の整数 a_1,\,a_2,\,\dots,\,a_n (1 \leq a_i \leq n) が与えられる。全ての a_i は相異なる。

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

出力

各テストケースについて、答えを個別の行に出力せよ。

与えられた最終の値 a が各操作での任意の数の巡回シフトによって得ることが場合は -1 を出力せよ。そうでない場合、n 個の非負整数 d_1,\,d_2,\,\dots,\,d_n (d_i \geq 0) を出力せよ、ここでの d_i は、i 番目の操作の間に配列の最初の i 個の要素が右に d_i 回巡回シフトされたことを意味する。

複数の答えが存在する場合、シフトの総数が最小となる(つまり d_i の値の合計が最小の)ものを出力せよ。そのような答えが複数存在する場合は、そのうちのいずれかを出力せよ。

入出力例

3
6
3 2 5 6 1 4
3
3 1 2
8
0 1 1 2 0 4 
0 0 1 
0 1 2 0 2 5 6 2

注記

1つ目のテストケースは、問題文中の例と同じです。

2つ目の入力データセットは単純なものです。答え [3,\,2,\,1] でも同じ順列になりますが、シフトの総数 3+2+1 は 0+0+1 よりも大きいため、この答えは正しくありません。

E. Rescheduling the Exam / Перенос экзамена

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
Дмитрий*3は試験期間に n 個の試験に合格しなければなりません。試験期間は 1 日目から d 日間に渡ります。i 番目の試験は a_i 日目 (1 \leq a_i \leq d) に行われ、a_i はすべて異なるものです。
f:id:Flkanjin:20220310171210p:plain
n=3, d=12, a=[3,\,5,\,9] の場合のサンプル。試験日は橙。Дмитрийには1つ目の試験の前に 2 日、2つ目の試験の前に 1 日、3つ目の試験の前に 3 日の休みがある。

試験期間のスケジュールについて、Дмитрийは特別な値 \mu について考えています、この値は全ての試験の前の休息時間の最小値です。例えば、上の図について、\mu = 1 です。スケジュールにおいて、彼は正確に n 個の数、試験 i-1 と i の間の休息日数(試験機関の開始を i=0 と見做す*4 )を数えます。そして、この n 個の数の中で最小値である \mu を求めます。

Дмитрийは試験期間のスケジュールを改善できると考えています。彼は、1つの試験の日程を変更する(任意の1つの a_i を変更する)よう求めることができます。a_i が全て異なるままで、\mu の値ができるだけ大きくなるように、彼が日付を変更するのを手助けしてください。

例えば、上のスケジュールについて、2回目の試験を試験期間の一番最後に動かすのがДмитрийにとって最も有利です。新しいスケジュールは次のようになります。

f:id:Flkanjin:20220310173431p:plain
試験前の休息期間は [2,\,2,\,5] となり、\mu = 2 である

(状況を改善するために試験を移動させる方法がない場合、)Дмитрийは提供されたスケジュールを変更しないままにしておくこともできます。

入力

入力データの1行目には1個の整数 t (1 \leq t \leq 10^4) が与えられる、これは入力のテストケース数である。テストケースについての記述が続く。

各テストケースの前には空行が書かれている。

各テストケースの1行目には2個の整数 n,\,d (2 \leq n \leq 2 \cdot 10^5, 1 \leq d \leq 10^9) が与えられる、これらはそれぞれ、試験の個数と期間の長さである。

各テストケースの2行目には n 個の整数 a_i (1 \leq a_i \leq d, a_i \lt a_{i+1}) が与えられる、この i 番目の数が i 番目の試験の日付を表す。

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

出力

各テストケースについて、Дмитрийが1つの試験を任意の日に移動させることができる場合の \mu の最大値を出力せよ。a_i の値は全て異なるままでなければならない。

入出力例

9

3 12
3 5 9

2 5
1 5

2 100
1 2

5 15
3 6 9 12 15

3 1000000000
1 400000000 500000000

2 10
3 4

2 2
1 2

4 15
6 11 12 13

2 20
17 20
2
1
1
2
99999999
3
0
1
9

注記

1つ目の入出力例は、問題文中に書かれています。

2つ目の入出力例での最適なスケジュール変更は次の通りです。

f:id:Flkanjin:20220310174740p:plain
初期スケジュール
f:id:Flkanjin:20220310174950p:plain
新しいスケジュール

3つ目の入出力例では、1 日目の試験を 4 日目から 100 日目の間の任意の日に移動させる必要があります。

4つ目の入出力例では、いかなるスケジュールの変更でも \mu が小さくなるため、スケジュールをそのままにしておくべきです。

5つ目の入出力例では、1 日目の試験を 100000000 日目から 300000000 日目の間の任意の日に移動させる必要があります。

6つ目の入出力例での最適なスケジュール変更は次の通りです。

f:id:Flkanjin:20220310175502p:plain
初期スケジュール
f:id:Flkanjin:20220310175514p:plain
新しいスケジュール

7つ目の入出力例では、どの日も試験日であり、スケジュールを変更することは不可能です。

F. Vitaly and Advanced Useless Algorithms / Виталий и Advanced Useless Algorithms

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
Виталий*5は"Advanced Useless Algorithms"というコースを登録しました。このコースは n 個のタスクで構成されています。Виталийはを行うのにコース登録した日からタスク i を完了させるのに a_i 時間あるということを計算しました。言い換えれば、i 番目のタスクの締め切りの前に a_i 時間あるということです。配列 a は昇順ソートされていて、即ち、タスク番号は提出する順序に対応しています。

Виталийは何事も誠実に行うため、各タスクを 100 \% 以上完了させたいと思っています。初期状態では、彼の各タスクの完了率は 0 \% です。

Виталийには複数のトレーニングオプションがあり、各オプションは1度までしか使用できません。i 番目のオプションは3つの整数 e_i,\,t_i,\,p_i によって特徴づけられます。Виталийが i 番目のオプションを利用した場合、(現時点から) t_i 時間後に彼は、タスク e_i の進捗を p_i \% 進めることになります。

例えば、Виталийに3つのタスクがあるとします。配列 a が a = [5,\,7,\,8] であるとします。Виталийには次の 5 つのオプションがあるとします: [e_1=1,\,t_1=1,\,p_1=30], [e_2=2,\,t_2=3,\,p_2=50], [e_3=2,\,t_3=3,\,p_3=100], [e_4=1,\,t_4=1,\,p_4=80], [e_5=3,\,t_5=3,\,p_5=100]。

このとき、次のように準備を行うと、Виталийは時間内に全てを完了させることができます。

  • Виталийが 4 番目のオプションを選ぶ。1 時間後に、1 番目のタスクを 80 \% にする。1 番目のタスクの締切まであと 4 時間である。
  • Виталийが 3 番目のオプションを選ぶ。3 時間後に、2 番目のタスクを完了させる。1 番目のタスクの締切まであと 1 時間、3 番目のタスクの締切まであと 4 時間である。
  • Виталийが 1 番目のオプションを選ぶ。1 時間後に、1 番目のタスクを 110 \% で完了させ、締め切りちょうどに 1 番目のタスクが完了したことになる。
  • Виталийが 5 番目のオプションを選ぶ。2 時間後に、3 番目のタスクを完了させ、締め切りちょうどに 1 番目のタスクが完了したことになる。*6

このようにして、4 つのオプションを行うことで、Виталийは時間内にコースを完全に完了させることができます。

Виталийは正しい順番でタスクを完了させることができるように、オプションを出力し、Виталийを助けてください。各オプションは一度までしか使用できないことに注意してください。答えが複数存在する場合、そのいずれをを出力してもいいです。

入力

入力データの1行目には1個の整数 T (1 \leq T \leq 10^4) が与えられる、これは入力のテストケース数である。

テストケースについての記述が続く。

各テストケースの記述の1行目には2個の整数 n,\,m (1 \leq n,\,m \leq 10^5) が与えられる、これらはそれぞれ、タスクとトレーニングオプションの個数である。

次の行には n 個の整数 a_1,\,a_2,\,\dots,\,a_n (1 \leq a_i \leq 10^9) が与えられる、タスク i の締め切りを表す。配列の値は非減少、即ち a_1 \leq a_2 \leq \dots \leq a_n となっている。

続く m 行には、3つ組の整数 e_i,\,t_i,\,p_i (1 \leq e_i \leq n, 1 \leq t_i \leq 10^9, 1 \leq p_i leq 100) が与えられる、もしВиталийがこのオプションを選択すれば、t_i 時間後にタスク e_i の進捗を p_i \% 進める。オプションには入力データの順に 1 から m までの番号が振られている。

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

出力

各テストケースについて、1行目に、数 k を出力せよ、これは、オプションのうち k 個を用いて、Виталийが各タスクを 100 \% 以上で完了できることを表す。同じオプションは繰り返してはいけない。Виталийが全てのタスクを時間内に完了できない場合は、-1 を出力せよ。

もし答えが存在する場合、続く行に 1 から m までの異なる整数 k 個を、望む順序での選択肢の番号を、出力せよ。複数の答えが存在する場合、そのいずれを出力してもよい。

入出力例

5
3 5
5 7 8
1 1 30
2 3 50
2 3 100
1 1 80
3 3 100
1 5
51
1 36 91
1 8 40
1 42 83
1 3 45
1 13 40
2 9
9 20
2 8 64
2 7 64
1 20 56
2 8 76
2 20 48
1 2 89
1 3 38
2 18 66
1 7 51
3 2
7 18 33
1 5 80
3 4 37
2 5
569452312 703565975
1 928391659 66
1 915310 82
2 87017081 92
1 415310 54
2 567745964 82
4
1 4 3 5 
3
2 4 5 
4
6 7 1 2 
-1
4
2 4 3 5 
3
3 9
20 31 40
1 9 64
3 17 100
3 9 59
3 18 57
3 20 49
2 20 82
2 14 95
1 8 75
2 16 67
2 6
20 36
2 2 66
2 20 93
1 3 46
1 10 64
2 8 49
2 18 40
1 1
1000000000
1 1000000000 100
-1
4
3 4 1 5 
1
1

G. Counting Shortcuts / Подсчёт коротких путей

テストごとの時間制限: 2秒
テストごとのメモリ制限: 512 MB
入力: 標準入力
出力: 標準出力
n 個の頂点と m 本の辺を持つ無向の連結グラフが与えられます。このグラフには自己辺(ある頂点からそれ自身への辺)や多重辺が含まれません(即ち、各頂点の組の間に1つ以上の辺がない)。グラフの頂点には 1 から n までの番号が振られています。

頂点 s から t への経路のうち、s から t までの最短経路と長さの差が 1 以下である経路の数を求めて下さい。このとき、同じ頂点や辺を2回以上通るもの(単純でないパス)であっても、条件を満たす形を全てを考慮する必要があります。

f:id:Flkanjin:20220310185641p:plain
6 頂点 8 辺から成るグラフ

例えば、n=6, m=8, s=6, t=1として、上図のようなグラフであるとします。s から t への最短経路の長さは 1 です。長さが最大で 1+1=2 である経路を全て考えます。

  • 6 \rightarrow 1: 経路長は 1
  • 6 \rightarrow 4 \rightarrow 1: 経路長は 2
  • 6 \rightarrow 2 \rightarrow 1: 経路長は 2
  • 6 \rightarrow 5 \rightarrow 1: 経路長は 2

合致する経路は全部で4本あります。

入力

入力データの1行目には1個の整数 t (1 \leq t \leq 10^4) が与えられる、これは入力のテストケース数である。テストケースについての記述が続く。

各テストケースの前には空行が書かれている。

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

2行目には2個の整数 s,\,t (1 \leq s,\,t \leq n; s \neq t) が与えられる、これらは経路の始点と終点の番号である。

続く m 行には辺の記述が与えられ、その i 行目には2個の整数 u_,\,v_i (1 \leq u_,\,v_i \leq n) が与えられる、これらは i 本目の辺が結ぶ頂点の番号である。グラフは連結であり、自己辺や多重辺が含まないことは保証されている。

入力データ内の全てのテストケースでの n の和が 2 \cdot 10^5 を超えないことは保証されている。同様に、入力データ内の全てのテストケースでの m の和が 2 \cdot 10^5 を超えないことは保証されている。

出力

各テストケースについて、単一の数を出力せよ、その数とは s から t までの最短経路と長さの差が 1 以下である経路の個数である。

この数は大きくなるかもしれないため、modulo 10^9+7 で出力せよ。

入出力例

4

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

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

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

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

*1:露[vɫat](ヴラド、Vlad); Vladはルーマニア語などではスラブ系の男性名 Vladimirなどの短縮形・愛称の一つであるが、ここではロシア人名とした

*2:露[ˈpʲetʲə](ピェチャ、Petya, Pjetja): ロシア男性名 Пётр(Петр、Petr、ピョートル)の指小形、愛称、英Peteに相当、Пётрは英独Peter等と同じく聖ペテロに由来

*3:露[ˈdmʲitrʲɪj](ドミトリー、Dmitri, Dmitry, Dmitrij) ロシア男性名、英Demetriusに相当、Пётрは英独Peter等と同じく古典ギリシャ男性名Δημήτριος(Dēmḗtrios)に由来

*4:この部分は意訳、恐らく誤記あり

*5:露[vʲɪˈtalʲɪj](ヴィタリー、Vitali, Vitaly, Vitalij) ロシア男性名、ラテン男性名Vītālisに由来

*6:この部分も意訳

AtCoder Beginner Contest 242のきろく

AtCoder 競技プログラミング AtCoder Beginner Contest 参戦記

AtCoder Beginner Contest 242に参加。

A - T-shirt (100点)

X \leq A の時は必ずTシャツは貰えるので、答えの確率は 1、X \gt B の時は、Tシャツをもらえることが無いので 0 です。
その他のときは B-A 人の中から一様に C 人を選ぶとき、自分が選ばれるときの確率ですので \displaystyle \frac{C}{B-A} が答えとなります。

B - Minimize Ordering (200点)

S 内の文字を昇順に並び替えればいいので、sort関数で並び替えてやればいいです。

C - 1111gal password (300点)

桁DPです。

{\mathrm{dp}}_{i,j} = (\text{最下位の桁が \(j\) である \(i\) 桁の条件を満たす整数の個数})
とします。このとき、初期条件を
{\mathrm{dp}}_{1,j} = 1 (1 \leq j \leq 9)
として、遷移条件
{\mathrm{dp}}_{i+1,j} = \left\{ \begin{array}{ll} {\mathrm{dp}}_{i,j} + {\mathrm{dp}}_{i,j+1} & (j = 1)\\ {\mathrm{dp}}_{i,j} + {\mathrm{dp}}_{i,j+1} + {\mathrm{dp}}_{i,j-1} & (1 \lt j \lt 9)\\ {\mathrm{dp}}_{i,j} + {\mathrm{dp}}_{i,j-1} & (j = 9)\\ \end{array} \right.
によって i = N まで 1 \leq j \leq 9 でDPの値を求めたときの、\displaystyle\sum_{j = 1}^{9} {\mathrm{dp}}_{N,j} が答えとなります。

D - ABC Transform (400点)

この問題では文字列を0-based indexで考えます。
A→B→C→A という循環を考えます。
S^{(i)} から S^{(i+1)} が作られるとき、S^{(i)} の j 文字目から S^{(i+1)} の 2j 文字目と 2j+1 文字目が作られます。このとき、2j 文字目は循環において 1 つ進んだ文字、2j+1 文字目は循環において 2 つ進んだ文字となります。
このことから次のことが分かります。

  • S^{(i)} の j 文字目は大本を辿ると S^{(0)} の \displaystyle \left\lfloor \frac{j}{2^i} \right\rfloor 文字目に由来する。
    → クエリ"t\ \ k"について S'^{(0)} = S_{\left\lfloor \frac{k}{2^t} \right\rfloor}、k' = k \bmod 2^t として、S'^{(t)} の k' 文字目を求める問題として読み替えることができます。
  • 元の 0 文字目から t 回操作後の k 文字目に遷移するまで、(j \rightarrow 2j+1) の遷移を \operatorname{popcount}(k) 回、(j \rightarrow 2j) の遷移を t-\operatorname{popcount}(k) 回行う。ここでの \operatorname{popcount}(\cdot) は二進数表記での 1 である桁の数を表す函数
    → 循環上では 2\operatorname{popcount}(k) +1 (t-\operatorname{popcount}(k)) = t+\operatorname{popcount}(k) だけ進んだ文字になります。

よってこの二つの観察から答えを導くことができました。

E - (∀x∀) (500点)

回文であるので先頭 \displaystyle \left\lceil \frac{N}{2} \right\rceil 文字の決め方について考えます。

まず、S の先頭 \displaystyle \left\lceil \frac{N}{2} \right\rceil 文字よりも辞書順で小さい \displaystyle \left\lceil \frac{N}{2} \right\rceil 文字の文字列の数を求めます。
先頭 i 文字が等しいものは 26^{\left\lceil \frac{N}{2} \right\rceil-i} f(S_i) 個あります。ここでの f(c) は文字 c のアルファベット順の順番から 1 を引いたものです。よって i を 1 から \displaystyle \left\lceil \frac{N}{2} \right\rceil までを足し合わせたものがここでの値です。

次に、 S と先頭 \displaystyle \left\lceil \frac{N}{2} \right\rceil 文字が等しい N 文字の回文が S よりも辞書順で小さいかどうかを調べます。これで g(S) を定義します。この段落での最初の文での条件を満たせるなら 1、そうでなければ 0 を返します。

これらよりこの問題の答えは \displaystyle g(S) + \sum_{i = 1}^{ \left\lceil \frac{N}{2} \right\rceil} {26^{\left\lceil \frac{N}{2} \right\rceil-i} f(S_i)} となります。

F - Black and White Rooks (500点)

包除原理が思いつかなかった... 通したら追記します。 upsolveしたので追記します。

白と黒の飛車/Rookが同一列、同一行内に存在するとき、その行または列内で、互いに利いている白と黒のペアが存在します。その為、各行、列は駒なし/白/黒のいずれかです。よって、各行、列の状態について、各色が選ばれた行、列の全てに駒が存在し、かつ選ばれた行、列以外に駒が存在しないような配列の方法数が分かればいい、ということまではコンテスト中には分かっていました。

選ばれた行、列のみ注目します。「いずれの行、列にも駒が存在する」ということはde Morganの法則から包除原理で計算することができます。このことから最終的な答えは \displaystyle \sum_{i=1}^{N} \sum_{j=1}^{N-i} \sum_{k=1}^{M} \sum_{l=1}^{M-k} \tbinom{N}{i}\tbinom{N-i}{j}\tbinom{M}{k}\tbinom{M-k}{l} \left\{\sum_{I=0}^{i}\sum_{K=0}^{k}(-1)^{I+K}\tbinom{i}{I}\tbinom{k}{K}\tbinom{(i-I)(k-K)}{B}\right\} \left\{\sum_{J=0}^{j}\sum_{L=0}^{l}(-1)^{J+L}\tbinom{j}{J}\tbinom{l}{L}\tbinom{(j-J)(l-L)}{W}\right\} です。括弧の中をメモ化しておくことで計算量 O(N^2M^2) で答えることができました。

G - Range Pairing Query (600点、実行時間制限: 5 sec)

Mo’s Algorithm(莫のアルゴリズム、平方根分割)だと気づくのが遅く実装できませんでした... 通したら追記します。 upsolveしたので追記します。

各クエリに対する答えは \displaystyle \sum_{c=1}^{N} \left\lfloor \frac{(\text{区間内で色 \(c\) の服を着ている人数})\hspace{2.5cm}}{2}\right\rfloor です。区間を [l,\,r] から [l\pm1,\,r] や [l,\,r\pm1] に更新するとき、追加または削除された色の人数の偶奇によって、答えが 1 増減したり、変わらなかったりします(具体的には人数増加して偶数になったら +1、人数減少して奇数になったら -1、その他は不変)。そのため、各色の人数と答えを変数で管理することで区間の \pm1 の更新は O(1) で行うことができるため、Mo’s Algorithmを適用することができます。

Mo’s Algorithmはクエリを先読みし、ある特定の順番でクエリを処理することでクエリの更新回数を減らすというアルゴリズムです。全体区間をある大きさのブロックに分割し、各区間を左端がどのブロックに属すかで、ソートします。同一ブロック内の区間たちについては右端でソートします(こちらはブロックではなくもとの値でソート)。このときのブロックの大きさは大体 \sqrt{Q} ぐらいにすることが多く、そのとき計算量は O(N\sqrt{Q}) となります。

Ex - Random Painting (600点、実行時間制限: 3 sec): 未提出

難しそう...

結果、感想


何とかレートが暖まりました。
コンテスト終了直後のperfやレート変化の予測値では冷えてた筈なんですけど、AtCoder公式のTwitterで言及されていた「不正者に対する作業」による影響でしょうか?

Codeforces Round #774 (Div. 2)のきろく

Codeforces 競技プログラミング Codeforces Div. 2 参戦記

Highest更新!! 問題文和訳はこちら

A. Square Counting / Сколько квадратов? (750点)

n^2 の個数が k である時、kn^2 から kn^2 + (n+1-k)(n-1) までの整数を作ることができます。(n+1-k)(n-1) = n^2-1 + k - nk < n^2 であるため、各 k について作ることができる整数は互いに異なります。したがって、答えは \displaystyle \left\lfloor \frac{s}{n^2}\right\rfloor となります。

B. Quality vs Quantity / Качество против количества (1000点)

赤の要素の和を大きく、青の要素の和を小さくしたいので、赤は大きい方から、青は小さい方から要素をとればいいことが分かります。

予め、大きい方に並べたときの累積和を計算しておくと、青の要素が k 個であるとき、sumの条件を満たす赤の要素の最低個数を二分探索(std::upper_bound等)で調べることができ、その値を m としたとき、k + m \leq n かつ k \gt m を満たすような k が存在するとき、その数列では条件を満たす彩色方法が存在します。

また、赤の要素数を m としたとき、青が m+1 個の要素で条件を満たせないとき、要素数を増やしても、条件は満たされないため、2m + 1 \leq n の条件で、大きい方からの m 個の和と小さい方からの m + 1 個の和の大小を比べることでも判別することができます。

C. Factorials and Powers of Two / Факториалы и степени двойки (1250点)

二進数表記で 1 である桁に対応して足し合わせることで、2の累乗の和として数を表現することができます。
そのため、用いる階乗の集合を定めた時、2の累乗の集合は簡単に求まります。そのため、用いる階乗の集合を全探索すれば良いことが分かります。使える階乗は最大でも 14! = 87\,178\,291\,200 までであり、1! = 1 と 2! = 2 は2の累乗でもあるため、3! から 14! までの 12 通りです。そのため、それぞれ使う/使わないのbit全探索で間に合うことが分かります。

D. Weight the Tree / Взвесьте дерево (2000点)

この問題はコンテスト中には通せませんでした... 気付けてもよかったのに...
n = 2 の場合は、自明でしょう。

n = 2 の場合を除いて、隣接する頂点の両方を良い頂点にすることはできません。また、木全体の重みの和を小さく抑えたいので良い頂点の重さはその頂点の次数、そうでない頂点の重さは 1 になります。
頂点 1 を根として次のような木DPを考えることができます。{\mathrm{dp}}_{i, j} は、1 を根とした部分木で i を良い頂点として(j ? 選ぶ : 選ばない)ときの最適な(良い頂点の数, 重みの和)の組とします。但し、j = \mathrm{True} のとき、i の重みには元の木での i の親頂点を考慮します。このときの遷移式は

{\mathrm{dp}}_{i,j}=\left\{ \begin{array}{ll} \displaystyle \sum_{c \in C_i} {\mathrm{dp}}_{c,\mathrm{False}} + (1,\,d_i)& (j = \mathrm{True})\\ \displaystyle \sum_{c \in C_i} \operatorname{Opt}\{{\mathrm{dp}}_{c,\mathrm{True}},\,{\mathrm{dp}}_{c,\mathrm{False}} \} + (0,\,1)& (j = \mathrm{False}) \end{array} \right.
となります。ここで d_v は頂点 v の次数を、C_v は頂点 v の子頂点の集合を表します。また、(a,\,b) + (c,\,d) = (a+c,\,b+d) とし、\operatorname{Opt} は適当な状態(\operatorname{Opt}( (a,\,b),\,(c,\,d)) = (a,\,b) \Leftrightarrow a \gt c \lor (a = c \land b \lt d) \lor (a,\,b) = (c,\,d))を表します。
よって、(i,\,j) = (1,\,\mathrm{True}), (1,\,\mathrm{False}) のそれぞれからDFSによって木DPを行い、\operatorname{Opt}\{{\mathrm{dp}}_{1,\mathrm{True}},\,{\mathrm{dp}}_{1,\mathrm{False}} \} が答えとなります。

各頂点の重みは経路復元によって求めますが、DFSの際、各 (i,\,j) においての最適条件で、どの子頂点が良い頂点であるかを記憶しておくことで簡単に求めることができます。

E. Power Board / Степенная таблица (2500点)

ボード上の数の集合を S とします。
1 行目は 1 のみが含まれます。

2 行目以降について考えます。非累乗数 x について x の累乗である S の要素の集合は \{x^{ij}; i,\,j \in \mathbb{N},\, 1 \leq i \leq m,\, 1 \leq j \leq \lfloor \log_x n \rfloor\} となり、その大きさは \{ij; i,\,j \in \mathbb{N},\, 1 \leq i \leq m,\, 1 \leq j \leq \lfloor \log_x n \rfloor\} と等しいです。これらは各 x について互いに素(共通部分を持たない)であるため、上記の集合の要素数が分かればいいです。これは T_{z} = \#\{ij; i,\,j \in \mathbb{N},\, 1 \leq i \leq m,\, 1 \leq j \leq z\} を予め求めておくことで、高速で計算することができます。

累乗数についてはそれより小さい非累乗数のいずれかの累乗であるため、こちらについて考える必要はありません。

F. Playing Around the Table / Игра вокруг стола (3000点): 未提出

分かりません...

結果、感想

f:id:Flkanjin:20220305201458p:plain
今回E問題を通してレートを大幅に上げることができました。ただ、D問題が通せなかったのは要反省ですね。

Codeforces Round #774 (Div. 2) 問題文和訳

Codeforces 競技プログラミング Codeforces 和訳 Codeforces Div. 2 和訳

A. Square Counting / Сколько квадратов? (750点)

テストごとの時間制限: 1秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
Luis*1は n+1 個の整数 a_1,\,a_2,\,\dots,\,a_{n+1} を持っています。各 i = 1,\,2,\,\dots,\,n+1 について、0 \leq a_i \lt n または a_i = n^2 であることが分かっています。彼は数列の全要素の和を計算し、その値を s としました。

Luisは数列を失くしてしまいましたが、n と s の値は覚えています。数列の要素のうち、n^2 に等しいものの個数を求めることができますか?

与えられた制約のもとでは答えが一意であることは証明できます。

入力

各テストは複数のテストケースが含まれる。1行目にはテストケースの個数 t (1 \leq t \leq 2 \cdot 10^4) が与えられる。以下、テストケースの記述が続く。

各テストケースの唯一の行には2個の整数 n,\,s (1 \leq n \leq 10^6, 0 \leq s \leq 10^{18}) が与えられる。s の値は、上記の制約を満足する数列の和として有効なものであることが保証されている。

出力

各テストケースについて、単一の整数を出力せよ、その数とは数列内の n^2 に等しい項の個数である。

入出力例

4
7 0
1 1
2 12
3 12
0
1
3
1

注記

1つ目のテストケースでは、s = 0 であるため、全ての数が 0 であり、49 となる数は存在しません。

2つ目のテストケースでは、s = 1 です。可能な数列は2つあります: [0,\,1], [1,\,0]。どちらの場合でも、数 1 は一度だけ現れます。

3つ目のテストケースでは、s = 12 で、このケースでの s の可能な最大値です。そのため、数 4 は数列内に 3 回現れます。

B. Quality vs Quantity / Качество против количества (1000点)

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
n 個の非負整数 a_1,\,a_2,\,\dots,\,a_n が与えられます。初期状態では、数列のどの要素も彩色されていません。各数を \color{red}{\underline{\text{赤}}} か \color{blue}{\overline{\text{青}}} に塗ることができ(両方は不可)、塗らないままにしておくこともできます。

色 c について、\operatorname{Count}(c) は数列内のその色で塗られた要素数、\operatorname{Sum}(c) は数列内のその色で塗られた要素の和を表します。

例えば、与えられた数列が [2,\,8,\,6,\,3,\,1] で、次のように彩色します: [\color{blue}{\overline{2}},\,8,\,\color{red}{\underline{6}},\,\color{blue}{\overline{3}},\,1](6 は赤に、2 と 3 は青に塗られ、1 と 8 は無彩色)。この時、\operatorname{Sum}(\color{red}{\underline{\text{赤}}}) = 6, \operatorname{Sum}(\color{blue}{\overline{\text{青}}}) = 2 + 3 = 5, \operatorname{Count}(\color{red}{\underline{\text{赤}}}) = 1, \operatorname{Count}(\color{blue}{\overline{\text{青}}}) = 2 となります。

\operatorname{Sum}(\color{red}{\underline{\text{赤}}}) \gt \operatorname{Sum}(\color{blue}{\overline{\text{青}}}) かつ \operatorname{Count}(\color{red}{\underline{\text{赤}}}) \lt \operatorname{Count}(\color{blue}{\overline{\text{青}}}) となるように数列を塗り分けることができるか判別してください。

入力

各テストは複数のテストケースが含まれる。1行目にはテストケースの個数 t (1 \leq t \leq 1000) が与えられる。以下、テストケースの記述が続く。

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

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

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

出力

各テストケースについて、与えられた数列を上記の要件を満たすように塗ることが可能であればYESと出力せよ、そうでなければNOと出力せよ。

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

入出力例

4
3
1 2 3
5
2 8 6 3 1
4
3 5 4 2
5
1000000000 1000000000 1000000000 1000000000 1000000000
NO
YES
NO
NO

注記

1つ目の入力例では、条件を満たす数列の彩色方法はありません。例えば、次のように彩色したとします: [\color{blue}{\overline{1}},\,\color{blue}{\overline{2}},\,\color{red}{\underline{3}}](3 は赤、1 と 2 は青)。この時、\operatorname{Count}(\color{red}{\underline{\text{赤}}}) = 1 \lt \operatorname{Count}(\color{blue}{\overline{\text{青}}}) = 2 ですが、 \operatorname{Sum}(\color{red}{\underline{\text{赤}}}) = 3 \ngtr \operatorname{sum}(\color{blue}{\overline{\text{青}}}) = 3 です。そのため、これは条件を満たす数列の彩色方法ではありません。

2つ目の入力例では、問題文で記述されているように塗ることができます。\operatorname{Sum}(\color{red}{\underline{\text{赤}}}) = 6 \gt \operatorname{Sum}(\color{blue}{\overline{\text{青}}}) = 5, \operatorname{Count}(\color{red}{\underline{\text{赤}}}) = 1 \lt \operatorname{Count}(\color{blue}{\overline{\text{青}}}) = 2 であることが確認できます。

3つ目の入力例では、条件を満たす数列の彩色方法はありません。例えば、次のように彩色したとします: [\color{red}{\underline{3}},\,\color{red}{\underline{5}},\,\color{blue}{\overline{4}},\,\color{blue}{\overline{2}}](3 と 5 は赤、4 と 2 は青)。この時、\operatorname{Sum}(\color{red}{\underline{\text{赤}}}) = 8 \gt \operatorname{Sum}(\color{blue}{\overline{\text{青}}}) = 6 ですが、\operatorname{Count}(\color{red}{\underline{\text{赤}}}) = 2 \nless \operatorname{Count}(\color{blue}{\overline{\text{青}}}) = 2] です。そのため、これは条件を満たす数列の彩色方法ではありません。

4つ目の入力例では、sumとcountの制約を満たす数列の塗り分けは不可能であることを証明することができます。

C. Factorials and Powers of Two / Факториалы и степени двойки (1250点)

テストごとの時間制限: 3秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
ある数が2の累乗か、階乗である場合、その数を強力であるといいます。つまり、m = 2^d または m = d! であるような非負整数 d が存在するとき、数 m は強力であるといいます、ここで d! = 1 \cdot 2 \cdot \cdots \cdot d (また特別に 0! = 1) を表します。例えば 1, 4, 6 は 1 = 1!, 4 = 2^2, 6 = 3! であるので強力な数ですが、7, 10, 18 はそうではありません。

正整数 n が与えられます。n が k 個の相異なる強力な数の和として表現できるような最小の数 k を求めて下さい、もしくは、そのような k が存在しないことを判別してください。

入力

各テストは複数のテストケースが含まれる。1行目にはテストケースの個数 t (1 \leq t \leq 100) が与えられる。以下、テストケースの記述が続く。

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

出力

各テストケースについて、別々の行に答えを出力せよ。

n が相異なる強力な数の和として表現できない場合は、-1 を出力せよ。

そうでない場合、単一の正整数を出力せよ、その数とは、k の可能な最小値である。

入出力例

4
7
11
240
17179869184
2
3
4
1

注記

1つ目のテストケースでは、7 は 7 = 1 + 6 と表現することができ、1 と 6 は強力な数です。7 は強力な数ではないので、このケースでの k の可能な最小値は k = 2 であることが分かります。

2つ目のテストケースでは、11 を3個の強力な数の和として表現できる方法として 11 = 1 + 4 + 6 が考えられます。11 を2個以下の強力な数の和として表現することができないことを証明することができます。

3つ目のテストケースでは、240 は 240 = 24 + 32 + 64 + 120 と表現することができます。強力な数は相異ならなければならないので 240 = 120 + 120 は有効な表現でないことに注意して下さい。

4つ目のテストケースでは、17179869184 = 2^{34} であるため、 17179869184 は強力な数であり、このケースの最小の k は k = 1 です。

D. Weight the Tree / Взвесьте дерево (2000点)

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
1 から n の番号を附けられた n 個の頂点の木が与えられます。木とはサイクルの無い連結無向グラフのことです。

各 i = 1,\,2,\,\dots,\,n について、i 番目の頂点の重みを w_i とします。その重みが全ての隣接頂点の重みの和と等しい時、その頂点は良いと言います。

初期状態では、全ての頂点の重みは未定義です。木内の良い頂点の数が最大になるように、各頂点に正整数の重みを割り当てて下さい。複数の方法がある場合は、木の全頂点の重みの和を最小にする方法を求めて下さい。

入力

1行目には1つの整数 n (1 \leq n \leq 2 \cdot 10^5) が与えられる、この数は木の頂点数です。

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

出力

1行目には、2個の整数を出力せよ、その数とは良い頂点の最大数とその最大値に対する重みの和の可能な最小値である。

2行目には、n 個の整数 w_1,\,w_2,\,\dots,\,w_n (1 \leq w_ i \leq 10^9) を出力せよ、これらは各頂点に割り当てられた重みである。これらの制約を満たす最適解が存在することは証明することができる。

複数の最適解が存在する場合は、いずれを出力してもよい。

入出力例

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

注記

1つ目のテストケースでの木はこちらです。

f:id:Flkanjin:20220305151214p:plain:w300
このケースでは、各頂点に重み 1 を割り当てると、良い頂点(黒)は 1, 3, 4 となります。全ての頂点を良い頂点にするように重みを割り当てることはできません。このケースでの重みの和の最小値は 1 + 1 + 1 + 1 = 4 であり、重みは正整数でなければならないので、和をこれより小さくすることはできません。
2つ目のテストケースでの木はこちらです。
f:id:Flkanjin:20220305163135p:plain:w300
このケースでは、各頂点に重み 1 を割り当てると、良い頂点(黒)は 2, 3 となります。これが最適な割り当てであることを示すことができます。

E. Power Board / Степенная таблица (2500点)

テストごとの時間制限: 1.5秒
テストごとのメモリ制限: 512 MB
入力: 標準入力
出力: 標準出力
大きさ n \times m(n 行 m 列)の長方形のボードがあります。n 個の行には上から下へ [tex1] から n までの番号が、m 個の列には左から右へ [tex1] から m までの番号が振られています。

i 行と j 列の交点にあるセルには i^j(i の j 乗)が書かれています。例えば、n = 3, m = 3 であるとき、このボードは次のようになります。

f:id:Flkanjin:20220305164344p:plain
ボード上に書かれた相異なる整数の数を求めて下さい。

入力

唯一の行には2個の整数 n,\,m (1 \leq n,\, m \leq 10^6) が与えられる、これらはボードの行と列の数である。

出力

1個の整数を出力せよ、その数とはボード上の相異なる整数の数である。

入出力例

3 3
7
2 4
5
4 2
6

注記

問題文には、1つ目のテストケースでのボードが示されています。このケースでは 1, 2, 3, 4, 8, 9, 27 の 7 個の相異なる整数が書かれています。

2つ目のテストケースでは、ボードは次のようになります。

f:id:Flkanjin:20220305165423p:plain
1, 2, 4, 8, 16 の 5 個の相異なる整数が書かれています。

3つ目のテストケースでは、ボードは次のようになります。

f:id:Flkanjin:20220305165543p:plain
1, 2, 3, 4, 9, 16 の 6 個の相異なる整数が書かれています。

F. Playing Around the Table / Игра вокруг стола (3000点)

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
1 から n の番号が振られた n 人のプレイヤーが円卓を囲むように座っています。1 \leq i \lt n について (i + 1) 番目のプレイヤーは i 番目のプレイヤーの右側に座っていて、1 番目のプレイヤーは n 番目のプレイヤー右側に座っています。

1 から n までの整数が1つ書かれているカードが n^2 枚あります。1 から n までの各整数について、ちょうど n 枚のカードにこの数が書かれています。

始めに、各プレイヤーがちょうど n 枚のカードを持っているように、カードがプレイヤーに分配されます。1ステップで各プレイヤーは自分のカードを1枚選び、右側のプレイヤーに渡します。全プレイヤーが同時にこのステップを実行します。

プレイヤー i が持っている全てのカードに整数 i が書かれている場合、そのプレイヤーはsolidであるといいます。プレイヤーの目的は、全員がsolidであるカード配置にすることです。(n^2 - n) 回以内の操作で実現できる方法を求めて下さい。操作数を最小化する必要はありません。

入力

1行目には1個の整数 n (2 \leq n \leq 100) が与えられる。

それから n 行が続く。その i 行目には n 個の整数 c_1,\,c_2,\,\dots,\,c_n (1 \leq c_j \leq n) が与えられる、これらは i 番目のプレイヤーの初期カードである。

1 から n までの各整数 i について、数 i が書かれたカードがちょうど n 枚あることは保証されている。

出力

1行目には、1個の整数 k (0 \leq k \leq (n^2 - n)) を出力せよ、これは操作数である。

その後、k 行を続けよ。その i 行目には n 個の整数 d_1,\,d_2,\,\dots,\,d_n (1 \leq d_j \leq n) を出力せよ。ここで、d_j は j 番目のプレイヤーが右隣のプレイヤーに渡したカードに書かれている数字である。

与えられた制約の中で、必ず答えが存在することを示すことはできる。複数の解がある場合は、いずれかを出力せよ。

入出力例

2
2 1
1 2
1
2 1
3
1 1 1
2 2 2
3 3 3
6
1 2 3
3 1 2
2 3 1
1 2 3
3 1 2
2 3 1

注記

1つ目のテストケースでは、1番目のプレイヤーが数 2 のカードを、2番目のプレイヤーが数 1 のカードをパスすると、1番目のプレイヤーは数 1 のカードを2枚、2番目のプレイヤーは数 2 のカードを2枚持っていることになります。そして、この操作を行った後、両プレイヤーはsolidとなります。

2つ目のテストケースでは、0 回の操作で十分です。操作回数を最小化する必要はないことに注意してください。

*1:西[lwis]、ルイス: 高地ゲルマン語のHlūtwīg(名高い戦い)に由来する名前、Lewis(英)、Louis(仏)、Luigi(伊)、Ludwig(独)等と同語源

AtCoder Beginner Contest 241（Sponsored by Panasonic）のきろく

AtCoder 競技プログラミング AtCoder Beginner Contest 参戦記

AtCoder Beginner Contest 241（Sponsored by Panasonic）に参加。

A - Digit Machine (100点)

a_{a_{a_0}} が答えです。
見にくいので別表記すると f(x) = a_x として f^3(0) = f(f(f(0))) となります。

B - Pasta (200点)

std::mapで各長さの麵の本数を管理すると楽。

C - Connect 6 (300点、実行時間制限: 3 sec)

4 マス以上が黒であるような連続 6 マスが存在するとき、答えはYes、そうでないときNoとなります。
連続 6 マスは各マスから8方向へ6回探索すればよく、それぞれについて黒マスの数を数えればいいです。
尚、全てのマスについて調べるので8マスのうち半分は調べなくてもいいです((上, 下), (左, 右), (左上, 右下), (右上, 左下)の各組について片方のみでよい)。

斜めについて 6 マスに達してないのにYesにしてしまうというミスで4WAしました...

D - Sequence Query (400点)

k は高々 5 であるので、std::multisetやstd::mapで管理したとき、イテレータの移動が高々 5Q 回なので、間に合います。
前にbegin()を超えるかよりも後ろにend()を超えるかを判定する方が楽だったりするので、c_i = 2 のクエリについては全体に -1 を掛けたもので行うと少し楽になるかも(人に依る?)。

std::multisetでbegin()やend()を超えて操作を行ってしまったコードを出してしまい、1TLEしてしまいました...

E - Putting Candies (500点)

ダブリングを行います。

{\mathrm{dp}}_{i,j} = (\text{\(X=i\) から \(2^j\) 回の操作を行った後の飴の個数})
とします。このとき N で割った時の商と余りに注目することで
{\mathrm{dp}}_{i,j} = \left\{ \begin{array}{ll} i + A_i & (j = 0)\\ \displaystyle \left\lfloor \frac{{\mathrm{dp}}_{i,j-1} }{N} \right\rfloor N + {\mathrm{dp}}_{{({\mathrm{dp}}_{i,j-1} \mod N)},j-1}& (j \neq 0) \end{array} \right.
となるので、K を二進数で表した時、1 である桁を下から s_1,\,s_2,\,\dots,\,s_n とした時、最初 a = 0 として i を 1 から n へ順に
a \leftarrow \displaystyle \left\lfloor \frac{a }{N} \right\rfloor N +{\mathrm{dp}}_{{(a \mod N)},s_i}
を繰り返して、最終的な a が答えとなります。
本番では各DPの値は (商, 余り) の組として実装しました。

F - Skate (500点)

H も W も最大で 10^9 まで取りえるので、全てのマスについて調べることはできません。しかし、途中で立ち寄ることができるマスは障害物の上下左右いずれかの隣接マスのみなのでスタート地点を入れても高々 4N + 1 箇所です。そのため、これらの限定した頂点についてのBFSで答えを求めることができます。
ぶつかる障害物についてはstd::map<int, std:::vector>での二分探索によって求めることができます。

G - Round Robin (600点)

終了後に解説ACしました。
この解説のとおりに実装しました。
試合からプレイヤーへの辺のうち一方にしか流せないようにすることで一方のみが勝つという状況を表せるのがすごいと思いました。
ちゃんとフローについて勉強しなきゃ...

Ex - Card Deck Score (600点、実行時間制限: 3 sec): 未提出

多項式.... 分かんね...

結果、感想

f:id:Flkanjin:20220227030343p:plain
1700附近まで回復させることができました。でもCの4WAで焦ってしまったのは要反省だなと思いました。