AtCoder Beginner Contest 264 メモ(A-E)

今回の結果

4AC

D問題よりC問題のほうが難しいと感じたけど、Difficultyを見たらその感覚はあってた。
最近WAを出すことが続いていたけど、今回はWAなしの4ACできてよかった。

A - "atcoder".substr()

https://atcoder.jp/contests/abc264/tasks/abc264_a

Difficulty: 8

問題文

文字列 atcoder の $L$ 文字目から $R$ 文字目までを出力してください。

制約

• $L,R$ は整数
• $1 \le L \le R \le 7$

入力

入力は以下の形式で標準入力から与えられる。

$L$ $R$

出力

答えを出力せよ。

入出力例

入力例 1

3 6

出力例 1

code

入力例 2

4 4

出力例 2

o

入力例 3

1 7

出力例 3

atcoder

参加中に考えたこと

substr関数は開始位置とそこから何文字を取得する関数なのに対し、この問題では開始位置と終了位置を受け取ってその範囲の文字列を返したい。
また、substr関数の開始位置は0からなのでl-1を開始位置にして、文字数はr-l+1で取れるのでこの2つをsubstr関数の引数にすると出力したい値が取れる。

B - Nice Grid

https://atcoder.jp/contests/abc264/tasks/abc264_b

Difficulty: 55

問題文

次の図に示す、各マスが黒または白に塗られた縦 $15$ 行 $\times$ 横 $15$ 列のグリッドにおいて、
上から $R$ 行目、左から $C$ 列目のマスが何色かを出力して下さい。

制約

• $1 \leq R, C \leq 15$
• $R, C$ は整数

入力

入力は以下の形式で標準入力から与えられる。

$R$ $C$

出力

図のグリッドにおいて上から $R$ 行目、左から $C$ 列目のマスが黒色の場合は black と、白色の場合は white と出力せよ。
ジャッジは英小文字と英大文字を厳密に区別することに注意せよ。

入出力例

入力例 1

3 5

出力例 1

black

入力例 2

4 5

出力例 2

white

参加中に考えたこと

数式を使って一発で求められるような気もするが式を考えるのに時間がかかりそうなので、この15x15の二次元配列を作ってしまって $(R,C)$ の値を出力する方法をとることにした。
ではこの図はどうやって作ろうか。手作業で作る方法もあるが面倒なので数式でできればと考えて、2度のループに分けて i=0,2,4,6 の時に横のライン、 j=0,2,4,6 の時に縦のラインを黒にする方法で作成した。

考察・感想

Difficultyが低いのは15x15の二次元配列を手作業でも作れてしまうからかな。
解説のチェビシェフ距離というのは初めて聞いた。
マンハッタン距離というのは聞いたことはあったんだけど。

C - Matrix Reducing

https://atcoder.jp/contests/abc264/tasks/abc264_c

Difficulty: 758

問題文

$H_1$ 行 $W_1$ 列の行列 $A$ と、$H_2$ 行 $W_2$ 列の行列 $B$ が与えられます。

• $1 \leq i \leq H_1$ かつ $1 \leq j \leq W_1$ を満たす整数の組 $(i, j)$ について、行列 $A$ の $i$ 行目 $j$ 列目の要素は $A_{i, j}$ です。
• $1 \leq i \leq H_2$ かつ $1 \leq j \leq W_2$ を満たす整数の組 $(i, j)$ について、行列 $B$ の $i$ 行目 $j$ 列目の要素は $B_{i, j}$ です。

行列 $A$ に対して、下記の $2$ つの操作のうちどちらかを行うことを、好きなだけ（ $0$ 回でも良い）繰り返すことができます。

• $A$ の行を任意に $1$ つ選んで削除する。
• $A$ の列を任意に $1$ つ選んで削除する。

行列 $A$ を行列 $B$ に一致させることができるかどうかを判定して下さい。

制約

• $1 \leq H_2 \leq H_1 \leq 10$
• $1 \leq W_2 \leq W_1 \leq 10$
• $1 \leq A_{i, j} \leq 10^9$
• $1 \leq B_{i, j} \leq 10^9$
• 入力中の値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$H_1$ $W_1$
$A_{1, 1}$ $A_{1, 2}$ $\ldots$ $A_{1, W_1}$
$A_{2, 1}$ $A_{2, 2}$ $\ldots$ $A_{2, W_1}$
$\vdots$
$A_{H_1, 1}$ $A_{H_1, 2}$ $\ldots$ $A_{H_1, W_1}$
$H_2$ $W_2$
$B_{1, 1}$ $B_{1, 2}$ $\ldots$ $B_{1, W_2}$
$B_{2, 1}$ $B_{2, 2}$ $\ldots$ $B_{2, W_2}$
$\vdots$
$B_{H_2, 1}$ $B_{H_2, 2}$ $\ldots$ $B_{H_2, W_2}$

出力

行列 $A$ を行列 $B$ に一致させることができる場合は Yes を、
一致させることができない場合は No を出力せよ。
ジャッジは英小文字と英大文字を厳密に区別することに注意せよ。

入出力例

入力例 1

4 5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
2 3
6 8 9
16 18 19

出力例 1

Yes

入力例 2

3 3
1 1 1
1 1 1
1 1 1
1 1
2

出力例 2

No

参加中に考えたこと

$H_1, W_1 < 10$ と数が小さいから総当たり的な方法が取れるのかと思ったが、削除するパターンは最大で縦横それぞれ $(10-1)=9$ 本ずつあるので $(18)! \simeq 6.4 \times 10^{15}$ もあるのでTLEしてしまう。
入力例2を見るとAの要素の重複があるので、それを踏まえて正しく判定する方法が閃かない。。
通したいテストケースとしては以下を用意した。

