Facebook Hacker Cup 2013 Qualification Round

参加記

Problem A : Beautiful strings

出現回数が多いアルファベットに対して、大きい数字を割り当てればいいだけです。

int main(){
  int T;
  cin >> T;

  string s;
  getline(cin, s);

  for(int CASE = 1; CASE <= T; CASE++){
    cout << "Case #" << CASE << ": ";

    getline(cin, s);

    int cnt[26];
    memset(cnt, 0, sizeof(cnt));

    for(int i = 0; i < s.length(); i++){
      if(!isalpha(s[i])) continue;
      cnt[tolower(s[i]) - 'a']++;
    }

    int ans = 0;

    sort(cnt, cnt + 26, greater<int>());

    for(int i = 0; i < 26; i++){
      if(cnt[i] == 0) break;
      ans += cnt[i] * (26 - i);
    }

    cout << ans << endl;
  }
}

Problem B : Balanced Smileys

DPで解きました。
dp[何文字目][カッコを何個開いた状態か] = true or false (このパターンがあるかないか)
文字数がnとしたとき、dp[n][0]がtrueならば、閉じカッコにより開きカッコが全て閉じられて、カッコの対応が正しいということになるので、YESになります。

bool dp[102][102];

int main(){
  int T;
  cin >> T;

  string s;
  getline(cin, s);

  for(int CASE = 1; CASE <= T; CASE++){
    cout << "Case #" << CASE << ": ";

    getline(cin, s);

    memset(dp, 0, sizeof(dp));
    dp[0][0] = true;

    for(int i = 0; i < s.length(); i++){
      for(int j = 0; j <= s.length(); j++){
        if(!dp[i][j]) continue;

        bool col = (0 <= i - 1 && s[i - 1] == ':');

        if(s[i] == '('){
          dp[i + 1][j + 1] = true;
          if(col){
            dp[i + 1][j] = true;
          }
        }
        else if(s[i] == ')'){
          if(0 <= j - 1){
            dp[i + 1][j - 1] = true;
          }
          if(col){
            dp[i + 1][j] = true;
          }
        }
        else{
          dp[i + 1][j] = true;
        }
      }
    }

    cout << (dp[s.length()][0] ? "YES" : "NO") << endl;
  }
}

Problem C : Find the Min

「多分」、O(k)の解法

とりあえず、以下の性質は他の人も言ってますよね。

  • m[0]〜m[k-1]がどんな数列になるにしろ、m[1*k]〜m[2*k]には、0〜kの値がそれぞれ1個ずつ入る。
  • m[2*k+1]以降は、m[1*k]〜m[2*k]の周期が繰り返される。


2つ目の性質と、mapを利用して解いている人がいます( id:hirokazu1020さん : http://d.hatena.ne.jp/hirokazu1020/20130129/1359463036 )


僕の解法は、非常にこの人の解法と似ています。ただし、僕はmapではなく配列を使ってカウントしています。hirokazuさんの場合、m[0]~m[k-1]に出てくる、全ての数字の出現回数を数えていますが、実はカウントするのは0~kの数字の出現回数だけでいいです。これは、先ほど述べた1つ目の性質によるものです。いくらkより大きい数字をカウントしていたところで、周期の中にkより大きい数字が入ることはないわけだから、そんなカウントは必要ないわけです。

つまりこういう方針になります。

  • m[0]~m[k-1]に出現する、0以上k以下の値の出現回数を配列cntでカウントしておく(ただし、kより大きい数は無視する)。
    • 配列cntは、直前k個の数の出現回数を記憶した配列。
    • cnt[i]が0になっているときは、直前のk個の要素の中にiが含まれていないということになる。
  • 周期となるm[k]~m[k+k]の各要素を順番に求めていく。
  • 基本的に、0, 1, 2...の順番で小さい方から割り当てる。
  • ただし、添え字を後ろにずらしていく内に、使えるようになる数が出てくるので、その数の方が小さければ、そちらを使う。


以下のコードで、O(k)になってる(はず)。周期を求めるところがforとwhileの二重ループになっていて、一見O(k^2)に見えるかもですが、それは違います。外側のforループをk回まわしたとき、内側のwhileループがまわった回数を合計すると、それは最大でもk回にしかなりません。

typedef long long ll;

ll n, k;
ll a, b, c, r;
ll m[1000010];
ll cnt[1000010]; //カウント用配列

int main(){
  int T;
  cin >> T;

  for(int CASE = 1; CASE <= T; CASE++){
    cout << "Case #" << CASE << ": ";

    cin >> n >> k;
    cin >> a >> b >> c >> r;

    memset(cnt, 0, sizeof(cnt));
    m[0] = a;

    //0~kの数だけをカウントする
    if(m[0] <= k){
      cnt[m[0]] = 1;
    }

    for(int i = 1; i < k; i++){
      m[i] = (b * m[i - 1] + c) % r;

      //0~kの数だけをカウントする
      if(m[i] <= k){
        cnt[m[i]]++;
      }
    }

    //基本的に、このnowを周期に追加していく
    //1,2,3...の順番で小さい方を優先的に使うって言ってたやつです
    ll now = 0;

    vector<ll> cycle;

    //周期の要素である、k+1個の値を順番に求めます
    for(int i = k; i <= k + k; i++){
      //直前のk個より1個手前は、使われなくなる数字なので、これを取りだす
      ll val = (0 <= i - k - 1 ? m[i - k - 1] : INT_MAX);

      //0~kの値であれば、cntの配列を更新(直前のk個から1回分出現回数が減る)
      if(val <= k){
        cnt[val]--;
      }

      //小さい順に見て、次に使える数を探す
      //ここでnowを0からループさせていないのは、
      //[0]~[now-1]に使える数が存在しないから(valを除いて)
      while(cnt[now] > 0) now++;

      //新たに使えるようになる数(val)の方がnowより小さければ、それを使用
      if(val <= k && cnt[val] == 0 && val < now){
        cycle.push_back(val);
        cnt[val]++;
      }
      else{
        cycle.push_back(now);
        cnt[now]++;
      }
    }

    int idx = (n - k - 1) % cycle.size();
    cout << cycle[idx] << endl;
  }
}