Codeforces Round #696 (Div. 2)

A

桁数を大きく→左の桁から数を大きく

の順に貪欲にやる、いつもの

 

B

p,qを素数として、p^3かpqの形しかない

p<qとする、条件よりd+1 \leqq p, p+d \leqq  q

これを満たすp,qを貪欲に取ってpqを計算する

 

p^3は調べなくてもよい

ベルトラン=チェビシェフの定理より、 \forall n \exists p:n\lt p\leqq 2n

 

C

二乗オーダーでよいことに注意して考える

xは単調減少→最初にmaxを選ばないとmaxが消せなくなって詰む

最初にmaxとpairにして消すものを全探索、最初に消すものを決めれば以降の操作は定まる

multisetのcountは、同じ要素がたくさん入っている場合に計算量が要素数の分だけかかる

→se.find(x)!=se.end()

 

D

swap操作がない場合、一番左/右から順番に操作をしていけばよい(左から操作を漸次決定できる)

一度だけswapできる→swap位置の全探索を考える

左端、右端から操作をしていった場合の途中結果を保持しておけばよい

添え字回りで時間を溶かしていた、バグったらちゃんと図を描く

 

E

2 3 4 5 ... n 1が最適では?(一敗)

最初の状態から考えるのは大変

操作は逆順に考えてもよいので、完全順列からスタートして、 a_i =i を満たすiが存在しなくなるまで操作を繰り返すことを考える

一回の操作で a_i =i の数が少なくとも一つ増えること、最初の操作では2つ増えることから、操作回数は高々n-1回

 

一度 a_i =iでなくなったiが a_i =iに戻ることはない

 a_i =iであるiを一つずつ両端の遠い方とswapすることを考えると、

(n-1)+ (n-2)^2 + (n-3)^2 + ...が達成可能で、これが最大

 

最大ケースの構築にかなり手間取ってしまった

操作を言い換えるとき、同値性に注意