読者です 読者をやめる 読者になる 読者になる

CodeJam2016 Qual

 誰でも突破できるみたいな情報を入手していたのですが普通に手間取りました……。
A
 羊が数を数えている問題。詳細は忘れました。
B
 パンケーキをひっくり返して全部表にするとき先頭からN枚という形式でひっくり返さないといけない問題。
Small: 思考停止幅優先探索で解きました。
Large: パンケーキを圧縮。

int main(){
    ifstream ifs("B-large.in");
    ofstream ofs("op_b2.txt");
    int test; ifs >> test;
    rep(casenum, test){
        vector<int> cake;
        string s; ifs >> s;
        int n = s.length();
        cake.push_back((s[0] == '+')? 1 : 0);
        rep(i, n - 1){
            int num = cake[cake.size() - 1]; num ^= 1;
            if(s[i + 1] != s[i]) cake.push_back(num);
        }
        int ans = cake.size();
        int f = ans % 2;
        if((cake[0] && f) || (!cake[0] && !f)) ans--;
        cout << "Case #" << casenum + 1 << ": " << ans << endl;
    }
    return 0;
}

C
 2~10進数に直したときにすべて合成数になるn桁の2進数を約数つきでhoge個列挙しろみたいな問題。
Small: 思考停止幅優先全探索。

map<int, vector<ll>> ans;
set<int> used;
ll pow(int temp, int n){
    ll res = 1;
    rep(i, n) res *= temp;
    return res;
}
ll diviser(ll n){
    for(int i = 2; i * i <= n; i++){
        if(n % i == 0) return i;
    }
    return 0;
}
bool init(int nisin, int keta){
    vector<ll> divs;
    REP(i, 2, 11){
        ll num = 0;
        rep(j, keta) num += pow(i, j) * (1 & nisin >> j);
        ll div = diviser(num);
        if(div <= 0) return false;
        divs.push_back(div);
    }
    ans[nisin] = divs;
    return true;
}
void bfs(int coin, int n, int m){
    queue<int> que;
    que.push(coin);
    int sum = 0;
    if(init(coin, n)) sum++;
    while(!que.empty()){
        int now = que.front(); que.pop();
        REP(i, 1, n - 1){
            int bf = now;
            bf ^= (1 << i);
            if(used.count(bf) != 0) continue;
            if(init(bf, n)) sum++;
            if(sum >= m) return;
            que.push(bf);
            used.insert(bf);
        }
    }
    return;
}
int main(){
    ifstream ifs("C-small-attempt0.in");
    ofstream ofs("op_c.txt");
    
    int test;
    cin >> test;
    rep(casenum, test){
        int n, m; cin >> n >> m;
        int ip = (1 << n) - 1;
        used.insert(ip);
        bfs(ip, n, m);
        ofs << "Case #" << casenum + 1 << ": " << endl;
        int it = 0;
        for(auto k : ans){
            int temp = k.first;
            for(int i = n - 1; i >= 0; --i) ofs << (1 & temp >> i);
            ofs << ' ';
            vector<ll> kk = k.second;
            rep(i, kk.size()){
                ofs << kk[i];
                if(i == kk.size() - 1) ofs << endl; else ofs << ' ';
            }
        }
    }
    return 0;
}

Large: わからず。
D
 学生を雇用して遺跡調査。
Small: 問題を読めば終わり。
Large: 考えれば分かりそうだが脳が思考を拒否したため(以下略)。

ということで55点でした。参加者が桁違いに多くて大変な大会だなあという感じです。問題はアイディアゲー・実験ゲーが多かったと思います。僕は五分以上思考すると脳がフリーズし全探索以外のコードが書けなくなるので今後も厳しい戦いを強いられそうです。