AtCoder Beginner Contest 124
Updated:
Source codes
Solutions
A - Buttons
答えは以下で与えられる。
\[ \max(A + (A - 1), B + (B - 1), A + B). \]
B - Great Ocean View
指示通りやれば $O(N^2)$ の解法になるが、ここでは $O(N)$ の解法を述べる。
$0$-indexed とする。 $0 \leq i \leq N - 1$ に対し、 $H _ 0 \leq H _ i$ かつ $H _ 1 \leq H _ i$ かつ … かつ $H _ {i - 1} \leq H _ i$ とは、 $\max _ {j < i} H _ j \leq H _ i$ と同値である。そこで $M = \max _ {j < i} H _ j$ を動的に管理していけば十分である。
$M = 0$, $ans = 0$ とする。 $i = 0, \dots, N - 1$ に対し以下を実行する。
- $M \leq H _ i$ ならば、 $ans \mathbin{ {+} {+} }$ とする。
- $M \gets \max(M, H _ i)$ とする。
ポイント
本番では $O(N^2)$ 解法を使った。
C - Coloring Colorfully
最終結果は "010101..." か "101010..." しかない。最終結果と $S$ のそれぞれの距離を求め、大きくないほうが答え。
D - Handstand
解答
$1, 0$ 列を Run Length 圧縮する。答えは $1$ から始まった区間から $2K + 1$ 個の区間の長さの和の最大値が答えである。これは累積和を使うことで $O(N)$ で求まる。
実装について
解説放送での chokudai さんの実装が非常に参考になったのでここにエッセンスを書いておこう。
Run Length 圧縮のところ
今回は $1, 0$ 列を圧縮するだけなので同じ動的配列に入れて良い。最初と最後が $1$ になるように番兵を用意しておく。
int now = 1;
int cnt = 0;
for (auto i = 0; i < N; i++)
{
if (S[i] == ('0' + now))
{
cnt++;
}
else
{
V.push_back(cnt);
cnt = 1;
now = 1 - now;
}
}
if (cnt > 0)
{
V.push_back(cnt);
}
if (V.size() % 2 == 0)
{
V.push_back(0);
}
累積和について
愚直にやれば十分であるが、 int goal = min(i + 2 * K + 1, (int)W.size() - 1); が重要である。これがないと $K$ が大きすぎる時に答えが出なくなる。
W = vector<int>(V.size() + 1, 0);
for (auto i = 0; i < (int)V.size(); i++)
{
W[i + 1] = W[i] + V[i];
}
int ans = 0;
for (auto i = 0; i < (int)W.size(); i += 2)
{
int start = i;
int goal = min(i + 2 * K + 1, (int)W.size() - 1);
ans = max(ans, W[goal] - W[start]);
}
cout << ans << endl;
ポイント
chokudai さんくらいのスーパープログラマーだと $O(N^2)$ の解答を書いても TLE しないらしい。ワロタ。