ICPC 2013 アジア地区予選 参加記 (競技について)

ICPC オンサイト参加記

競技以外についてはこちら

チームに割り当てられた端末のホームディレクトリ以下のsouvenirフォルダに入れたファイルはおみやげとしてメールで送られてくるというシステムでした。 先ほど届いたので提出コードを貼り付けます

A

  • solve(n,k,s) = solve(n-1,k-1,s-n) + solve(n-1,k,s) みたいな漸化式のほうが良さそう (DPの練習的には)
  • もっと言えば for(int b = 0; b < (1 << n); b++) if(__builtin_popcount(b) == k) { .. } みたいなほうが良さそう (実装の容易さ的には)
#include <bits/stdc++.h>
using namespace std;

int solve(int n, int k, int s) {
    if(k == 0 && s == 0) return 1;
    int res = 0;
    for(int i = 1; i <= n; i++) {
        res += solve(i - 1, k - 1, s - i);
    }
    return res;
}

int main() {
    while(true) {
        int N, K, S; cin >> N >> K >> S;
        if(N == 0 && K == 0 && S == 0) break;
        cout << solve(N, K, S) << endl;
    }
}

B

#include <bits/stdc++.h>
using namespace std;

#define DEBUG(x) cerr << #x << " = " << x << endl

int main() {
    while(true) {
        int N, L; cin >> N >> L;
        if(N == 0 && L == 0) break;
        vector<int> pos(N);
        // L=-1, R=1
        vector<int> dir(N);
        for(int i = 0; i < N; i++) {
            int p; char d;
            cin >> d >> p;
            pos[i] = p;
            dir[i] = (d == 'R') ? 1 : -1;
        }
        int last = 0;
        int lastsecond = 0;
        int second = 0;
        int lastPos = (int)1e9;
        vector<int> live(N, 1);
        while(true) {
            second++;
            vector<int> on(L + 1, 0);
            for(int i = 0; i < N; i++) {
                if(live[i]) {
                    pos[i] += dir[i];
                    on[pos[i]]++;
                }
            }
            for(int i = 0; i < N; i++) {
                if(live[i]) {
                    if(on[pos[i]] >= 2) {
                        dir[i] *= -1;
                    }
                }
            }
            for(int i = 0; i < N; i++) {
                if(live[i]) {
                    if(pos[i] == 0 || pos[i] == L) {
                        live[i] = 0;
                        if(second == lastsecond) {
                            if(pos[i] < lastPos) {
                                last = i;
                                lastsecond = second;
                                lastPos = pos[i];
                            }
                        }
                        else {
                            last = i;
                            lastsecond = second;
                            lastPos = pos[i];
                        }
                    }
                }
            }
            bool f = false;
            for(int i = 0; i < N; i++) {
                if(live[i]) f = true;
            }
            if(!f) break;
        }
        cout << lastsecond << ' ' << last + 1 << endl;
    }
}

C

  • dfs関数の中でbfsしたりしていますが、最初に実装した時は本当にdfsだったんです…
#include <bits/stdc++.h>
using namespace std;

#define DEBUG(x) cerr << #x << " = " << x << endl

const int MAX_N = 50;
// x, y
int field[2 * (2 * MAX_N) + 1][2 * (2 * MAX_N) + 1];

int X, Y;

typedef pair<int, int> P;
void dfs(int x, int y) {
    queue<P> Q;
    Q.push(P(x, y));
    while(!Q.empty()) {
        P p = Q.front(); Q.pop();
        for(int i = 0; i < 4; i++) {
            int dx[4] = { 1, 0, -1, 0 };
            int dy[4] = { 0, 1, 0, -1 };
            int nx = p.first + dx[i];
            int ny = p.second + dy[i];
            if(0 <= nx && nx < X && 0 <= ny && ny < Y && field[nx][ny] == 0) {
                field[nx][ny] = 1;
                Q.push(P(nx, ny));
            }
        }
    }
}

void show() {
#if 0
   cerr << '-' << endl;
   for(int i = Y - 1; i >= 0; i--) {
       for(int j = 0; j < X; j++) {
           cerr << field[j][i];
       }
       cerr << '|' << endl;
   }
   cerr << '-' << endl;
#endif
}

