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

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

A. Meximization / Мексимизация (500点)

テストごとの時間制限: 1秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
整数 n と配列 a_1,\,a_2,\,\dots,\,a_n が与えられます。全ての接頭辞(i 番目の接頭辞は a_1,\,a_2,\,\dots,\,a_i) の \textbf{MEX} の和が最大化されるように配列 a の要素を並べ替えなければなりません。

形式的には、配列 a の要素の集合と配列 b の要素の集合が等しく(配列 b が配列 a の要素をある程度並べ替えることで得られることと同値)、\displaystyle \sum_{i = 1}^{n} \textbf{MEX}(b_1,\,b_2,\,\dots,\,b_i) が最大となるような配列 b_1,\,b_2,\,\dots,\,b_n を求めなければなりません。

非負整数の集合の \textbf{MEX} とはその集合に属さない最小の非負整数の事です。

例えば \textbf{MEX}(\{1,\,2,\,3\}) = 0, \textbf{MEX}(\{0,\,1,\,2,\,4,\,5\}) = 3 となります。

入力

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

各テストケースの1行目には単一の整数 n (1 \leq n \leq 100) が与えられる。

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

出力

各テストケースについて配列 b_1,\,b_2,\,\dots,\,b_n を出力せよ、この配列は全接頭辞の \textbf{MEX} の和が最大となるように a_1,\,a_2,\,\dots,\,a_n を適切に並べ替えたものである。

答えが複数ある場合、そのいずれかを求めよ。

入出力例

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

注記

1つ目のテストケースの答えの接頭辞の \textbf{MEX} は次のようになります。

  1. \textbf{MEX}(\{0\}) = 1
  2. \textbf{MEX}(\{0,\,1\}) = 2
  3. \textbf{MEX}(\{0,\,1,\,2\}) = 3
  4. \textbf{MEX}(\{0,\,1,\,2,\,3\}) = 4
  5. \textbf{MEX}(\{0,\,1,\,2,\,3,\,4\}) = 5
  6. \textbf{MEX}(\{0,\,1,\,2,\,3,\,4,\,7\}) = 5
  7. \textbf{MEX}(\{0,\,1,\,2,\,3,\,4,\,7,\,3\}) = 5

\textbf{MEX} の和 = 1 + 2 + 3 + 4 + 5 + 5 + 5 = 25 です。これが接頭辞の \textbf{MEX} の和の可能な最大値であることは証明できます。

B. M-arrays / M-массивы (750点)

テストごとの時間制限: 1秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
n 正整数からなる配列 a_1,\,a_2,\,\dots,\,a_n と整数 m が与えられます。

この配列の要素をいくつかの配列に分割しなければなりません。新しい配列内の要素は好きなように並び替えることができます。

配列内での各隣り合う2つの数字(各 i について i と i + 1 の位置にある2つの数字を隣り合っていると呼ぶ)の和が m で割り切れる時、その配列を m-可分であるといいます。要素数1の配列は m-可分です。

a_1,\,a_2,\,\dots,\,a_n を分割して得られる m-可分な配列の最小数を求めよ。

入力

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

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

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

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

出力

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

入出力例

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

注記

1つ目のテストケースでは、要素を以下のように分けることができます。

  • [4,\,8]: 4 + 8 は 4 で割りきれるので 4-可分な配列です。
  • [2,\,6,\,2]: 2 + 6 と 6 + 2 は 4 で割りきれるので 4-可分です。
  • [9]: 1要素からなるので 4-可分な配列です。

C1. k-LCM (easy version) / k-НОК (простая версия) (750点)
C2. k-LCM (hard version) / k-НОК (сложная версия) (500点)

テストごとの時間制限: 1秒
テストごとのメモリ制限:256 MB
入力: 標準入力
出力: 標準出力
この問題はイージー版/ハード版です。唯一の違いはこの版では k = 3 (イージー版)/ 3 \leq k \leq n (ハード版)であることです。

正整数 n が与えられます。次を満たすような k 個の正整数 a_1,\,a_2,\,\dots,\,a_k を求めてください。

  • a_1 + a_2 + \dots + a_k = n
  • LCM(a_1,\,a_2,\,\dots,\,a_k) \leq \displaystyle \frac{n}{2}

ここで LCM とは数 a_1,\,a_2,\,\dots,\,a_k の最小公倍数*1です。

与えられた制約に対し、答えが常に存在することは示すことができます。

入力

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

各テストケースの唯一の行には2つの整数 n,\,k (3 \leq n \leq 10^9, k = 3 (イージー版)/ 3 \leq k \leq n (ハード版)) が与えられる。

出力

各テストケースに対して、すべての条件を満たす k 個の正整数 a_1,\,a_2,\,\dots,\,a_k を出力せよ。

入出力例

3
3 3
8 3
14 3
1 1 1
4 2 2
2 6 6
2
6 4
9 5
1 2 2 1 
1 3 3 1 1

D. Genius / Гений (1750点)

テストごとの時間制限: 2秒
テストごとのメモリ制限: 32 MB
入力: 標準入力
出力: 標準出力
非標準的なメモリ制限に注意してください。

