ARC086 F : Shift and Decrement(1200)
作成日：2017.12.14
最終更新日：2017.12.14
問題概要
$N$個の非負整数$A_1 , ... , A_N$がある。
操作A「すべての整数を$2$で割って小数点以下を切り捨てたものに置き換える」、
操作B「すべての整数を$1$で引いたものに置き換える」を好きな順で合わせて$K$回まで行える。
但し、操作Bは$A_i = 0$となるようなものがある時には行えない。
操作後の整数列で異なるものは何通りあるかを$mod \: 10^9 + 7$で求めよ。
制約
$1 \leq N \leq 200$
$1 \leq A_i \leq 10^{18}$
$1 \leq K \leq 10^{18}$
考え方
2種類の操作を同時に考えるのは難しいので片方の操作だけを考えることにする。
操作Aのみを行う時に得られる異なる整数列は、すべての要素が$0$になるまで操作ごとに異なる数列が得られることから$(log\:max(A_i))+1$個、つまり高々$61$個である。
一方操作Bのみを行う時は、条件から$min(A_i)$回までしか操作を行えず操作ごとに異なる数列が得られることから$(min(A_i)+1)$個である。
これらのことを踏まえると、操作Aを$60$回を超えて行っても意味がないから、操作Aを行う回数を初めに決めた後に操作Bを行う回数及びタイミングを決めれば良さそうである。
操作Aを決めた回数だけ行った後は$0$になる要素が出ない限り操作Bを行える。
操作Bを行うごとに異なる数列が得られその数も容易に分かるので、これらはまとめて数えたい。
しかし異なる操作方法によって同じ数列が得られる可能性があるから、重複して数えないようにもしたい。
これは例えば得られた数列の各要素から最も小さい要素の値を引いた列を保持したり隣接する項の差分を取ったりしたものをキーとし、最も小さい要素が取り得る値の範囲の集合を保持する連想配列を使えば達成できる。
次に操作Aを決めた回数だけ行う前に行う操作Bについて考える。
操作Aを$w$回行った後に操作Bを行うとする。
これは操作Aを1回も行っていない時に操作Bを$2^w$回行ったとしても同じ結果を得ることができる。
そこで操作Aを行う前に操作Bを行うとする。
さらに、操作Aを行った後に同じ数列が得られるものは同一視できるようにすることを考える。
操作Aを行う回数を$x$とすると、操作Bを$2^x$回行うのは操作Aを終えてから操作Bを1回行うことと同じである。
また操作Bを行った時に数列の各要素を$2^x$で割った時の商が同じであるような回数は1つとして良い。
以上のことを考慮すると、操作Aを行う前に操作Bを行う回数は、数列の各要素を$2^x$で割った時の余りをまたがないような2つをを考える必要がないことが分かる。
これにより考えるべき回数は高々$N$個であることが分かる。
問題では操作の合計回数が制限されているので、操作回数を極力減らすことを考える。
上記の考察を総合すると、操作Aを行う前に操作Bを$y$回行う時は、$y$を2進数で見た時の下から$i$桁目が$1$であれば、操作Aを$i$回行った後に操作Bを1回行うようにすれば良いことが分かる。
以上によりこの問題で考えるべき状態は$O(N \: log (max(A_i)))$個で良い。
連想配列のキーが$O(N)$個の数列であることを考えると、全体の計算量は$O(N^2$$\: log (max(A_i))$$\: log(log(N \: log(max(A_i)))))$である。
これは十分高速である。
ソースコード
マクロ等はこちら
const int MC = 222;
const LL mod = 1e9 + 7;
int N;
LL K;
LL A[MC];
LL B[MC];
int s[MC];
map<vector<LL>,int> key;
vector<vector<pair<LL,LL> > > ans;
int main(){
cin >> N >> K;
repp(i,0,N){
cin >> A[i];
s[i] = i;
}
sort(A,A+N);
repp(i,0,61){
if(i > K) break;
vector<LL> v;
repp(j,1,N) v.PB((A[j]>>i)-(A[j-1]>>i));
repp(j,0,N) B[j] = A[j]%((LL)1<<i);
sort(s,s+N,[&](const int &x , const int &y){return B[x] < B[y];});
auto it = key.find(v);
if(it != key.end()) ans[(*it).second].PB(MP(A[0]>>i,K-i));
else {
key[v] = ans.size();
ans.push_back(vector<pair<LL,LL> >(1,MP(A[0]>>i,K-i)));
}
repp(j,0,N-1){
if(s[j]) --v[s[j]-1];
if(s[j]<N-1) ++v[s[j]];
if(B[s[j]] == B[s[j+1]]) continue;
int z = 1;
LL x = B[s[j]] ^ B[s[j+1]];
while(x != (x&-x)) x -= x&-x;
LL p = x;
for(LL y = B[s[j]] ; y ; y -= y&-y){
if((y&-y) > x){
p += y&-y;
++z;
}
}
if(p<=A[0] && i+z<=K){
auto it = key.find(v);
if(it != key.end()) ans[(*it).second].PB(MP((A[0]-p)>>i,K-i-z));
else {
key[v] = ans.size();
ans.push_back(vector<pair<LL,LL> >(1,MP((A[0]-p)>>i,K-i-z)));
}
}
}
}
LL r = 0;
for(auto v : ans){
LL z = -1;
sort(v.begin(),v.end());
for(auto u : v){
(r += min(u.second+1,u.first-z)) %= mod;
z = u.first;
}
}
cout << r << endl;
return 0;
}解法まとめ
操作Aの回数$x$をまず決める。
その後、各要素を$2^x$で割った余りをまたがない領域ごとに操作Aの前に行うとした時の操作Bを行う回数$y$を決める。
この時に選ぶ回数は極力2進数で見た時に$1$が立っている桁の数が少なくなるようにする。
$x$と$y$を決めるごとに操作Aを行った後の状態を保持する。
この際に元の数列の階差数列をキーとし、残りの操作回数と数列の要素のうち最小のものの値をもつ連想配列を用いる。(18-53行)
答えはキーごとに見て重複がないように数える。(54-63行)