Educational Codeforces Round 107 問題文和訳

A. Review Site / Сайт отзывов
- 入力
- 出力
- 入出力例
- 注記
B. GCD Length / Длина НОД
- 入力
- 出力
- 入出力例
- 注記
C. Yet Another Card Deck / Очередная задача про колоду карт
- 入力
- 出力
- 入出力例
- 注記
D. Min Cost String / Строка минимальной стоимости
E. Colorings and Dominoes / Раскраски и домино
F. Chainword / Чайнворд
- 入力
- 出力
- 入出力例
- 注記
G. Chips on a Board / Фишки на доске

A. Review Site / Сайт отзывов

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

貴方は将来の映画監督で、最初の映画を公開したところです。また、「いいね」と「ひどいね」の2つのボタンのついたシンプルなサイトを立ち上げました。

しかし、このサイトは内部的にはそれほど単純ではありません。サーバが2台あり、「いいね」と「ひどいね」をそれぞれのサーバが別々にカウントしています。

$n$ 人のレビュアーが1人ずつサイトを訪れます。各レビュアーは以下のタイプのいずれかです。

タイプ $1$ : レビュアーは映画を見て気に入り、「いいね」ボタンを押す
タイプ $2$ : レビュアーは映画を見て気に入らず、「ひどいね」ボタンを押す
タイプ $3$ : レビュアーは映画を見ないで、自分のいるサーバの「いいね」と「ひどいね」の現在の数を見て、どちらのボタンを押すかを決める。「ひどいね」が「いいね」より多い場合、この映画に対して「ひどいね」を押す。そうでない場合、この映画に対して「いいね」を押す。

各レビュアーは1回のみ映画に対して評価を行います。

サーバが2つあるので、映画にできるだけ多くの「いいね」が付くように投票を操作することができます。レビュアーがサイトを訪れたときその人のタイプが分かるので、第1サーバに送るか第2サーバに送るかを選ぶことができます。

各レビュアーをどちらのサーバに送るかを決めたとき、両方のサーバで集められる「いいね」の合計値の最大値はいくらでしょう?

入力

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

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

各テストケースの1行目には単一の整数 $n$ $(1 \leq n \leq 50)$ が与えられる、これはレビュアーの人数である。

各テストケースの2行目には $n$ 個の整数 $r_1,\,r_2,\,\dots,\,r_n$ $(1 \leq r_i \leq 13)$ が与えられる、これらはサイトを訪れる順に並べたレビュアーの種類である。

出力

各テストケースについて、単一の整数を出力せよ、その整数とは各レビュアをどちらのサーバーに送るかを決めたとき、両方のサーバで集められる「いいね」の合計値の最大値である。

入出力例

注記

入出力例の1つ目のテストケースでは、唯一のレビュアをどちらのサーバにも送ることができますが、どちらにしても「ひどいね」を押します。この映画は「いいね」の評価を受けません。

入出力例の2つ目のテストケースでは、レビュアーを全員第1サーバに送ることができます。

1人目のレビュアーが「いいね」を押す
2人目のレビュアーが「ひどいね」を押す
最後のレビュアーが「ひどいね」が「いいね」を上回っていなことを確認し、「いいね」を押す

「いいね」は合計で2つです。別の方法として、1人目のレビュアーと2人目のレビュアーを第1サーバに、最後のレビュアーを第2サーバに送ることもできます。

1人目のレビュアーが第1サーバで「いいね」を押す
2人目のレビュアーが第1サーバで「ひどいね」を押す
最後のレビュアーが第2サーバで「いいね」も「ひどいね」もないことを確認し、「いいね」を押す

B. GCD Length / Длина НОД

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

3つの整数 $a,\,b,\,c$ が与えられます。

次の条件を満たす2つの正整数 $x,\,y$ $(x \gt 0,$ $y \gt 0)$ を求めて下さい。

