AtCoder Beginner Contest 099
Updated:
Source codes
Solutions
A - ABD
問題文に書かれている通りに場合わけをし、 ABC or ABD を出力する。
ポイント
leading zeros を出力するかと思って焦った。サンプルはしっかり見ないとロスする。
B - Stone Monument
$x = b - a$ とすると、右側は西から $x$ 番目の塔である。その本来の高さは $x (x + 1) / 2$ であるから、ここから $b$ を引くと所望の数字が得られる。
C - Strange Bank
動的計画法。まず 1 回の操作で引き出せる金額を set<int> S; に登録する。 $100010$ 以下であれば十分である。
$X[i] = i$ 円を引き出すために必要な最小の操作回数
と定める。 $X[0] = 0$ として、 $i = 0, \dots, N-1$ に対し以下の操作を行う。 $x \in S$ に対して $i + x \leq N$ ならば $X[i + x] \gets \min(X[i + x], X[i] + 1)$ とする。
D - Good Grid
まず TLE 解から。「良いグリッド」とは、つまるところ $3$ 色に彩色されたグリッドのことである。出来上がりのグリッドの色を $3$ で割った余りの順に $i, j, k$ でもっておき、その色に塗り替えた盤面のスコアの和を毎回計算する。これだと $O(N^2 C^3)$ で、間に合うかなと思って出したんだけど TLE であった。
この解答には同じ計算を何度もやっているところがある。 $i, j, k$ の色をそれぞれ指定した段階で、それぞれのコストが決まる。つまり、各色 $0 \leq i < C$ に対し、各座標 $(x, y)$ に対し $total[(x+y)\%3][i] += D[c[x][y]][i]$ としていけば、 $i, j, k$ で塗るコストというのは $total[0][i] + total[1][j] + total[2][k]$ で求まる。これは計算量は $O(C N^2 + C^3)$ であり、十分間に合う。
ポイント
間に合うかもと思って TLE 解を書いてしまった。それ自体は悪いことだったが、ソースコードの改変は最小限で済んだ。