AtCoder Beginner Contest 009
Updated:
Source codes
Solutions
A - 引越し作業
$(N + 1)/2$ を出力する。ただし割り算は計算機の割り算。
B - 心配性な富豪、ファミリーレストランに行く。
Ruby では全て hash に適当な value で突っ込んで hash.keys.sort[-2] を出力するとよろしい。
C - 辞書式順序ふたたび
以下の図は解説スライド の p.35 から引用した。
これに従って考えればよろしい。
使える文字の判定
これは最初に int cnt[26]; に数字を持っておき、前から見ていって $0$ でないものを見つけたら試し、うまくいったら $1$ 減らす。
check の実装
$T$ に文字 $c$ を付け加えたものを $U$ とし、 $cnt’ \gets cnt$ とし、 $cnt’[c] -= 1$ しておく。この時 $(U, cnt’)$ によって作られる文字列のうち最も小さいスコア $score$ を求める。 $S$ と $U$ は素直に比べて差が出たら $score += 1$ とする。さらにそれ以降の文字列についてはできるだけ合わせるしかないので $cnt’[S[i]] > 0$ ならばこれを $1$ 減らす、そうでないなら $score$ を $1$ 足す。これで $score \leq K$ ならば可能、そうでないならば不可能とわかる。
ポイント
辞書順最小は、貪欲法と相性が良い。ここまではすぐわかる。
貪欲法は 「全探索」 と 「可能判定」 でできている。スライドのような方法で貪欲に試していき、可能なら決定するというプロセスをとる。私の場合はスライドのような全体像が思い浮かばなかったため、うまくいかなかった。 答えそのものを貪欲に全探索する のがポイントである。