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

A. Min Or Sum / Минимальная OR сумма (500点)
- 入力
- 出力
- 入出力例
- 注記
B. Avoid Local Maximums / Избегайте локальных максимумов (1000点)
- 入力
- 出力
- 入出力例
- 注記
C. Differential Sorting / Дифференциальная сортировка (1500点)
- 入力
- 出力
- 入出力例
- 注記
D. Infinite Set / Бесконечный набор (2250点)
- 入力
- 出力
- 入出力例
- 注記
E. Cars / Автомобили (2550点)
F. Closest Pair / Ближайшая пара (3000点)
- 入力
- 出力
- 入出力例
- 注記

A. Min Or Sum / Минимальная OR сумма (500点)

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

大きさ $n$ の配列 $a$ が与えられます。
この配列に対して次の操作を行うことができます。

異なる2つの整数 $i,\,j$ $(1 \leq i \lt j \leq n)$ を選び、 $a_i$ を $x$ に、 $a_j$ を $y$ に置き換える。配列の破壊を行わないために、 $a_i | a_j = x | y$ を満たさなければなりません、ここで $|$ はビットOR *1を表す。 $x$ と $y$ は非負整数であることに注意せよ。

上記の操作を任意の回数行った後に得られる配列の要素の和の最小値を出力してください。

入力

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

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

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

出力

各テストケースについて、単一の値を出力せよ、その値とは達成できる配列の最小和である。

入出力例

注記

1つ目の入力例では、次のような操作で配列 $[1,\,0,\,2]$ を得ることができます。

$i = 1,$ $j = 2$ と選び、 $a_1 = 1,$ $a_2 = 2$ とする、この操作は $1|3 = 1|2$ であるため有効である。配列は $[1,\,2,\,2]$ となる。
$i = 2,$ $j = 3$ と選び、 $a_2 = 0,$ $a_3 = 2$ とする、この操作は $2|2 = 0|2$ であるため有効である。配列は $[1,\,0,\,2]$ となる。

最小和が $1 + 0 + 2 = 3$ であることは証明することができます。

2つ目の入力例では、操作は必要ありません。

B. Avoid Local Maximums / Избегайте локальных максимумов (1000点)

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

大きさ $n$ の配列 $a$ が与えられます。この配列の各要素は $1$ から $10^9$ までの整数です。

この配列に対して何回か操作を行うことができます。1回の操作では、配列の中の1つの要素を $1$ から $10^9$ までの任意の整数に置き換えることができます。

結果として得られる配列に極大要素が含まれないようにするため必要な操作の最小回数と、操作後の配列を出力してください。

要素 $a_i$ はその近傍の両方よりも厳密に大きい(即ち、 $a_i \lt a_{i-1}$ かつ $a_i \lt a_{i+1}$ )時、極大要素であるといいます。 $a_1$ と $a_n$ は近傍要素がそれぞれ1つずつしかないため、極大要素となることはありません。

入力

各テストは複数のテストケースが含まれる。1行目には単一の整数 $t$ $(1 \leq t \leq 10000)$ が与えられる、これはテストケースの個数である。以下、 $t$ 個のテストケースが続く。

