# Gori#017(ABC037)

問題セット

# B - 編集

# 概要

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

  • 数列のLiL_i番目からRiR_i番目をTiT_iに書き換える.

# 解法

制約が1N1001 \leq N \leq 100かつ1Q1001 \leq Q \leq 100なので, O(NQ)でも間に合う.
したがって, 愚直にQQ回だけ数列のLiL_i番目からRiR_i番目をTiT_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 - 総和

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

e.g.)  
4 3  
1 2 4 8  

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

# 解法

累積和を取って, i=0nksum[i+k]sum[i]\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×WH \times Wのそれぞれのマス目に整数が書いてある.
あなたは, そのうちの任意のマスから以下の制約を満たした時のみ動けるとき, 移動経路の総和を109+710^9+7で割ったあまりを求めよ.ただし, その場から動かないものも移動経路の1つとする.

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

# 解法

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

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

制約は, 0H,W1030 \leq H, W \leq 10^3なので, O(HW)O(HW)でも高々10610^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;
}

以上.
お疲れ様でした.

# 参考資料

Last Updated: 2019-2-15 04:38:05