int main() {
    while(true) {
        int N; cin >> N;
        if(N == 0) break;
        vector<int> x1(N), y1(N), x2(N), y2(N);
        vector<int> xs;
        vector<int> ys;
        for(int i = 0; i < N; i++) {
            cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
            xs.push_back(x1[i]);
            xs.push_back(x2[i]);
            ys.push_back(y1[i]);
            ys.push_back(y2[i]);
        }
        sort(xs.begin(), xs.end());
        sort(ys.begin(), ys.end());
        xs.erase(unique(xs.begin(), xs.end()), xs.end());
        ys.erase(unique(ys.begin(), ys.end()), ys.end());
        for(int i = 0; i < N; i++) {
            x1[i] = find(xs.begin(), xs.end(), x1[i]) - xs.begin();
            y1[i] = find(ys.begin(), ys.end(), y1[i]) - ys.begin();
            x2[i] = find(xs.begin(), xs.end(), x2[i]) - xs.begin();
            y2[i] = find(ys.begin(), ys.end(), y2[i]) - ys.begin();
        }
        memset(field, 0, sizeof(field));
        for(int i = 0; i < N; i++) {
            for(int x = 2 * x1[i]; x <= 2 * x2[i]; x++) {
                field[x + 1][2 * y1[i] + 1] = 1;
                field[x + 1][2 * y2[i] + 1] = 1;
            }
            for(int y = 2 * y1[i]; y >= 2 * y2[i]; y--) {
                field[2 * x1[i] + 1][y + 1] = 1;
                field[2 * x2[i] + 1][y + 1] = 1;
            }
        }
        X = 2 * (int)xs.size() + 1;
        Y = 2 * (int)ys.size() + 1;
        show();
        int ans = 0;
        for(int x = 0; x < X; x++) {
            for(int y = 0; y < Y; y++) {
                if(field[x][y] == 0) {
                    ans++;
                    field[x][y] = 1;
                    dfs(x, y);
                    show();
                }
            }
        }
        cout << ans << endl;
    }
}

E

  • 最初は盤面の状態をstringで持っていたのですが、TLEしそうだったのでint64_tにエンコードしました
  • ぶっちゃけstringでも通ると思う
#include <bits/stdc++.h>
using namespace std;

#define DEBUG(x) cerr << #x << " = " << x << endl

const int swx[9][2] = {
    { 1, 8 },
    { 2, 0 },
    { 3, 1 },
    { 4, 2 },
    { 5, 3 },
    { 6, 4 },
    { 7, 5 },
    { 8, 6 },
    { 0, 7 }
};

const int swy[9][2] = {
    { 6, 3 },
    { 7, 4 },
    { 8, 5 },
    { 0, 6 },
    { 1, 7 },
    { 2, 8 },
    { 3, 0 },
    { 4, 1 },
    { 5, 2 }
};

typedef long long i64;
const int INF = (int)1e9;
typedef pair<int, i64> P;

template <class T, class U>
T lexical_cast(const U& from) {
    T to;
    stringstream ss;
    ss << from; ss >> to;
    return to;
}

// hidarikara
i64 stateChange(i64 S, int i, int j) {
    i = 8 - i;
    j = 8 - j;
    i64 powI = 1LL;
    i64 powJ = 1LL;
    for(int x = 0; x < i; x++) powI *= 10LL;
    for(int x = 0; x < j; x++) powJ *= 10LL;
    i64 mulI = (S / powI) % 10;
    i64 mulJ = (S / powJ) % 10;
    return S - (mulI * powI) + (mulJ * powI) - (mulJ * powJ) + (mulI * powJ);
}

int main() {
    while(true) {
        int costX, costY;
        cin >> costX >> costY;
        if(costX == 0 && costY == 0) break;
        i64 start;
        i64 goal;
        string str;
        str = "";
        for(int i = 0; i < 9; i++) {
            char c; cin >> c;
            str.push_back(c);
        }
        start = lexical_cast<i64>(str);
        str = "";
        for(int i = 0; i < 9; i++) {
            char c; cin >> c;
            str.push_back(c);
        }
        goal = lexical_cast<i64>(str);
        map<i64, int> d;
        priority_queue<P, vector<P>, greater<P> > Q;
        Q.push(P(0, start));
        d[start] = 0;
        while(!Q.empty()) {
            P p = Q.top();
            Q.pop();
            int costNow = p.first;
            i64 curS = p.second;
            if(curS == goal) break;
            if(d.count(curS) && costNow > d[curS]) continue;

            int zero;
            str = lexical_cast<string>(curS);
            if(curS < 100000000LL) zero = 0;
            else zero = find(begin(str), end(str), '0') - begin(str);

            i64 s;
            s = stateChange(curS, zero, swx[zero][0]);
            if(d.count(s) == 0 || d[s] > costNow + costX) {
                d[s] = costNow + costX;
                Q.push(P(d[s], s));
            }

            s = stateChange(curS, zero, swx[zero][1]);
            if(d.count(s) == 0 || d[s] > costNow + costX) {
                d[s] = costNow + costX;
                Q.push(P(d[s], s));
            }

            s = stateChange(curS, zero, swy[zero][0]);
            if(d.count(s) == 0 || d[s] > costNow + costY) {
                d[s] = costNow + costY;
                Q.push(P(d[s], s));
            }

            s = stateChange(curS, zero, swy[zero][1]);
            if(d.count(s) == 0 || d[s] > costNow + costY) {
                d[s] = costNow + costY;
                Q.push(P(d[s], s));
            }
        }
        cout << d[goal] << endl;
    }
}