先行ゼロを除いた $x$ の十進数表現は $a$ 桁である
先行ゼロを除いた $y$ の十進数表現は $b$ 桁である
先行ゼロを除いた $gcd(x,\,y)$ の十進数表現は $c$ 桁である

$gcd(x,\,y)$ は整数 $x$ と $y$ の最大公約数(greatest common divisor, GCD)*1を表します。

$x$ と $y$ を出力してください。答えが複数存在する場合、そのいずれかを出力してください。

入力

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

続く $t$ 行のそれぞれには3つの整数 $a,\,b,\,c$ $(1 \leq a,\,b \leq 9,$ $1 \leq c \leq \min(a,\,b))$ が与えられる、これらは数字の長さの条件である。

与えられた制約のもとで、全てのテストケースに対して答えが存在することは証明できる。

入力についての追加制約: 全てのテストケースは異なるものである。

出力

各テストケースについて2つの整数を出力せよ、その2つの整数は以下の条件を満たす $x,\,y$ $(x \gt 0,$ $y \gt 0)$ である。

先行ゼロを除いた $x$ の十進数表現は $a$ 桁である
先行ゼロを除いた $y$ の十進数表現は $b$ 桁である
先行ゼロを除いた $gcd(x,\,y)$ の十進数表現は $c$ 桁である

入出力例

11 492
13 26
140133 160776
1 1

注記

入出力例では次の通りになります。

$gcd(11,\,492) = 1$
$gcd(13,\,26) = 13$
$gcd(140133,\,160776) = 21$
$gcd(1,\,1) = 1$

C. Yet Another Card Deck / Очередная задача про колоду карт

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

上から下に番号が振られた $n$ 枚のカードデッキがあります。つまり，一番上のカードのインデックスは $1$ で、一番下のカードのインデックスは $n$ となります。各カードにはそれぞれの色があり、 $i$ 枚目の色は $a_i$ です。

$q$ 個のクエリを処理しなければなりません。 $j$ 番目のクエリは整数 $t_j$ で表されます。各クエリについて次のようなことを行わなければなりません。

デッキ内で色 $t_j$ である最も上のカード、即ち、最小のインデックスを持つカードを見つける
見つけたカードの位置を出力する
そのカードを取り出し、デッキの一番上に置く

入力

1行目には2つの整数 $n,\,q$ $(2 \leq n \leq 3 \cdot 10^5;$ $1 \leq q \leq 3 \cdot 10^5)$ が与えられる、これらはデッキ内のカードの枚数とクエリの個数である。

2行目には $n$ 個の整数 $a_1,\,a_2,\,\dots,\,a_n$ $(1 \leq a_i \leq 50)$ が与えられる、これらはカードの色である。

3行目には $q$ 個の整数 $t_1,\,t_2,\,\dots,\,t_q$ $(1 \leq t_j \leq 50)$ が与えられる、これらはクエリの色である。クエリではデッキ内に存在する色のみを尋ねられることは保証される。

出力

$q$ 個の整数を出力せよ、それらは各クエリに対する答えである。

入出力例

7 5
2 1 1 4 3 3 1
3 2 1 1 4

5 2 3 1 5

注記

入出力例の説明:

デッキは $[2,\,1,\,1,\,4,\,\underline{3},\,3,\,1]$ で、色 $t_1 = 3$ である最初のカードの位置は $5$ である。
デッキは $[3,\,\underline{2},\,1,\,1,\,4,\,3,\,1]$ で、色 $t_2 = 2$ である最初のカードの位置は $2$ である。
デッキは $[2,\,3,\,\underline{1},\,1,\,4,\,3,\,1]$ で、色 $t_3 = 1$ である最初のカードの位置は $3$ である。
デッキは $[\underline{1},\,2,\,3,\,1,\,4,\,3,\,1]$ で、色 $t_4 = 1$ である最初のカードの位置は $1$ である。
デッキは $[1,\,2,\,3,\,1,\,\underline{4},\,3,\,1]$ で、色 $t_5 = 4$ である最初のカードの位置は $5$ である。

