予選ラウンド結果・・・（Facebook Hacker Cup 2012 Qualification Round)

2完324位でした。
まぁ１完でラウンド１いけるので片方だけでもよかったのですがとりあえず通過です。
ちなみにラウンド1が駿台模試受けたあとに考え始めなければならなくて色々とあれw
ラウンド2までは最低でも行ってラウンド2頑張ってTシャツを貰わなければいけない←

Billboards

まぁ二分探索です。
今まで自力で本格的な二分探索実装したことなかったのですが、なんとかできました。
判定はまず高さで場合分けをして、一行以上になる場合は横幅に収まるような連続した文字列をつなげれば十分なので貪欲っぽくやりました。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
vector<string> s;
bool C(int n, int w, int h) {
    int sz=s.size();
    if (n*sz<=h) {
        int len=0;
        for (int i=0; i<sz; i++) len=max(len,(int)s[i].length());
        if (n*len<=w) return true;
        else return false;
    } else {
        int len[sz];
        for (int i=0; i<sz; i++) len[i]=s[i].length();
        int lim=sz-floor(h/n);
        int can=0, bef=len[0];
        if (bef*n>w) return false;
        for (int i=1; i<sz; i++) {
            if (len[i]*n>w) return false;
            if ((bef+len[i]+1)*n<=w) {
                bef+=len[i]+1;
                can++;
            } else {
                bef=len[i];
            }
        }
        if (can>=lim) return true;
        else return false;
    }
}
int main() {
    int t; cin >> t;
    int w, h;
    string line;
    getline(cin,line);
    for (int ix=1; ix<=t; ix++) {
        cin >> w >> h;
        getline(cin, line);
        s.clear();
        string temp="";
        for (int i=1; i<line.length(); i++) {
            if (line[i]==' ') {
                s.push_back(temp);
                temp="";
            } else temp+=line[i];
        }
        s.push_back(temp);
        int l=1, r=min(w, h)+1;
        while (r-l>1) {
            int mid=(l+r)/2;
            if (C(mid,w,h)) {
                l=mid;
            } else {
                r=mid;
            }
        }
        cout << "Case #" << ix << ": " << l << endl;
    }
}

Alphabet Soup

単純問題ですが、引っかかっていた人も多かったようです。
多分HACKERCUPを作るのにCが２個必要なのを忘れていたとかそんなかんじでしょうが、とにかく出てくるアルファベットを数え上げればいいです。

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
// "H-1A-2C-3K-4E-5R-6C-3U-7P-8"
int main() {
    int t; cin >> t;
    int cnt[8];
    string temp; getline(cin, temp);
    for (int ix=1; ix<=t; ix++) {
        string line; getline(cin, line);
        fill(cnt, cnt+8, 0);
        for (int i=0; i<line.length(); i++) {
            if (line[i]=='H') cnt[0]++;
            if (line[i]=='A') cnt[1]++;
            if (line[i]=='C') cnt[2]++;
            if (line[i]=='K') cnt[3]++;
            if (line[i]=='E') cnt[4]++;
            if (line[i]=='R') cnt[5]++;
            if (line[i]=='U') cnt[6]++;
            if (line[i]=='P') cnt[7]++;
        }
        int res=1001;
        for (int i=0; i<8; i++) {
            if (i==2) res=min(res,cnt[2]/2);
            else res=min(res,cnt[i]);
        }
        cout << "Case #" << ix << ": " << res << endl;
    }
}