Educational Codeforces Round 106 問題文和訳

A. Domino on Windowsill / Домино на подоконнике
- 入力
- 出力
- 入出力例
- 注記
B. Binary Removals / Двоичные удаления
- 入力
- 出力
- 入出力例
- 注記
C. Minimum Grid Path / Минимальный путь на поле
- 入力
- 出力
- 入出力例
- 注記
D. The Number of Pairs / Количество пар
- 入力
- 出力
- 入出力例
- 注記
E. Chaotic Merge / Хаотичное слияние
- 入力
- 出力
- 入出力例
- 注記
F. Diameter Cuts / Разрезы диаметров
- 入力
- 出力
- 入出力例
- 注記
G. Graph Coloring / Раскраска графа

A. Domino on Windowsill / Домино на подоконнике

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

$2 \times n$ のセルからなる格子で表される盤面があります。

1行目の最初の $k_1$ セルと2行目の最初の $k_2$ セルが白で塗られています。その他のセルは黒で塗られています。

$w$ 枚の白いドミノ( $2 \times 1$ タイルで、両方のセルが白で着色されている)と $b$ 枚の黒いドミノ( $2 \times 1$ タイルで、両方のセルが黒で着色されている)があります。

白いドミノは盤面のその下の2つのセルに他のドミノが置かれておらず、両方のセルが白である場合、盤面に置くことができます。同様に、黒いドミノはその下の2つのセルに他のドミノが置かれておらず、両方のセルが黒である場合、盤面に置くことができます。

ドミノを縦にも横にも置くことができるとすれば、 $w + b$ 枚のドミノを全て置くことができるでしょうか?

入力

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

各テストケースの1行目には3つの整数 $n,\,k_1,\,k_2$ $(1 \leq n \leq 1000;$ $0 \leq k_1,\,k_2 \leq n)$ が与えられる。

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

出力

各テストケースについて、 $w + b$ 個のドミノを全て盤面に置くことができればYESと、そうでなければNOと出力せよ。

各文字について大文字で出力しても小文字で出力してもよい(それゆえ、例えば、文字列yEs, yes, Yes, YES は全て肯定の答えとして認識される)。

入出力例

NO
YES
NO
YES
YES

注記

1つ目のテストケースでは $n = 1,$ $k_1 = 0,$ $k_2 = 0$ です。これは $2 \times 1$ の盤面には黒のセル $(1,\,1)$ と白のセル $(2,\,1)$ があることを表します。白いセルが1つしかないので、白いドミノを置くことができません。

2つ目のテストケースでは同じ大きさ $2 \times 1$ の盤面ですがどちらのセルも白です。 $w = 0,$ $b = 0$ なので $0 + 0 = 0$ 枚のドミノを置くことができます。

3つ目のテストケースでは盤面は $2 \times 3$ ですが、全て黒で塗られている( $k_1 = k_2 = 0$ であるため)ので、白いドミノを置くことができません。

4つ目のテストケースではセル $(1,\,1),$ $(1,\,2),$ $(1,\,3),$ $(2,\,1)$ が白で、そのほかのセルは黒です。 $2$ 枚の白いドミノを位置 $( (1,\,1),\,(2,\,1) )$ と $( (1,\,2),\,(1,\,3) )$ に、 $2$ 枚の黒いドミノを位置 $( (1,\,4),\,(2,\,4) )$ と $( (2,\,2),\,(2,\,3) )$ に置くことができます。

B. Binary Removals / Двоичные удаления

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

文字'0'と'1'のみから成る文字列 $s$ が与えられます。 $s$ の長さを $|s|$ とします。

ある整数 $k$ $(k \gt 0)$ を選び、次のような長さ $k$ の数列 $a$ を求めて下さい。

$1 \leq a_1 \lt a_2 \lt \cdots \lt a_k \leq |s|$
$2$ から $k$ までの全ての $i$ について $a_{i-1} + 1 \lt a_i$

位置 $a_1,\,a_2,\,\dots,\,a_k$ の文字は削除され、残りの文字を順序を変えずに連結します。つまり、配列 $a$ の位置が隣接してはいけません。

この結果得られる文字列を $s'$ とします。 $2$ から $|s'|$ の全ての $i$ について $s'_{i-1} \leq s'_i$ であるとき $s'$ はソートされているといいます。

得られる文字列 $s'$ がソートされているような配列 $a$ は存在するでしょうか?

入力

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

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

各テストケースについての唯一の行には文字列 $s$ $(2 \leq |s| \leq 100)$ が与えられる。各文字は'0'か'1'のいずれかである。

出力

