AtCoder Beginner Contest 104
Updated:
結構難しかった。
Source codes
Solutions
A - Rated for Me
if 文で比較するだけ。
B - AcCepted
これも指示通りやるだけである。 Ruby だと以下の通り。
- 先頭の文字の条件は
S[0] == 'A'である。 - 次の条件は
S[2...-2].count('C') == 1である。 - 最後の条件は
T = S.downcaseとしてSとTを地道に比較するとよろしい。
ポイント
この問題はセンスなさすぎだと思う。ただ面倒なだけ。 downcase を知らずぐぐっていた。
C - All Green
点数は $100$ で割っておく。コンプリートボーナスがあるので、点数の大きい順にとくのが最適であるとは限らない。
最適な方法は「 $1$ から $D$ 点の問題のいくつかを全完」＋「全完しなかった点数のうち最大の点数を何問か解く( $0$ 問かもしれない)」という形をしている。そこで $D \leq 10$ であるから、前者の $2^{D}$ 通りを全部調べる。その時点で要求スコアに届いた場合は記録して continue する。そうでなければ後者をやってみて、できた時点で記録して continue する。後者をやっても要求スコアに届かなかった場合は記録せず continue する。
ポイント
最初のサンプルを読めば勘違いしなくてよかった。
D - We Love ABC
コンテスト中に思いついた解法
方針が最大のポイントである。 int N = S.size(); とする。部分列であって ABC, ?BC, AB?, ?B?, A?C, A??, ??C, ??? であるものを数え上げればよいのだが、気をつけなければならないのは、今取り出してこなかった 他の部分 の ? には A B C の好きなものを入れて良いということである。ゆえにこれらは全て分けて考える必要がある。
こういうときは 真ん中から決めると数えやすい。 $i = 1, \dots, N - 1$ に対し、 S[i] == 'B' ならば、ABC, ?BC, AB?, ?B? をそれぞれ数え上げて足す。
- 例えば
ABCならば「$i - 1$ 文字目までに登場したAの数」$\times$「$i + 1$ 文字目以降に登場するCの数」 $\times 3^{Q}$ である。ここで $Q$ は?の数の合計。 - 例えば
AB?ならば「$i - 1$ 文字目までに登場したAの数」$\times$「$i + 1$ 文字目以降に登場する?の数」 $\times 3^{Q-1}$ である。
以下同様。「」でくくった部分は imos 法で前処理しておけば $O(1)$ で求まる。 S[i] == '?' の場合も類比的である。
実装上の注意
場合分けを避けるために、 power(ll x, ll n) の実装では $n < 0$ の時は $0$ を返すようにしておくと安全である。計算量は $O(N)$ である。
ポイント
これは方針が曖昧なまま実装し、「今取り出してこなかった 他の部分 の ? には A B C の好きなものを入れて良い」を理解していなかった。 真ん中から決める を意識しだしてからは正しい実装ができた。
「真ん中から決める」の類題
- AtCoder Regular Contest 100 D - Equal Cut $P, Q, R, S$ に分けるのだが、 $(P, Q)$ と $(R, S)$ の境目を決めてから、その後の境目を imos 法 or 二分探索で高速に求める。
解説放送での模範解答
DP をする。 $0 \leq k \leq 3$ とする。文字を前から見ていき、 “ABC” を順に選ぶことにする。状態 $k$ を、 “ABC” の $k$ 文字目まで選び終わった状態と定める。文字列は $1$-indexed とする。
$DP[i][k] = i$ 文字目まで見たときに状態 $k$ であるような場合の数
と定める。
- 初期状態： $DP[0][0] = 1$ 、他は $0$ 。
- 答え： $DP[N][3]$ 。
遷移は以下の通りである。 $i = 1, \dots, N$ に対し、以下のことを行う： $S[i]$ が A または ? であるならば、
- $k = 0, \dots, 3$ に対し、 $DP[i][k] += DP[i - 1][k]$ 。これは「文字を選ばない」に対応する。
- $DP[i][1] += DP[i-1][0]$ 。これは「
Aという文字を選ぶ」に対応する。
同様に $S[i]$ が B または ? であるならば、 1. を行い、 2. は類比的に行う。 $S[i]$ が C または ? も同様である。
雑感
部分列は「 $i$ 文字目まで見て $k$ 番目まで選び終わった状態」を DP するというのがポイントかもしれない。当然のことながら模範解答の方が汎用性が高い。この方法なら “ABCDEFG” のようになっても全く問題なくクリアできる。
Others
A - sample: 3, tle: 2.000, time: 01:21, from_submit: 64:21
B - sample: 5, tle: 2.000, time: 05:04, from_submit: 59:17
C - sample: 4, tle: 2.000, time: 23:45, from_submit: 35:31
D - sample: 3, tle: 2.000, time: 35:32, from_submit: 00:00
C, D が普通に難しかった。気づけばできるのだが。
最近、暑さのせいで覚醒が早く、睡眠不足になっている。昨日のコンテストも、今日のコンテストも、もっと成績はよかったのではないかと思う。結構疲れた。