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

A. Déjà Vu / Дежавю (500点)
- 入力
- 出力
- 入出力例
- 注記
B. Flip the Bits / Меняем биты (1000点)
- 入力
- 出力
- 入出力例
- 注記
C. Balance the Bits / Сбалансируйте биты (1750点)
- 入力
- 出力
- 入出力例
- 注記
D. 3-Coloring / 3-раскраска (2000点)
E. Travelling Salesman Problem / Задача коммивояжёра (2250点)
- 入力
- 出力
- 入出力例
- 注記
F. Flip the Cards / Переверните карты (3000点)
- 入力
- 出力
- 入出力例
- 注記

A. Déjà Vu / Дежавю (500点)

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

回文とは、前から読んでも後ろから読んでも同じように読める文字列のことです。例えば、文字列"z"や"aaa", "aba", "abccba"は回文ですが、"codeforces"や"ab"は回文ではありません。回文には既視感を覚えるので嫌いです。

文字列 $s$ が与えられます。 $s$ のどこかに文字'a'をちょうど1文字挿入しなければなりません。回文でない文字列を作ることができるならその例を求めてください。そうでなければ、それが不可能であることを報告してください。

例えば $s =$ "cbabc"とします。'a'を挿入することで"acbabc"や"cababc", "cbaabc", "cbabac", "cbabca"を作ることができます。しかし"cbaabc"は回文ですので、他の選択肢のいずれかを出力しなければなりません。

入力

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

各テストケースについての唯一の行には小文字の英字から成る文字列 $s$ が与えられる。

全ての文字列の長さの合計は $3 \cdot 10^5$ を超えない。

出力

各テストケースについて解が存在しない場合、"NO"と出力せよ。

そうでない場合、"YES"と出力し、次の行に構築した長さ $|s| + 1$ の文字列を出力せよ。解が複数存在する場合、そのいずれかを出力せよ。

"YES"と"NO"の各文字はどのケース(大文字、小文字)でもよい。

入出力例

6
cbabc
ab
zza
ba
a
nutforajaroftuna

YES
cbabac
YES
aab
YES
zaza
YES
baa
NO
YES
nutforajarofatuna

注記

1つ目のテストケースは、問題文で説明されています。

2つ目のテストケースでは、"aab"と "aba"を作ることができます。しかし、"aba"は回文なので、"aab"が唯一の正解となります。

3つ目のテストケースでは、"zaza"と"zzaa"は正解ですが、"azza"は正解ではありません。

4つ目のテストケースでは、"baa"が唯一の正解です。

5つ目のテストケースでは、"aa"しか作ることができませんが、これは回文です。そのため、答えは"NO"になります。

6つ目のテストケースでは、"anutforajaroftuna"は回文ですが、他の場所に'a'を挿入すると正解になります。

B. Flip the Bits / Меняем биты (1000点)

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

長さ $n$ の二進文字列 $a$ があります。1回の操作で $a$ の接頭辞であり $0$ と $1$ の文字数が等しいものを任意に選ぶことができます。そうすると、その接頭辞に含まれる全ての記号が反転します: それぞれの $0$ が $1$ に、それぞれの $1$ が $0$ になります。

例えば、 $a = 0111010000$ とします。

1回目の操作では、長さ $8$ の接頭辞は $0$ を4つ、 $1$ を4つ持つためこれを選ぶことができる: $[01110100]00 \to [10001011]00$
2回目の操作では、長さ $2$ の接頭辞は $0$ を1つ、 $1$ を1つ持つためこれを選ぶことができる: $[10]00101100 \to [01]00101100$
3回目の操作では、長さ $4$ の接頭辞を選ぶことは $0$ を3つ、 $1$ を1つ持つためルール違反となります。

文字列 $a$ を有限個の演算(0回でもよい)で文字列 $b$ に変換できるでしょうか?

入力

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

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

続く2行には長さ $n$ の $0$ と $1$ の文字から成る文字列 $a$ と $b$ が与えられる。

全てのテストケースでの $n$ の和は $3 \cdot 10^5$ を超えない。

出力

各テストケースについて、 $a$ を $b$ に変換することが可能であれば"YES"と、不可能であれば"NO"と出力せよ。各文字はどのケース(大文字、小文字)でもよい。

入出力例

5
10
0111010000
0100101100
4
0000
0000
3
001
000
12
010101010101
100110011010
6
000111
110100

YES
YES
NO
YES
NO

注記

1つ目のテストケースは、問題文で説明されています。

2つ目のテストケースでは、0回の操作で $a$ を $b$ に変換します。

