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

A. Split it! / Раздели! (500点)
- 入力
- 出力
- 入出力例
- 注記
B. Max and Mex / Max и Mex (1000点)
- 入力
- 出力
- 入出力例
- 注記
C. Diamond Miner / Добытчик алмазов (1500点)
- 入力
- 出力
- 入出力例
- 注記
D. Let's Go Hiking / Идем в поход! (2000点)
- 入力
- 出力
- 入出力例
- 注記
E. Garden of the Sun / Солнечный огород (2500点)
- 入力
- 出力
- 入出力例
- 注記
F. BFS Trees / Деревья поиска в ширину (3000点)
- 入力
- 出力
- 入出力例
- 注記

A. Split it! / Раздели! (500点)

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

ある日彼女は文字列と整数を見つけました。問題作成上級者である彼女はすぐに問題を思いつきました。

文字列 $s$ とパラメータ $k$ が与えられたとき、次を満たす $k + 1$ 個の空でない文字列 $a_1,\,a_2,\,\dots,\,a_{k + 1}$ が存在するかを調べなければなりません。

$s = a_1 + a_2 + \dots + a_k + a_{k + 1} + R(a_k) + R(a_{k - 1}) + \dots + R(a_1)$

ここで $+$ は文字列の連結を表します。 $R(x)$ を $x$ の反転文字列と定義します。例えば $R(abcd) = dcba$ となります。上式では $R(a_{k + 1})$ の部分を意図的に飛ばしていることに注意してください。

入力

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

各テストケースについての記述の1行目には2つの整数 $n,\,k$ $\biggl(1 \leq n \leq 100,$ $0 \leq k \leq \displaystyle \left\lfloor \frac{n}{2} \right\rfloor \biggr)$ が与えられる、これらは文字列 $s$ の長さとパラメータ $k$ である。

各テストケースについての記述の2行目には小文字英字からなる長さ $n$ の単一の文字列 $s$ が与えられる。

出力

各テストケースについて、 $a_1,\,a_2,\,\dots,\,a_{k + 1}$ が見つかる場合は"YES"(引用符なし)と出力せよ、そうでない場合は"NO"(引用符なし)と出力せよ。

ケース(大文字小文字)はいかなる組み合わせで出力してよい。

入出力例

7
5 1
qwqwq
2 1
ab
3 1
ioi
4 2
icpc
22 0
dokidokiliteratureclub
19 8
imteamshanghaialice
6 3
aaaaaa

YES
NO
YES
NO
YES
NO
NO

注記

1つ目のテストケースでは $a_1 = qw,$ $a_2 = q$ が可能な解の1つのとなります。

3つ目のテストケースでは $a_1 = i,$ $a_2 = o$ が可能な解の1つのとなります。

5つ目のテストケースでは $a_1 = dokidokiliteratureclub$ が可能な解の1つのとなります。

B. Max and Mex / Max и Mex (1000点)

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

初期状態では異なる $n$ 個の非負整数から成る多重集合 $S$ が与えられます。多重集合とは要素を複数回含むことができる集合です。

次の操作を $k$ 回行います。

$a = \mathrm{mex}(S),$ $b = \max(S)$ として、要素 $\displaystyle \left\lceil \frac{a + b}{2} \right\rceil$ (切り上げ)を $S$ に追加する。集合内にこの数がすでにある場合も再び追加する。

ここで、多重集合の $\max$ とは多重集合内の最大整数を表し、多重集合の $\mathrm{mex}$ とは多重集合内に現れない最小の非負整数を表します。例えば次のようになります。

$\mathrm{mex}(\{1,\,4,\,0,\,2\}) = 3$
$\mathrm{mex}(\{2,\,5,\,1\}) = 0$

$k$ 回の操作を行った後の $S$ 内の異なる要素数を計算してください。

入力

各テストケースについての記述の1行目には2つの整数 $n,\,k$ $(1 \leq n \leq 10^5,$ $0 \leq k \leq 10^9)$ が与えられる、これらは多重集合 $S$ の初期サイズと操作を行う回数である。

