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

A. Ezzat and Two Subsequences / Ezzat и две подпоследовательности (500点)
- 入力
- 出力
- 入出力例
- 注記
B. Moamen and k-subarrays / Moamen и k-подотрезки (1000点)
- 入力
- 出力
- 入出力例
- 注記
C. Moamen and XOR / Moamen и XOR (1750点)
- 入力
- 出力
- 入出力例
- 注記
D. Ezzat and Grid / Ezzat и таблица (2500点)
- 入力
- 出力
- 入出力例
- 注記
E. Assiut Chess / Шахматы в Assiut (3000点)

A. Ezzat and Two Subsequences / Ezzat и две подпоследовательности (500点)

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

Ezzat(عزت)*1は $n$ 個の整数(負の可能性もあり)から成る配列を持っています。彼はこの配列の各要素が正確に1つの部分列に属し、 $f(a) + f(b)$ の値が可能な限り最大となるように、空でない2つの部分列に分割したいと思っています。ここで、 $f(x)$ は部分列 $x$ の平均を表します。

数列 $y$ からいくつか(0個や全ての場合もあり)を削除することで数列 $x$ が得られるとき、 $x$ は $y$ の部分列であるといいます。

部分列の平均とは、この部分列の数値の合計を部分列の大きさで割ったものです。

例えば、 $[1,\,5,\,6]$ の平均は $\displaystyle \frac{1+5+6}{3} = \frac{12}{3} = 4$ であるため、 $f([1,\,5,\,6]) = 4$ となります。

入力

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

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

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

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

出力

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

絶対誤差または相対誤差が $10^{-6}$ を越えなければ正解と見做される。

形式的には、提出解を $a$ 、ジャッジ解を $b$ とする。 $\displaystyle \frac{|a-b|}{\max\{1,\,|b|\}} \leq 10^{-6}$ であるとき、正答とみなされる。

入出力例

4.500000000
-12.500000000
4.000000000
18.666666667

注記

1つ目のテストケースでは、配列は $[3,\,1,\,2]$ です。この配列を分割する全ての方法は次のようなものです。

$a = [3],$ $b=[1,\,2]$ 。このとき値は $f(a) + f(b) = 3 + 1.5 = 4.5$ となる
$a = [3,\,1],$ $b=[2]$ 。このとき値は $f(a) + f(b) = 2 + 2 = 4$ となる
$a = [3,\,2],$ $b=[1]$ 。このとき値は $f(a) + f(b) = 2.5 + 1 = 3.5$ となる

従って、可能な最大値は $4.5$ となります。
2つ目のテストケースでは、配列は $[-7,\,-6,\,-6]$ です。この配列を分割する全ての方法は次のようなものです。

$a = [-7],$ $b=[-6,\,-6]$ 。このとき値は $f(a) + f(b) = (-7) + (-6) = -13$ となる
$a = [-7,\,-6],$ $b=[-6]$ 。このとき値は $f(a) + f(b) = (-6.5) + (-6) = -12.5$ となる

従って、可能な最大値は $-12.5$ となります。

B. Moamen and k-subarrays / Moamen и k-подотрезки (1000点)

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

Moamen(مؤمن)*2は異なる $n$ 個の整数から成る配列を持っています。彼は次の操作を順番に正確に1回行うことで、この配列を非減少順に並び替えたいと考えています。

各要素が正確に1つの連続部分列に属すように、配列をちょうど $k$ 個の空でない連続部分列に分割する
これらの部分配列を任意に並び替える
新しい順序で部分配列を結合する

数列 $b$ の先頭からいくつか(0個や全ての場合もあり)の要素を削除し、末尾からいくつか(0個や全ての場合もあり)の要素を削除することで数列 $a$ が得られるとき、 $a$ は $b$ の連続部分列であるといいます。

上記の操作を正確に一度だけ行って、配列を非減少順に並び替える方法があるかどうか、Moamenに教えてください。

入力

1行目には単一の整数 $t$ $(1 \leq t \leq 10^3)$ が与えられる、これはテストケース数である。テストケースについての記述が続く。

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

2行目には $n$ 個の整数 $a_1,\,a_2,\,\dots,\,a_n$ $(0 \leq |a_i| \leq 10^9)$ が与えられる。全ての数が相異なることは保証されている。

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

出力

各テストケースについて、単一の文字列を出力せよ。

Moamenが配列を非減少順に並び替えることができる場合、"YES"(引用符なし)と出力せよ。そうでなければ、"NO"(引用符なし)と出力せよ。

