Google Code Jam 2014 Round2 - pes

巨人-オリックス戦を観戦しに行っていたのですが、
息詰まる投手戦のまま延長に突入したため泣く泣く撤退しての参加でした。
野球の方は12回までやって1-0とかアツい展開だったらしいです。ぐぬぬ…。

A : Data Packing

最初「1個のディスクにデータは高々2個」という制約を読み落としてた
NP困難的な空気を感じたので、流石に無いわと思って問題文を読み返して気付いた
サイズ大きいのから貪欲に2個ずつ詰めたら良さそうだったので詰めた

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>

using namespace std;

int main(){
    int T; cin >> T;
    for(int test=1;test<=T;test++){
        int N, X; cin >> N >> X;
        vector<int> S(N);
        for(int i=0;i<N;i++) cin >> S[i];
        sort(S.rbegin(), S.rend());
        vector<int> used(N, 0);
        int res = 0;
        for(int i=0;i<N;i++){
            if(used[i]) continue;
            used[i] = 1;
            for(int j=i+1;j<N;j++){
                if(used[j]) continue;
                if(S[i]+S[j] <= X){
                    used[j] = 1;
                    break;
                }
            }
            res++;
        }
        printf("Case #%d: %d\n", test, res);
    }
}

B : Up and Down

反転数をアレするアレだな！って思ってたら2WAしたので頭冷やしてsmall書いた。
largeがガチで分からなくて一旦D(small)に逃避

smallのコードで、swap回数が最小になる時の並び順を出力してみた
これ小さい方から左右の近い方に寄せてるだけだ…。
一応smallの解と比較してみたら合ってたので投げた。

記念にsmallのコードも晒しておく

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>

using namespace std;

int solveSmall(const vector<int>& vi){
    vector<int> v = vi;
    vector<int> a(v.size());
    sort(v.begin(), v.end());
    int res = 10000000;
    vector<int> minV;
    do{
        bool valid = true;
        int maxPos = 0;
        for(int i=1;i<v.size();i++){
            if(v[maxPos] < v[i]) maxPos = i;
        }
        for(int i=0;i+1<=maxPos;i++){
            if(v[i] > v[i+1]) valid = false;
        }
        for(int i=maxPos;i+1<v.size();i++){
            if(v[i] < v[i+1]) valid = false;
        }
        if(!valid) continue;
        for(int i=0;i<v.size();i++){
            for(int j=0;j<vi.size();j++){
                if(v[i]==vi[j]) a[j] = i;
            }
        }
        int cnt = 0;
        for(int i=0;i<v.size();i++){
            for(int j=i+1;j<v.size();j++)
                if(a[i] > a[j]) cnt++;
        }
        if(cnt < res) minV = v;
        res = min(res, cnt);
    }while(next_permutation(v.begin(), v.end()));
    return res;
}

int solveLarge(const vector<int>& vi){
    vector<int> v = vi;
    vector<int> vp;
    for(int i=0;i<v.size();i++) vp.push_back(v[i]);
    sort(vp.begin(), vp.end());
    int l = 0, r = vi.size()-1;
    int res = 0;
    for(int i=0;i<vi.size();i++){
        int pos = -1;
        for(int j=l;j<=r;j++){
            if(v[j] == vp[i]){
                pos = j;
                break;
            }
        }
        if(pos-l < r-pos){
            res += pos-l;
            for(int j=pos;j-1>=l;j--) swap(v[j], v[j-1]);
            l++;
        } else {
            res += r-pos;
            for(int j=pos;j+1<=r;j++) swap(v[j], v[j+1]);
            r--;
        }
    }
    return res;
}

int main(){
    int T; cin >> T;
    for(int test=1;test<=T;test++){
        int N; cin >> N;
        vector<int> vi(N);
        for(int i=0;i<N;i++) cin >> vi[i];
        printf("Case #%d: %d\n", test, solveLarge(vi));
    }
}

C : Don't Break The Nile

WindPassageに激似だなとは思った。コンテスト中は思っただけだった。

smallは適当に流したら通るんじゃねと思って左手法で流していった。
largeも座標圧縮したら通るんじゃねと思ったけど嘘しか書けなかった(´・ω・｀)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

int river[1000][4000];
int mem[1000][4000];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

