問題

$n$ 個の正の整数からなる数列 $\{ {a}_{i} \}$ がある。

この数列 $\{ {a}_{i} \}$ に対して、以下の操作を必ず1回行わなければならない。

2つの整数（ただし、）を選び、をからまでの積に置き換える。
- すなわち、数列 $\{ {a}_{i} \}$ は $[ {a}_{1}, \cdots , {a}_{l - 1} , \left({a}_{l} \cdot {a}_{l + 1} \cdot \cdots \cdot {a}_{r} \right), {a}_{r+1} , \cdots , {a}_{n} ]$ に置き換わる。

この操作を行った後の数列について、数列の和の最大値を与える $(l, r)$ の値を求めよ。ただし、テストケースは $t$ 個与えられるので、それぞれのテストケースについての $(l, r)$ の値を出力すること。なお、最大値を与える $(l, r)$ の組が複数個存在する場合は、そのうちの1つを示すこと。

入力

まず最初の1行目に、テストケースの個数を表す整数 $t$ が与えられる。

その後、 $t$ 個のテストケースのそれぞれに対して、以下のように入力が与えられる。

最初の1行には、数列の要素数 $n$ が与えられる。
その次の1行には、数列 ${a}_{1}, {a}_{2} , \cdots , {a}_{n}$ が与えられる。

条件

$1 \leq t \leq {10}^{4}$
- $t$ 個のテストケースにおける $n$ の総和は $2 \cdot {10}^{5}$ を超えない。
$1 \leq {a}_{i} \leq {10}^{9}$

出力

行にわたり、それぞれのテストケースでのの値を出力すること。
- ただし、 $1 \leq l \leq r \leq n$ であること。

解法

$\{ {a}_{i} \}$ のすべての要素が2以上である場合、すべての整数の積を取ると値が最大になることは明白です。（ $n$ を $n \geq 1$ の整数とするとき、必ず $2n \leq {2}^{n}$ が成立します。）

したがって、この問題の肝は「1」をどのように扱うかということになります。

ここで、まずは数列 $\{ {a}_{i} \}$ が以下のように、左右を1で囲まれているという状況を考えます。

このとき、図の赤い部分についてどのような範囲で積をとるべきかを考える必要がありますが、赤い部分以外の左右のすべて1の部分については考える必要がありません。

なぜならば、左右の1で覆われた部分については、全て1であるために全部積を取ったとしても、値が増えることはありません。一方で、この1で覆われた部分は和を取ることにすると、赤い部分についての値に、更に値を増加させることができます。

従って、このような数列に対しては、以下のように考えると和の最大をとることができます。

以上の考察から、ここからは「1以外の数字から始まり、1以外の数字で終わる最長の部分」（図の赤い部分）について、どのように操作を行えば和の最大値をとるかについて考えます。

この図の赤い部分について、すべての要素の積の値が十分に大きいとするならば、すべての積をとることにより最大値を得られます。

与えられる数列の長さ $n$ が最大でも $2 \cdot {10}^{5}$ であることから、例えばすべての積の値が ${10}^{9}$ を超えているときには、この赤い部分について「一部で積を取り、それ以外の部分で和を取る」とするよりも「すべての部分で積を取る」とする方が、最大値を得られるということが明白です。

（厳密にはすべての積の値が $2n$ よりも大きければ、すべての部分で積を取るのが最大値を得る方法となる*1ようなのですが、証明ができませんでした。）

以上から、赤い部分の積の値が ${10}^{9}$ 以上のときについては「すべての部分で積をとる」という方法をとります。ここからは、積の値が ${10}^{9}$ 以下の場合について考えていきます。

ここで、先程の考察と同様の考え方から、 $l$ や $r$ の値として、 ${a}_{i} = 1$ である $i$ を取ることはありません。というのも、例えば ${a}_{j} = 1$ かつ ${a}_{j + 1} > 1$ というときに、 $l = j$ として選んでしまうと、 $l = j + 1$ のときよりも置換後の和の値が小さくなってしまうからです。（ $r$ についても同様のことが言えます。）

従って、 $l$ や $r$ の値としてなり得るのは、 ${a}_{i} > 1$ である $i$ のみとなります。このことから、 ${a}_{i} > 1$ である $i$ のみについて考えます。

今回は1よりも大きい要素すべての積の値が ${10}^{9}$ 以下の場合について考えており、また ${10}^{9} \leq {2}^{30}$ であることから、この場合で2以上の値の要素の個数はせいぜい30個程度であるということが言えます。

従って、このせいぜい30個程度の値に対して、順番に $l, r$ を設定していき、最終的に置換された数列の和の値の最大値を求めていっても特に実行時間に問題は生じません。

ただし、毎回 $l, r$ を設定した後に和や積を ${a}_{1}$ から順番に求めていくと、それだけで $O(n)$ の計算量がかかってしまうので、工夫は必要です。

