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

A. Alexey and Train / Леша и поезд (500点)
- 入力
- 出力
- 入出力例
- 注記
B. Napoleon Cake / Торт Наполеон (1000点)
C. Going Home / Поеду домой (1750点)
- 入力
- 出力
- 入出力例
- 注記
D. Two chandeliers / Две люстры (1750点)
- 入力
- 出力
- 入出力例
- 注記
E. Matrix Sorting / Сортировка матрицы (2500点)
- 入力
- 出力
- 入出力例
- 注記
F. Tiles for Bathroom / Плитка для ванной (3000点)
- 入力
- 出力
- 入出力例
- 注記

A. Alexey and Train / Леша и поезд (500点)

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

Леша*1は電車で旅をしています。不幸なことに、悪天候のため電車の運行が遅くなっています。

Лешаは鉄道ターミナル駅で電車に乗りました。この電車は時刻 $0$ に他0美成駅を出発するとします。また、この電車は途中で $1$ から $n$ の番号が付いた $n$ 駅を順に訪れ、Лешаの目的地は駅 $n$ であるとします。

Лешаは時刻表から $n$ 個の整数の組 $(a_i,\,b_i)$ を知りました、ここで $a_i$ は電車が $i$ 番目の駅に着く見込み時刻で、 $b_i$ は電車が $i$ 番目の駅を出発する見込み時刻です。

また、全ての情報を用いてЛешаは $n$ 個の整数 $tm_1,\,tm_2,\,\dots,\,tm_n$ を計算することができました、ここで電車が $tm_i$ は駅 $i - 1$ から駅 $i$ まで行くのに余分にかかる時間です。形式的には、電車が $tm_i$ は駅 $i - 1$ から駅 $i$ まで行くのにちょうど $a_i - b_{i - 1} + tm_i$ の時間がかかります( $i = 1$ のときは $b_0$ はターミナル駅を出発した時刻であり、 $0$ である)。

電車が駅 $i$ を出発するのは次の2つの条件の両方を満たす場合です。

電車が少なくとも $\displaystyle \left\lceil \frac{b_i - a_i}{2} \right\rceil$ 単位時間(割って切り上げ) 駅にいる
現在時刻 $\geq b_i$

Лешаは時間の遅れの予測に全エネルギーを費やしたので、彼が駅 $n$ への到着時刻を計算するのを手伝ってください。

入力

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

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

つづく $n$ 行には2つの整数 $a_i,\,b_i$ $(1 \leq a_i \lt b_i \leq 10^6)$ が与えられる。 $b_i \leq a_{i + 1}$ であることは保証されている。

次の行には $n$ 個の整数 $tm_1,\,tm_2,\,\dots,\,tm_n$ $(0 \leq tm_i \leq 10^6)$ が与えられる。

出力

各テストケースについて1つの整数を出力せよ、その整数とはЛешаの最終駅への到着時間である。

入出力例

12
32

注記

1つ目のテストケースではЛешаは駅 $1$ に遅延なしで $a_1 = 2$ の時刻に到着します( $tm_1 = 0$ であるため)。そののち彼は $b_1 = 4$ の時刻に出発します。最終的に、彼は駅 $2$ に $tm_2 = 2$ の遅延時間で、すなわち時刻 $12$ に到着します。

2つ目のテストケースではЛешаは1駅目に $tm_1 = 1$ の遅延時間で、すなわち時刻 $2$ に到着します。この電車は1つの条件からこの駅に少なくとも $\displaystyle \left\lceil \frac{b_1 - a_1}{2} \right\rceil = 2$ 単位時間いなければならす、もう1つの条件から時刻 $b_i = 4$ よりも早く出発してはいけません。結果として電車は時刻 $4$ に出発することになります。

同じ理屈で、2駅目には時刻 $9$ に到着し、時刻 $10$ に出発、3駅目には時刻 $14$ に到着し、時刻 $15$ に出発、4駅目には時刻 $22$ に到着し、時刻 $23$ に出発することがわかります。そして最終的に、5駅目には時刻 $32$ に到着します。