1 から n の番号が付いた n 問の問題があります。i 問目の問題の複雑さは c_i = 2^i、タグは tag_i、スコアは s_i です。

問題 i を解いた後、\mathrm{IQ} < |c_i - c_j| かつ tag_i \neq tag_j を満たし、かつその場合のみ問題 j を解くことができます。それを解いたのち \mathrm{IQ} が変化し、\mathrm{IQ} = |c_i - c_j| となり、|s_i - s_j| 点を獲得します。

どの問題も1匁にすることができます。問題はどんな順番でもよく、同じ問題を何度も解くこともできます。

初期状態では \mathrm{IQ} = 0 です。得られる点数の最大値を求めてください。

入力

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

各テストケースの1行目には1つの整数 n (1 \leq n \leq 5000) が与えられる、これは問題数である。

各テストケースの2行目には n 個の整数 tag_1,\,tag_2,\,\dots,\,tag_n (1 \leq tag_i \leq n) が与えられる、これらは問題のタグである。

各テストケースの3行目には n 個の整数 s_1,\,s_2,\,\dots,\,s_n (1 \leq s_i \leq 10^9) が与えられる、これらは問題のスコアである。

全てのテストケースでの n の和が 5000 を超えないことは保証されている。

出力

各テストケースについて単一の整数を出力せよ、その数とは得られる点数の最大値である。

入出力例

5
4
1 2 3 4
5 10 15 20
4
1 2 1 2
5 10 15 20
4
2 2 4 1
2 8 19 1
2
1 1
6 9
1
1
666
35
30
42
0
0

注記

1つ目のテストケースでは、最適な問題を解く順番は次のようなものです。

  1. 1 \rightarrow 2: 合計点は 5 で \mathrm{IQ} = 2 となる
  2. 2 \rightarrow 3: 合計点は 10 で \mathrm{IQ} = 4 となる
  3. 3 \rightarrow 1: 合計点は 20 で \mathrm{IQ} = 6 となる
  4. 1 \rightarrow 4: 合計点は 35 で \mathrm{IQ} = 14 となる

2つ目のテストケースでは、最適な問題を解く順番は次のようなものです。

  1. 1 \rightarrow 2: 合計点は 5 で \mathrm{IQ} = 2 となる
  2. 2 \rightarrow 3: 合計点は 10 で \mathrm{IQ} = 4 となる
  3. 3 \rightarrow 4: 合計点は 15 で \mathrm{IQ} = 8 となる
  4. 4 \rightarrow 1: 合計点は 35 で \mathrm{IQ} = 14 となる

3つ目のテストケースでは、最適な問題を解く順番は次のようなものです。

  1. 1 \rightarrow 3: 合計点は 17 で \mathrm{IQ} = 6 となる
  2. 3 \rightarrow 4: 合計点は 35 で \mathrm{IQ} = 8 となる
  3. 4 \rightarrow 2: 合計点は 42 で \mathrm{IQ} = 12 となる

E1. Square-free division (easy version) / Бесквадратное разбиение (простая версия) (1500点)
E2. Square-free division (hard version) / Бесквадратное разбиение (сложная версия) (1500点)

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
この問題はイージー版/ハード版です。唯一の違いはこの版では k = 0 (イージー版)/ 0 \leq k \leq 20 (ハード版)であることです。

n 正整数の配列 a_1,\,a_2,\,\dots,\,a_n があります。各セグメント内に積が完全平方となる2つの数(違う位置の数)が存在しないように最小数の連続セグメントに分割しなければなりません。

さらに、分割する前に次の操作を最大 k 回行うことができます: 配列内の数を選び、その値を任意の正整数に変える。イージー版では k = 0 であるため、これは重要ではありません。

最適な変更を行ったときの、連続セグメントの最小数はいくつでしょうか?

入力

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

各テストケースの1行目には2つの整数 n,\,k (1 \leq n \leq 2 \cdot 10^5, k = 0 (イージー版)/ 0 \leq k \leq 20 (ハード版)) が与えられる。

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

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

出力

各テストケースに対して単一の整数を出力せよ、その数は問題の答えである。

入出力例

3
5 0
18 6 2 4 1
5 0
6 8 1 24 8
1 0
1
3
2
1
3
5 2
18 6 2 4 1
11 4
6 2 2 8 9 1 3 6 3 9 7
1 0
1
1
2
1

注記(easy)

1つ目のテストケースでは、次のように分割できます。

  • [18,\,6]
  • [2,\,4]
  • [1]

注記(hard)

1つ目のテストケースでは、次のように配列を変化させることができます: [\underline{3},\,6,\,2,\,4,\,\underline{5}](変化した要素は下線されている)。その後、配列を分割する必要はなく、答えは 1 となります。

2つ目のテストケースでは、次のように配列を変化させることができます: [6,\,2,\,\underline{3},\,8,\,9,\,\underline{5},\,3,\,6,\,\underline{10},\,\underline{11},\,7]。その後、次のような分割が最適となります。

  • [6,\,2,\,3]
  • [8,\,9,\,5,\,3,\,6,\,10,\,11,\,7]

*1:原文では英語、ロシア語のWikipediaへのリンク