Hatena::Grouptopcoder

hotokuの日記@topcoder部 このページをアンテナに追加 RSSフィード

2013-01-30

Facebook Hacker Cup 2013 Qualification Round

21:26

20点問題をつまらないヘマで落とす。泣。

Balanced Smileys

先頭から1文字づつ読んでいく。"(" / ")"に出会ったら、"深さ"が1つ深く / 浅くなる。但し、":"の次であれば、顔文字の一部とみなして、"深さ"を深く / 浅くしなくても良い。というルールで、最後の文字を読んだ時に"深さ"が0になるような読み方はあるかどうか。

#include <sstream>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>
#include <numeric>
#include <functional>

using namespace std;
typedef unsigned long long ull;
typedef long long ll;


int T;
const int n = 200;
bool mat[n][n];
string s;

void debug(){
  for(size_t i = 0; i < n; ++i){
    copy(mat[i], mat[i]+n, ostream_iterator<bool>(cout, " "));
    cout << endl;
  }
  cout << "==========" << endl;
}

void update(int pos, int d){
  for(int i = 0; i < n; ++i){
    // cout << pos+1 << "," << i+d << endl;
    if(mat[pos][i] && i+d >= 0) mat[pos+1][i+d] = true;
  }
}

bool check(char s){
  return
    (s >= 'a' && s <= 'z') ||
    s == ' ' ||
    s == ':' ||
    s == '(' ||
    s == ')';
}

void doit(int num){
  getline(cin, s);
  for(size_t i = 0; i < n; ++i){
    fill(mat[i], mat[i]+n, false);
  }
  mat[0][0]=true;
  bool after_colon = false;
  for(size_t i = 0; i < s.size(); ++i){
    if(!check(s[i])){
      cout << "Case #" << (num+1) << ": NO" << endl;
      return;
    }
    if(s[i]=='('){
      update(i, 1);
      if(after_colon)update(i, 0);
    }
    else if(s[i]==')'){
      update(i, -1);
      if(after_colon)update(i, 0);
    }
    else{
      update(i, 0);
    }
    after_colon = s[i] == ':';
  }
  // debug();
  cout << "Case #" << (num+1) << ": ";
  if(mat[s.size()][0]) cout << "YES";
  else cout << "NO";
  cout << endl;
}

int main(int argc, char *argv[]){
  cin >> T;
  string temp;
  getline(cin, temp);
  for(size_t i = 0; i < T; ++i){
    doit(i);
  }
  return 0;
}


Find the Min

馬鹿正直にシミュレーションしてしまうと、時間が足りなくなる。制限の中で、kだけ小さいので、こいつで何とかなるんでないかと考える。で、やはり、よく考えると、2k までシミュレーションしてしまえば、残りは周期kの列になる。

#include <sstream>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>
#include <numeric>
#include <functional>



using namespace std;
typedef unsigned long long ull;
typedef long long ll;

int T;
ll k, n, a, b, c, r;
int used[100010];
ll m[200010];

void debug(){
  copy(m, m+2*k+1, ostream_iterator<ll>(cerr, " "));
}

ll getmin(){
  ll i = 0;
  while(used[i]){
    i++;
  }
  return i;
}
void doit(int num){
  cin >> n >> k >> a >> b >> c >> r;
  fill(used, used+k+1, 0);
  fill(m, m+(2*k+1), -1);
  m[0] = a; if(a<=k)used[a]++;
  for(size_t i = 1; i < k; ++i){
    m[i] = (b*m[i-1]+c) % r;
    if(m[i]<=k){
      used[m[i]]++;
    }
  }
  m[k] = getmin();
  used[m[k]]++;
  for(size_t i = k+1; i <= 2*k; ++i){
    if(m[i-k-1]<=k) used[m[i-k-1]]--;
    m[i] = getmin();
    used[m[i]]++;
  }
  //debug();
  ll ret;
  if(n-1<=2*k){
    ret = m[n-1];
  }
  else{
    ret = m[k+(n-1-k)%(k+1)];
  }
  cout << "Case #" << (num+1) << ": " << ret << endl;
}

int main(int argc, char *argv[]){
  cin >> T; char c;
  while((c=getchar())!='\n'){}
  ungetc(c, stdin);
  for(size_t i = 0; i < T; ++i){
    doit(i);
  }
  return 0;
}

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/hotoku/20130130