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

A. Anti-knapsack / Антирюкзак (750点)
B. Planet Lapituletti / Планета Лапитулетти (1250点)
- 入力
- 出力
- 入出力例
- 注記
C. K-beautiful Strings / K-красивые строки (1750点)
- 入力
- 出力
- 入出力例
- 注記
D. GCD of an Array / НОД массив (2250点)
- 入力
- 出力
- 入出力例
- 注記
E. Enormous XOR / Огромный XOR (2750点)
- 入力
- 出力
- 入出力例
- 注記
F. Enchanted Matrix / Заколдованная матрица (3250点)

A. Anti-knapsack / Антирюкзак (750点)

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

2つの整数 $n,\,k$ が与えられます。和が $k$ となる部分集合が存在しないように $1$ から $n$ までの整数から異なる数を最大個数選ばなければなりません。

集合の部分集合とはその集合から要素をいくつか(全てでもよいし0個でもよい)取り除くことで得られる集合のことです。

入力

1行目にはテストケース数 $T$ $(1 \leq T \leq 100)$ が与えられる。

つづく $T$ 行の各行には2つの整数 $n,\,k$ $(1 \leq k \leq n \leq 1000)$ が与えられる、これらがテストケースについての説明である。

出力

各テストケースについて2行出力せよ。1行目には単一の整数 $m$ を出力せよ、これは選んだ整数の個数である。

2行目には $1$ から $n$ までの $m$ 個の異なる整数を出力せよ、これらが選んだ整数である。

もし答えが複数ある場合、そのいずれを出力してよい。数についてはどのような順序でもよい。

入出力例

B. Planet Lapituletti / Планета Лапитулетти (1250点)

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

惑星Lapituletti(Лапитулетти)では地球と同じように時間が進みますが、1日は $h$ 時間で、1時間は $m$ 分です。この惑星の住民は地球のものと同じようなデジタル時計を使っています。時計には時刻はHH:MM(最初に時数が十進法で表示され、その後(コロンの後)に十進法での分数が続く。時数と分数は2桁で表示されるため必要に応じて頭に0がつく)という形式で表示されます。時数は $0$ から $h-1$ まで、分数は $0$ から $m-1$ までの番号がつけられている。

f:id:Flkanjin:20210307161818p:plain — 時計での数字の表記方法です。数字の $1$ は中央に位置することに注意してください。

時計での数字の表記方法です。数字の $1$ は中央に位置することに注意してください。

惑星Lapitulettiでは標準的な鏡が使われています。住民はよく鏡に映ったデジタル時計を見ますが、反射した時計が有効な時刻を示していると幸せな気分になります(つまり、反射した数字が有効であり、そのような反射時刻が1日のある瞬間に普通の時計が示すものであるときです)。

鏡に映った時計の像は縦線に対して反射します。

f:id:Flkanjin:20210307163540p:plain — 反射像は有効な時刻ではありません。

f:id:Flkanjin:20210307163642p:plain — $h = 24,$ $m = 60$ のとき、反射像は有効な時刻です。しかし例えば $h = 10,$ $m = 60$ のときは有効な時刻ではありません

$h = 24,$ $m = 60$ のとき、反射像は有効な時刻です。しかし例えば $h = 10,$ $m = 60$ のときは有効な時刻ではありません

惑星Lapitulettiのある住民は時刻 $s$ に時計の鏡像を皆締め、次に反射時刻が有効なものになる最も近い瞬間(次の日になる可能性もある)はいつなのか知りたいと思っています。

任意の $h,\,m,\,s$ についてそのような瞬間が存在することは示すことができます。この住民が時計を見始めた瞬間に反射時刻が有効である場合、その瞬間が最も近いものとみなされます。

いくつかのテストケースについて問題を解いてください。

入力

1行目には $T$ $(1 \leq T \leq 100)$ が与えられる、これはテストケース数である。

つづく $2 \cdot T$ 行にはテストケースについての記述が与えられる。各テストケースの記述は2行からなる。

テストケースの1行目には2つの整数 $h,\,m$ $(1 \leq h,\,m \leq 100)$ が与えられる。

2行目には開始時刻 $s$ がHH:MMの記述形式で与えられる。

出力

各テストケースについて反射時刻が正しくなる最近瞬間をHH:MMの形式でそれぞれの行に出力せよ。

入出力例

注記

2つ目のテストケースでは23:59の反射が不正であり、次の日の00:00の反射が正当であることが簡単にわかります。
f:id:Flkanjin:20210307165128p:plain

C. K-beautiful Strings / K-красивые строки (1750点)

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

小文字英字からなる文字列 $s$ と数 $k$ が与えられます。小文字英字からなる文字列について、各文字の出現回数が $k$ で割り切れる場合、その文字列を美しいと呼ぶことにしましょう。長さ $n$ の美しい文字列で辞書順で $s$ 以上のもののうち最小のものを求めてください。そのような文字列が存在しない場合、 $-1$ を出力してください。

