Codeforces Round 1050

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 が更新されたときには愚直に更新します.

CodeForces
スポンサーリンク
シェアする
maspyをフォローする
maspyのHP
タイトルとURLをコピーしました