AtCoder Beginner Contest 104

更新日時:

AtCoder Beginner Contest 104

結構難しかった。

ソースコード

解法のメモ

A - Rated for Me

if 文で比較するだけ。

B - AcCepted

これも指示通りやるだけである。 Ruby だと以下の通り。

  • 先頭の文字の条件は S[0] == 'A' である。
  • 次の条件は S[2...-2].count('C') == 1 である。
  • 最後の条件は T = S.downcase として ST を地道に比較するとよろしい。

ポイント

この問題はセンスなさすぎだと思う。ただ面倒なだけ。 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 の好きなものを入れて良い」を理解していなかった。 真ん中から決める を意識しだしてからは正しい実装ができた。

「真ん中から決める」の類題

解説放送での模範解答

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 または ? であるならば、

  1. $k = 0, \dots, 3$ に対し、 $DP[i][k] += DP[i - 1][k]$ 。これは「文字を選ばない」に対応する。
  2. $DP[i][1] += DP[i-1][0]$ 。これは「A という文字を選ぶ」に対応する。

同様に $S[i]$ が B または ? であるならば、 1. を行い、 2. は類比的に行う。 $S[i]$ が C または ? も同様である。

雑感

部分列は「 $i$ 文字目まで見て $k$ 番目まで選び終わった状態」を DP するというのがポイントかもしれない。当然のことながら模範解答の方が汎用性が高い。この方法なら “ABCDEFG” のようになっても全く問題なくクリアできる。

その他

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 が普通に難しかった。気づけばできるのだが。

最近、暑さのせいで覚醒が早く、睡眠不足になっている。昨日のコンテストも、今日のコンテストも、もっと成績はよかったのではないかと思う。結構疲れた。

コメントする