3つ目のテストケースでは、合法的な操作がないので、 $a$ を $b$ に変換することは不可能です。

4つ目のテストケースでは、次のような変換を行います。

長さ $2$ の接頭辞を選び $1001010101$ を得る
長さ $12$ の接頭辞を選び $011010101010$ を得る
長さ $8$ の接頭辞を選び $100101011010$ を得る
長さ $4$ の接頭辞を選び $011001011010$ を得る
長さ $6$ の接頭辞を選び $100110011010$ を得る

5つ目のテストケースでは、唯一の合法的な操作は $a$ を $111000$ に変換することです。そこから先は、最初に入力した文字列に戻ることしかできないので、 $a$ を $b$ に変換することはできません。

C. Balance the Bits / Сбалансируйте биты (1750点)

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

括弧列は文字'+'と'1'を追加することで有効な数学的表現に変換することができるとき、バランスが取れているといいます。例えば、'(())()'や'()', '(()(())'はバランスが取れていますが、')('や'(()', '(()))('はそうではありません。

長さ $n$ の二進文字列 $s$ が与えられます。全ての $1 \leq i \leq n$ について以下を満たすような長さ $n$ のバランス取れた2つの文字列 $a,\,b$ を構築してください。

$s_i = 1$ の場合 $a_i = b_i$
$s_i = 0$ の場合 $a_i \neq b_i$

不可能な場合、そのことを報告してください。

入力

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

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

次の行には長さ $n$ の0と1の文字から成る文字列 $s$ が与えられる。

全てのテストケースでの $n$ の和は $3 \cdot 10^5$ を超えない。

出力

このような2つのバランスの取れた括弧列が存在すれば、1行目に"YES"と、そうでなければ"NO"と出力せよ。各文字はどのケース(大文字、小文字)でもよい。

答えが"YES"の場合は、次の2行に条件を満たすバランスの取れた括弧列 $a$ と $b$ を出力せよ。

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

入出力例

YES
()()()
((()))
YES
()()((()))
(())()()()
NO

注記

1つ目のテストケースでは、 $a =$ "()()()", $b =$ "((()))"となっています。位置 $1,$ $3,$ $4,$ $6$ の文字は等しく、これらは $s_i = 1$ の位置と全く同じです。

2つ目のテストケースでは、 $a =$ "()()((()))", $b =$ "(())()()()"となっています。位置 $1,$ $4,$ $5,$ $7,$ $8,$ $10$ の文字は等しく、これらは $s_i = 1$ の位置と全く同じです。

3つ目のテストケースでは、解がありません。

D. 3-Coloring / 3-раскраска (2000点)

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

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

AliceとBobはあるゲームをしています。 $n \times n$ の格子があり、初期状態では空です。 $1 \leq i,\,j \leq n$ について $i$ 行 $j$ 列のセルを $(i,\,j)$ と表記します。 $1,$ $2,$ $3$ という番号の $3$ 色のトークンが無限にあります。

ゲームは次のようにターンが進んでいきます。各ターンはAliceが3色のうちの1色を選びます、これを $a$ とします。Bobが $b \neq a$ である色と空のセルを選び、そのマスに色 $b$ のトークンを置きます。

同じ色のトークンが置かれた隣接する2つのセルが存在する場合、コンフリクトが発生しているといいます。2つのセルは共通の辺を共有している場合、隣接していると見なされます。

ある瞬間コンフリクトが発生した場合、Aliceが勝利します。そうではなく、 $n^2$ ターンがコンフリクトが発生せずに完了した(即ち、全てのセルが埋まっている)場合、Bobが勝利します。

Bobが勝利戦略を持っているという証拠があります。Bobとしてゲームをプレイして買ってください。

相互入出力機は適応性があります。つまり、Aliceの色の選択は、Bobのそれまでの動きに依存し得ます。

相互入出力

相互入出力は単一の整数 $n$ $(2 \leq n \leq 100)$ を読むことから始まる、これはグリッドのサイズである。

その後、ゲームのターンが始まります。各ターンは1つの整数 $a$ $(1 \leq a \leq 3)$ を読むことから始まる、これはAliceの選択した色である。

次に3つの整数 $b,\,i,\,j$ $(1 \leq b \leq 3,$ $b \neq a,$ $1 \leq i,\,j \leq n)$ を出力しなければならない、これらはBobが色 $b$ のトークンをセル $(i,\,j)$ に置くことを表している。セル $(i,\,j)$ には前のターンでのトークンがおかれていてはいけません。手番が無効であったり、ゲームに負けた場合、相互入出力は終了し、Wrong Answerの評価を得る。

