れとろのメモ置場

とあるSEのメモ置場

AtCoder Beginner Contest 242

AtCoder Beginner Contest 242に参加しました。

結果

A,B,Cの3問ACでパフォーマンスが735でした。 D問題が難しかった… 解説を読んでみると解法が1クエリあたりO(t _ {i})な気がしたけどt_ {i} \leq 10 ^ {18}だからテストケースによっては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通り(X _ {i}-1X _ {i}X _ {i}+1)に派生するのでX _ {i}-1X _ {i}+1が0とか10になっていないかを確認しつつi桁目の時点での条件を満たすパターン数をi+1桁目に伝搬させていった。

D - ABC Transform

難しかった。手計算してみていると
- S ^ {(i)}S ^ {(i+1)}に遷移すると文字数は2倍になる。
- 0文字目の遷移には周期があるA→B→C→A→・・・
くらいは気がついた。 後は制約を確認すると1 \leq Q \leq 10 ^ {5}だったので各クエリはO(1)かO(logN)くらいで答えられないとTLEしそうだと思った。他には0 \leq t _ {i} \leq 10 ^ {18}なのでO(t _ {i})な解き方をすると最悪10 ^ {18}回の処理が必要になるのでそのクエリ単体でTLEになりそうだと思った。

とりあえず2分木の親をたどる要領でkをt回2で割って答えたい文字はもともとどの文字が遷移したものか求めた。次に、t回遷移すると1文字が2 ^ {t}文字に膨れるので、kを2 ^ {t}で割った余りを求めて最初に求めたもともとの文字がt回遷移した後の文字列の何文字目を答えればよいか求めた。最後に、最初に特定した文字をt回遷移させて出来た文字列の適切な文字数目を出力させた。
最初に考察したとおりこの解法だとO(t _ {i})なのでTLEしてダメだった。

コンテストが終わって解説を軽く読んでみたけど、解法が再帰で解くアルゴリズムで計算量がO(t _ {i})くらいありそうな気がした。 後でちゃんと読み直してみるけど。