ICPC Domestic 2014

ICPC 国内予選

今日の16時30分からICPCの国内予選に参加してきました. 7問中6問を解いて,215チーム中8位でした.(順位表)

自分が担当した問題はAとD(とC)だった. 序盤は調子が良かったんだけど,Cで泥沼にハマってしまって一時は通過が危ぶまれるくらい危なかった. とはいえ,チームメイトが大活躍してくれたおかげである程度の順位を取ることができ,無事アジア予選に行くことができる.

ログ

どんな感じで問題を解いたかの記録を適当に書いてみた.

A 問題

eha君がテンプレートを書いている間に,僕がA問題を読みnatsugiri君がB問題を読むという戦略. 実装が楽そうな方針が見えたのでそれを書いた. 5分ごろにAC.

B 問題

Bはチームメイトが書いた.実装するだけ.19分頃にAC.

D 問題

B問題を書いている間に僕がD問題,eha君がC問題を読んでいた. DもCも一応方針が立ったけど,Dはすぐ書けると僕が主張してパソコンを奪い取る. 28分頃にAC.

E 問題

Cと同時並行で書いた.

AOJでみたことあるよねー.みたいな話をしながら 最初チームメイトは木DPと言っていたけど,少し考えて,もっとよさ気な方針を出して解いてくれた. 50分頃にAC.

C 問題

C問題を考えていたチームメイトに方針を聞いてみたら,解法が難しい幾何っぽく聞こえてなんかやばそうだとおもった. ということを伝えてみたら,別の方針を出してくれた. それも自分がやったことない方法だったので,「よくわからない.誤差は大丈夫なのか」と思ったけど, なんやかんやでその方針で行くことに.

チームメイトが書いてみたらサンプルは通ったんだけど, 提出したら通らない (1WA)

「やっぱり誤差が原因じゃないの」と言って別の解法を提案してみた.(本当はテストケースの終了条件が間違ってて,多分解法は正しい…….最悪.) その解法を書いてみたはいいものの書き終わった後に,全然間違ってることに気づく.

なんか色々考えてみるとよさそうな方針が浮かんだのでもう一回書く, が,バグりまくって,デバッグに時間がかかる. 書けたので,テストケースに通してみる.最初に提出したやつとDiffを取るとほとんど一致している……. 「誤差じゃないのか……?」とか思いつつ提出→WA.

さっきのコードとほとんど答え一緒だし解法は間違ってなさそう,何がわるいんだろう……と思いながらいろんなケースを考える. で,ここでn = 0のときの処理が間違ってることに気づく.(ふたりとも間違えてしまうとは…….) 直して提出.135分頃にAC.

F 問題

二人がC問題と戯れている間に, natsugiri君がF問題を考えて紙コーディングまで終わらせていた. 移すだけとか言って,本当に1回もバグを出さずに17分ぐらいでACしてしまった.すごい. 149分頃にAC.

G 問題

あと30分だし解ける気がしない. ペイントで絵を書いて,塗りつぶしツールを使うと辿れるかどうか分かるよ,とか言っているうちにコンテストが終了.

反省

C問題以外は,おおよそ成功と言ってよさそう. C問題は嘘解法を編み出したりバグを埋め込んだりして無駄に時間を使ってしまった反省が大きい. こんなかんじの問題で泥沼にハマってしまったときはどうすればいいのか未だによくわからん.

ソースコード

コンテスト中に自分が書いたコード.

A問題

int main(){
    int x, y, s;
    while(cin >> x >> y >> s && x) {
        int ans = 0;
        for(int a = 1; a <= 2000; a++) {
            for(int b = 1; b <= 2000; b++) {
                int y1 = a * (100 + x) / 100;
                int y2 = b * (100 + x) / 100;
                if(y1 + y2 != s) continue;
                int z1 = a * (100 + y) / 100;
                int z2 = b * (100 + y) / 100;
                ans = max(ans, z1 + z2);
            }
        }
        cout << ans << endl;
    }
}

D問題

string s;
vector<string> ans;
void rec(int idx, vector<bool> state, string sum) {
    if(idx == s.size()) {
        ans.push_back(sum);
        return ;
    }
    char c = s[idx];
    if(state[c - 'a']) {
        rec(idx + 1, state, sum + c);
    }
    if(c + 1 <= 'z' && !state[c + 1 - 'a']) {
        state[c + 1 - 'a'] = true;
        rec(idx + 1, state, sum + string(1, (c + 1)));
    }
}

int main(){
    while(cin >> s && s != "#") {
        ans.clear();
        vector<bool> state(26, false);
        state[0] = true;
        rec(0, state, "");
        cout << ans.size() << endl;
        sort(ans.begin(), ans.end());
        if(ans.size() <= 10) {
            REP(i, ans.size()) cout << ans[i] << endl;
        } else {
            REP(i, 5) cout << ans[i] << endl;
            REP(i, 5) cout << ans[ ans.size() - 5 + i] << endl;
        }
    }
}

C 問題

int n;
int r;
const int MAX_X = 60;
const int base = MAX_X / 2;
bool ok(double y, vector<int> height, vector<int> block) {
    /*
    for(int x = -r + base + 1; x <= r + base - 1; x++) {
        double c_h = sqrt(r * r - (x - base) * (x - base));
        if(c_h > height[x]) {
            printf("bad x = %d c_h = %f height[%d] = %d\n", x - base, c_h, x, height[x]);
            return false;
        }
    }
    */
    REP(i, MAX_X) {
        int x1 = i - base;
        int x2 = i - base + 1;
        if(-r <= x1 && x2 <= r) {
            double ch1 = sqrt(1.0 * r * r - (x1) * (x1)) + y - r;
            double ch2 = sqrt(1.0 * r * r - (x2) * (x2)) + y - r;
            if(x1 == -1) {
                //printf("-1 : y = %f x1 = %d x2 = %d block[%d] = %d\n", y, x1, x2, i, block[i]);
                //printf("-1 : ch1 = %f ch2 = %f\n", ch1, ch2);
            }
            if(ch1 > block[i] || ch2 > block[i]) {
                //printf("bad : y = %f x1 = %d x2 = %d block[%d] = %d\n", y, x1, x2, i, block[i]);
                //printf("bad : ch1 = %f ch2 = %f\n", ch1, ch2);
                return false;
            }
        }
    }
    return true;
}

int main(){
    while(cin >> r >> n && (r > 0)) {
        vector<int> xl(n), xr(n);
        vector<int> h(n);
        vector<int> block(MAX_X, 0);

        REP(i, n) {
            cin >> xl[i] >> xr[i];
            xl[i] += base;
            xr[i] += base;
            cin >> h[i];
            for(int x = xl[i]; x < xr[i]; x++) {
                block[x] = max(block[x], h[i]);
            }
        }

        vector<int> height(MAX_X);
        REP(i, MAX_X - 1) {
            height[i + 1] = min(block[i + 1], block[i]);
        }
        /*
        REP(i, MAX_X) {
            printf("block[%d] = %d\n", i, block[i]);
        }
        */
        double lb = 0, ub = 100;
        REP(_, 60) {
            double y = (lb + ub) / 2;
            if(ok(y, height, block)) {
                lb = y;
            } else {
                ub = y;
            }
        }
        double ans =  (lb + ub) / 2;
        printf("%.9f\n", ans);
    }
}