文字列 $a$ が文字列 $b$ よりも辞書順で小さいとは、次の条件のいずれかを満たし、かつそのような場合のみです。

$a$ が $b$ の接頭辞であるが、 $a \neq b$ である場合
$a$ と $b$ が異なるような最初の位置において、文字列 $a$ の文字がアルファベット順で文字列 $b$ の文字よりも先に出てくる場合

入力

1行目には $T$ $(1 \leq T \leq 10\,000)$ が与えられる、これはテストケース数である。

つづく $2 \cdot T$ 行にはテストケースについての記述が与えられる。各テストケースの記述は2行からなる。

テストケースの1行目には2つの整数 $n,\,k$ $(1 \leq n,\,k \leq 10^5)$ が与えられる、これらは文字列の $s$ の長さと数 $k$ である。

2行目には小文字英字からなる文字列 $s$ が与えられる。

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

出力

各テストケースについて、長さ $n$ の美しい文字列で辞書順で $s$ 以上のもののうち最小のものを出力せよ、そのような文字列が存在しない場合 $-1$ を出力せよ。

入出力例

4
4 2
abcd
3 1
abc
4 3
aaaa
9 3
abaabaaaa

acac
abc
-1
abaabaaab

注記

1つ目のテストケースでは、"acac"は $s$ 以上であり、その中には各文字は $2$ 回か $0$ 回出現するため美しいです。

2つ目のテストケースでは、 $s$ の中には各文字は $0$ 回か $1$ 回出現するため $s$ 自身が答えになります。

3つ目のテストケースでは、適切な文字列が存在しないことを示すことができます。

4つ目のテストケースでは、"abaabaaab"の中には各文字は $0$ 回か $3$ 回、 $6$ 回出現すします。全ての整数は $3$ で割り切れます。

D. GCD of an Array / НОД массив (2250点)

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

長さ $n$ の配列 $a$ が与えられます。次の形式の $q$ 個のクエリを処理しなければなりません: 整数 $i,\,x$ が与えられ、 $a_i$ に $x$ を掛ける。

各クエリを処理した毎に、配列 $a$ の全要素の最小公約数(GCD)*1を出力しなければなりません。

答えは大きくなりすぎることもあるため、modulo $10^9 + 7$ で出力してください。

入力

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

2行目には $n$ 個の整数 $a_1,\,a_2,\,\dots,\,a_n$ $(1 \leq a_i \leq 2 \cdot 10^5)$ が与えられる、これらは変化前の配列 $a$ の要素である。

つづく $q$ 行には次の形式でクエリが与えられる: 各行に2つの整数 $i,\,x$ $(1 \leq i \leq n,$ $1 \leq x \leq 2 \cdot 10^5)$ が与えられる。

出力

$q$ 行出力せよ、各クエリを処理した後の全要素のGCDのmodulo $10^9 + 7$ を各行に出力せよ。

入出力例

2
2
6

注記

1つ目のクエリの後: $[12,\,6,\,8,\,12],$ $\gcd(12,\,6,\,8,\,12) = 2$

2つ目のクエリの後: $[12,\,18,\,8,\,12],$ $\gcd(12,\,18,\,8,\,12) = 2$

3つ目のクエリの後: $[12,\,18,\,24,\,12],$ $\gcd(12,\,18,\,24,\,12) = 6$

ここで $\gcd$ 函数は最大公約数を表します。

E. Enormous XOR / Огромный XOR (2750点)

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

二進数表現で2つの整数 $l,\,r$ が与えられます。 $g(x,\,y)$ を $x$ から $y$ までの全ての整数(両端を含む)のビットXOR *2(即ち $x \oplus (x+1) \oplus \dots \oplus (y-1) \oplus y$ )とします。 $f(l,\,r)$ を $l \leq x \leq y \leq r$ を満たす全ての $g(x,\,r)$ の最大値と定義しましょう。

$f(l,\,r)$ を出力してください。

入力

1行目には単一の整数 $n$ $(1 \leq n \leq 10^6)$ が与えられる、これは $r$ の2進数表現での長さである。

2行目には $l$ の二進数表現が与えられる、これは $0$ と $1$ の数字からなる長さ $n$ の文字列である。

3行目には $r$ の二進数表現が与えられる、これは $0$ と $1$ の数字からなる長さ $n$ の文字列である。

$l \leq r$ であることは保証されている。 $r$ の二進数表現には余分なleading zeroは含まれない( $r = 0$ のときは二進数表現は単一のゼロから成る)。 $l$ の二進数表現は長さが $n$ になるようにleading zeroが附けられる。