D. Min Cost String / Строка минимальной стоимости

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

文字列 $s$ のコストを $s_i = s_j$ かつ $s_{i+1} = s_{j+1}$ を満たすインデックスの組 $i,\,j$ $(1 \leq i \lt j \leq |s|)$ の個数と定義しましょう。

2つの正整数 $n,\,k$ が与えられます。ラテン文字の最初の $k$ 文字のみを含む長さ $n$ の全ての文字列の中で、可能な限り最小コストの文字列を求めて下さい。そのような最小コストの文字列が複数存在する場合は、そのいずれかを出力してください。

入力

唯一の行には2つの整数 $n,\,k$ $(1 \leq n \leq 2 \cdot 10^5;$ $1 \leq k \leq 26)$ が与えられる。

出力

$n$ 文字で構成され、その各文字がラテン文字の最初の $k$ 文字のうちの1つであり、これらの文字列の中でコストが最小となるような文字列 $s$ を出力せよ。このような文字列が複数ある場合は、そのうちのいずれかを出力せよ。

入出力例

9 4

aabacadbb

5 1

aaaaa

10 26

codeforces

E. Colorings and Dominoes / Раскраски и домино

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

$n \times m$ 個のセルに分割されている大きな長方形のボードがあります( $n$ 行 $m$ 列)。各セルは白か黒です。

各白セルを赤か青で塗ります。自明ですが、白セルの数を $w$ とすると塗り方は $2^w$ 通りあります。

ボード上の白セルを塗ったのち、次のようなルールに従って最大数のドミノを置いていきます。

各ドミノは隣接する2つのセルを覆う
各セルは高々1枚のドミノで覆われる
ドミノを横向きに置いた(1行の2つセルを覆う)場合、赤セルのみを覆う
ドミノを縦向きに置いた(1列の2つセルを覆う)場合、青セルのみを覆う

ボードの値を置くことができるドミノの最大枚数とします。可能な $2^w$ 通りの塗り方全てについての値の合計を計算してください。個の和が巨大になる可能性があるので、modulo $998\,244\,353$ で出力してください。

入力

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

そののち、 $n$ 行が続き、各行には $m$ 文字の文字列が与えられる。 $i$ 個目の文字列の $j$ 文字目は $i$ 行目の $j$ 番目のセルが黒のとき *、そうでないときoである。

出力

1つの整数を出力せよ、その数とは可能な $2^w$ 通りの塗り方についてボードの値の和を $998\,244\,353$ で割った余りである。

入出力例

3 4
**oo
oo*o
**oo

3 4
**oo
oo**
**oo

2 2
oo
o*

1 4
oooo

F. Chainword / Чайнворд

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

チェーンワードはクロスワードの特殊な種類です。大体のクロスワードと同様に、文字を入れるセルと、その文字が何であるかを示すヒントがあります。

チェーンワードの文字セルは1列に並べられています。この課題では長さ $m$ のチェーンワードを考えます。

チェーンワードのヒントとは、互いに交差せず、 $m$ 個の文字セルを全てカバーするような、一連のセグメントのことです。各セグメントには、対応するセルにある単語の説明が含まれています。

奇妙なことに実際にはヒントは2つあります: 1つは文字セルの上の行のセグメント列で、もう1つは文字セルの下の行のセグメント列です。列が異なる場合は、答えの曖昧さを解消するのに役立っています。

$n$ 単語の辞書が当たられます、各語は小文字のラテン文字から成ります。全ての語は互いに相異なります。

チェーンワードのインスタンスは次のような3つ組です。

$m$ 文字の小文字のラテン文字の文字列
第1ヒント: 各セグメントに対応する文字が辞書内の単語となるようなセグメント列
第2ヒント: 各セグメントに対応する文字が辞書内の単語となるような別のセグメント列