B. Napoleon Cake / Торт Наполеон (1000点)

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

今週、Аркадий*2は(古代からの伝統に則って)パンケーキを焼き、それについての問題を作ろうと思っていました。しかし、特定のIT企業に勤めていないとパンケーキを重ねる問題は作れないことを思い出し、代わりにNapoleonケーキ*3を焼くことにしました。

Napoleonケーキを焼くには、まずドライ層 $n$ 層を焼き、それをそれぞれクリームを加えながら重ねていきます。Аркадийはからの皿から始め、次の手順を $n$ 回繰り返します。

新しいケーキの層を重ねる
$i$ 番目のケーキを置いたのち、上部に $a_i$ 単位のクリームを加える

$x$ 単位のクリームを加えると、上から $x$ 層がクリームに浸されます。 $x$ 層未満しかない場合、全ての層が浸され、残ったクリームは無駄になります。 $x = 0$ の場合は、1層も浸りません。

f:id:Flkanjin:20210314021853p:plain — 入出力例の1つ目のテストケースを表した図

Аркадийがこのプロセスが終わったときに、ケーキのどの層が最終的に浸っていて、どの層が浸ってないかを判断できるように手伝ってください。

入力

各テストには複数のテストケースが含まれる。1行目には単一の整数 $t$ $(1 \leq t \leq 20\,000)$ が与えられる、これはテストケースの数である。その後、テストケースの記述が続く。

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

各テストケースについての記述の2行目には $n$ 個の整数 $a_1,\,a_2,\,\dots,\,a_n$ $(0 \leq a_i \leq n)$ が与えられる、これらは各層を乗せたあとにケーキに加えるクリームの量である。

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

出力

各テストケースについて $n$ 個の整数を単一行に出力せよ。これらの整数の $i$ 番目は下から $i$ 層目が浸っている場合 $1$ 、そうでない場合 $0$ である。

入出力例

3
6
0 3 0 0 1 3
10
0 0 0 1 0 5 0 0 0 2
3
0 0 0

1 1 0 1 1 1 
0 1 1 1 1 1 0 0 1 1 
0 0 0

C. Going Home / Поеду домой (1750点)

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

通信教育をはじめて3ヶ月経ち、Настя*4は寮にいるのに飽きて*5故郷に帰ることに思案した。この旅が楽しくするために、Настяの友人の1人が彼女に整数列 $a$ をプレゼントしてくれました。

家路への出発から数時間*6経ち、Настяはそのプレゼントについて思い出しました。楽しむため $a_x + a_y = a_z + a_w$ となるような4つの異なるインデックス $x,\,y,\,z,\,w$ があるかどうか調べることにしました。

彼女の乗った電車はもう目的地に着きましたが、彼女はまだ答えを見つけていません。この謎を解く彼女の手伝いをしてください。

入力

1行目には単一の整数 $n$ $(4 \leq n \leq 200\,000)$ が与えられる、これは配列の大きさである。

2行目には $n$ 個の整数 $a_1,\,a_2,\,\dots,\,a_n$ $(1 \leq a_i \leq 2.5 \cdot 10^6)$ が与えられる。

出力

そのような4つのインデックスが存在する場合"YES"と、そうでない場合"NO"と出力せよ。

このようなインデックスが存在する場合、インデックス $x,\,y,\,z,\,w$ $(1 \leq x,\,y,\,z,\,w \leq n)$ を出力せよ。

答えが複数ある場合、そのいずれかを出力せよ。

入出力例

6
2 1 5 2 7 4

YES
2 3 1 6

5
1 3 1 9 20

NO

注記

1つ目の入出力例では、 $a_2 + a_3 = 1 + 5 = 2 + 4 = a_1 + a_6$ となっています。なお、他にも答えはあり、例えば2 3 4 6です。

