AtCoder Beginner Contest 242に参加しました。
結果
A,B,Cの3問ACでパフォーマンスが735でした。 D問題が難しかった… 解説を読んでみると解法が1クエリあたりO()な気がしたけどだからテストケースによってはTLEしそうだなあと思った。
A - T-shirt
問題文の通りに場合分けして確率を計算すれば良い。1~A位までは1.0でB+1位~は0.0。
A+1位~B位までは確率がC/(B-A)になる。
確率を求めよって言われるとちょっと苦手意識があって避けたくなる…
B - Minimize Ordering
これも問題文の通りに処理する。大体の言語にソート関数があるから、受け取った文字列Sをソートしてその結果を出力すればいい。
ソート関数の存在と使い方がわかっていれば即答できる問題。簡単すぎてちょっと困惑した、何か間違ってないのかなと。
C - 1111gal password
動的計画法で解いた。C問題は全探索すれば解ける問題が多いからC問題でDPが出てくるのはちょっと難しめな気がする。
i桁目を確定させるとi+1桁目の整数は3通り(、、)に派生するので、が0とか10になっていないかを確認しつつi桁目の時点での条件を満たすパターン数をi+1桁目に伝搬させていった。
D - ABC Transform
難しかった。手計算してみていると
- がに遷移すると文字数は2倍になる。
- 0文字目の遷移には周期があるA→B→C→A→・・・
くらいは気がついた。
後は制約を確認するとだったので各クエリはO(1)かO(logN)くらいで答えられないとTLEしそうだと思った。他にはなのでO()な解き方をすると最悪回の処理が必要になるのでそのクエリ単体でTLEになりそうだと思った。
とりあえず2分木の親をたどる要領でkをt回2で割って答えたい文字はもともとどの文字が遷移したものか求めた。次に、t回遷移すると1文字が文字に膨れるので、kをで割った余りを求めて最初に求めたもともとの文字がt回遷移した後の文字列の何文字目を答えればよいか求めた。最後に、最初に特定した文字をt回遷移させて出来た文字列の適切な文字数目を出力させた。
最初に考察したとおりこの解法だとなのでTLEしてダメだった。
コンテストが終わって解説を軽く読んでみたけど、解法が再帰で解くアルゴリズムで計算量がくらいありそうな気がした。 後でちゃんと読み直してみるけど。