ケース1

[A]
2 1 4 6 8
2 2 1 4 8
1 3 5 9 1
3 3 5 5 9

[B]
2 4 8
3 5 9

ケース2

[A]
2 1 4 6 8
2 2 1 4 8
3 5 9 1 1
1 3 5 9 1

[B]
2 4 8
3 5 9

ケース1は Yes を、ケース2は No を返すようにしたい。
ケース2は $A$ には $B$ の要素は全て含まれているものの、列がずれているのでBは作れない。

ここまで整理してから解放を探る。30分ほど経ってようやく1つの方法を見つけた。
それが $H_1$ から $H_2$ 箇所、$W_1$ から $W_2$ 箇所を選んだものが $B$ と一致するかどうかを判定するという方法。
削除する順番は問わないので、最終的に残った行列の組み合わせであれば計算量は $(_{10}C_5)^2 = 252^2 = 63504$ で全然足りる。
※ $max(_{10}C_i) \enspace (0 \le i \le n)$ を満たす $i$ は $5$ なので計算に $_{10}C_5$ を使った。
組み合わせとなると next_permutation を使う。縦と横と2軸あるので、組み合わせを二重にする。
組み合わせでループさせる配列には縦のほうであれば $0$ を $H_2$ 個と、$1$ を $H_1-H_2$ 個数並べたものに、横のほうも同様のものを作って、next_permutation のループの中で値が $1$ である行・列を選んで $H_2 \times W_2$ の二次元配列を作り、それが $B$ と一致するかを調べる。
この方法でACできた。

考察・感想

解説見たら「この問題はbit全探索で解く」って出てきて全探索でいけるのかとの後から気付いた。
最終的な行列の組み合わせに視点を当てれば、$2^{20} = 1048576 \simeq 10^6$ で全探索でも間に合うね。

D - "redocta".swap(i,i+1)

https://atcoder.jp/contests/abc264/tasks/abc264_d

Difficulty: 414

問題文

atcoder の並べ替えである文字列 $S$ が与えられます。
この文字列 $S$ に対して以下の操作を $0$ 回以上行います。

• $S$ 中の隣接する $2$ 文字を選び、入れ替える。

$S$ を atcoder にするために必要な最小の操作回数を求めてください。

制約

• $S$ は atcoder の並べ替えである文字列

入力

入力は以下の形式で標準入力から与えられる。

$S$

出力

答えを整数として出力せよ。

入出力例

入力例 1

catredo

出力例 1

8

入力例 2

atcoder

出力例 2

0

入力例 3

redocta

出力例 3

21

参加中に考えたこと

並び替えをしやすくするために、最初に文字を数値に置き換えることにした。
atcoderの順で 1,2,3,4,5,6,7 の値に変換する。

隣接する2文字ということはやることはバブルソートと同じで、ソート中に値を入れ替える回数をカウントすれば答えになると考えた。
10分ほどでAC。C問題と比べると随分楽に解けた。

考察・感想

解説を見て想定の解法とは異なるのかと一瞬思ったが、転倒数というものがバブルソートの交換回数と一致するというのが調べると出てきたので解き方としては間違っているわけではなさそう。
転倒数は数が多い時には有用らしいが、今回は文字列が7文字しかないのでバブルソートを行う方法で十分。

E - Blackout 2

https://atcoder.jp/contests/abc264/tasks/abc264_e

Difficulty: 1229

問題文

ある国には $N$ 個の都市と $M$ 個の発電所があります。これらを総称して地点と呼びます。
地点には $1,2,\dots,N+M$ の番号がつけられており、そのうち都市は地点 $1,2,\dots,N$ で発電所は地点 $N+1,N+2,\dots,N+M$ です。

この国には電線が $E$ 本あり、電線 $i$ ( $1 \le i \le E$ ) は地点 $U_i$ と地点 $V_i$ を双方向に結びます。
また、ある都市に 電気が通っている とは、ある都市から電線をいくつか辿って少なくともひとつの発電所に辿り着くことができる状態を言います。

今、 $Q$ 個のイベントが起こります。そのうち $i$ ( $1 \le i \le Q$ ) 番目のイベントでは電線 $X_i$ が切れ、その電線を辿ることができなくなります。一度切れた電線は、その後のイベントにおいても切れたままです。

全てのイベントについて、そのイベントが終わった直後に電気が通っている都市の数を求めてください。

制約

• 入力は全て整数
• $1 \le N,M$
• $N+M \le 2 \times 10^5$
• $1 \le Q \le E \le 5 \times 10^5$
• $1 \le U_i < V_i \le N+M$
• $i \neq j$ ならば、 $U_i \neq U_j$ または $V_i \neq V_j$
• $1 \le X_i \le E$
• $X_i$ は相異なる

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $E$
$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_E$ $V_E$
$Q$
$X_1$
$X_2$
$\vdots$
$X_Q$

出力

$Q$ 行出力せよ。
そのうち $i$ ( $1 \le i \le Q$ ) 行目には $i$ 番目のイベントが終わった直後に電気が通っている都市の数を出力せよ。

入出力例

入力例 1

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

出力例 1

4
4
2
2
2
1

参加中に考えたこと

時間が全然残ってないので方針を考えるだけ考えてみる。
断線していく状況をシミュレーションするよりも、最後の状態から逆順に線をつないでいくほうが楽そう。
あと、隣接リストや隣接行列を使っても、順番に辿っていく方法だと最悪 $O(N^2)$ くらいになる？

考察・感想

Union-Find 使えば計算量落とせるか。
まだ実践で使ったことないのでこれは後で解いて覚えよう。