2つ目の入出力例では、4つのインデックスを選ぶことはできません。 $a_1 + a_2 = 1 + 3 = 3 + 1 = a_2 + a_3$ ですが、インデックスは異ならなければならないので、1 2 2 3という答えは不正解です。

D. Two chandeliers / Две люстры (1750点)

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

Вася*7は大手建設会社のCEOです。他の大企業の社長と同じように2つのクリスタルのシャンデリア付きの広々とした豪華な家具を備えたオフィスを持っています。モチベーションを維持するために、Васяはオフィスの光の色を毎日変えなければなりません。そのため、周期的に色を変えれるような2つのシャンデリアを注文したのです。例えば、赤-茶-黄-赤-茶-黄のような感じです。

色の集合やその順番が異なるシャンデリアが沢山あります。そして、証明たんっ当社は致命的なミスを犯してしまいました、異なる2つのシャンデリアを買ってしまったのです。

シャンデリアが異なるため、色が同じ日もあれば、異なる日もあります。勿論、見た目としても悪く、Васяをイライラさせるだけです。その結果、シャンデリアが $k$ 回違う色で光った時Васяはは激怒し、恐らく、シャンデリアを購入した人を解雇するでしょう。

このことがいつ起こるか(シャンデリアが設置された日から数える)を計算するのが貴方の仕事です。Васяは週末も休日もなく毎日働いているものと考えてよいです。

入力

1行目には3つの整数 $n,\,m,\,k$ $(1 \leq n,\,m \leq 500\,000;$ $1 \leq k \leq 10^{12})$ が与えられる、これらは1つ目と2つ目のシャンデリアの色数と、Васяが激怒し出すときのシャンデリアの色が異なる回数である。

2行目には1つ目のシャンデリアの色列を表す $n$ 個の異なる整数 $a_i$ $(1 \leq a_i \leq 2 \cdot \max(n,\,m))$ が与えられる。

3行目には2つ目のシャンデリアの色列を表す $m$ 個の異なる整数 $b_i$ $(1 \leq b_i \leq 2 \cdot \max(n,\,m))$ が与えられる。

$i$ 日目の1つ目のシャンデリアの色は $a_x$ で、2つ目のシャンデリアの色は $b_y$ である、ここで $x = ((i-1 \bmod{n}) + 1),$ $y = ((i-1 \bmod{m}) + 1)$ である。

配列 $a$ と配列 $b$ が異なることは保証されており、シャンデリアの色が異なる日は存在します。

出力

単一の整数を出力せよ、その整数はВасяが激怒する日のインデックスである。

入出力例

4 2 4
4 2 3 1
2 1

3 8 41
1 3 2
1 6 4 3 5 7 2 8

1 2 31
1
1 2

注記

1つ目の入出力例では、 $1$ 日目、 $2$ 日目、 $3$ 日目、 $5$ 日目にシャンデリアの色が異なります。そのため、答えは $5$ となります。

E. Matrix Sorting / Сортировка матрицы (2500点)

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

大きさ $n \times m$ の2つの表 $A,\,B$ が与えられます。

ここで、列によるソートを次のように定義します: ある列を選び、全ての行をこの列の値が小さい行から大きい行へと並び替えます。この列に同じ値の行が2つ以上存在する場合、その相対的な順序は変わりません(このようなソートアルゴリズムは安定であるといわれます)。

このような列によるソートの動作は、スプレッドシートを管理する多くのオフィスソフトで見られます。Петя*8はこのソフトを使っていて、現在、表 $A$ を開いています。彼はこの表を表 $B$ に変換するために列によるソートを0回以上実行したいと思っています。

それが可能かどうかを判断し、可能であればソートする列の順序を見つけてください。並べ替えの回数を最小化する必要はありません。

入力

1行目には2つの整数 $n,\,m$ $(1 \leq n,\,m \leq 1500)$ が与えられる、これらは表の大きさである。