各テストケースについての記述の2行目には異なる $n$ 個の整数 $a_1,\,a_2,\,\dots,\,a_n$ $(0 \leq a_i \leq 10^9)$ が与えられる、これらは多重集合の初期の要素である。

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

出力

各テストケースについて $k$ 回の操作を行った後の $S$ 内の異なる要素数を出力せよ。

入出力例

注記

1つ目のテストケースでは $S = \{0,\,1,\,3,\,4\},$ $a = \mathrm{mex}(S) = 2,$ $b = \max(S) = 4,$ $\displaystyle \left\lceil \frac{a + b}{2} \right\rceil = 3$ です。 $3$ が $S$ に追加され、 $S$ は $\{0,\,1,\,3,\,3,\,4\}$ となります。答えは $4$ です。

2つ目のテストケースでは $S = \{0,\,1,\,4\},$ $a = \mathrm{mex}(S) = 2,$ $b = \max(S) = 4,$ $\displaystyle \left\lceil \frac{a + b}{2} \right\rceil = 3$ です。 $3$ が $S$ に追加され、 $S$ は $\{0,\,1,\,3,\,4\}$ となります。答えは $4$ です。

C. Diamond Miner / Добытчик алмазов (1500点)

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

Diamond MinerはGold Minerに似たゲームですが、このゲームでは採鉱者が $1$ 人ではなく $n$ 人います。

採掘場は平面として表せます。 $n$ 人の採鉱者はy軸上の $n$ 点とみなせます。採掘場には $n$ 個のダイアモンド鉱山があります。これらはx軸上の $n$ 点とみなせます。事情により原点(点 $(0,\,0)$ ) 上には採鉱者はおらず、ダイアモンド鉱山もありません。

どの採鉱者もちょうど1つのダイアモンド鉱山を採掘しなければなりません。採鉱者はホックを持っていて、それでダイアモンド鉱山を採掘します。点 $(a,\,b)$ にいる採鉱者がホックで点 $(c,\,d)$ にあるダイアモンド鉱山を採掘する場合、 $\sqrt{(a - c)^2 + (b - d)^2}$ のエネルギー(これらの点の間の距離)を採掘で消費します。採鉱者は移動できず、互いに助け合うこともできません。

このゲームの目的は採鉱者の消費するエネルギーの和を最小化することです。最小値を求めてくれませんか?

入力

入力は複数のテストケースからなる。1行目には単一の整数 $t$ $(1 \leq t \leq 10)$ が与えられる、これはテストケースの数である。その後、テストケースの記述が続く。

各テストケースについての記述の1行目には単一の整数 $n$ $(1 \leq n \leq 10^5)$ が与えられる、これは採鉱者や鉱山の数である。

つづく $2n$ 行の各行にはスペースで区切られた2つの整数 $x$ $(-10^8 \leq x \leq 10^8),$ $y$ $(-10^8 \leq x \leq 10^8)$ が与えられる、これらは採鉱者や鉱山の位置を表す点 $(x,\,y)$ である。点 $(0,\,y)$ に採鉱者がいることを表す $x = 0$ か、点 $(x,\,0)$ に鉱山があることを表す $y = 0$ のいずれかである。複数の採鉱者や鉱山が同じ点に存在することもある。

原点上に点が存在しなことは保証される。x軸上にある点が $n$ 個で、y軸上にある点が $n$ 個であることは保証されている。

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

出力

各テストケースについて単一の実数を出力せよ、その数は消費エネルギーの和の最小値である。

出力解は絶対誤差または相対誤差が $10^{-9}$ を超えない場合正しいと見なされる。

形式的に、出力解を $a$ 、想定解を $b$ とする。出力解は $\displaystyle \frac{|a - b|}{\max(1,\,|b|)} \leq 10^{-9}$ であり、その場合に限り正解となる。

入出力例

3.650281539872885
18.061819283610362
32.052255376143336

注記

1つ目のテストケースでは、採鉱者は $(0,\,1)$ と $(0,\,-1)$ にいて、ダイヤモンド鉱山は $(1,\,0)$ と $(-2,\,0)$ にあります。図のようにダイヤモンド鉱山を採鉱者が採掘するように配分すると、エネルギーの和 $\sqrt{2} + \sqrt{5}$ が得られます。
f:id:Flkanjin:20210311152334p:plain

