AtCoder Beginner Contest 043 - プログラミング備忘録

成績

700点、77分29秒＝125位

B問題で思わぬ落とし穴にハマって2回ペナルティ食らったのがよくなかったが、D問題の部分点解法まで解けたのでわりと満足。翌日は朝早くから予定があったので解答時間途中で終了。

解法メモ

A問題

与えられた $N$ に対して、必要なキャンディーの個数は $\sum_{n=1}^N n = N(N+1)/2$ である。

B問題

入力文字列 $s$ に対して、エディタ上の文字列 $K$ *1を用意する。
$|s|\leq 10$ だから、 $|K|\leq 10$ とわかる。ヌル文字を含めて11文字確保されていれば十分。
$s$ の文字を先頭から順に見ていき、

次の文字が0のときは、 $K$ の末尾に0をつける。
次の文字が1のときは、 $K$ の末尾に1をつける。
次の文字がBのときは、 $K$ が空なら何もしない。 $K$ が空でない時は、末尾から1文字消す。

最初に $K$ をヌル文字で埋めておき、 $K$ の現在の文字位置を示す変数 $j$ を用意すればよい。 $K$ の先頭がヌル文字ならば $K$ は空だから何もしない。そうでない時は $K$ の $j$ 文字目をヌル文字に置き換えて、 $j$ をデクリメントする。

C問題

$N$ 個の整数すべてを最小コストで書き換えられる整数を $K$ とおく。コストの総和は
$(a_1-K)^2+(a_2-K)^2+\cdots+(a_N-K)^2 \\ = NK^2-2(a_1+a_2+\cdots+a_N)K+a_1^2+a_2^2+\cdots+a_N^2 \\ = N(K-(a_1+a_2+\cdots+a_N)/N)^2-(a_1+a_2+\cdots+a_N)^2/N+a_1^2+a_2^2+\cdots+a_N^2$
だから、 $K=(a_1+a_2+\cdots+a_N)/N$ とわかる。

実際には、 $(a_1+a_2+\cdots+a_N)/N$ は整数とは限らないので、一旦 $K$ をdouble型で計算し、nearbyint関数などで最近接整数 $[K]$ をとるとよい。
そのときのコストは $-(a_1+a_2+\cdots+a_N)^2+a_1^2+a_2^2+\cdots+a_N^2$ をバカ正直に展開するよりは最初から $(a_1-[K])^2+(a_2-[K])^2+\cdots+(a_N-[K])^2$ を計算するほうが早い。

$N$ 個の整数の範囲が $-100\leq a_i \leq 100$ だから全探索でもすぐに終わるが、こういう問題を数学的に解けるようになっておいたほうがあとで生きてくることがあると思う。

D問題

部分点解法

$1\leq a < b \leq |t|$ なる $a,b$ に対して、 $a$ 文字目から $b$ 文字目までの間に各アルファベットが何回出てくるか毎回数え、どれかひとつでも過半数になった瞬間に探索を打ち切って答え（ $a b$ ）を表示する。 $2\leq |s|\leq 100$ を満たすデータセットに対しては時間内に答えが出せる。

満点解法

$t$ がアンバランスな文字列であるのは、 $t$ の部分列として $XX$ または $XYX$ の形（ $X,Y$ は異なる任意のアルファベット）が存在する場合に限る*2。
各アルファベット $X$ に対して、 $t$ 内で、ある場所の1文字先または2文字先が $X$ になっているところを探索する。あればそこで探索を打ち切って $a b$ を表示、なければ $-1 -1$ を表示。

*1:何を思ったのかキーボードのKにしていた。

*2:証明は文字数に対する帰納法を用いるのが簡単？