つづく $n$ 行のそれぞれには $m$ 個の整数 $a_{i,j}$ $(1 \leq a_{i,j} \leq n)$ が与えられます、これらは表 $A$ の要素である。

つづく $n$ 行のそれぞれには $m$ 個の整数 $b_{i,j}$ $(1 \leq b_{i,j} \leq n)$ が与えられます、これらは表 $B$ の要素である。

出力

$A$ を $B$ に変換することができなければ、 $-1$ を出力せよ。

そうでなければ、まず1つの整数 $k$ $(0 \leq k \leq 5000)$ を出力せよ、これは解でのソート回数である。

次に、 $k$ 個の整数 $c_1,\,\dots,\,c_k$ $(1 \leq c_i \leq m)$ を出力せよ、これらはПетяがソートを行う必要のある列である。

解が存在するとき、 $5000$ 回以下のソートの解があることは示すことができる。

入出力例

1
1

2
1 2

-1

1
1

注記

2つ目の入出力例を考えてみましょう。1列目でソートした後、表は次のようになります。

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

2列目でソートした後、表は

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

となり、これが私たちが欲しいものです。

3つ目の入出力例では列は既にソートされているため、どのようなソートでも何も変わりません。

F. Tiles for Bathroom / Плитка для ванной (3000点)

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

Костя*9は非常に忙しいです、彼の家を改装しています! 紙を貼ったり、家具を組み立てたり、ゴミを捨てたりしなければなりません。

今日Костяはバスルーム用のタイルを買うつもりです。彼は、お店のタイルが並んだ大きな正方形の台の前に立っています。台は $n \times n$ セルの正方形で、各セルには色 $c_{i,j}$ のタイルがおかれています。この店ではタイルをパッケージで売っています: より具体的に言うと、元の正方形の部分正方形しか買うことができません。

部分正方形とは台の任意の正方形部分であり、すなわち、 $1 \leq i_0,\,j_0 \leq n - k + 1$ についての任意の集合 $S(i_0,\,j_0,\,k) = \{c_{i,j} \mid i_0 \leq i \leq i_0 +k,\,j_0 \leq j \leq j_0 +k\}$ のことです。

Костяには必要なタイルの枚数がまだ分からないので、あらゆる可能な大きさの部分正方形を考慮します。彼はバスルームをあまりカラフルにはしたくありません。Костяが各 $k \leq n$ について高々 $q$ 個の異なる色のタイルからなる大きさ $k \times k$ の部分正方形の数を数えるのを手伝ってください。2つの部分正方形は台上の位置が異なれば違うものとみなされます。

入力

1行目には2つの整数 $n,\,q$ $(1 \leq n \leq 1500,$ $1 \leq q \leq 10)$ が与えられる、これは台の大きさと部分正方形内の異なる色の数の制限である。

つづく $n$ 行のそれぞれには $n$ 個の整数 $c_{i,j}$ $(1 \leq c_{i,j} \leq n^2)$ が与えられる、 $i$ 行目の $j$ 番目の整数はセル $(i,\,j)$ 内のタイルの色である。

出力

$1$ から $n$ までの各 $k$ について、1つの整数を出力せよ、これは $q$ 個以下の異なる色を持つ大きさ $k \times k$ の部分正方形の数である。

入出力例

9
4
0

注記

1つめの入出力例では全ての色が異なります。Костяは $4$ 色よりも奥の色を持つ部分正方形は欲しくないため、任意の大きさ $1 \times 1$ や $2 \times 2$ の部分正方形は買うことができますが、任意の大きさ $3 \times 3$ の部分正方形は購入できません。

2つめの入出力例では複数回現れる色があります。 $q = 8$ であるため、任意の大きさ $1 \times 1$ や $2 \times 2$ の部分正方形は買うことができ、また、 $7$ 個の異なる色からなるため任意の大きさ $3 \times 3$ の部分正方形を買うことができます。台全体の $4 \times 4$ は $9$ 色あるため買うことができません。