D. Let's Go Hiking / Идем в поход! (2000点)

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

今週末、青山（チンシャン）(Qingshan)*2は彼女の友人のDanielに一緒にハイキングに行こうと提案してします。残念なことに彼らは忙しい高校生であるため、ハイキングにはメモ用紙上でしか行くことができません。

順列 $p$ が紙面上に左から右へ書かれています。まず、青山が整数インデックス $x$ $(1 \leq x \leq n)$ を選び、Danielに伝えます。そののち、Danielは他の整数インデックス $y$ $(1 \leq y \leq n,$ $y \neq x)$ を選びます。

ゲームは通常のターン制で進行し、青山が先手です。ルールは以下の通りです。

青山のターン: $x$ の値を $1 \leq x' \leq n,$ $|x' - x| = 1,$ $x' \neq y,$ $p_{x'} \lt p_{x}$ を同時に満たすような $x'$ に変化させなければならない
Danielのターン: $y$ の値を $1 \leq y' \leq n,$ $|y' - y| = 1,$ $y' \neq x,$ $p_{y'} \gt p_{y}$ を同時に満たすような $y'$ に変化させなければならない

手を打てなくなった人が負け、もう1人が勝ちます。青山のファンである貴方は、両プレイヤーが最適なプレイをしたときに青山が勝てるような $x$ の個数を計算するように求められている。

入力

1行目は単一の整数 $n$ $(2 \leq n \leq 10^5)$ が与えられる、これは順列の長さである。

2行目には $n$ 個の異なる整数 $p_1,\,p_2,\,\dots,\,p_n$ $(1 \leq p_i \leq n)$ が与えられる、これらは順列である。

出力

青山が勝つように選択できる $x$ の値の数を出力せよ。

入出力例

5
1 2 5 4 3

7
1 2 4 6 5 3 7

注記

1つ目のテストケースでは、青山が勝つには $x = 3$ を選ぶしかないので、答えは $1$ となります。

2つ目のテストケースでは、青山が $x = 4$ を選ぶと、Danielは $y = 1$ を選ぶことができます。第1ターン(青山のターン)で青山は $x' = 3$ を選んで $x$ を $3$ に変えます。第2ターン(Danielのターン)でDanielは $y' = 2$ を選んで $y$ を $2$ に変えます。この時点で $y = 2$ なので青山は $x' = 2$ を選ぶことができません。そのため、青山の負けとなります。

E. Garden of the Sun / Солнечный огород (2500点)

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

太陽の庭には向日葵がたくさん咲いています。

太陽の庭は $n$ 行 $m$ 列の長方形の表で、表の各セルは農地になっています。全ての表には向日葵が生えいます。残念なことに、ある日の夜、雷がいくつかの(ゼロの可能性もある)セルに落ち、そのセルの向日葵は焼けて灰になってしまいました。言い換えると、雷が落ちたセルは空になってしまいました。不思議なことに、どの2つの空のセルも共有点(辺も角も)を持ちません。

さて、所有者はいくつかの(ゼロの可能性もある)向日葵を取り除くことで次の2つの目標を達成したいと考えています。

空のセル上にいる時は他のどの空のセルにも歩いていける。言い換えれば、これらの空のセルは連結である
任意の2つの空のセルの間にはちょうど1つの単純パスが存在する。言い換えれば、空のセル間にはサイクルが存在しない

空のセルから他の空のセルへは辺を共有していれば移動できます。

所有者の要求をすべて満たすような解を彼女に提示していただけませんか?

向日葵を植えることは許可されていないことに注意してください。取り除く向日葵の数を最小化する必要はありません。答えが常に存在することは証明することができます。

入力

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

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

つづく $n$ 行の各行には $m$ 文字が与えられる。各文字は'X'か'.'であり、それぞれ空のセルと向日葵の生えているセルを表している。

全てのテストケースでの $n \cdot m$ の和が $250\,000$ を超えないことは保証されている。

出力

各テストケースについて $n$ 行出力せよ。各行には表の1行を表す $m$ 文字を出力せよ。各文字はそれぞれ空のセルと向日葵の生えているセルを表す、'X'か'.'でなければならない。

