ICPC 2014 国内予選参加記

★メンバー
@no15_rennne :M1
@inu_hir0shi :M1
@zr_4 :M1
という学内平均年齢最高チームで参加しました。

★タスクの割り当ては
@inu_hir0shi　コーダー
@no15_rennne　アルゴリズム、ペアプロ
@zr_4　アルゴリズム、ペアプロ
数年一緒にやってきて最適に近い配置になっているはず。

開始前に練習していた部屋が授業で使われているという軽アクシデントに見舞われるも無事スタート

☆A問題
16:56にAC。doubleにハマって涙目になってた。少し泣いた。

#include <iostream>
#include <cmath>
using namespace std;
#define EPS 1e-9
int main () {
    int x, y, s;
    while (cin >> x >> y >> s, x||y||s) {
        int ans = 0;
        for (int i = 1; i <= s-1; i++) {
            for (int j = 1; j <= s-1; j++) {
                double p = ((100+x)/100.0);
                int pre = (int)floor(p*i+EPS) + (int)floor(p*j+EPS);
                    //cout << i << " " << j << " " << pre << endl;
                if (pre == s) {
                    double t = ((double)(100+y)/100.0);
                    ans = max<int>(ans, (int)floor(t*i+EPS)+(int)floor(t*j+EPS));
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

☆B問題
17:12にAC。特筆すべきことなし。

#include <iostream>
#include <cmath>
#include <vector>

int H, W = 5;
using namespace std;
int main () {
    while(cin >> H, H){
        vector< vector<int> > cells(H);
        for (int i = 0; i < H; i++) {
            for(int j = 0; j < W; j++){
                int a;
                cin >> a; 
                cells[i].push_back(a);
            }
        }
        int ans = 0;
        while (1) {

                /*cout << endl;
            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    cout << cells[i][j] << " ";
                }
                cout << endl;
            }
                cout << endl;*/
            bool ok = false;
            vector< vector<int> > next = cells;
            for(int i = 0; i < H; i++){
                for(int j = 0; j < W-2; j++){
                    if (cells[i][j] != 0 && cells[i][j] == cells[i][j+1] && cells[i][j+1] == cells[i][j+2]) {
                        next[i][j] = next[i][j+1] = next[i][j+2] = -1;
                        ok = true;
                    }
                }
            }
            if (!ok) break;
            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    if (next[i][j] == -1) {
                        ans += cells[i][j];
                        next[i][j] = 0;
                    }
                }
            }
            bool update = true;
            while (update) {
                update = false;
                for (int i = 0; i < H-1; i++) {
                    for (int j = 0; j < W; j++) {
                        if (next[i][j] != 0 && next[i+1][j] == 0) {
                            next[i+1][j] = next[i][j];
                            next[i][j] = 0;
                            update = true;
                        }
                    }
                }
            }
            cells = next;
        }
        cout << ans << endl;
    }
    return 0;
}

☆C問題
18:15にAC。ぱっと見で軽実装な解法が浮かばなかったので完全に二人に任せました。
境界となる点を列挙して，円を0.0005刻みで可能な限り移動する．無駄な点省くのをさぼったら実行に時間がかかった。

#include <iostream>
#include <cstdio>
#include <complex>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef complex<double> P;
bool bad  (int r, double t, const vector<P> & vp) {
    P center(50, -r + t);
    for (int i = 0; i < vp.size(); i++) {
        if (abs(vp[i]-center) < r) {
            return true;
        }
    }
    return false;
}
int main () {
    int r, n;
    while (cin >> r >> n, r||n) {
        vector< vector<int> > field(100, vector<int>(100, 0));
        for (int i = 0; i < n; i++) {
            int xl, xr, h;
            cin >> xl >> xr >> h;
            xl += 50; xr += 50;
            for (int i = 0; i <= h; i++) {
                for (int j = xl; j < xr; j++) {
                    field[i][j] = 1;
                }
            }
        }
        /*
        for (int i = 0; i <= 5; i++) {
            for (int j = 40; j < 60; j++) {
                cout << field[i][j] << " ";
            }
            cout << endl;
        }
        */
        vector<pair<int,int> > vp;
        int dx1[] = {1, 1, 0};
        int dy1[] = {0, 1, 1};
        int dx2[] = {0, -1, -1};
        int dy2[] = {1, 1, 0};
        for (int i = 0; i < field.size()-1; i++) {
            for (int j = 1; j < field[0].size()-1; j++) {
                bool ok = false;
                if (i != 0 && field[i][j] == 0) continue;
                for (int k = 0; k < 3; k++) {
                    int ny = i + dy1[k];
                    int nx = j + dx1[k];
                    if (field[ny][nx] == 0) ok = true;
                }
                if (ok) vp.push_back(pair<int,int>(i, j+1));
                ok = false;
                 for (int k = 0; k < 3; k++) {
                    int ny = i + dy2[k];
                    int nx = j + dx2[k];
                    if (field[ny][nx] == 0) ok = true;
                }
                if (ok) vp.push_back(pair<int,int>(j, i));
            }
        }
        sort(vp.begin(), vp.end());
        vp.erase(unique(vp.begin(), vp.end()), vp.end());
        vector<P> vc;
        for (int i = 0; i < vp.size(); i++) {
            vc.push_back(P(vp[i].first, vp[i].second));
        }
        for (double t = 0; ; t += 0.0005) {
            if (bad(r, t, vc)) {
                printf("%.5lf\n", t);
                break;
            }
        }
    }
}

☆D問題
18:33にAC。C問題を二人が解いている時に解法を考えていた。
全探索してチェックするだけ。解法をすり合わせても@inu_hir0shiが腑に落ちないところがあるらしかったけどとりあえず実装。実装早かった。手元の実行は遅かったので多少ヒヤヒヤした。

#include <string>
#include <set>
#include <iostream>
#include <cstdio>
#include <complex>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef complex<double> P;
int main () {
    string s;
    while (cin >> s, s!="#") {
        int n = s.size();
        set<string> ss;
        vector<int> mask(26);
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < n; j++) {
                if (s[j] == char(i+'a')) {
                    mask[i] |= 1<<j;
                }
            }
        }
        for (int i = 0; i < (1<<n); i++) {
            if (__builtin_popcount(mask[s[i]-'a'] & j
            string t;
            for (int j = 0; j < n; j++) {
                if ((1 << j) & i) {
                    t += s[j]+1;
                } else {
                    t += s[j];
                }
            }
            ss.insert(t);
            //cout << t << endl;
        }
        vector<string> ans;
        for (set<string>::iterator it = ss.begin(); it != ss.end(); it++) {
            string tmp = *it;
            for (int i = 1; i <= 25; i++) {
                for (int j = 0; j < n; j++) {
                    if (tmp[j] == char(i+'a')) {
                        tmp[j] = char(i+'a'-1);
                        break;
                    }
                }
            }
            if (tmp == s) ans.push_back(*it);
        }
        cout << ans.size() << endl;
        if (ans.size() <= 10)  {
            for (int i = 0; i < ans.size(); i++) {
                cout << ans[i] << endl;
            }
        } else {
            for (int i = 0; i < 5; i++) {
                cout << ans[i] << endl;
            }
            for (int i = ans.size()-5; i < ans.size(); i++) {
                cout << ans[i] << endl;
            }
        }
    }
}

この時点で、学内３位で予選通過が危ぶまれていた。E頑張ろうという雰囲気に。

☆E問題
終了６分前である19:24にAC。まず@inu_hir0shiが思いついた解法を実装する。その間に@no15_rennneと@zr_4がいろいろ意見を言い合う。そこで2点対経路長解法を発見。木上のパスは一意に定まるというそれ自明だけどグラフ理論ゼミで証明やった！という感じのやつ。実装はある程度できていたコードをくっつけて無事AC。喜びでPCの前で踊っていた。

#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
using namespace std;
struct E {
    int dst, cost;
    E (int d, int c) {
        dst = d; cost = c;
    }
};
int dfs (const vector< vector<E> > &G, const vector<bool> &leaf, int v, int pre) {
    int res = 0;
    //cout << "v " << v << " pre"  << pre << endl;
    for (int i = 0; i < G[v].size(); i++) {
        if (G[v][i].dst == pre) continue;
        if (leaf[G[v][i].dst]) res += G[v][i].cost;
        else {
            res += dfs(G, leaf, G[v][i].dst, v) + G[v][i].cost*3;
        }
    }
    return res;
}

int main () {
    int n;
    while (cin >> n, n) {
        vector< vector<E> > G(n);
        vector< vector<int> > d(n, vector<int>(n, 1<<28));
        vector<int> t(n), v(n);
        for (int i = 1; i <= n-1; i++) {
            cin >> t[i];
            t[i]--;
        }
        for (int i = 1; i <= n-1; i++) {
            cin >> v[i];
        }
        for (int i = 1; i <= n-1; i++) {
            G[i].push_back(E(t[i], v[i]));
            G[t[i]].push_back(E(i, v[i]));

            d[i][t[i]] = d[t[i]][i] = v[i];
        }
        for (int i = 0; i < n; i++) d[i][i] = 0;
        vector<bool> leaf(n);
        for (int i = 0; i < n; i++) {
            if (G[i].size() == 1) leaf[i] = true;
        }
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (!leaf[i]) {
                sum = dfs(G, leaf, i, -1);
                break;
            }
        }
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }
        int ans = sum;
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                if (leaf[i] || leaf[j]) continue;
                ans = min(ans, sum - d[i][j]);
            }
        }
        cout << ans << endl;
    }
}

★結果
＞　http://icpc.iisf.or.jp/2014-waseda/domestic/results/
5完23位で恐らく国内予選通過。大学で２チーム国内予選通過が目標だったので目標達成。nekonyaso強い。

★所感
2年連続学内2位（共に30位くらい）で予選落ちしていたため、今年こそはという気分だった。@no15_rennneと@inu_hir0shiは今年が最後のICPCだったため、引退が伸びてよかったかなというところ。チーム戦は最高に楽しい！