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

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

D - Pyramid / AtCoder Beginner Contest 336

ABC336 AtCoder C++ AtCoder Beginner Contest 400点 DP 競技プログラミング

問題

正の整数 k について、サイズ k のピラミッド数列を、長さ (2k - 1) の数列で各項の値が順に 1, \, 2, \, \cdots , \, k - 1, \, k, \, k - 1, \, \cdots , \, 2, \, 1 であるようなものを指す。

長さ n の数列 a = ({a}_{1}, \, {a}_{2}, \, \cdots , \, {a}_{n}) が与えられる。 数列 a に対して、以下のいずれかの操作を0回以上繰り返して得ることのできるピラミッド数列のサイズの最大値を求めよ。

  • 数列の項を1つ選び、その項の値を 1 減少させる。
  • 先頭または末尾の項を削除する。

入力

まず最初の1行目に、整数 n が与えられる。

次の1行には、整数 {a}_{1}, \, {a}_{2}, \, \cdots, \, {a}_{n} が順に与えられる。

条件

  • 実行時間制限: 2s
  • メモリ制限: 1024MB
  • 1 \leq n \leq 2 \times {10}^{5}
  • 1 \leq {a}_{i} \leq {10}^{9}

出力

問題文の操作を繰り返して得られるピラミッド数列のサイズの最大値を1行に出力すること。

解法

まず、数列 a を {a}_{1}, \, {a}_{2}, \, \cdots の順に、操作を加えて 1, \, 2, \, \cdots , \, k となるようにできるかを考えます。

このとき、値 {l}_{i} を「 i 番目の要素を右端とするときに、操作を加えて 1, \, 2, \, \cdots, \, k とするときの k の最大値」として定めます。

ここで、 {l}_{i - 1} が定まっているとします。 すなわち、 {a}_{1}, \, \cdots , \, {a}_{l - 1} に対して操作を行うことで、 1, \, 2, \, \cdots , \, {l}_{i - 1} という数列ができるものとします。

このとき、 {l}_{i} の値については、

  • {l}_{i - 1} + 1 \leq {a}_{i} のとき: {a}_{i} を {l}_{i - 1} + 1 まで減らすことによって、数列が 1, \, 2, \, \cdots , \, {l}_{i - 1}, \, {l}_{i - 1} + 1 とできるので、 {l}_{i} = {l}_{i - 1} + 1
  • {l}_{i - 1} \geq {a}_{i} のとき: 数列 1, \, 2, \, \cdots , \, {l}_{i - 1} の適当な部分を減らしていくことによって、数列を 1, \, 2, \, \cdots , \, {a}_{i} - 1 とできるので、 {l}_{i} = {a}_{i}

として遷移することになります。

同様に、値 {r}_{i} を「 i 番目の要素を左端とするときに、操作を加えて k, \, \cdots, \, 2, \, 1 とするときの k の最大値」として定めます。

このとき、 {r}_{i + 1} が定まっているとすると、 {a}_{i + 1} を左端として {r}_{i + 1}, \, \cdots , \, 2, \, 1 という数列ができます。

従って、 {r}_{i} の値については、 {l}_{i} と同様に考えて、

  • {a}_{i} \geq {r}_{i + 1} + 1 のとき: {r}_{i} = {r}_{i + 1} + 1
  • {a}_{i} \leq {r}_{i + 1} のとき: {r}_{i} = {a}_{i}

として遷移することになります。

以上のようにして求まった {l}_{i}, \, {r}_{i} の値から、

  • i 番目の要素を右端として 1 , \, 2, \, \cdots , \, {l}_{i} という数列が出来上がる
  • i 番目の要素を左端として {r}_{i}, \, \cdots, \, 2, \, 1 という数列が出来上がる

ということが同時に言えるので、 i 番目の要素を中心としたピラミッド行列のレベルの最大値は \min{( {l}_{i}, \, {r}_{i} )} によって与えられると言えます。

従って、すべての i に対して \min{( {l}_{i}, \, {r}_{i} )} を求め、その中の最大値がこの問題の答えとして言えます。

以上をまとめると、

  1. i = 1, \, 2, \, \cdots , \, n の順に {l}_{i} の値を求める
  2. i = n, \, n - 1, \, \cdots , \, 1 の順に {r}_{i} の値を求める
  3. すべての i について、 \min{( {l}_{i}, \, {r}_{i} )} の値を求め、その中の最大値を出力する

という手順によって、この問題の答えが得られます。

この手順では全体の計算量が O(n) 程度となり、これは実行時間制限に十分に間に合うと言えます。

ソースコード

main() 関数の中に、答えを出力する部分を直接実装しました。

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

int l[int(2e5 + 5)], r[int(2e5 + 5)];

int main() {
  // 値の入力
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }

  // i = 1, ..., n の順に l[i] の値を計算
  for (int i = 1; i <= n; i++) {
    if (l[i - 1] + 1 <= a[i]) {
      l[i] = l[i - 1] + 1;
    } else {
      l[i] = a[i];
    }
  }

  // i = n, ..., 1 の順に r[i] の値を計算
  for (int i = n; i >= 1; i--) {
    if (a[i] >= r[i + 1] + 1) {
      r[i] = r[i + 1] + 1;
    } else {
      r[i] = a[i];
    }
  }

  int ans = 0; // 最終的に出力する値
  for (int i = 1; i <= n; i++) {
    ans = max(ans, min(l[i], r[i])); // min(l[i], r[i]) の値と比較して、 ans を更新していく
  }
  cout << ans << endl; // 答えの出力

  return 0;
}