CODE FESTIVAL 2016 qual C - C: 二人のアルピニスト

問題

山脈の高さの列が与えられる。山を登るときは高さの最大値を記録して登る。左から登った人と右から登った人の記録が与えられる。このとき、本当の高さの列としてありうるパターン数をで求めよ。記録に矛盾がある場合もあるので、そのときは0と出力せよ。

• 
• 
• 
• 
• 

解法

山を登って値が上昇するとき、上昇後の値は(矛盾がなければ)その山の本当の高さを表している。これを利用してまず矛盾判定をする。山の高さが確定していない部分について、]と]の小さい方のパターン数の積を取れば良い。

int main() {
 
  int N; cin >> N;
  int A[N], B[N];
  rep(i, N) cin >> A[i];
  rep(i, N) cin >> B[i];
 
  int L = -inf;
  int pat[N]; zero(pat);
  rep(i, N) if(L < A[i]) pat[i] = 1, L = A[i];
 
  int R = -inf;
  for(int i=N-1; i>=0; i--) {
    if(R < B[i]) {
      if(pat[i] && A[i] != B[i]) { cout << 0 << endl; exit(0); }
      pat[i] = 1, R = B[i];
    } else {
      if(pat[i] && A[i] > B[i]) { cout << 0 << endl; exit(0); }      
    }
  }
 
  ll ans = 1;
  rep(i, N) {
    if(!pat[i]) pat[i] = min(A[i], B[i]);
    (ans *= pat[i]) %= MOD;
  }
 
  cout << ans << endl;
  
  return 0;
}

感想

本番は二人の歩くピアニストと誤読していたので、登山と何の関係が？と思っていました