gyouzasushi’s diary

競プロとか

AtCoder Beginner Contest 167 に参加しました

成績

f:id:gyouzasushi:20200510232837p:plain

1級！

A - Registration

ちょっと難しめ？ T.substr(0, |S|) == S かどうか。

B - Easy Linear Programming

書かれてる数が大きい方から $K$ 枚使う。

C - Skill Up

$N$ がめっちゃ小さいので、 $N$ 冊の本を買う / 買わないの $2^N$ 通りを全部試せる。

D - Teleporter

競技コピーアンドペースト…

E - Colorful Blocks

これ好き。「隣り合うブロックの組であって同じ色で塗られている組」が $i$ 組になるような塗り方はこんな感じで作れる：

初めから色が塗られたブロックを用意する
$N-i$ 個のブロックを同じ色が隣合わないように並べる
（ブロックの総数が $N$ 個になるように）いくつかのブロックを合計 $i$ 回砕く

なので、各 $i \leq K$ に対して

ブロックの並べ方　 $M \times (M-1)^{N-i-1}$ 通り
砕くブロックの選び方　 ${}_{N-i} H_{i}$ 通り

をかけたものを足し上げればOK。

F - Bracket Sequencing

文字列 $T$ が括弧列であるための条件は

「' ( ' の数　＝　' ) ' の数」になること
前から見ていったときに、「' ( ' の数　<　' ) ' の数」となる瞬間がないこと

よって、各 $S_i$ について興味があるのは

' ( ' の数　-　' ) 'の数（ $cnt_i$ とする）
前から見ていったときの「' ( ' の数　-　' ) 'の数」の最小値（ $min_i$ とする）

だけ。 $\sum cnt_i \neq 0$ のときは明らかに"No"なのでそれ以外の場合を考えればいい。

直前までの「' ( ' の数　-　' ) 'の数」が $x$ のとき、次に $S_i,S_j$ の順で連結する場合と $S_j,S_i$ の順で連結する場合とを比べてみる。前者がアウトにならない条件は、 $x+min_i \geq 0$ かつ $x+cnt_i+min_j \geq 0$ 、つまり $x \geq max(-min_i,-cnt_i-min_j)$ 。同様に、後者がアウトにならない条件は $x \geq max(-min_j,-cnt_j-min_i)$ 。よって、 $max(-min_i,-cnt_i-min_j) \lt max(-min_j,-cnt_j-min_i)$ なら $S_i$ を前に、そうでなければ $S_j$ を前に持ってきた方がお得。

あとはこのルールでソートして、前から順番に確認していけばOK。

途中ガチャに走ってもうて、不要不急の5ペナ…。

反省

貪欲は証明