Educational Codeforces Round 105 問題文和訳

A. ABC String / Строка ABC
- 入力
- 出力
- 入出力例
- 注記
B. Berland Crossword / Берляндский кроссворд
- 入力
- 出力
- 入出力例
- 注記
C. 1D Sokoban / 1D Сокобан
- 入力
- 出力
- 入出力例
- 注記
D. Dogeforces
- 入力
- 出力
- 入出力例
- 注記
E. A-Z Graph / A-Z граф
- 入力
- 出力
- 入出力例
- 注記
F. Delete The Edges / Уничтожение ребер

A. ABC String / Строка ABC

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

$n$ 文字からなる文字列 $a$ が与えられます、 $n$ は偶数です。 $1$ から $n$ までの各 $i$ について $a_i$ は'A', 'B', 'C'のいずれかです。

括弧列とは"("と")"のみを含む文字列です。正規括弧列とは元の文字列に文字"1"や"+"を挿入することで正しい算術式に変換できるような括弧列です。例えば、括弧列"()()"や"(())"は正規括弧列であり(得られる表現式は"(1)+(1)"や"((1+1)+1)"になる)、")("や"("、")"は正規括弧列ではありません。

次のような $n$ 文字からなる文字列 $b$ を見つけたいです。

$b$ は正規括弧列である
$a_i = a_j$ である $i,\,j$ $(1 \leq i,\,j \leq n)$ について $b_i = b_j$

言い換えれば、全ての出現する'A', 'B', 'C'をそれぞれ同じ種類の括弧で置き換えたいのです。

このような文字列 $b$ が存在するかどうか判別してください。

入力

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

その後、 $t$ 個のテストケースについての記述が続く。

各テストケースについての唯一の行には文字列 $a$ が与えられる。 $a$ は大文字の'A', 'B', 'C'のみから成る。 $a$ の長さを $n$ とする。 $n$ が偶数であり、 $2 \leq n \leq 50$ であることは保証されている。

出力

各テストケースについて次のような文字列 $b$ が存在する場合、"YES"と出力せよ。

$b$ は正規括弧列である
$a_i = a_j$ である $i,\,j$ $(1 \leq i,\,j \leq n)$ について $b_i = b_j$

そうでない場合、"NO"と出力せよ。

どの文字も大文字小文字は好きなように出力してよい(例えば、文字列yEs, yes, Yes, YESはすべて肯定とみなされる)。

入出力例

4
AABBAC
CACA
BBBBAC
ABCA

YES
YES
NO
NO

注記

1つめのテストケースでの、可能な文字列 $b$ の1つは"(())()"です。

2つめのテストケースでの、可能な文字列 $b$ の1つは"()()"です。

B. Berland Crossword / Берляндский кроссворд

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

Berland*1のクロスワードとは $n$ 行 $n$ 列の正方形マス上のパズルです。最初は全てのマスが白です。

このパズルを解くために、次のように、グリッドの端にある行くとかのマスを黒く塗らなければなりません。

一番上の行のちょうど $U$ マスが黒
一番右の列のちょうど $R$ マスが黒
一番下の行のちょうど $D$ マスが黒
一番左の列のちょうど $L$ マスが黒

マスを全く黒く塗らず、全てのマスを白のままにしておくこともできることに注意してください。

与えられたパズルに解が存在するかどうかをチェックしてください。

入力

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

その後、 $t$ 個のテストケースについての記述が続く。

各テストケースについての唯一の行には $5$ つの整数 $n,\,U,\,R,\,D,\,L$ $(2 \leq n \leq 100,$ $0 \leq U,\,R,\,D,\,L \leq n)$ が与えられる。

出力

各テストケースについて解が存在するなら"YES"を、そうでないなら"NO"を出力せよ。

どの文字も大文字小文字は好きなように出力してよい(例えば、文字列yEs, yes, Yes, YESはすべて肯定とみなされる)。

入出力例

YES
YES
NO
YES

注記

テストケース $1,\,2,\,4$ についての可能解はこのようなものになります。
f:id:Flkanjin:20210304011109p:plain

C. 1D Sokoban / 1D Сокобан

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

無限長の数直線上で倉庫番 *2に似たゲームをしています。このゲームは離散的であるので、直線上の整数の位置のみを考えます。

位置 $0$ からスタートします。直線上には $n$ 個の箱があり、 $i$ 番目の箱は位置 $a_i$ にあります。全ての箱の位置は異なります。 $m$ 箇所、特別な場所があり、 $j$ 番目の特別な場所は位置 $b_j$ です。全ての特別な場所の位置は異なります。

1回の手で位置を1つだけ左右のどちらかに動くことができます。移動方向に箱が1箱ある場合はその箱をその方向の次の位置に押し込みます。その次の位置が他の箱に占有されている場合、その箱もその次の位置へ押され、その次も...となります。箱の中を通過することがはできません。箱を自分の方向へ引っ張ることもできません。

何手でも打つことができます(0回でもよい)。できるだけ多くの箱を目標は特別な位置に置くことです。最初から特別な場所に置かれている箱があるかもしれないことに注意して下さい。

