日々精進

aikoと旅行とプログラミング

【AOJ 2565】Broken Audio Signal

問題

Broken Audio Signal | Aizu Online Judge

方針

  • 区間を狭めていって, その区間によって結果を出力する.
  • xが偶数番目のときに上界, 奇数番目のときに下界を決めることができる.
  • xが連続した時はnone, 上界がないなど様々な場合分けがあってとてもつらい.

コード

#include<bits/stdc++.h>

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define MAX_V 1000000000

using namespace std;

typedef long long ll;

int n;
string data[10000];

ll toNum(string s){
  return (int)atoi(s.c_str());
}

string solve(){
  ll upper, lower;
  string prev;
  upper = MAX_V * 2; lower = -MAX_V * 2;
  prev = to_string(upper);

  rep(i, n){
    if(data[i] == "x"){
      if(prev == "x") return "none"; // xが連続
      if((i+1) % 2 == 1){ // odd
    upper = min(upper, toNum(prev));
    if(i < n-1) upper = min(upper, toNum(data[i+1]));
      }else{ // even
    lower = max(lower, toNum(prev));
    if(i < n-1) lower = max(lower, toNum(data[i+1]));
      }
    }else{ // 数字のときに正しいか判別
      if((i+1)%2 == 1 && prev != "x"){
    if((toNum(prev)) <= toNum(data[i])) return "none";
      }else if(prev != "x"){
    if((toNum(prev)) >= toNum(data[i])) return "none";
      }
    }
    
    prev = data[i];
    if(upper - lower < 2) return "none"; 
  }
  if(upper - lower > 2) return "ambiguous";
  return to_string((upper + lower) / 2);
}

signed main(){

  while(cin >> n, n){
    rep(i, n){
      cin >> data[i];
    }
    cout << solve() << endl;
  }
}

参考

http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2013%2FPractice%2F模擬地区予選%2F講評&openfile=A.pdf:image=http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2013%2FPractice%2F模擬地区予選%2F講評&openfile=A.pdf