2023-05-28

AtCoder Beginner Contest 303 E問題 A Gift From the Stars

AtCoder ABC ABC303 E問題 475 pts

問題
提出解答
問題の概要
- 制約
解法

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

$k \geq 2$ に対して, $(k+1)$ 頂点からなるスターグラフをレベル $k$ の星という.

いくつかの星の直和からなるグラフに対して, 以下の操作を繰り返し行い, 連結になるようにした.

次数が $1$ であり, 互いに非連結であるような $2$ つの頂点を選び, その頂点間を結ぶ辺を追加する.

その後, 各頂点に対して, $1$ から $N$ までの番号をつけた.

このグラフ $T=(V,E)$ は木になり, 次のようになっていた.

$V=\{1,2, \dots, N\}$
$E=\{u_j v_j \mid j=1,2, \dots, N-1\}$

最初の状態における星の状態を求めよ.

制約

$3 \leq N \leq 2 \times 10^5$
$T$ は木

解法

$T$ は木であるので, 葉が存在する. その葉を $x$ とする. すると, $x$ に接続する唯一の頂点 $y$ は星の中心になっている. また, $y$ の次数は $2$ 以上であり, $y$ を中心とする星のレベルは $y$ の次数と一致する.

これにより, $y$ を中心とする星が確定したので, $y$ 及び, $y$ に接続する全ての頂点を削除することによって, 頂点数が小さい問題に帰着することができた.

これを繰り返して行くことにより, 全ての星の情報を求めることができた.

なお, 頂点を削除するとき, 削除する頂点に接続する星の中心ではない頂点が新たに葉になることに注意すること.

時間計算量は $O(N)$ 時間である.

※ なお, 実際の問題はレベルを昇順に並べる必要があり, ソートがボトルネックになって, $O(N \log N)$ 時間になる.

2023-05-28

AtCoder Beginner Contest 303 D問題 Shift vs. CapsLock

AtCoder ABC ABC303 D問題 400 pts

問題
提出解答
問題の概要
- 制約
解法

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

a key, Shift key, CapsLock key からなるキーボード, ランプ, 画面がある. 最初, ランプは off であり, 画面には空文字列が表示されている.

以下の $3$ 種類の操作のうち, $1$ つを選んで実行するということを $0$ 回以上何度でも行うことができる.

ミリ秒かけて, a key のみ押す. このとき, ランプの on/off によって, 次のように分岐する.
- ランプが off ならば, 画面の文字列の末尾に ${\tt a}$ が付け足される.
- ランプが on ならば, 画面の文字列の末尾に ${\tt A}$ が付け足される.
ミリ秒かけて, Shift key, a key を同時に押す. このとき, ランプの on/off によって, 次のように分岐する.
- ランプが off ならば, 画面の文字列の末尾に ${\tt A}$ が付け足される.
- ランプが on ならば, 画面の文字列の末尾に ${\tt a}$ が付け足される.
$Z$ ミリ秒かけて, CapsLock key を押す. CapsLock key のランプの off/on が切り替わる.

${\tt A}, {\tt a}$ からなる文字列 $S$ が与えられる. 画面の文字列を $S$ に一致させるのに必要な最短の時間は何ミリ秒か?

制約

$1 \leq X,Y,Z \leq 10^9$
$S$ は ${\tt a}, {\tt A}$ からなる長さ $1$ 以上 $3 \times 10^5$ 以下の文字列.

解法

まず, 次のことに注意する.

操作において, 文字列の長さは増える一方である.
CapsLock key は $2$ 回連続で押す必要がない.
$S$ の最後の文字を入力した後, CapsLock key を押す必要はない.

よって, 調べるべき入力の方法は順に

CapsLock key を $1$ 回押す. または押さない.
$S$ の $1$ 文字目をランプの状態に応じたボタンを押す.
CapsLock key を $1$ 回押す. または押さない.
$S$ の $2$ 文字目をランプの状態に応じたボタンを押す.
$\vdots$
CapsLock key を $1$ 回押す. または押さない.
$S$ の $\lvert S \rvert$ 文字目をランプの状態に応じたボタンを押す.

に限られる.

このことから, ランプの off/on を状態に持った動的計画法で考えれば良いことがわかる.

次のような動的計画法を考える. ただし, $0 \leq i \leq N, x \in \{{\rm off}, {\rm on}\}$ とする.

${\rm DP}[i,x]$ : $i$ 文字目まで入力した際, $i$ 文字目入力終了直後のランプの状態が $x$ である場合における最短時間

ベースケースは $i=0$ のときで,

${\rm DP}[0,x ]=\begin{cases} 0 & (x = {\rm off}) \\ \infty & (x = {\rm on}) \end{cases}$

である.

遷移式について, $S_i={\tt a}$ ならば, ランプの動きで場合分けすることにより,

${\rm DP}[i, {\rm off}]=\min ({\rm DP}[i-1, {\rm off}], {\rm DP}[i-1, {\rm on}]+Z)+X$
${\rm DP}[i, {\rm on}]=\min ({\rm DP}[i-1, {\rm off}]+Z, {\rm DP}[i-1, {\rm off}])+Y$

となる.

また, $S_i={\tt A}$ の場合も同様にして, ランプの動きで場合分けすることにより,