答えが複数ある場合、そのうちのいずれを出力してもよい。答えが常に存在することは証明できる。

入出力例

5
3 3
X.X
...
X.X
4 4
....
.X.X
....
.X.X
5 5
.X...
....X
.X...
.....
X.X.X
1 10
....X.X.X.
2 2
..
..

XXX
..X
XXX
XXXX
.X.X
.X..
.XXX
.X...
.XXXX
.X...
.X...
XXXXX
XXXXXXXXXX
..
..

注記

ここでは $(x,\,y)$ で $x$ 行 $m$ 列のセルを表すことにします。

次の図では、白、黄、青のセルは、それぞれ向日葵が咲いているセル、雷が落ちたセル、向日葵を取り除いたセルを削除するセルを表しています。
f:id:Flkanjin:20210311163437p:plain
1つ目のテストケースでは $(1,\,2),$ $(2,\,3),$ $(3,\,2)$ の向日葵を取り除くことが可能解の1つです。
f:id:Flkanjin:20210311163648p:plain
他の可能解として $(1,\,2),$ $(2,\,2),$ $(3,\,2)$ の向日葵を取り除くことがあります。
f:id:Flkanjin:20210311163801p:plain
この出力は任意のセルの組の間には2つの単純パスが存在(サイクルが存在)するため、間違いです。例えば、 $(1,\,1)$ と $(3,\,3)$ の間には2つの単純パスが存在します。

$(1,\,1) \rightarrow (1,\,2) \rightarrow (1,\,3) \rightarrow (2,\,3) \rightarrow (3,\,3)$
$(1,\,1) \rightarrow (2,\,1) \rightarrow (3,\,1) \rightarrow (3,\,2) \rightarrow (3,\,3)$

f:id:Flkanjin:20210311164303p:plain
この出力では $(1,\,1)$ から $(3,\,3)$ へ歩くことができないので不正解です

F. BFS Trees / Деревья поиска в ширину (3000点)

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

全てのノード $t$ についてグラフ上の $s$ と $t$ の最短距離が全域木での $s$ と $t$ の最短距離と等しい場合、その頂点全域木をそのグラフの $s$ を根とするBFS木とします。

グラフが与えられたとき、 $f(x,\,y)$ を同時に頂点 $x$ を根とするBFS木と $y$ を根とするBFS木であるような、このグラフの全域木の数と定義します。

$n$ 頂点 $m$ 辺の連結無向グラフが与えられます。全ての $i,\,j$ について $f(i,\,j)$ をmodulo $998\,244\,353$ で計算してください。

入力

1行目には2つの整数 $n,\,m$ $(1 \leq n \leq 400,$ $0 \leq m \leq 600)$ が与えられる、これらは頂点数と辺の本数である。

つづく $m$ 行のうち $i$ 行は目には2つの整数 $a_i,\,b_i$ $(1 \leq a_i,\,b_i \leq n,$ $a_i \lt b_i)$ が与えられる、これは $a_i$ と $b_i$ を結ぶ辺を表す。

全ての辺が異なり、グラフが連結されていることは保証されている。

出力

$n$ 行出力せよ、各行は $n$ 個の整数からなる。

$i$ 行 $j$ 列に出力される整数は $f(i,\,j) \bmod{998\,244\,353}$ でなければならない。

入出力例

1 0 0 0 0 0 0 0
0 2 0 0 0 0 2 0
0 0 1 0 1 1 0 0
0 0 0 2 0 0 0 2
0 0 1 0 1 1 0 0
0 0 1 0 1 1 0 0
0 2 0 0 0 0 2 0
0 0 0 2 0 0 0 2

注記

次の図は1つ目の例を説明するものです。
f:id:Flkanjin:20210311170431p:plain
赤い辺のある木は $1$ を根とするBFS木でもあり $2$ を根とするBFS木でもあります。
f:id:Flkanjin:20210311170452p:plain
同様にして他の隣接する頂点のペアについてのBFS木もこのようにして生成することができます。

*1:東方Projectのキャラクター

*2:Qīngshān [t͡ɕʰiŋ.ʂan]中国語で地名だがここでは人名