"YES"と"NO"の各文字はどの活字ケース(大文字/小文字)で出力してもよい。

入出力例

Yes
No
Yes

注記

1つ目のテストケースでは、 $a = [6,\,3,\,4,\,2,\,1],$ $k = 4$ であり、次のように操作を行うことができます。

$a$ を $\{[6],\,[3,\,4],\,[2],\,[1]\}$ に分割する
並び替える: $\{[1],\,[2],\,[3,\,4],\,[6]\}$
結合する: $[1,\,2,\,3,\,4,\,6].$ これで配列はソートされた

2つ目のテストケースでは、配列を $2$ つの連続部分列に分割してソートを行う方法はありません。

例えば、配列を $\{[1,\,-4],\,[0,\,-2]\}$ に分割した場合、 $\{[1,\,-4],\,[0,\,-2]\}$ または $\{[0,\,-2],\,[1,\,-4]\}$ のようにしか並び替えることができません。しかし、どちらの場合も、結合後の配列はソートされていません。

C. Moamen and XOR / Moamen и XOR (1750点)

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

Moamen(مؤمن)とEzzat(عزت)がゲームをしています。彼らは、各要素が $2^k$ より小さいような、 $n$ 個の非負整数から成る配列 $a$ を作ります。

$a_1 \,\&\, a_2 \,\&\, a_3 \,\&\, \ldots \,\&\, a_n \ge a_1 \oplus a_2 \oplus a_3 \oplus \ldots \oplus a_n$ である場合、Moamenが勝ちます。

ここで $\&$ はbit単位AND *3を、 $\oplus$ はbit単位XOR *4を表します。

Moamenが勝つような配列 $a$ の個数を計算してください。

結果は非常に大きくなる可能性があるため、 $1\,000\,000\,007$ $(10^9+7)$ で割った値を出力してください。

入力

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

各テストケースは2つの整数 $n,\,k$ $(1 \leq n \leq 2 \cdot 10^5,$ $0 \leq k \leq 2 \cdot 10^5)$ を含む1行で構成される。

出力

各テストケースについて、単一の値を出力せよ、その値はMoamenが勝つような配列の個数である。

結果を modulo $1\,000\,000\,007$ $(10^9+7)$ で出力せよ。

入出力例

5
2
1

注記

1つ目のテストケースでは、 $n = 3,$ $k = 1$ です。結果として、可能な配列は $[0,\,0,\,0],$ $[0,\,0,\,1],$ $[0,\,1,\,0],$ $[1,\,0,\,0],$ $[1,\,1,\,0],$ $[0,\,1,\,1],$ $[1,\,0,\,1],$ $[1,\,1,\,1]$ で全てです。

Moamenはそのうち5つでのみ勝利します: $[0,\,0,\,0],$ $[1,\,1,\,0],$ $[0,\,1,\,1],$ $[1,\,0,\,1],$ $[1,\,1,\,1]$ 。

D. Ezzat and Grid / Ezzat и таблица (2500点)

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

Moamen(مؤمن)は $0$ と $1$ の数字だけを含む $n$ 行 $10^9$ 列のグリッドを描いていました。Ezzat(عزت)はMoamenが描いているものに気付き、グリッドを美しくするために削除する必要のある行の最小個数に興味を持ちました。

グリッドの全ての連続する2行について、この2行に $1$ を持つような列が少なくとも1つ存在する場合、かつその場合のみグリッドは美しいといいます。

Ezzatは行数 $n$ と、数字 $1$ を含むグリッドの $m$ 個のセグメントを与えます。各セグメントは3つの整数 $i,\,l,\,r$ で表され、 $i$ は行番号を、 $l,\,r$ はその行のセグメントの最初と最後の列を表します。

例えば、 $n = 3,$ $m = 6$ で、セグメントが $(1,\,1,\,1),$ $(1,\,7,\,8),$ $(2,\,7,\,7),$ $(2,\,15,\,15),$ $(3,\,1,\,1),$ $(3,\,15,\,15)$ であるとき、グリッドは次のようになります。

$\begin{align*}10000011000000000\dots\dots\dots\dots\\00000010000000100\dots\dots\dots\dots\\10000000000000100\dots\dots\dots\dots\end{align*}$

グリッドを美しくするために削除しなければならない最小の行数をEzzatに伝えてください。

入力

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

続く $m$ 行のそれぞれには3つの整数 $i,\,l,\,r$ $(1 \leq i \leq n,$ $1 \leq l \leq r \leq 10^9)$ が与えられる。これら $m$ 行のそれぞれは行番号 $i$ は $l$ 列目から $r$ 列目(両端含む)までに数字 $1$ を含んでいることを表す。

