Educational Codeforces Round 15 F. T-Shirts

• まえがき

解説が無かったので、正解につながるキーワードを書いておきます。

(解説と呼べるほど丁寧には書いてありません)

• 問題概要

https://codeforces.com/contest/702/problem/F

問題を言い換えると、結局長さnの数列aがあって、クエリxに対して

int cnt=0;

for(int i=0;i<n;i++){

  if(x>=a[i])x-=a[i],cnt++;

}

return cnt;

をする問題。

• キーワード

この問題を解くにあたってのキーワードは、「xの値を高速にx/2未満にする」です。

• 解法の概要

いま、数列中での現在地iと現在のクエリの値xがあります。

2^k<=x<2^(k+1)を満たす整数kを用意します。

ここから、O(logN)でiの値を進めてxの値を2^k未満にします。

このとき、次の2パターンがあります。

1. aの値が2^k以上のものを1つ以上とる
2. aの値が2^k未満のものだけでxの値が2^k未満になる。

一旦1.のパターンがおこり得ないとすると、2.のパターンはあらかじめ各0<=k<20に対して値が2^k未満のものだけの数列を作っておくと、累積和を良い感じに二分探索することで、iをどこまで進めるとxが2^k未満になるか分かります。

逆に2.のパターンがおこり得ないとすると、1.のパターンはこれもあらかじめ各0<=k<20に対してb_i=(2^k<=a_iかつa_i<2^(k+1)のときは0<=j<iでa_j<2^kを満たすものの総和+a_i、そうでない時は2^100)という数列を用意しておくと、「整数le,supに対し、j>=leかつb_j<=supを満たすjの最小値」を求める話になります。

そこで、2つのパターンのうち行き先が近い方に行くことで、iの値を進めてかつxの値を2^k未満にすることができます。

• 計算量

Aを数列aの最大値として、O(NlogA+QlogNlogA)

• 関連問題

Codeforces Global Round 14 I. Phoenix and Diamonds

https://codeforces.com/contest/1515/problem/I

この問題に個数と個数の変更クエリがついて複雑になった問題。

逆にいえば複雑になっただけなので、ほとんど同じ解法でものすごく頑張ると解けます。

• あとがき

かなり雑に書いたので、何かあれば 

https://twitter.com/heno_code

まで気軽にご連絡ください。