ARMERIA

放置していたけど更新再開、Rubyと競技プログラミングの話が中心になっていく予定です

ABC104 参加記録

AtCoder Beginner Contest 104 - AtCoder

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

f:id:betrue12:20180805214841p:plain

A - Rated for Me

A - Rated for Me

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

Submission #2950051 - AtCoder Beginner Contest 104

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

B - AcCepted

B - AcCepted

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

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

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

Submission #2952457 - AtCoder Beginner Contest 104

C - All Green

C - All Green

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

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

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

Submission #2954029 - AtCoder Beginner Contest 104

D - We Love ABC

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

さいごに

今回は難しかったですね…

脚注

*1:問題のルール通り厳密に処理すると、後半のパートで点数の高い問題を解いたときにも、コンプリートボーナスが発生したらそのぶんの点を追加しないといけません。ただ、そのようなケースは他の全探索パターンに含まれているため、やらなくても大丈夫です。