Codeforces 107

問題が途中で別物になろうが何しようが、解ける人間がいる以上、解けない方が悪いのは事実。

A

ある整数から開始して、1または自分以外の約数を取り出すという処理を交互に行うことを考える。先にその処理ができなくなるのはどちらか、答えよ、という問題。

要は約数の数が2個以下になったらダメなので、素因数分解して約数を数え、約数が2個以下になるように調整してやれば良いので、最初に変なものがこなければ先手必勝。

B

N文字からなる文字列で、どのK文字の部分文字列を取っても回文であるものはいくつあるか答えよ、という問題。

ある文字と別の文字が同じかどうかでグループ分けして、グループの数だけ文字を任意に割り当てれば良いだけの問題。やるだけ...。

C

キセル乗車の支援をせよ、という問題。稼ぎは半分もらえるが、ペナルティは全部こちら持ちなので、最適キセルをたくさんのクエリに対して答える。

この手のクエリ系の問題は、どのクエリにも即座に答えられるような適切なデータ構造を用意すれば良いので、やるだけ。問題が途中で変わったのが悩ましいが、最初からこの問題であるという可能性に気付くことができない時点でダメだった。

D

見てない。

E

見てない。