各テストケースの1行目には単一の整数 $n$ $(2 \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$ を超えないことは保証されている。

出力

各テストケースについて、まず、単一の整数 $m$ を単一行にで出力せよ、この数は必要な操作の最小回数である。次に $n$ 個の整数から成る1行を出力せよ、この整数は操作の結果得られる配列である。この配列は、最初の配列とちょうど $m$ 個の要素が異なっていなければならないことに注意せよ。

答えが複数ある場合は、そのうちのいずれかを出力せよ。

入出力例

5
3
2 1 2
4
1 2 3 1
5
1 2 1 2 1
9
1 2 1 3 2 3 1 2 1
9
2 1 3 1 3 1 3 1 3

0
2 1 2
1
1 3 3 1
1
1 2 2 2 1
2
1 2 3 3 2 3 3 2 1
2
2 1 3 3 3 1 1 1 3

注記

1つ目の入力例では、配列内に極大要素がないため、操作を行う必要はありません。

2つ目の入力例では、 $a_2$ を $3$ に変えることができ、そうすることで配列は極大要素を持たないようになります。

C. Differential Sorting / Дифференциальная сортировка (1500点)

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

大きさ $n$ の配列 $a$ が与えられます。

次の操作を $n$ 回まで行うことができます: 3つのインデックス $x,\,y,\,z$ $(1 \leq x < y < z \leq n)$ を選び、 $a_x$ を $a_y - a_z$ に置換する。この操作の後、 $|a_x|$ は $10^{18}$ 以下でなければなりません。

結果として得られる配列が非減少になるようにすることが目標です。解が複数存在する場合は、そのいずれをも出力することができます。実現不可能である場合は、そのことを知らせてください。

入力

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

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

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

出力

各テストケースについて、解が存在しない場合、単一行に $-1$ を出力せよ。そうでない場合、1行目に単一の整数 $m$ $(0 \leq m \leq n)$ を出力せよ、この数は実行した操作の回数である。

その後、続く $m$ 行の $i$ 行目には3個の整数 $x,\,y,\,z$ $(1 \leq x < y < z \leq n)$ を出力せよ、これらは $i$ 回目の操作についての説明である。

解が複数存在する場合は、どれを出力してもよい。このタスクでは、操作回数を最小化する必要はないことに注意せよ。

入出力例

3
5
5 -4 2 -1 2
3
4 3 2
3
-3 -2 -1

注記

1つ目の入力例では、配列は次のようになります。

1回目の操作の後: $[-6,\,-4,\,2,\,-1,\,2]$

2回目の操作の後: $[-6,\,-4,\,-3,\,-1,\,2]$

2つ目の入力例では、どのような操作を行っても配列を昇順にすることは不可能です。

3つ目の入力例では、配列は既に昇順になっているため、操作を行う必要はありません。

D. Infinite Set / Бесконечный набор (2250点)

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

$n$ 個の相異なる正整数から成る配列 $a$ が与えられます。

以下の条件の少なくとも一つを満たす全ての整数 $x$ を含む無限整数集合 $S$ を考えます。

ある $1 \leq i \leq n$ について $x = a_i$
$y \in S$ について $x = 2y+1$
$y \in S$ について $x = 4y$

例えば、 $a = [1,\,2]$ のとき、 $S$ 内の小さい方から $10$ 個の要素は $\{1,\,2,\,3,\,4,\,5,\,7,\,8,\,9,\,11,\,12\}$ となります。

$S$ の要素のうち $2^p$ よりも厳密に小さい要素の個数を求めて下さい。答えは大きくなる可能性があるため、modulo $10^9+7$ で出力してください。

入力

1行目には2つの整数 $n,\,p$ $(1 \leq n,\,p \leq 2 \cdot 10^5)$ が与えられる。

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

$a$ 内の全ての数が相異なることは保証される。

出力

単一の整数を出力せよ、その数とは $S$ の要素のうち $2^p$ よりも厳密に小さい要素の個数である。modulo $10^9+7$ で出力することに忘れないようにせよ。

入出力例

2 4
6 1

4 7
20 39 5 200

2 200000
48763 1000000000

448201910

注記

1つ目の入力例では、 $2^4$ よりも小さい要素は $\{1,\,3,\,4,\,6,\,7,\,9,\,12,\,13,\,15\}$ です。

2つ目の入力例では、 $2^7$ よりも小さい要素は $\{5,\,11,\,20,\,23,\,39,\,41,\,44,\,47,\,79,\,80,\,83,\,89,\,92,\,95\}$ です。

E. Cars / Автомобили (2550点)

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

座標軸 $OX$ 上に $n$ 台の自動車があります。各自動車は最初は整数の点上に位置し、2台以上の自動車が同一点上に位置することはありません。また、各自動車は左右いずれかを向いており、どの瞬間においてもその方向に任意の一定の正の速度で動くことができます。

より形式的には、 $i$ 番目の車を1文字と1つの整数で表すことができます: 方向 $ori_i$ と位置 $x_i$ です。 $ori_i=L$ である場合、 $x_i$ は時間に対して一定の割合で減少します。同様に $ori_i=R$ である場合、 $x_i$ は時間に対して一定の割合で増加します。

2台の車が速度に関係なく決して同じ地点に着かない場合、無関係であるといいます。つまり、どの瞬間にも同じ座標を共有することはありません。

2台の車が速度に関係なく同じ地点に着く場合、運命的であるといいます。つまり、同じ座標を共有する瞬間があります。

残念なことに、車に関する情報はすべて失われてしまいましたが、 $m$ 個の関係は覚えています。関係には2種類あります。

$1\ i\ j$ : $i$ 台目と $j$ 台目の自動車が無関係である。

$2\ i\ j$ : $i$ 台目と $j$ 台目の自動車が運命的である。

この関係を満たす自動車の方向と位置を復元するか、それが不可能であることを報告してください。解が複数存在する場合、そのいずれをも出力してもいいです。

2台の車が同じ座標を共有している場合は交差となりますが、そのままそれぞれの方向への移動が継続されることに注意してください。

入力

1行目には2つの整数 $n,\,m$ $\biggl(2 \leq n \leq 2 \cdot 10^5;$ $\displaystyle 1 \leq m \leq \min\left\{2 \cdot 10^5, \frac{n(n-1)}{2}\right\} \biggr)$ が与えられる、それぞれ自動車の台数と制限の個数である。

次の $m$ 行のそれぞれには3個の整数 $type,\,i,\,j$ $(1 \leq type \leq 2;$ $1 \leq i,\,j \leq n;$ $i \neq j)$ が与えられる。

$type = 1$ の場合、 $i$ 台目と $j$ 台目の自動車は無関係である。そうでないとき、 $i$ 台目と $j$ 台目の自動車は運命的である。

自動車の各ペアについて、その間の関係は最大でも $1$ つであることは保証される。

出力

1行目には、関係を満たす車の方向と位置を復元できるかどうか、"YES"または"NO"のいずれかを出力せよ(大文字小文字はいずれの場合でも可)。

答えが"YES"である場合、それぞれの行が1文字と1つの整数を含む $n$ 行出力せよ。1文字と1つの整数とは $ori_i,\,x_i$ $(ori_i \in \{L,\,R\};$ $-10^9 \leq x_i \leq 10^9)$ であり、 $i$ 台目の自動車の情報を表す。

方向が左の場合は $ori_i = L$ で、そうでない場合 $ori_i = R$ とする。

$x_i$ は $i$ 台目の自動車の位置である。 $x_i$ は全て異なることに注意せよ。

解が存在する場合、 $x_i$ の制約を満たす解が存在することは証明することができる。

入出力例

YES
R 0
L -3
R 5
L 6

NO

F. Closest Pair / Ближайшая пара (3000点)

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

$OX$ 軸上に重み付きの点が $n$ 点あります。 $i$ 番目の点の座標と重みはそれぞれ $x_i$ と $w_i$ です。全ての点は、座標は相異なり、正の重みを持ちます。また、任意の $1 \leq i < n$ について $x_i < x_{i+1}$ が成り立ちます。

$i$ 番目の点と $j$ 番目の点の重み付き距離は $|x_i - x_j| \cdot (w_i + w_j)$ と定義されます、ここで $|val|$ は $val$ の絶対値を表します。

$q$ 個のクエリに答える必要があり、その $i$ 番目のクエリは次のようなものです: 部分列 $[l_i,\,r_i]$ 内の相異なる全ての点の組の間での最小の重み付き距離を求めよ。

入力

1行目には2個の整数 $n,\,q$ $(2 \leq n \leq 3 \cdot 10^5;$ $1 \leq q \leq 3 \cdot 10^5)$ が与えられる、これらは点とクエリの個数である。

$n$ 行が続き、その $i$ 行目には2個の整数 $x_i,\,w_i$ $(-10^9 \leq x_i \leq 10^9;$ $1 \leq w_i \leq 10^9)$ が与えられる、これらは $i$ 番目の点の座標と重みである。

点は $x$ の昇順に与えられることは保証されている。

その後、 $q$ 行が続き、その $i$ 行目には2個の整数 $l_i,\,r_i$ $(-1 \leq l_i < r_i \leq n)$ が与えられる、これらは $i$ 番目のクエリの部分列である。

出力

各クエリについて1個の整数を出力せよ、その数とは与えられた部分列内の異なる全ての点の組の間での最小の重み付き距離である。

入出力例

注記

1つ目のクエリについて、最小重み付き距離は点 $1$ と点 $3$ の間のもので、 $|x_1 - x_3| \cdot (w_1 + w_3) = |-2 - 1| \cdot (2 + 1) = 9$ となります。

2つ目のクエリについて、最小重み付き距離は点 $2$ と点 $3$ の間のもので、 $|x_2 - x_3| \cdot (w_2 + w_3) = |0 - 1| \cdot (10 + 1) = 11$ となります。

4つ目のクエリについて、最小重み付き距離は点 $3$ と点 $4$ の間のもので、 $|x_3 - x_4| \cdot (w_3 + w_4) = |1 - 9| \cdot (1 + 2) = 24$ となります。

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