各テストケースについて位置 $a_1,\,a_2,\,\dots,\,a_k$ の文字を取り除き、順番を変えずに連結することで、ソートされている文字列が得られるような配列 $a$ が存在する場合、"YES"と出力せよ。

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

各文字について大文字で出力しても小文字で出力してもよい(それゆえ、例えば、文字列yEs, yes, Yes, YES は全て肯定の答えとして認識される)。

入出力例

5
10101011011
0000
11111
110
1100

YES
YES
YES
YES
NO

注記

1つ目のテストケースでは列 $a = [1,\,3,\,6,\,9]$ を選ぶことができます。"10101011011"から下線附きの文字を取り除くと文字列"0011111"ができ、これはソートされています。

2つ目と3つ目のテストケースでは列は既にソートされています。

4つ目のテストケースでは列 $a = [3]$ を選ぶことができます。 $s' =$ "11"となり、これはソートされています。

5つ目のテストケースでは $s'$ がソートされているような列 $a$ を選ぶ方法はありません。

C. Minimum Grid Path / Минимальный путь на поле

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

$XY$ -平面の点 $(0,\,0)$ に立っていて、点 $(n,\,n)$ に行きたいと思っています。

2方向にしか動くことができません。

右方向: 水平方向で、 $x$ 座標が大きくなる方向
上方向: 垂直方向で、 $y$ 座標が大きくなる方向

つまり、経路は次のような構造になっています。

最初、右に行くか上に行くかを選択する
次に、選択した方向にある正整数の距離だけ進む(距離は独立して選ぶことができる)
その後、方向を変えて(右から上、もしくは上から右)、このプロセスを繰り返す

方向転換を何度もしたくないので、 $n - 1$ 回よりも多く方向転換はしません。

結果として、経路は、各線分が正整数の長さを持ち、垂直線分と水平線分が交互に出てくる高々 $n$ 本の線分から成る $(0,\,0)$ から $(n,\,n)$ までの折れ線の鎖となります。

全ての経路が等価であるというわけではありません。 $n$ 個の整数 $c_1,\,c_2,\,\dots,\,c_n$ があり、ここで $c_i$ は $i$ 番目の成分のコストを表します。

これらのコストを用いて、経路のコストをその経路の線分の長さとコストの積の和として定義できます、すなわち、経路が $k$ 本の線分 $(k \leq n)$ から成る場合、経路のコストは $\displaystyle \sum\limits_{i=1}^{k}{c_i \cdot length_i}$ (線分は $1$ から $k$ まで経路の順に番号が振られている)となります。

最小コストの経路を求め、そのコストを出力してください。

入力

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

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

各テストケースの2行目には $n$ 個の整数 $c_1,\,c_2,\,\dots,\,c_n$ $(1 \leq c_i \leq 10^9)$ が与えられる、これらは各線分のコストである。

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

出力

各テストケースについて、高々 $n$ 本の交互に並ぶ線分から成る $(0,\,0)$ から $(n,\,n)$ までの経路の可能な最小コストを出力せよ。

入出力例

202
13
19

注記

1つ目のテストケースでは、 $(2,\,2)$ に到達するためには少なくとも1回は曲がらなければならないので経路はちょうど $2$ 本の線分から構成されます: 長さ $2$ の水平線分と長さ $2$ の垂直線分です。経路のコストは $2 \cdot c_1 + 2 \cdot c_2 = 26 + 176 = 202$ となります。

2つ目のテストケースでは、最適経路の1つが $3$ 本の線分から構成されています: 長さ $1$ の1本目と長さ $3$ の2本目、長さ $2$ の3本目です。

この経路のコストは $1 \cdot 2 + 3 \cdot 3 + 2 \cdot 1 = 13$ です。

3つ目のテストケースでは、最適経路の1つが $4$ 本の線分から構成されています: 長さ $1$ の1本目と長さ $1$ の2本目、長さ $4$ の3本目、長さ $4$ の4本目です。この経路のコストは $1 \cdot 4 + 1 \cdot 3 + 4 \cdot 2 + 4 \cdot 1 = 19$ です。

D. The Number of Pairs / Количество пар

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

3つの正の(0より大きい)整数 $c,\,d,\,x$ が与えられます。

等式 $c \cdot lcm(a,\,b) - d \cdot gcd(a,\,b) = x$ が成り立つような正整数の組 $(a,\,b)$ の個数を求めなければなりません。ここで $lcm(a,\,b)$ は $a,\,b$ の最小公倍数で、 $gcd(a,\,b)$ は $a,\,b$ の最大公約数です。

入力

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

各テストケースは1行からなり、3つの整数 $c,\,d,\,x$ $(1 \leq c,\,d,\,x \leq 10^7)$ が与えられる。