セグメント列は必ずしも異なるものである必要はないことに注意してください。

チェーンワードの2つのインスタンスは、異なる文字列または異なる第1ヒントまたは異なる第2ヒントを持つ場合、異なるものと見做されます。

チェーンワードの異なるインスタンスの数を数えます。この数はかなり大きくなるかもしれないので、modulo $998\,244\,353$ で出力してください。

入力

1行目には2つの整数 $n,\,m$ $(1 \leq n \leq 8,$ $1 \leq m \leq 10^9)$ が与えられる、これらは辞書の単語数と文字セルの数である。

続く $n$ 行のそれぞれには単語が与えられる、これらは小文字のラテン文字 $5$ 文字以内の空でない文字列である。全ての単語は互いに異なる。

出力

1つの整数を出力せよ、与えられた辞書に対する長さ $m$ の異なるチェーンワードのインスタンスの数を $998\,244\,353$ で割った余りである。

入出力例

3 5
ababa
ab
a

2 4
ab
cd

5 100
a
aa
aaa
aaaa
aaaaa

142528942

注記

ここにあるのは、1つ目の入出力例についての有効なチェーンワードの全てのインスタンスです。
f:id:Flkanjin:20210413181239p:plain
文字の上の赤い線は第1ヒントのセグメントを、文字の下の青い線は第2ヒントのセグメントを示しています。

2つ目の入出力例では、以下の文字列が考えられます: "abab", "abcd", "cdab", "cdcd"。ヒントは全て、最初の2文字と最後の2文字をカバーするセグメントです。

G. Chips on a Board / Фишки на доске

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

AliceとBobは $n$ 行 $m$ 列から成る長方形のボードを持っています。各行にはチップがちょうど1枚置かれています。

AliceとBobは次のようなゲームをします。2人は $1 \leq l \leq r \leq m$ である2整数 $l,\,r$ を選び、列 $l$ から列 $r$ まで(区間の両端を含む)の部分のみが残るようにボードを切ります。つまり、列 $l$ より左にある全ての列と列 $r$ より右にある全ての列はもはやボードの一部ではなくなります。

ボードを切った後、ボードの残った部分(列 $l$ から列 $r$ までの部分)のチップを移動させます。交互に手を打ち、手を打てなかったプレイヤーがゲームに負けます。1手目はAlice、2手目はBob、3手目はAliceというように進行します。手を打つ際、プレイヤーはボード上のチップを1つ選び、任意の正の数のセル分左に移動させなければなりません(つまり、列 $i$ にあったチップは列 $j \lt i$ に移動させることができ、一番左の列にあるチップは選べない)。

AliceとBobは数の組 $L_i,\,R_i$ を $q$ 組持っています。そのような各ペアについて、 $l = L_i,$ $r = R_i$ としたときに、どちらがゲームの勝者になるかを判別したいと思っています。これらのゲームは独立である(次のゲームのボードの状態には影響を与えない)と考えられ、AliceもBobも最適なプレーを行います。

入力

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

2行目には $n$ 個の整数 $c_1,\,c_2,\,\dots,\,c_n$ $(1 \leq c_i \leq m)$ が与えられる、ここで $c_i$ は $i$ 行目のチップのある列のインデックスである(つまり、 $i$ 行目のチップは $c_i$ 列目にある)。

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

そののち、 $q$ 行が続き、その $i$ 行目には2つの整数 $L_i,\,R_i$ $(1 \leq L_i \leq R_i \leq 2 \cdot m)$ が与えられる。

出力

$q$ 文字の文字列を出力せよ。 $i$ 文字目は、 $l = L_i,$ $r = R_i$ のゲームでAliceが勝った場合はA、Bobが勝った場合はBとする。

入出力例

8 10
1 3 3 7 4 2 6 9
7
2 3
1 3
1 4
1 10
5 10
8 10
9 10

BAAAAAB

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