ABC104参加記録 - notepad.exe

久しぶりにCで苦戦した回でした。

A - Rated for Me

どのコンテストでレーティングが変化するか求める問題

入力された文字列が条件に当てはまるかチェックする問題

S の先頭の文字は大文字の A である。

この条件は1文字目がAでない時にWAを出力するだけ

S の先頭から 3文字目と末尾から2文字目の間（両端含む）に大文字の C がちょうど1個含まれる。

この二つをやってどちらも置き換え前と文字列の長さが１文字だけ違えば途中にCが一つだけあることがわかる。

以上の A , C を除く S のすべての文字は小文字である。

上記二つの条件に当てはまっている段階で先頭にA, それ以外にCが一つだけあることがわかっているので、この二つを除いた残りが全部小文字であるかループして調べれば答えがでます。

解くべき問題を最小にする問題
全部解くとボーナス点がついて処理が増えるので、最初に全部解く点数を決めてしまいます。

全部解く問題の組み合わせは最大でも $2^{10}$ = 1024通りなので全探索しても問題なさそうです。全部解くと決めたものの得点をすべて足して点数が足りればその時も問題数を記録します。

すべて足りて点数が足りないときはすべて解くものではないものの中で点数が一番大きいものを何問か解く。何問か解いて点数が届くのであればその時の問題数を記録する。もしその点数を全部解いてしまうのであれば別の組み合わせのことを指しているのでこの時は無視します。

上記の二つの条件で記録されている問題数のうち最小のものが答えとなります。

アルゴリズム的にはbit全探索 + Greedyです。本番中はbit全探索の部分で詰まってしまったので精進不足ですね…

本番中にほとんど手を出すことができなかったので省略