ZOJ 2876 Phone list

ZOJ

ZOJ :: Problems :: Show Problem

問題

n個の文字列が与えられる。ある文字列が、もう一方の文字列のprefixになるような２つの文字列が存在するか判定する。

解法

O(n^2)の全探索だと間に合わない。sortして隣り合う文字列を調べるとo(nlogn)で判定できる。

コード

int main(){
  int T,n;
  cin>>T;
  while(T--){
    cin>>n;
    vector<string> nums(n);
    REP(i,n){
      cin>>nums[i];
    }
    bool ans = true;
    sort(nums.begin(),nums.end());
    REP(i,n-1){
      int j = i+1;
      if(nums[i].size() <= nums[j].size() && 
          nums[i] == nums[j].substr(0,nums[i].size())){
        ans = false;
        goto PRINT;
      }
    }
PRINT:
    if(ans)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
  }
  return 0;
}

ZOJ 3123 Subsequence

ZOJ

問題

長さNの数列a[0],..,a[N]が与えられる。総和がSを超えるような連続する部分列の、最小の長さを求めよ。

解法

まず部分和sを計算する(s[i+1] = s[i] + a[i], s[0] = 0)。
するとa[i],...,a[j]の総和はs[j+1]-s[i]となるので、始点iを決めると、終点はS+s[i]の二分探索で求まる。

コード

int main(){
  int T;
  cin>>T;
  while(T--){
    int N,S;
    cin>>N>>S;
    vector<int> a(N);
    REP(i,N)cin>>a[i];
    vector<int> sum(N+1);
    REP(i,N)sum[i+1] = sum[i]+a[i];
    int ans = INF;
    REP(i,N){
      int cond = S + sum[i];
      vector<int>::iterator it = lower_bound(sum.begin(),sum.end(),cond);
      if(it != sum.end()){
        ans = min(ans, (int)distance(sum.begin(),it) - i);
      }
    }
    if(ans == INF) ans = 0;
    cout<<ans<<endl;
  }
        
  return 0;
}

AOJ 1174 Identically Colored Panels Connection

AOJ

問題

問題文読んで。

解法

色の変化をdfsする。隣接するマスの判定もdfsで。

コード

int h,w,c;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,-1,0,1};
int p[8][8];
bool ck[8][8];
bool valid(int x, int y){
  return x>=0&&x<w&&y>=0&&y<h;
}
void check(int x, int y, int c){
  if(ck[y][x]||p[y][x]!=c) return;
  ck[y][x] = true;
  REP(r,4){
    int nx = x+dx[r];
    int ny = y+dy[r];
    if(valid(nx,ny)){
      check(nx,ny,c);
    }
  }
}
int dfs(int t){
  int ret = 0;
  if(t==5){
    memset(ck,0,sizeof(ck));
    check(0,0,c);
    REP(y,h)REP(x,w)if(ck[y][x])ret++;
  }else{
    int tmp[8][8];
    memcpy(tmp,p,sizeof(p));
    REP(nc,6){
      memset(ck,0,sizeof(ck));
      check(0,0,p[0][0]);
      REP(y,h)REP(x,w)if(ck[y][x])p[y][x] = nc;
      ret = max(ret,dfs(t+1));
      memcpy(p,tmp,sizeof(tmp));
    }
  }
  return ret;
}
int main(){
  while(cin>>h>>w>>c,h){
    c--;
    REP(y,h)REP(x,w)cin>>p[y][x],p[y][x]--;
    cout<<dfs(0)<<endl;
  }
  return 0;
}

AOJ 1173 The Balance of the World

AOJ

問題

括弧のバランスがとれているか判定。

解法

左括弧ならstackに入れ、右括弧ならstackから取り出す。
左括弧と右括弧の対応が違っていたり、左括弧が余っていたり、右括弧が多すぎたりすればNG

コード

bool solve(string str){
  map<char, int> t;
  t['['] = 1; t[']'] = 1;
  t['('] = 2; t[')'] = 2;
  stack<char> stk;
  REP(i,str.size()){
    if(str[i]=='['||str[i]=='('){
      stk.push(t[str[i]]);
    }else if(str[i]==']'||str[i]==')'){
      if(stk.empty()||stk.top()!=t[str[i]]) return false;
      else stk.pop();
    }
  }
  return stk.empty();
}
int main(){
  string str;
  while(getline(cin,str)){
    if(str==".") break;
    if(solve(str)) cout<<"yes"<<endl;
    else cout<<"no"<<endl;
  }
  return 0;
}

AOJ 1172 Chebyshev's Theorem

AOJ

問題

整数nに対し、n

解法

試し割りで素数判定

コード

bool isPrime(int n){
  for(int i = 2; i*i<=n; i++){
    if(n%i == 0) return false;
  }
  return true;
}

int main(){
  int n;
  while(cin>>n,n){
    int ans = 0;
    FOR(i,n+1,2*n+1){
      if(isPrime(i))ans++;
    }
    cout<<ans<<endl;
  }
  return 0;
}