ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ABC104

unratedでよかった… 人生初のABCunratedでした。爆死しました

A - Rated for Me

提出コード
最初の問題からなんかとっつきにくいなぁって思いました。
少し思考が停止しましたがきちんと3つの場合分けをしてなんとかACでした。
以下と未満に惑わされないようにしましょう。

B - AcCepted

提出コード
こちらもかなり条件が複雑で、焦りました(普通に1WAしました)
すべての条件を満たすように一つ一つ試していく以外とくになさそうです…

C - All Green

提出コード(時間外)
C問題は終わってから見ました。せっかくのunratedだったのでDから解いてやろう!って思っていたら、結局解き終わらなかったので…
Dの解説放送待っていたらCの解説をチラ見してしまいましたが、与えられた条件が少ないことから全探索をする発想が必要みたいです。
ある得点の問題の集合について、全部解く、少し解く、解かないの3つに分けると、少し解くパターンは多くても1種類しか存在しないので、全て解くor全く解かないの2通りを全探索し、最後に少しだけ解くパターンを考えた上で最小値を更新していけばいいみたいです。
実装自体はそこまで…?全探索を思いつくかどうかな気がします(この問題に手をつけても解けるか怪しいです)

D - We Love ABC

提出コード(時間外)
こちらは方針がうかんでいたのですが、結局オーバーフローがとれなかったので最後まで解けませんでした。最終的にはint型の変数が2つ残っていたせいでした。これに1時間以上悩まされていたわけですね(コンテスト終了後も含めるともっとですが)
方針としては、Bを固定したときに、AとCの決め方は累積和によって簡単に計算することができます。また、AとCは、AC、A?、?C、??による4種類の選び方があるので、A、C、?の3種類の累積和をとってあげる必要があります。加えて、固定するBも、Bではなく?を代用できるので、全部で8通りの計算になります。
加えて、選んだABCの文字以外は、任意の文字でいいので、?はそれぞれ3通りになります。
?の選び方は全体で
3^{Q}
通りですが、今回ABCを選ぶ部分で?を使う場合もあるので、B(もしくは代用の?)を固定したときの場合の数は、その時代用として?を使った個数をxとして、
AおよびC(もしくは代用の?)の選び方×3^{Q-x}
となります。あとはこれをループで探索し、すべてのBおよび代用の?に対して計算してあげて、和をとれば答えが求まります。


今回の問題はかなり難しかった上、C問題にいたってはすごくもったいない消費の仕方(先に解説の一番重要な部分をチラ見してしまった)をしてしまったので、素直に次回は前から順番に解いていこうと思います…