\begin{align} \text{sum}_{i} & := {a}_{1} + {a}_{2} + \cdots + {a}_{i} \\ \text{prod}_{i} & := {a}_{1} \times {a}_{2} \times \cdots \times {a}_{i} \end{align}

というようにして、数列 $\left\{ {a}_{i} \right\}$ が与えられた際に予め累積和と累積積の配列を記録しておくと、

\begin{align} & {a}_{i} + \cdots + {a}_{j} = \left( {a}_{1} + \cdots + {a}_{j} \right) - \left( {a}_{1} + \cdots + {a}_{i - 1} \right) = \text{sum}_{j} - \text{sum}_{i - 1} \\ & {a}_{i} \times \cdots \times {a}_{j} = \frac{{a}_{1} \times \cdots \times {a}_{j}}{{a}_{1} \times \cdots \times {a}_{i - 1}} = \frac{\text{prod}_{j}}{\text{prod}_{i - 1}} \end{align}

によって、 ${a}_{i}$ から ${a}_{j}$ までの要素の和、積をそれぞれ $O(1)$ で求めることができます。（ただし、 $i \leq j$ であり、便宜上 $\text{sum}_{0} = 0, \text{prod}_{0} = 1$ とします。）

以上から、 $l, r$ を設定した際の置換後の数列の総和については

\begin{align} & {a}_{1} + {a}_{2} + \cdots + {a}_{l - 1} + \left( {a}_{l} \times {a}_{l+1} \times \cdots \times {a}_{r} \right) + {a}_{r + 1} + \cdots + {a}_{n} \\ = \ & \text{sum}_{l - 1} + \frac{\text{prod}_{r}}{\text{prod}_{l - 1}} + \left( \text{sum}_{n} - \text{sum}_{r} \right) \end{align}

から、 $O(1)$ で求めることができるので、これを ${a}_{i} > 1$ である $i$ について全探索して最大値となる組み合わせが答えとなります。

以上をまとめると、求める $l, r$ の値については

$\left\{ {a}_{i} \right\}$ の要素がすべて1のとき: $l = 1, r = 1$
$\left\{ {a}_{i} \right\}$ のすべての要素の積が ${10}^{9}$ 以上のとき: ${a}_{i} > 1$ である $i$ に対して、 $l$ はその最小値、 $r$ はその最大値
それ以外のとき: ${a}_{i} > 1$ である $i$ の値を全探索して、和が最大となるものを求める

という方法で導出することができます。

ソースコード

以下のような solve() を実装しました。

int n;
ll a[int(2e5 + 5)], sum[int(2e5 + 5)], prod[int(2e5 + 5)];

void solve() {
  cin >> n;
  vector<int> indexes; // a[i] > 1 である i の値を保存するためのvector
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    if (a[i] > 1) {
      indexes.push_back(i); // a[i] > 1 ならば indexes に i を追加する
    }
  }

  if (indexes.size() == 0) {
    cout << "1 1" << endl; // indexesが空のときはすべての要素が1なので、l = 1, r = 1を表示して終了する
    return;
  }

  int l = indexes[0], r = indexes[indexes.size() - 1]; // 記事中の赤い部分の端と端のindexをそれぞれ持っておく

  prod[l - 1] = 1;
  for (int i = l; i <= r; i++) {
    sum[i] = sum[i - 1] + a[i]; // 累積和を計算する
    prod[i] = prod[i - 1] * a[i]; // 累積積を計算する
    if (prod[i] > ll(1e9)) {
      cout << l << " " << r << endl; // 累積積の要素が10^9を超えたらすべての積も10^9を超えるので、赤い部分の端を表示して終了する
      return;
    }
  }

  ll max_value = 0; // 赤い部分の置換後の和の最大値を表す
  int ans_l = 1, ans_r = 1; // 答えとなる l, r の値を表す
  for (int i = 0; i < indexes.size(); i++) {
    for (int j = i; j < indexes.size(); j++) {
      int now_l = indexes[i], now_r = indexes[j];
      ll now_value = sum[now_l - 1] + (prod[now_r] / prod[now_l - 1]) +
                     (sum[r] - sum[now_r]); // 記事中の計算を行う

      if (now_value > max_value) { // もし現在の置換後の和がこれまでの最大値を超えたら、答えの l, r の値を更新する
        max_value = now_value;
        ans_l = now_l;
        ans_r = now_r;
      }
    }
  }

  cout << ans_l << " " << ans_r << endl;
  return;
}

提出したコード: https://codeforces.com/contest/1872/submission/233412815
GitHub

感想

厳密な証明が行えなかったのがやや心残りですが、もしコンテストに出ていたとしたらそんな時間の余裕はないので仕方ないのかもしれません。

とりあえずで始めたこのコンテストの解説記事が全部書けたので嬉しいです。

*1:https://codeforces.com/topic/120790/en3

yutasの競技プログラミング勉強帖

競技プログラミングの問題についての解説記事を主に書いています。

G - Replace With Product / Codeforces Round 895 (Div.3)

問題

入力

条件

出力

解法

ソースコード

感想