A. Sublime Sequence
$2$ 個ずつで打ち消しあいます.
B. Lasers
すべての縦線・横線と $1$ 度ずつ交わる場合が最小です.
$n,m$ のみから答は決まりますが,マルチテストケースでは入力は受け取りきるようにしましょう.
C. Pacer
$0, a_1, a_2, \ldots$ それぞれの $2$ 時刻間で解きます.全部移動すると逆側になってしまう場合に $1$ 回の停止が入ります.
D. Destruction of the Dandelion Fields
奇数のものを並べて間に偶数のものを挿入すると思います.
奇数が $0$ 個ならば答は $0$.そうでなければ偶数のものは on になっているところに挿入できます.
奇数は on でとれる個数が決まるので,ソートして大きい方からとります.
E. Split
どの数の頻度も $k$ の倍数であることが必要.必要条件のもと,$[l,r]$ 内でどの数の頻度も全体の $1/k$ 倍以下であることと同値です.
尺取り法で $l$ に対する $r$ の個数を求めます.
F. Gravity Falls
計算量解析は結構面白い.
計算量を問わなければ,次を繰り返せばよいです.
– 辞書順最初の数列をとる.
– これの長さが $n$ であるとき,ANS の最初の $n$ 文字が確定.
– 数列の手前 $n$ 文字を削除.空になった数列は削除.
以下,数列の長さの総和を $N$ とします.
解法 1
長さ $x,y$ の列の辞書比較が $O(\min(x,y))$ 時間で行えることから,min_element の取得が $O(N)$ 時間で行えます.比較 $1$ 回ごとに「min でないことが確定する列」があって,その列の長さをコストと思えばよいです.
列の長さの種類数は $O(\sqrt{N})$ 通りなので,(削除関係で下手をしなければ)全体で $O(N\sqrt{N})$ 時間になります.
長さ $k,k-1,\ldots,2,1$ の列を適当に作れば最悪ケースも作れると思います.
解法 2
長さの短い方から順にチェックする形で min_element をすることで,$O(N)$ 時間にできます(開幕で長さのソートもしますがこれも計数ソートなどの適当なソートで $O(N)$ 時間).
比較に $O(k)$ 時間かけた文字列は次のステップで先頭 $k$ 文字以上消すことになって,全体のコストを文字列長の総和で抑えられるからです.
でも実装しても高速化になりませんでした.
G. Farmer John’s Last Wish
列全体に対する答を出す方法について.全体の gcd を $g$ とします.$g<x$ となるような $x$ に対して,$x$ の倍数の個数を数えてその最大値,という要領です.
列の各 prefix の場合を考えます.$x$ の倍数の個数 $\mathrm{cnt}[x]$ を保持します.全体では約数の個数の $\max$ を $\sigma_0$ として,$O(N\sigma_0)$ 時間でこれをできます.全体 gcd が更新されたときには愚直に更新します.