入力

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

その後、 $t$ 個のテストケースについての記述が続く。

各テストケースの1行目には2つの整数 $n,\,m$ $(1 \leq n,\,m \leq 2 \cdot 10^5)$ が与えられる、それぞれ箱の個数と特別な場所の数である。

各テストケースの2行目には $n$ 個の異なる昇順の整数 $a_1,\,a_2,\,\dots,\,a_n$ $(-10^9 \leq a_1 \lt a_2 \lt \dots \lt a_n \leq 10^9;$ $a_i \neq 0)$ が与えられる、これらは箱の初期位置である。

各テストケースの3行目には $m$ 個の異なる昇順の整数 $b_1,\,b_2,\,\dots,\,b_m$ $(-10^9 \leq b_1 \lt b_2 \lt \dots \lt b_m \leq 10^9;$ $b_i \neq 0)$ が与えられる、これらは特別な場所の位置である。

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

出力

各テストケースについて単一の整数を出力せよ、その整数とは特別な場所に置くことのできる箱の最大数である。

入出力例

5
5 6
-1 1 5 11 15
-4 -3 -2 6 7 15
2 2
-1 1
-1000000000 1000000000
2 2
-1000000000 1000000000
-1 1
3 5
-1 1 2
-2 -1 1 2 5
2 1
1 2
10

注記

1つ目のテストケースでは $5$ だけ右に進み、位置 $1$ にあった箱を位置 $6$ に、位置 $5$ にあった箱を位置 $7$ に押し込めます。それから $6$ だけ左に進み、位置 $-1$ へ到達すると、箱を $-2$ へ押し込むことができます、そうすると箱はそれぞれ位置 $[-2,\,6,\,7,\,11,\,15]$ にあります。このうち、位置 $[-2,\,6,\,7,\,15]$ は特別な位置であるので、答えは $4$ となります。

2つ目のテストケースでは箱の1つを $-1$ から $-10^9$ へ動かし、別の箱を $1$ から $10^9$ へ動かすことで答え $2$ を得ることができます。

3つ目のテストケースでは箱を引っ張ることはできないため、箱を特別な場所へ近づけることはできません。

4つ目のテストケースでは全ての箱がすでに特別な場所にあり、何もしないことで答え $3$ を得ることができます。

5つ目のテストケースでは箱よりも特別な場所の方が少ないです。右に $8$ か $9$ 進むことで箱を位置 $10$ に動かすことができます。

D. Dogeforces

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

Dogeforces社には $k$ 人の従業員がいます。下級従業員を除く各従業員には少なくとも $2$ 人の部下がいます。下級従業員には部下がいません。社長を除く各従業員にはちょくぞくのじょうしがちょうど1人います。社長は全ての従業員の直属、もしくは間接的な上司です。Dogeforcesでは、各上司は全部下よりも真に多い給料をもらうことが知られています。

会社の完全な構造は秘密ですが、下級従業員の数は知っていますし、各下級従業員の組について共通上司(そのような上司が複数いる場合は給料が一番低い上司)の給料は知られています。会社の構造を復元しなければなりません。

入力

1行目には単一の整数 $n$ $(2 \leq n \leq 500)$ が与えられます、これは下級従業員の数である。

$n$ 行が続き、その $i$ 行目には $n$ 個の整数 $a_{i,1},\,a_{i,2},\,\dots,\,a_{i,n}$ $(1 \leq a_{i,j} \leq 5000)$ が与えられます、これらは番号 $i,\,j$ の従業員の共通上司の給料である。 $a_{i,j} = a_{j,i}$ であることは保証されている。 $a_{i,i}$ は $i$ 番目の従業員の給料である。

出力

1行目には単一の整数 $k$ を出力せよ、これは会社の従業員数である。

2行目には $k$ 個の整数 $c_1,\,c_2,\,\dots,\,c_k$ を出力せよ、 $c_i$ は番号 $i$ の従業員の給料である。

3行目には単一の整数 $r$ を出力せよ、これは社長のである従業員の番号である。

つづく $k - 1$ 行目には2つの整数 $v,\,u$ $(1 \leq v,\,u \leq k)$ を出力せよ、これらはその従業員と直属の上司の番号である。

下級従業員の番号は $1$ から $n$ であり、残りの従業員について $n + 1$ から $k$ の番号を振らなければならないことに注意せよ。正しい会社の構造が複数ある場合、そのいずれを出力してもよい。

入出力例

注記

1つ目の入出力例における可能な構造の1つは次のようなものがあります。
f:id:Flkanjin:20210304022436p:plain

E. A-Z Graph / A-Z граф

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

