コンテストページ
AtCoder Beginner Contest 150 - AtCoder
解法
A - 500 Yen Coins
k * 500 ≧ x かどうかで分岐です。
B - Count ABC
C++ の std::string には、substr というメンバ関数があります。これは終端を行き過ぎても短い substring を返してくれます。substr(i, 4) for all i in [0, n[ で全探索です。
C - Count Order
C++ には std::next_permutation という便利な関数があります。これですべての列を作って、a, b と一致するかどうかを毎回チェックです。
D - Semi Common Multiple
A の各項を 2 で割っておくと、条件は「A の各項の奇数倍」になります。すると A の中に 2 で割れる回数の異なるものがあるとダメであることがわかります。OK ならば A の LCM を求めましょう。するとこたえは floor( ( M + LCM ) / ( 2 * LCM ) ) です。
E - Change a Little Bit
0 点ですから、S = T の場合も入れてしまいましょう。そして各箇所について、それが変わる場合の変わる重みの期待値を計算です。大きい方から 0 始まりで k 番目ならば、重みは 1 + k / 2 です。これらを係数 C_i と畳み込んで足し合わせて、最後に 2^{2*n-1} で割っておきましょう。
F - Xor Shift
a, b それぞれの周回隣接 xor を A, B と書きましょう。すると (K, X) が答えである条件は、A の K 回周回右シフトが B に一致し、かつ X = a[k] xor b[0] であることです。
K を決めると X は決まりますがから、K を求めましょう。周回シフトは難しいですから、B を 2 つ並べておいて、部分列で A に一致するものを全列挙しましょう。あなたの文字列検索は、なにから？ 私は、Z - algorithm から！（訳：KMP を召喚したら std::string にしか対応していませんでした（泣））（ところで K = N がヒットするので、注意です。）
結果
38 位、2400（天井）橙パフォです。
D で嵌ってしまったのもあり、どちらかというと失敗した回という認識だったのですが、蓋を開けてみたらよさめで驚きました。やはり文字列アルゴルズムが要求されたのが大きかったでしょうか。（そもそも想定解なのかも怪しいですが……）
