ABC104 参加記録

AtCoder Beginner Contest 104 - AtCoder

全完43分台で46位。今回は手こずる問題が多かったです…

f:id:betrue12:20180805214841p:plain

A - Rated for Me

不等号で比較してifで分岐すればOK。

Submission #2950051 - AtCoder Beginner Contest 104

入力上限の4208、コンテスト当日時点でのtouristのhighestレートですね…

B - AcCepted

処理するだけといえば処理するだけなのですが、地味に実装が面倒です。私のコードの方針としては、

先頭が A であるかチェック
3文字目～末尾から2文字目の間に C がちょうど1つあるかチェック
上記2文字を取り除いてしまう
残りの文字が全部小文字であるかチェック

です。提出する際はヒヤヒヤしましたね…

Submission #2952457 - AtCoder Beginner Contest 104

C - All Green

ボーナス点の扱いが面倒なので、ボーナス点を固定してしまいたいですね。ボーナス点は「その点数の問題を全部解くかどうか」を決めれば固定できます。

幸い、点数の種類数が $D \le 10$ と非常に小さいので、それぞれの点数種類を全部解くかどうか、 $2^{D}$ の全探索を試みることができます。

「全部解く点数種類」を固定すれば、それらの問題の素点とボーナス点、そして問題数がまず計算できます。そこからは、合計点数が目標に足りるまで、点数の大きい順に解く問題を追加していけばよいです*1。 $2^{D}$ 全探索して、最も問題数が少なかったものが答えです。

Submission #2954029 - AtCoder Beginner Contest 104

D - We Love ABC

この問題はけっこう難しいです。 ? が出現するたびに増えていく文字列のパターンを、まとめて考える必要があるからです。

考え方としてはDPです。文字列を前から見ていって、

その時点までの A の個数
その時点までの AB のパターン総数（離れていても良い）
その時点までの ABC のパターン総数（離れていても良い）

を計算していきます。

まずは ? がややこしいので、? がないパターン、すなわち文字列1通りで考えます。そのとき、「文字列を1文字足す」ことによって、以下の効果が得られます。

f:id:betrue12:20180806000350p:plain

以前に出現した A それぞれに対して、 B がくっつくと AB ができます。
また、以前に出現した AB のパターンそれぞれに対して、 C がくっつくと ABC ができます。
また、 A がくっつくと、もちろん A が増えます。

このような遷移で、文字列が1通りの場合は計算していけます。

問題は ? があるときです。 ? が登場するたび、文字列の総数は一気に今までの3倍になります。これを個別で数えるのは不可能なので、全部まとめて数え上げるという方法を取ります。すなわち ? が存在する場合は、先ほどの数え上げるものリストを少し発展させて

その時点までの A の個数を、全文字列について合計したもの
その時点までの AB のパターン総数を、全文字列について合計したもの
その時点までの ABC のパターン総数を、全文字列について合計したもの
文字列の総数（←NEW！）

を計算します。

とはいえ、複数文字列を考慮した際の遷移は、先ほどのものとあまり変わりはありません。

f:id:betrue12:20180806000453p:plain

ちょっと大変ですが、1手前の文字列が3パターンある場合（AA? に対応します）の場合を列挙してみました。前から順番にDPを進めていくと、1手前に含まれる文字列の集合について、さきほどの4つの値が求まっているはずです。その後に A, B, C それぞれがくっついたときの遷移は、図に示した通りとなります。最後まで探索し終わったときの ABC のパターン総数が答えです。

くっつく文字列が ? の場合は、 A, B, C 全パターンの計算結果を全部足し合わせます。このとき、文字列の総数も3倍になることに注意しましょう。

考察が正しいのか結構不安になりますが、最後のサンプルが通ればほぼWAはないと思うので、サンプルを全部合わせることを目指して実装しましょう。

Submission #2955903 - AtCoder Beginner Contest 104