今日の精進（AtCoder ABC336-D）

今日は初見の問題 AtCoder ABC336-D「Pyramid」を解きました。

問題

D - Pyramid

ポイント

• $${1 \sim N}$$ までそれぞれをピラミッドの頂点とした場合に、左側に最大何段作ることができるのか、そして右側に最大何段作ることができるのかをあらかじめ計算しておく（左右から累積和するみたいな感じ）。

// 入力が以下のような場合だと
5
4 5 6 1 3

// i番目をピラミッドの頂点とした場合に、左側に最大何段つくれるか
1 2 3 1 2

// i番目をピラミッドの頂点とした場合に、右側に最大何段つくれるか
4 3 2 1 1

反省点

上記のポイントを以下のように実装していました。

// i番目をピラミッドの頂点とした場合に、左側に最大何段つくれるか
vector<int> sum1(N);
for (int i = 0; i < N; i++) {
  if (i == 0) {
    sum1[i] = 1;
  } else {
    if (A[i-1] < A[i] && 1 < A[i]) {
      sum1[i] = min(sum1[i-1]+1, A[i]);
    } else if (A[i] == A[i-1] && 1 < A[i]) {
      sum1[i] = min(sum1[i-1]+1, A[i]);
    } else if (A[i] < A[i-1] && 1 < A[i]) {
      sum1[i] = min(sum1[i-1]+1, A[i]);
    } else {
      sum1[i] = 1;
    }
  }
}

// i番目をピラミッドの頂点とした場合に、右側に最大何段つくれるか
vector<int> sum2(N);
for (int i = N-1; 0 <= i; i--) {
  if (i == N-1) {
    sum2[i] = 1;
  } else {
    if (A[i+1] < A[i] && 1 < A[i]) {
      sum2[i] = min(sum2[i+1]+1, A[i]);
    } else if (A[i] == A[i+1] && 1 < A[i]) {
      sum2[i] = min(sum2[i+1]+1, A[i]);
    } else if (A[i] < A[i+1] && 1 < A[i]) {
      sum2[i] = min(sum2[i+1]+1, A[i]);
    } else {
      sum2[i] = 1;
    }
  }
}

手計算した結果と合うように場合分けして考えていたのですが、同じコードになっていて 、わざわざif 文にする必要がなかったことに提出後まで気がつきませんでした（ACできたからまぁ、いいか）。
しかもこの実装に40分くらいかかっていたので、もう少しスムーズに実装できるよう、もっと練習が必要です。

ACしたコード

提出 #49339051 - AtCoder Beginner Contest 336

少し時間はかかりましたが、400点の問題を初見でACできたのはうれしかったです。
次回もがんばります。