${\rm DP}[i, {\rm off}]=\min ({\rm DP}[i-1, {\rm off}], {\rm DP}[i-1, {\rm on}]+Z)+Y$
${\rm DP}[i, {\rm on}]=\min ({\rm DP}[i-1, {\rm off}]+Z, {\rm DP}[i-1, {\rm off}])+X$

となる.

そして, 最終解答は $\min ( {\rm DP}[N, {\rm off}], {\rm DP}[N, {\rm on}])$ となる.

このとき, 時間計算量は $O(N)$ 時間となる.

2023-05-27

AtCoder Beginner Contest 303 C問題 Dash

AtCoder ABC ABC303 C問題 300 pts

問題
提出解答
問題の概要
- 制約
解法

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

座標平面上の点 $(0,0)$ に高橋君がいる. 最初, 高橋君の体力は $H$ である.

また, 座標平面上には $M$ 個のアイテムがあり, $j$ 番目のアイテムは点 $(x_j, y_j)$ にある.

高橋君はこれから $N$ 回行動する. $i$ 番目の行動は次のようにして行われる.

高橋君がこの瞬間にいる座標をとする. 体力を減らして, の文字目に応じて, 以下の点に移動する.
- $S_i={\tt R}$ のとき: $(x+1, y)$ に移動する.
- $S_i={\tt L}$ のとき: $(x-1, y)$ に移動する.
- $S_i={\tt U}$ のとき: $(x, y+1)$ に移動する.
- $S_i={\tt D}$ のとき: $(x, y-1)$ に移動する.
高橋君の体力が負になったならば, 高橋君は倒れてしまい, 移動を終了する. そうでなく, 移動した先にアイテムがあり, 高橋君の体力が $K$ 未満であるならば, 移動した先にあるアイテムを消費して, 体力を $K$ にする.

高橋君は $N$ 回の行動を完遂できるか?

制約

$1 \leq N,M,H,K \leq 2 \times 10^5$ .
$S$ は ${\tt R}, {\tt L}, {\tt U}, {\tt D}$ からなる長さ $N$ の文字列.
$\lvert x_j \rvert, \lvert y_j \rvert \leq 2 \times 10^5$
$(x_1, y_1), \dots, (x_M, y_M)$ は全て異なる.

解法

問題文にあるように, 各行動をシミュレーションして, 体力を管理すれば良い. ただし, 移動先にアイテムが存在するかどうかの判定については, 集合などのデータ構造を用いて高速化する必要がある. また, 細かい点について, 以下の点に注意すること.

順番どおりにシミュレーションすること.
負, $K$ 未満の境界に注意すること.
アイテムを使った場合, その点にあるアイテムは消える.
体力が $K$ 以上である場合, アイテムを消費しないことに注意する.

2023-05-27

AtCoder Beginner Contest 303 B問題 Discord

AtCoder ABC ABC303 B問題 200 pts

問題
提出解答
問題の概要
- 制約
解法

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

$N$ 人の人が横一列に並んだ写真を $M$ 枚撮った.

$i$ 枚目の写真において, 左から $j$ 番目の人は人 $a_{i,j}$ である.

$N$ 人から異なる $2$ 人を選ぶ方法のうち, $M$ 枚の写真で $1$ 枚も隣同士になっていないような選び方は何通りか?

制約

$2 \leq N \leq 50$
$1 \leq M \leq 50$
$a_{i,1}, \dots, a_{i,N}$ は $1,2, \dots, N$ の並び替え

解法

$N \times N$ の配列を隣同士になったことがあるかどうかを記録する配列として用意し, 各写真について, 隣同士になっているペアについて配列に記録し, 最終的に記録がつかなかったペアの数を答えれば良い.

なお, $N$ 人から異なる $2$ 人を選ぶ方法について, 順番は考慮しないので, 注意する.

2023-05-27

AtCoder Beginner Contest 303 A問題 Similar String

AtCoder ABC ABC303 A問題 100 pts

問題
提出解答
問題の概要
- 制約
解法

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

$2$ つの文字 $x,y$ が以下のうちのいずれかを満たすとき, $x,y$ は似た文字であるという.

$x=y$ .
$x,y$ のうち, 一方は ${\tt 1}$ で, 他方は ${\tt l}$ .
$x,y$ のうち, 一方は ${\tt 0}$ で, 他方は ${\tt o}$ .

また, 長さが $N$ の文字列 $S,T$ に対して, 以下を満たすとき, $S,T$ は似た文字列であるという.

各 $i=1,2, \dots, N$ に対して, $S$ の $i$ 文字目と $T$ の $i$ 文字目は似た文字である.

長さ $N$ の英小文字及び数字からなる文字列 $S,T$ が与えられる. $S,T$ は似た文字列か?

制約

$1 \leq N \leq 100$
$S,T$ は長さ $N$ の英小文字及び数字からなる文字列

解法

$i=1,2, \dots, N$ それぞれに対して, $S$ の $i$ 文字目と $T$ の $i$ 文字目が似た文字であるかどうかを判定し, 全て肯定的であるかどうかで判定すれば良い.

$x,y$ が似た文字であるかどうかの判定については $x=y$ 以外には $4$ つの等式を書くことによっても可能だが, $x,y$ のうち, 一方は ${\tt 1}$ で, 他方は ${\tt l}$ という条件については例えば集合の観点で $\{x,y\}=\{{\tt 1}, {\tt l}\}$ かどうかで判定すると, 記述が短くなる.