出力

各テストケースについて1つの整数を出力せよ、その数とは上記の等式を満たす組 $(a,\,b)$ の個数である。

入出力例

注記

1つ目の入出力例では、正しい組は $(1,\,4),$ $(4,\,1),$ $(3,\,6),$ $(6,\,3)$ です。

2つ目の入出力例では、正しい組は $(1,\,2),$ $(2,\,1),$ $(3,\,3)$ です。

E. Chaotic Merge / Хаотичное слияние

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

小文字のラテン文字のみで構成された2つの文字列 $x,\,y$ が与えられます。 $|s|$ を文字列 $s$ の長さとします。

列 $a$ をちょうど $|x|$ 個の0とちょうど $|y|$ 個の1がある順序で構成してる場合、それをマージ列を言います。

マージ $z$ は次のルールによって列 $a$ から生成されます。

$a_i = 0$ のとき、 $x$ の先頭から文字を削除し、 $z$ の末尾に追加する
$a_i = 1$ のとき、 $y$ の先頭から文字を削除し、 $z$ の末尾に追加する

$a_i \neq b_i$ となるような位置 $i$ がある場合、2つのマージ列 $a,\,b$ は異なります。

$2$ から $|z|$ までの全ての $i$ について $z_{i-1} \neq z_i$ であるばあい、文字列 $z$ をカオスであるといいます。

ある $1 \leq l \leq r \leq |s|$ について $s[l,\,r]$ を、位置 $l$ で始まり、位置 $r$ で終わる $s$ の連続した文字の部分列とします。

$f(l_1,\,r_1,\,l_2,\,r_2)$ を $x[l_1,\,r_1]$ と $y[l_2,\,r_2]$ のカオスなマージを生成する異なるマージ列の数とします。 $x$ と $y$ の空でない部分文字列のみを考慮することに注意してください。

$\displaystyle \sum \limits_{1 \leq l_1 \leq r_1 \leq |x| \\ 1 \leq l_2 \leq r_2 \leq |y|} f(l_1,\,r_1,\,l_2,\,r_2)$ を計算してください。答えはmodulo $998\,244\,353$ で出力してください。

入力

1行目には文字列 $x$ $(1 \leq |x| \leq 1000)$ が与えられる。

2行目には文字列 $y$ $(1 \leq |y| \leq 1000)$ が与えられる。

何方の文字列も小文字のラテン文字のみで構成される。

出力

単一の整数を出力せよ、その数は $1 \leq l_1 \leq r_1 \leq |x|$ かつ $1 \leq l_2 \leq r_2 \leq |y|$ での $f(l_1,\,r_1,\,l_2,\,r_2)$ の和 modulo $998\,244\,353$ である。

入出力例

aaa
bb

code
forces

aaaaa
aaa

justamassivetesttocheck
howwellyouhandlemodulooperations

667387032

注記

1つ目の入出力例では次のようになります。

$6$ 組の部分文字列"a"と"b"の組について、それぞれ"01"と"10"が有効なマージ列となる
$3$ 組の部分文字列"a"と"bb"の組について、それぞれ"101"が有効なマージ列となる
$4$ 組の部分文字列"aa"と"b"の組について、それぞれ"010"が有効なマージ列となる
$2$ 組の部分文字列"aa"と"bb"の組について、それぞれ"0101"と"1010"が有効なマージ列となる
$2$ 組の部分文字列"aaa"と"b"の組について、それぞれ有効なマージ列はない
$1$ 組の部分文字列"aaa"と"bb"の組について、それぞれ"01010"が有効なマージ列となる

従って、答えは $6 \cdot 2 + 3 \cdot 1 + 4 \cdot 1 + 2 \cdot 2 + 2 \cdot 0 + 1 \cdot 1 = 24$ となる。

F. Diameter Cuts / Разрезы диаметров

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

整数 $k$ と $n$ 頂点から成る無向木が与えられます。

ある頂点組間の単純経路(各頂点が高々1回しか現れない経路)の長さは、その経路の辺の数です。木の直径はその木の全ての頂点組間の単純経路の最大長です。

木から辺を1集合分取り除こうとしています。辺が削除されると気は複数の小さな気に分裂します。結果として得られる全ての木の直径が全て $k$ 以下であれば、辺の集合は有効です。

2つの辺の集合は一方にしか現れないような辺がある場合、異なります。

有効な辺の集合の数 modulo $998\,244\,353$ を数えてください。

入力

1行目には2つの整数 $n,\,k$ $(2 \leq n \leq 5000,$ $0 \leq k \leq n-1)$ が与えられる、それぞれ木の頂点数と最大許容直径である。