$n^2$ ターンが終了したら、予想外の判定を避けるため、すぐに終了せよ。

何かを出力した後、忘れず改行を出力し、出力をflushせよ。そうでなければIdleness limit exceededを得る。出力のflushのためには、次を利用せよ。

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

ハックの形式

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

1行目に単一の整数 $n$ $(2 \leq n \leq 100)$ を出力せよ。

2行目に $n^2$ 個の整数 $a_1,\,\dots,\,a_{n^2}$ $(1 \leq a_i \leq 3)$ を出力せよ、ここで $a_i$ は $i$ ターン目のAliceの色を表す。

相互入出力機はハックの色のリストから逸脱するかもしれませんが、それはBobが負ける原因になる場合だけである。

入出力例

注記

サンプルの最終的なグリッドは下図の通りです。同じ色のトークンを持つ隣接する2つのセルがないので、Bobの勝ちです。

$\begin{matrix}2&3\\3&1\end{matrix}$

このサンプルは入出力の形式を示すためのものです。Bobの最適戦略や相互入出力機の実際の行動を示すことを保証するものではありません。

E. Travelling Salesman Problem / Задача коммивояжёра (2250点)

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

$1$ から $n$ までの番号がついた $n$ 個の都市があり、都市 $i$ の美しさは $a_i$ です。

セールスマンは都市 $1$ から出発し、全ての都市をちょうど1回訪れ、都市 $1$ に戻りたいと考えています。

全ての $i \neq j$ について都市 $i$ から都市 $j$ へのフライトの費用は $\max(c_i,\,a_j - a_i)$ ドルです、ここで $c_i$ は都市 $i$ からの最低金額です。絶対値ではないことに注意してください。セールスマンが旅行を終えるための最小総費用を求めてください。

入力

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

続く $n$ 行の $i$ 行目には2つの整数 $a_i,\,c_i$ $(0 \leq a_i,\,c_i \leq 10^9)$ が与えられる、これは都市 $i$ の美しさと最低金額である。

出力

単一の整数を出力せよ、これは最小総費用である。

入出力例

注記

1つ目のテストケースでは、 $1 \to 3 \to 2 \to 1$ の順に移動することができます。

フライト $1 \to 3$ のコストは $\max(c_1,\,a_3 - a_1) = \max(9,\,4 - 1) = 9$ である
フライト $3 \to 2$ のコストは $\max(c_3,\,a_2 - a_3) = \max(1,\,2 - 4) = 1$ である
フライト $2 \to 1$ のコストは $\max(c_2,\,a_1 - a_2) = \max(1,\,1 - 2) = 1$ である

総費用は $11$ であり、これ以上改善することはできません。

F. Flip the Cards / Переверните карты (3000点)

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

$n$ 枚のカードの山があります。 $i$ 枚目のカードの表には数 $a_i$ が、裏には数 $b_i$ が書かれています。 $1$ から $2n$ までの各整数がカード上にちょうど1回現れます。

表の数字が大きい順、裏の数字が小さい順に並んでいれば、山札はソートされているといいます。つまり、全ての $1 \leq i \lt n$ について $a_i \lt a_{i+1},$ $b_i \gt b_{i+1}$ である場合です。

カード $i$ をめくるということは、 $a_i$ と $b_i$ の値を入れ替えることです。カードのある部分集合(空でもよい)をめくり、全てのカードを好きな順番に並べなければなりません。山札をソートするためにめくらなければならないカードの最小枚数は何枚でしょうか?

入力

1行目には単一の整数 $n$ $(1 \leq n \leq2 \cdot 10^5)$ が与えられる、これはカードの枚数である。

続く $n$ 行はカードの説明である。これらの $i$ 行目には2つの整数 $a_i,\,b_i$ $(1 \leq a_i,\,b_i \leq 2n)$ が与えられる。 $1$ から $2n$ までの各整数はちょうど1回現れる。

出力

デッキをソートすることが不可能な場合、"-1"を出力せよ。それ以外の場合は、デックをソートするのにめくらなければならないカードの最小枚数を出力せよ。

入出力例

2
1 2
3 4

-1

-1

注記

1つ目のテストケースでは、 $(1,\,9)$ と $(2,\,7)$ のカードをめくります。すると、山札は $(3,\,10),$ $(5,\,8),$ $(6,\,4),$ $(7,\,2),$ $(9,\,1)$ の順に並びます。 $3 \lt 5 \lt 6 \lt 7 \lt 9$ であり $10 \gt 8 \gt 4 \gt 2 \gt 1$ なので、ソートされています。

2つ目のテストケースでは、デッキをソートすることは不可能です。