$n$ 頂点有向グラフが与えられます。各有向辺(つまり弧は単一文字でらえr付けされています。最初、グラフは空です。

このグラフについて $m$ 個のクエリを処理しなければなりません。各クエリは次の3種類のうちの1つです。

" $+\ \ u\ \ v\ \ c$ ": $c$ のラベルのついた $u$ から $v$ への弧を追加する。この時点においてグラフ中に弧 $(u,\,v$ ) が存在しないことは保証される
" $-\ \ u\ \ v$ ": $u$ から $v$ への弧を削除する。この時点においてグラフ中に弧 $(u,\,v$ ) が存在することは保証される
" $?\ \ k$ ": $v_1 \rightarrow v_2 \rightarrow \cdots \rightarrow v_k$ と $v_k \rightarrow v_{k-1} \rightarrow \cdots \rightarrow v_1$ の両方の歩道が存在し、その両方の歩道に沿った文字を書き下していくと同じ文字列が得られる $k$ 頂点の列 $v_1,\,v_2,\,\dots,\,v_k$ を求める。同じ頂点を何度でも訪れてよい

入力

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

つづく $m$ 行には1行につき1クエリが与えられる。各クエリは3種類のうちの1つである。

" $+\ \ u\ \ v\ \ c$ " $(1 \leq u,\,v \leq n;$ $u \neq v;$ $c$ は小文字のラテン文字 $)$
" $-\ \ u\ \ v$ " $(1 \leq u,\,v \leq n;$ $u \neq v)$
" $?\ \ k$ " $(2 \leq k \leq 10^5)$

出力

各3種類目のクエリについて上述したような列 $v_1,\,v_2,\,\dots,\,v_k$ が存在する場合YESと、そうでない場合NOと出力せよ。

入出力例

3 11
+ 1 2 a
+ 2 3 b
+ 3 2 a
+ 2 1 b
? 3
? 2
- 2 1
- 3 2
+ 2 1 c
+ 3 2 d
? 5

YES
NO
YES

注記

3種類目のクエリの1つ目 $k = 3$ については、例えば、 $1 \xrightarrow{\mathrm{a}} 2 \xrightarrow{\mathrm{b}} 3,$ $3 \xrightarrow{\mathrm{a}} 2 \xrightarrow{\mathrm{b}} 1$ であるため、列 $[1,\,2,\,3]$ と選ぶことができます。

3種類目のクエリの2つ目 $k = 2$ については、弧 $(p_1,\,p_2)$ と $(p_2,\,p_1)$ が同じ文字を持つような列 $p_1,\,p_2$ は見つかりません。

3種類目のクエリの3つ目については、例えば、 $1 \xrightarrow{\mathrm{a}} 2 \xrightarrow{\mathrm{b}} 3 \xrightarrow{\mathrm{d}} 2 \xrightarrow{\mathrm{c}} 1$ であるため、列 $[1,\,2,\,3,\,2,\,1]$ と選ぶことができます。

F. Delete The Edges / Уничтожение ребер

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

$n$ 頂点 $m$ 辺からなる連結無向グラフが与えられます。与えられたグラフの全ての辺を破壊することが目標です。

任意の頂点を始点として選びそこから辺に沿って歩き始めることができます。辺に沿って歩くとき、その辺を破壊します。明らかに、辺が破壊されている場合、その辺に沿って歩くことはできません。

歩行中に1回までモード変更を行うことができ、この操作は頂点乗にいる時にしか行えません(辺上にいる場合は行えません)。モード変更後、辺は次のように錯押されます: モード変更後の1辺目は破壊されず、2辺目は破壊され、3辺目は破壊されず、4辺目は破壊され、... という具合です。元のモードに戻すことはできません。この操作をしたくなければ、しなくても構いません。

与えられたグラフの全ての辺を破壊することができるでしょうか?

入力

1行目には2つの整数 $n,\,m$ $\biggl(2 \leq n \leq 3000;$ $n - 1 \leq m \leq \displaystyle \min\left( \frac{n(n-1)}{2},\,3000 \right) \biggr)$ が与えられる、これらはそれぞれ頂点数と辺の本数である。

その後 $m$ 行が続く、各行には2つの整数 $x_i,\,y_i$ $(1 \leq x_i,\,y_i \leq n;$ $x_i \neq y_i)$ が与えられる、これらは $i$ 番目の辺の端点である。

これらは多重辺のない連結無向グラフを形成する。

出力

全ての辺を破壊することが不可能な場合、0と出力せよ。

そうでない場合、行動列を次のように出力せよ。まず、 $k$ $(k \leq 2m + 2)$ を出力せよ、これは行動数である。次に $k$ 個の整数からなる列自身を出力せよ。1つ目の整数は支店のインデックスでなければならない。それぞれの次の整数は探索での次の頂点のインデックスか、モード変更を行った場合 $-1$ でなければならない。モード変更は最大1回のみの使用が認められている。

入出力例

4
1 2 3 1

8
2 -1 1 2 3 2 4 2

9
2 3 1 2 -1 4 2 5 2

8
5 4 2 3 1 -1 2 1

*1:Берлянд: 木やグラフに関する問題でしばしば登場する架空の国家

*2:1982年12月にPC-8801用に発売されたゲーム。色々なプラットフォームに移植等がなされている。海外でもSokobanとして発売されている