つづく $n-1$ 行のそれぞれには辺の記述が与えらえる: 2つの整数 $v,\,u$ $(1 \leq v,\,u \leq n,$ $v \neq u)$ 。

与えられた辺は木を形成する。

出力

単一の整数を出力せよ、その数は有効な辺の集合の数 modulo $998\,244\,353$ である。

入出力例

2 0
1 2

注記

1つ目の入出力例では、与えられた木の直径は既に $k$ 以下です。したがって削除する辺の集合を任意に選べ、結果として得られる木の直径は $k$ 以下です。集合は空のものも含め $2^3$ 個あります。

2つ目の入出力例では、唯一の辺を削除しなければなりませんうでなければ、直径が $1$ となり、 $0$ よりも大きくなります。

3つ目と4つ目の入出力例の木はこちらです。
f:id:Flkanjin:20210319152538p:plain

G. Graph Coloring / Раскраска графа

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

第1部の $n_1$ 頂点、第2部の $n_2$ 頂点、 $1$ から $m$ の番号が附いた $m$ 本の辺からなる二分グラフが与えられます。各辺を赤と青のうちいずれかの1色で塗らなければなりません。次の値 $\displaystyle \sum_{v \in V} |r(v) - b(v)|$ を最小化しなければなりません、ここで、 $V$ はグラフの頂点の集合で、 $r(v)$ は $v$ についている赤い辺の本数で、 $b(v)$ は $v$ についている青い辺の本数です。

古典的で簡単そうな響きでしょう? さて、次の形式の $q$ 個のクエリを処理しなければなりません。

$1\ v_1\ v_2$ — 第1部の頂点 $v_1$ と第2部の頂点 $v_2$ を結ぶ新しい辺を追加する。この辺は次のように新しいインデックスを取得する: 最初に追加された辺はインデックス $m + 1,$ で2番目は $m + 2$ 等々という感じである。辺の追加後、現在の最適彩色のハッシュを出力しなければならない(最適彩色が複数存在する場合、そのいずれかのハッシュを出力する)。実際には、このハッシュは確認されず、このクエリへの答えとして任意の数を出力することができるが、このハッシュを持つ彩色を出力するように求められることがある。
$2$ — 前のクエリを処理したのと同じハッシュのグラフの最適彩色を出力します。このタイプのクエリはタイプ1のクエリの後にしか来ず、高々 $10$ 回までしか来ない。このハッシュに対応する最適彩色が複数ある場合、そのうちのいずれかを出力せよ。

ある彩色で辺が赤や青だったとしても次の彩色ではその色が変わるかもしれません。

彩色のハッシュは次のように計算されます: $R$ を赤い辺のインデックスの集合とした時ハッシュは $\displaystyle \left( \sum_{i \in R} 2^i \right) \bmod 998244353$ となります。

この問題はonlineで解かなければならないことに注意してください。つまり、入力全体を一度に読むことができないということです。最後のクエリの応答が出力されてから初めて各クエリを読むことができます。プログラム内で各出力ののち、C++ではfflush、JavaではBufferedWriter.flushという関数を用いてください。

入力

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

その後、 $m$ 行が続き、その $i$ 行目には2つの整数 $x_i,\,y_i$ $(1 \leq x_i \leq n_1:$ $1 \leq y_i \leq n_2)$ が与えられる、これは $i$ 番目の辺が第1部の頂点 $x_i$ と第2部の頂点 $y_i$ をと結んでいることを表す。

次の行には1つの整数 $q$ $(1 \leq q \leq 2 \cdot 10^5)$ が与えられる、これは処理しなければならないクエリの数である。

つづく $q$ 行には問題文に記載されている形式のクエリが与えられる；

入力の追加制約:

どの時点においてもグラフ多重辺を持たない
タイプ $2$ のクエリは前のクエリがタイプ $1$ のクエリであるときにしか来ない
タイプ $2$ のクエリは最大 $10$ 個である

出力

タイプ $1$ に答えるためには1つの整数を出力せよ、その数は最適彩色のハッシュである。

タイプ $2$ に答えるためには1行を出力せよ。これは整数 $k$ で始まっていなければならない、この数は赤い辺の本数である。そののち、 $k$ 個の異なる整数が続く、これらは彩色における赤い辺のインデックスで、順番は問わない。各インデックスは既存辺に対応してなければならず、生成する彩色のハッシュは1つ前の1つ前のクエリの答えとして出力したハッシュと同じでなければならない。

クエリに対する答えが複数ある場合、そのいずれかを出力せよ。

入出力例