AtCoder Beginner Contest 178の感想

具合が悪いのでさらっと書きます

100-200-0-400-0(3)-0でノーペナ3完700点。

A - Not

1なら0を、0なら1を出力する。if文で実装できるし、排他的論理和でエレガントに書くこともできる。 $O(1)$

B - Product Max

全通り試すと間に合わない。（B問題にしては厳しいね？）
負の数×負の数＝正の数　だったりするので場合分けをしようか迷うが、よく考えると範囲の最大値・最小値の組み合わせをすべて試せばそのどれかが最大値となる。
$\max (ac, ad, bc, bd)$ が答え。 $O(1)$

C - Ubiquity

考えられる数列の総数は $10^N$ 通り。0を使わない数列は $(10-1)^N$ 通り。9を使わない数列は $(10-1)^N$ 通り。0も9も使わない数列は $(10-2)^N$ 通り。
実はこれらの数値が求められれば、あとは包除原理で導出できる。 $10^N-2\times 9^N+8^N$ が答え。 $O(N)$

dpで解いた。
dp[i][j] := 数列の長さがiで、その総和がj
とする。遷移を簡単にするために、数列に0以上の整数、つまり3未満の数も含んでいいことにする代わり、答えを求めるときは数列の全要素に3を足したものとしてみる。
遷移は、dp[i+1][j] = dp[i][j] + dp[i][j-1] + ... + dp[i][0]となる。実装時は累積和を使って右辺を $O(1)$ で求める。
dp[i][S - 3 * i]の総和が答え。 $O(S^2)$