hogecoder

tsutaj 競技プログラミングの記録

TopCoder SRM 700 Div 2

TopCoder

記念すべき TopCoder SRM 700 に無理やり参加しました。

今まで Div2ぐらし！どころか、はいいろぐらし！ だったんですが、今日でやっと緑色になりました。TopCoderのレーティング維持するのは難しそうなのでこれからも頑張ります。

では適当に振り返ります。(載せているコードはコンテスト中に書いたものなので、不必要なものがあったり汚かったりしても怒らないでね)

Xylophone (Easy)

問題 → TopCoder Statistics - Problem Statement

これはほんとにやるだけ。気をつけるのは剰余取ることくらい？

class Xylophone {
    public:
    int countKeys(vector <int> keys) {
        int cnt[7] = {};
        rep(i,0,keys.size()) cnt[keys[i] % 7]++;

        int ans = 0;
        rep(i,0,7) if(cnt[i] != 0) ans++;
        return ans;
    }
};

XMarksTheSpot (Med)

問題 → TopCoder Statistics - Problem Statement

Medにしては親切な問題だった。けどちょっとめんどいかもしれない。

まず、 '?' の出た座標をvectorとかで管理しておきます。次に 'O' についてですが、 'O' が出現した座標の中で「最も左上」にあるものと「最も右下」にあるものを覚えておけば、現時点でお宝がある可能性がある長方形領域を把握できるので、その2点を求められるように処理します。

'?' は最大で19しかないので、 '?' が 'O' であるか '.' であるかを全列挙して問題ありません (最大でも 2^{19} = 524288 通りなので、間に合います)。あとはビット演算の力を借りて長方形領域がどう変わるかを判定して答えを足していきましょう。

class XMarksTheSpot {
    public:
    int countArea(vector <string> board) {
        pii lu = pii(INF,-1), rd = pii(-1, INF);
        vector<pii> question;
        rep(i,0,board.size()) {
            rep(j,0,board[i].size()) {
                if(board[i][j] == 'O') {
                    lu.fr = min(lu.fr, j);
                    lu.sc = max(lu.sc, i);
                    rd.fr = max(rd.fr, j);
                    rd.sc = min(rd.sc, i);
                }
                if(board[i][j] == '?') {
                    question.pb(pii(j,i));
                }
            }
        }

        ll x, y, ans = 0;
        x = (ll)rd.fr - lu.fr + 1;
        y = (ll)lu.sc - rd.sc + 1;

        int s = question.size();
        if(question.size() == 0) ans += x * y;
        else {
            rep(n,0,1 << s) {
                pii lun = lu, rdn = rd;
                ll xn, yn;
                rep(k,0,s) {
                    if(n >> k & 1) {
                        int j = question[k].fr;
                        int i = question[k].sc;
                        lun.fr = min(lun.fr, j);
                        lun.sc = max(lun.sc, i);
                        rdn.fr = max(rdn.fr, j);
                        rdn.sc = min(rdn.sc, i);
                    }
                }
                xn = (ll)rdn.fr - lun.fr + 1;
                yn = (ll)lun.sc - rdn.sc + 1;
                ans += xn * yn;
            }
        }
        return ans;
    }
};

XYZCoder (Hard)

問題 → TopCoder Statistics - Problem Statement

本番で解けず。あとでやります。

結果

解答状況

問題 時間 得点 (満点)
Easy 0:02:29.688 248.08 250.00
Medium 0:48:27.729 195.87 450.00
Hard - 0.00 900.00
(Challenge) - 0.00 -
(Sum) - 443.95 1600.00

順位 / レーティング

Ranking: 42nd / 287
Rating: 805 -> 930 (+125)

反省

Med解くのが遅い (予想以上に点が取れなくてびっくりした) 最初長方形領域を求めるのに四隅全部把握しようとしてたしダメ。自分の部屋の人、けっこうMedで落ちてたのにChallengeで1個も拾えなかったしダメ (Challengeの能力ってどうやって身につけたらいいんだろう・・・)

早解きの力、今まで考えていたより相当大事だなと思い知ったので、今度からは解答時間とかも記録するようにしたい。

あと何故か知らないけど、前にプラグイン入れたはずなのに全部忘れられてて慌てて入れなおした。コンテスト30分前くらいから用意してて本当に良かった・・・。

次出る時までに少しでもいいから過去問を解いておきたい。