int main(){
    int T; cin >> T;
    for(int test=1;test<=T;test++){
        int W, H, B; cin >> W >> H >> B;
        memset(river, -1, sizeof(river));
        memset(mem, 0, sizeof(mem));
        for(int i=0;i<B;i++){
            int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
            for(int j=x1;j<=x2;j++){
                for(int k=y1;k<=y2;k++){
                    river[j][k] = -2;
                }
            }
        }
        int res = 0;
        for(int i=0;i<W;i++){
            if(river[i][0]!=-1) continue;
            int x = i, y = 0, dir = 1;
            while(true){
                if(mem[x][y]&(1<<dir)) break;
                mem[x][y] |= 1<<dir;
                river[x][y] = i;
                if(y == H-1){ res++; break; }
                for(int j=0;j<4;j++){
                    int ndir = (dir+5-j)%4;
                    int nx = x+dx[ndir];
                    int ny = y+dy[ndir];
                    if(nx < 0 || W <= nx || ny < 0 || H <= ny || (river[nx][ny]!=-1&&river[nx][ny]!=i)) continue;
                    x = nx, y = ny, dir = ndir;
                    break;
                }
            }
        }
        printf("Case #%d: %d\n", test, res);
    }
}

ちなみに終了後にlarge通したコード。
WindPassageでした。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <queue>

using namespace std;

class Node{
public:
    int pos, cost;
    Node(int pos, int cost) : pos(pos), cost(cost) {}
    bool operator < (const Node& nd) const { return cost > nd.cost; }
};

int main(){
    int T; cin >> T;
    int x1[1000], y1[1000], x2[1000], y2[1000];
    for(int test=1;test<=T;test++){
        int W, H, B; cin >> W >> H >> B;
        if(B == 0){
        }
        for(int i=0;i<B;i++){
            cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
        }
        int res = 0;
        vector< vector<Node> > g(B+2, vector<Node>());
        g[B].push_back(Node(B+1, W));
        for(int i=0;i<B;i++){
            g[B].push_back(Node(i, x1[i]));
            g[i].push_back(Node(B+1, W-1-x2[i]));
            for(int j=i+1;j<B;j++){
                int c = max(0, max(max(x1[i], x1[j])-min(x2[i], x2[j])-1, max(y1[i], y1[j])-min(y2[i], y2[j])-1));
                g[i].push_back(Node(j, c));
                g[j].push_back(Node(i, c));
            }
        }
        vector<int> dist(B+2, 1000000007);
        priority_queue<Node> qu; qu.push(Node(B, 0));
        dist[B] = 0;
        while(!qu.empty()){
            Node nd = qu.top(); qu.pop();
            if(nd.cost > dist[nd.pos]) continue;
            for(int i=0;i<g[nd.pos].size();i++){
                int npos = g[nd.pos][i].pos;
                int ncost = nd.cost+g[nd.pos][i].cost;
                if(dist[npos] > ncost){
                    dist[npos] = ncost;
                    qu.push(Node(npos, ncost));
                }
            }
        }
        printf("Case #%d: %d\n", test, dist[B+1]);
    }
}

D : Trie Sharding

smallはどれだけ適当にやっても通りそうだったので通しておいた。
largeは全く分からなかった。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <set>

using namespace std;

int getNodeNum(const vector<string>& vs){
    set<string> S;
    for(int i=0;i<vs.size();i++){
        for(int j=1;j<=vs[i].size();j++){
            S.insert(vs[i].substr(0, j));
        }
    }
    return S.size();
}

int main(){
    int T; cin >> T;
    for(int test=1;test<=T;test++){
        int N, M; cin >> N >> M;
        int maxNode = 0;
        int cnt = 0;
        vector<string> vs(N);
        for(int i=0;i<N;i++) cin >> vs[i];
        for(int i=0;i<(1<<(2*N));i++){
            vector< vector<string> > v(4);
            for(int j=0;j<N;j++){
                v[(i>>(2*j))%4].push_back(vs[j]);
            }
            bool valid = true;
            int sum = 0;
            for(int j=0;j<4;j++){
                if(j < M){
                    if(v[j].empty()) valid = false;
                    else sum += getNodeNum(v[j]);
                } else {
                    if(!v[j].empty()) valid = false;
                }
            }
            if(!valid) continue;
            if(sum == maxNode){
                cnt++;
            }
            else if(sum > maxNode){
                maxNode = sum;
                cnt = 1;
            }
        }
        printf("Case #%d: %d %d\n", test, maxNode+M, cnt);
    }
}

Rank 323 : /oo/oo/o-/o-/ Score 50, Penalty 1:49:55

通過ですが点数的には500位と一緒。時間勝負勢でした。
C-largeも通したかったですが、それよりBでハマりすぎたのが悲しかったです。