Gori#017(ABC037)

問題セット (opens new window)

B - 編集

概要

全要素が$0$で長さ$N$の数列がある.
この数列に対して, 以下の操作を$Q$回行った結果の数列を出力せよ.

• 数列の$L_i$番目から$R_i$番目を$T_i$に書き換える.

解法

制約が$1 \leq N \leq 100$かつ$1 \leq Q \leq 100$なので, O(NQ)でも間に合う.
したがって, 愚直に$Q$回だけ数列の$L_i$番目から$R_i$番目を$T_i$に書き換えれば良い.

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N,Q; cin >> N >> Q;
  vector<int> a(N,0);

  while(Q--){
    int l,r,t; cin>>l>>r>>t;
    for(int i=l-1;i<r;++i){
      a[i] = t;
    }
  }
  
  for(int i=0;i<N;++i){
    cout << a[i] << endl;
  }
  return 0;
}

C - 総和

長さ$N$の数列が与えられたとき, 長さ$K(\leq N)$の連続する部分列の総和を求めよ.

e.g.)  
4 3  
1 2 4 8  

この場合は, 
(1+2+4) + (2+4+8) = 21
となる.

解法

累積和を取って, $\displaystyle \sum_{i=0}^{n-k} sum[i+k] - sum[i]$を求めれば良い.

#include <bits/stdc++.h>
using namespace std;
using int64 = int64_t;
#define int int64

signed main() {
  int n,k; cin >> n >> k;
  vector<int> a(n);
  for(int i=0;i<n;++i) cin >> a[i];
  
  vector<int> sm(n+1,0);
  for(int i=0;i<n;++i){
    sm[i+1] += sm[i] + a[i];
  }

  int ans = 0;
  for(int i=0;i<=n-k;++i){
    ans += sm[i+k] - sm[i];
  }
  cout << ans << endl;
  return 0;
}

D - 経路

$H \times W$のそれぞれのマス目に整数が書いてある.
あなたは, そのうちの任意のマスから以下の制約を満たした時のみ動けるとき, 移動経路の総和を$10^9+7$で割ったあまりを求めよ.ただし, その場から動かないものも移動経路の1つとする.

• 今いるマスの上下左右に隣接しているマスで, 今いるマスよりも大きな整数が書かれたマスに移動できる.

解法

遷移が上下左右に限られるので, DPっぽいことが分かる.
ここで, 任意のマス$(hi, wi)$について考えると, $(hi, wi)$への移動経路は,

• $(hi-1, wi)$からの経路
• $(hi+1, wi)$からの経路
• $(hi, wi-1)$からの経路
• $(hi, wi+1)$からの経路 のみであることが分かる($\because$ 移動できるのは, 今いるマスの上下左右に隣接しているマスのみ).

制約は, $0 \leq H, W \leq 10^3$なので, $O(HW)$でも高々$10^6$に落ち着き, メモ化すれば計算量は抑えられる.

#include <bits/stdc++.h>
using namespace std;
using int64 = int64_t;
#define int int64

constexpr int MOD = 1e9 + 7;

int H,W;
int a[1010][1010];
int memo[1010][1010];

int f(int hi, int wi){
  if (memo[hi][wi] > 0) return memo[hi][wi];
  
  int sm = 0;
  if (hi>0   && a[hi-1][wi]>a[hi][wi]) (sm += f(hi-1,wi)) %= MOD;
  if (hi+1<H && a[hi+1][wi]>a[hi][wi]) (sm += f(hi+1,wi)) %= MOD;
  if (wi>0   && a[hi][wi-1]>a[hi][wi]) (sm += f(hi,wi-1)) %= MOD;
  if (wi+1<W && a[hi][wi+1]>a[hi][wi]) (sm += f(hi,wi+1)) %= MOD;
  return (memo[hi][wi] = sm + 1) %= MOD;
}

signed main(){
  cin>>H>>W;
  for(int hi=0;hi<H;++hi){
    for(int wi=0;wi<W;++wi){
      cin >> a[hi][wi];
    }
  }
  
  int ans = 0;
  for(int hi=0;hi<H;++hi){
    for(int wi=0;wi<W;++wi){
      (ans += f(hi,wi)) %= MOD;
    }
  }
  cout << ans << endl;
  return 0;
}

以上.
お疲れ様でした.

参考資料

• editorial (opens new window)