出力

与えられた $l$ と $r$ の組に対する $f(l,\,r)$ の値を、余分なleading zeroを除いた二進数表現で単一行に出力せよ。

入出力例

7
0010011
1111010

4
1010
1101

注記

サンプルケースでは $l = 19,$ $r = 122$ です。 $f(x,\,y)$ *3は例えば $x = 27,$ $y = 100$ のとき $127$ となり最大値をとります。

F. Enchanted Matrix / Заколдованная матрица (3250点)

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

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

サイズ $n \times m$ ( $n$ 行 $m$ 列)の行列 $a$ がありますが、 $n,\,m$ の値しか分かりません。この行列の行は上から下へ $1$ から $n$ の番号が振られていて、列は左から右へ $1$ から $m$ の番号が振られています。行 $x$ と列 $y$ の交点のセルを $(x,\,y)$ と表記します。

行列をサイズ $r \times c$ の長方形に分解したとき (縦 $r$ 行、横 $c$ 列の長方形で、各セルはちょうど1つの長方形に所属する)、全ての長方形が互いに等しいような組 $(r,\,c)$ の個数を求めてください。

次のようなクエリを利用することができます。

$\texttt{?}\ \ h\ \ w\ \ i_1\ \ j_1\ \ i_2\ \ j_2$ $(i \leq h \leq n,$ $1 \leq w \leq m,$ $1 \leq i_1,\,i_2 \leq n,$ $1 \leq j_1,\,j_2 \leq m)$ : 行列 $a$ の縦 $h$ 行、横 $w$ 列の重ならない部分矩形が等しいかどうかを調べる。1つ目の部分矩形の左上角は $(i_1,\,j_1)$ で、2つ目の部分矩形の左上角は $(i_2,\,j_2)$ である。部分矩形は少なくとも1つの共通セルが存在するとき重なります。クエリ内の部分矩形の座標が不正であったり(例えば行列の境界外にあるとき)、重なっているとき、解答は不正なものとみなされる。

$3 \cdot \left \lfloor{ \log_2{(n+m)} } \right \rfloor$ 回までクエリを投げることができます。行列 $a$ の要素はプログラム開始前に固定されていて、クエリに依存することはありません。

入力

1行目には2つの整数 $n,\,m$ $(1 \leq n,\,m \leq 1000)$ が与えられる、それぞれ行と列の数である。

出力

答える準備ができたら1行に感嘆符('!')と答えを出力せよ、答えは適切な組 $(r,\,c)$ の数である。その後、プログラムは終了しなければならない。

相互入出力

クエリの作成には" $\texttt{?}\ \ h\ \ w\ \ i_1\ \ j_1\ \ i_2\ \ j_2$ "という形式で1行出力せよ、ここでそれぞれの整数は重ならない長方形の高さと幅と左上角の座標であり、これらの長方形が等しいかどうかを調べるものである。

各クエリの後、単一の整数 $t$ $(t$ は $0$ か $1)$ を読み取らなければならない。部分矩形が等しい場合 $t = 1$ で、そうでない場合 $t = 0$ である。

クエリの形式が間違っている場合や $3 \cdot \left \lfloor{ \log_2{(n+m)} } \right \rfloor$ 回よりも多くクエリを尋ねた場合、Wrong Answerという判定を得る。

クエリの出力後、改行出力、出力バッファのflushを忘れないようにせよ。そうでなければIdleness limit exceededとなる。出力バッファのflushのためには次を利用せよ。

C++の場合、fflush(stdout)やcout.flush()
Javaの場合、System.out.flush()
Pascalの場合、flush(output)
Pythonの場合、stdout.flush()
他の言語の場合は、ドキュメントを参照せよ

行列 $a$ は固定されていて、相互入出力のプロセスにおいて変化しないことは保証されている。

ハック形式

ハックを行うには、次のテスト形式に従いなさい。

1行目に2つの整数 $n,\,m$ $(1 \leq n,\,m \leq 1000)$ を出力せよ、これらはそれぞれ行列の行数と列数である。

つづく $n$ 行の各行には $m$ 個の整数を出力せよ、これらは行列 $a$ の要素である。この行列の要素は全て $1$ から $n \cdot m$ までの整数(両端含む)でなければならない。

入出力例

? 1 2 1 1 1 3
? 1 2 2 1 2 3
? 1 2 3 1 3 3
? 1 1 1 1 1 2
! 2

注記

例のテストではサイズ $3 \times 4$ の行列 $a$ は次のようになります。

$\begin{align} \texttt{1 2 1 2} \\ \texttt{3 3 3 3} \\ \texttt{2 1 2 1} \end{align}$

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

*2:これも原文では英語、ロシア語のWikipediaへのリンク

*3:恐らく $g(x,\,y)$ の誤記