ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

Codeforces Round #561 D. Cute Sequences

Problem - D - Codeforces

問題概要

以下の問題を  q 個解け。

  • 正整数  a, b, m が与えられる。以下の条件を満たす整数列  \lbrace x_{i} \rbrace を1つ構成するか、そのような数列が存在しないことを判定せよ。
    • 初項が  a で末項が  b である。
    • 項数を  n として、全ての  2 \le i \le n について  r_{i} = x_{i} - \sum_{k=1}^{i-1}x_{k} とすると  1 \le r_{i} \le m が成立する。

制約

  •  1 \le q \le 10^{3}
  •  1 \le a \le b \le 10^{14}
  •  1 \le m \le 10^{14}

解法

数列の長さ  n を全探索することを考えましょう。 n = 1 のときに条件を満たすのは  a=b の時だけなので、その場合は別扱いすることにして  n \ge 2 の場合を考えます。

長さ  n をある値に固定して、末項が最小でどのくらいの値になるか考えます。すなわち全て  r_{i} = 1 としたときの末項を計算してみます。

  •  x_{1} = a
  •  x_{2} = x_{1} + 1 = a+1
  •  x_{3} = x_{1} + x_{2} + 1 = 2a+2
  • ...
  •  x_{n} = x_{1} + \cdots + x_{n-1} + 1 = 2^{n-2}(a+1)

実際に計算してみるとこのような値になります。もしこの値が既に  b よりも大きい場合は、これ以上の長さでは絶対に答えを構成できないことが分かります。

 2^{n-2}(a+1) \le b のときは、ここから各  r_{i} を増やすことで  b との差を埋めることを考えます。各  r_{i} を1増やしたときに、末項の値はどれだけ増えるでしょうか。これも実際に手計算すると分かって、

  •  i \lt n のとき、 r_{i} が1増えると末項は  2^{n-1-i} だけ増える。
  •  r_{n} が1増えると末項は1だけ増える。

というようになります。

最小値の時点で既に1持っているので、各  r_{i} について増やせるのは  m-1 までです。これらの値をうまく決めて、先ほどの係数を掛けた合計が増やすべき値  d = b - 2^{n-2}(a+1) に一致するようにすればよいです。これは係数が大きい方から決めていって、足りない分を増やせるだけ増やすようにすることで求めることができます。

この方針で決めていっても合計が増やすべき値  d に満たない場合は、その数列の長さで条件を満たすものは存在しないことになります。これを  2^{n-2}(a+1) \le b となるような  n 全てについて計算し、条件を満たすものが見つからなかったら答えは存在しないと判定することができます。

2以上の長さの候補はおよそ  \log_{2} \frac{b}{a+1} 個なので、クエリが最大  10^{3} 個あることを加味しても計算時間は問題ないです。

ACコード

Submission #54298174 - Codeforces

コード中で  L という変数でループを回していますが、 L = n-2 として扱っているので読む場合はご注意ください…