4完。
各問題
A - T-shirt
単純な算数の問題で、XがA以上なら確率は1、XがAより小さくB以上なら確率はC / (B - A)
、それ以下なら確率は0です。
B - Minimize Ordering
問題文を言い換えると「Sを昇順にソートして出力しなさい」となります。文字列をソートできる言語ならそれを実行するだけです。
C - 1111gal password
DPするだけです。1-9までの初期値が1でスタートすることに注意。あと、DPのテーブルの幅は11取っておく(番兵をつくる)と、if文が不要になって楽です。
いやもうCでDP解かされるの当たり前になってきましたね...。
D - ABC Transform
t, kの位置からさかのぼっていくと、tが0になるかkが1になるかまでの回数がたかだかlogkなので、位置を保存しつつさかのぼっていって、保存した位置を使って復元していきます。
さかのぼっていった結果、tが0でないときはt%3を見ることで文字が確定できます。また、復元するときは位置の偶奇で次の文字が確定できます。
E - (∀x∀)
Dにほとんどの時間をつぎ込んでしまい、桁DP?いや違うな、と思ったところでタイムアップでした。
感想
Dの考察がなかなかうまくいかず、そこだけで76分使ってしまい残念なことに...。
かろうじて水パフォをキープできましたが...。