セグメントは重なることもあることに注意せよ。

出力

1行目には単一の整数 $k$ を出力せよ、これは削除しなければならない最小の行数である。

2行目には削除しなければならない行を表す $k$ 個の相異なる整数 $r_1,\,r_2,\,\dots,\,r_k$ $(1 \leq r_i \leq n)$ をいずれかの順序で出力せよ。

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

入出力例

3
2 4 5

注記

1つ目のテストケースのグリッドは問題文で説明されているものです。このグリッドは次のような特性を持っています。

$1$ 行目と $2$ 行目は列 $7$ に共通して $1$ を持つ
$2$ 行目と $3$ 行目は列 $15$ に共通して $1$ を持つ

結果として、このグリッドは美しく、どの行も削除する必要はありません。
2つ目のテストケースでは、グリッドは次のようになります。

$\begin{align*}01100000\dots\dots\dots\dots\\00011100\dots\dots\dots\dots\\00111000\dots\dots\dots\dots\\00000000\dots\dots\dots\dots\\10000000\dots\dots\dots\dots\end{align*}$

E. Assiut Chess / Шахматы в Assiut (3000点)

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

これはインタラクティブ問題です。

ICPC Assuit(أسيوط)*5 コミュニティ(以下、ICPC Assiut Community)がユニークなチェスの大会を開催することとなり、貴方はクイーンを操って隠れたキングを追い詰める役に選ばれました。キングはICPC Assiut Communityのメンバーがキングを操ります。

$8 \times 8$ のチェス盤上で対戦を行い、行は上から下へ、列は左から右へと数字が振られていて、 $x$ 行 $y$ 列にあるマスは $(x,\,y)$ と表されます。

1手でクイーンを同一横線上、縦線上、斜線上のいずれかのマスに移動させることができます。例えば、クイーンが $(4,\,5)$ にあった場合、 $(q_1,\,5),$ $(4,\,q_1)$ *6 $,$ $(q_1,\,9 - q_1),$ $(q_2,\,q_2+1)$ $(1 \leq q_1 \leq 8,$ $q_1 \neq 4,$ $1 \leq q_2 \leq 7,$ $q_2 \neq 4)$ のいずれかに移動できます。クイーンは現在のマスに留まることはできないことに注意してください。

1手でキングは盤面から出ないように「右」「左」「上」「下」「右下」「左下」「左上」「右上」のいずれかに移動できます。キングはクイーンと同じ行、列、斜線上にあるマス(クイーン自身がいるマスを含む)に移動することはできません。例えば、キングがマス $(4,\,5)$ にいた場合、 $(4+k_1,\,5+k_2)$ $(-1 \leq k_1,\,k_2 \leq 1,$ $(k_1,\,k_2) \neq (0,\,0))$ に移動することができます。 f:id:Flkanjin:20210810153934p:plain

ゲーム開始時に、クイーンを盤上の任意のマスに配置し、これはゲーム注意回のみ行われます。その後、クイーンとは異なる位置にキングが秘かに置かれます。貴方にはキングの位置は分かりません。その後、キングを先手として、キングとクイーンが交互に手を打ちます。キングは可能な方向(「右」「下」「上-左」など)に動き、その方向のみが貴方に伝えられます。そののち、クイーンが移動するマスを宣言し、クインを移動させなければなりません。このようにしてゲームは、貴方が勝つか、手番がなくなるまで続きます。

キングに有効な手がなくなれば貴方の勝ちです。 $130$ 回クイーンを動かした後もキングに有効な手があれば、貴方の負けです。

入力

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

相互入出力

各テストケースにおいて、クイーンの開始位置を直ちに出力せよ。キングのいるマスにクイーンを置いた場合、直ちに勝利する。

その後、最大で $130$ 手を打つことができる。各手は $x\ y$ という形式で行われる、ここで $x,\,y$ $(1 \leq x,\,y \leq 8)$ はそれぞれクイーンの亜tらしい行と列を表す2つの整数である。この手はクイーンの有効な手でなければならない。

最初のクイーンの配置の後や自分の手の後、キングの移動方向を表す文字列 $s$ を受け取る。これは次のうちのいずれかである: "Right", "Left", "Up", "Down", "Down-Right", "Down-Left", "Up-Left", "Up-Right"、もしくは勝利時の"Done"。"Done"は各テストケースの終わりとして考えよ。