Hatena::Grouptopcoder

kohyatohの日記

 - 非数学系な人のTopCoder参加記です。

2010-12-26

hos' Xmas Contest 2010

| 14:42

hos' Xmas Contest 2010の夜の部に参加。


22:00 Start

22:00 A

数学っぽい...?

とりあえず、最大の場合については、距離としてc+d, 最小の場合については距離としてabs(c-d)を考えればよい。

最大の場合については、左側の家がaの木の前にあるとき、bの木の前にあるときの二つを調べ最大をとる。

最小の場合については、左側の家がaの木の前よりわずかに右にあるとき、bの木の前よりわずかに右にあるときの二つを調べ最小をとる。

場合分けが複雑だが、「わずかに右にあるとき」の数は、「ちょうど前にあるとき」の数-1なので、少しは簡単になる。

書いて提出->60% Accepted.あれ?


int溢れしてないかとかいろいろ調べたり、問題文を読み返したりしていると、「二つの家は異なる場所にある」という文言が。つまり、c==dのときは最小の場合についてabs(c-d)の代わりにc+dで調べないといけない、ということ。

書く->AC.

問題文よく読まないと...


22:30 B

構文解析。とはいえ偶奇を調べるだけ&演算子が+,-のみなので、全ての数字の和をとって奇数か偶数かを調べればいいのみ。((a+b)の偶奇==(a-b)の偶奇より)

書く->提出。AC.


22:40 C

グラフの問題。部分木を求める問題で複雑そう...とりあえず飛ばす。


22:45 D

費用最小化問題?線形性がないのでかなり難しそう。

(現在の位置、買ったプレゼントの個数)でDPを考えるが、買ったプレゼントの個数は最大でQ/2までは行くので状態数が爆発して無理。とりあえず飛ばす。


22:50 E

幾何ゲー。無理です。次へ。


22:52 F

表を修正する問題。ワケわからないので、次へ。


22:54 G

数列の個数を求める問題。サンプルが0のみなので0を送ればいいかと思ったけど、ちょっと考えると反例があったのでやめる。次へ。


22:58 H

A~Gのうちどれの入力か判別せよ、という問題。死ぬほどめんどくさそうだが、めんどくさいだけみたいなので詰まったらやることにする。


23:00 C

とりあえずC~HではCが一番簡単そうなのでCをやる。

問題分をよく見ると、「使わないもの」の個数が10以下、と書いてあるので、どれを使わないかを2^10で調べればよさそう。どれを使わないかを決めたら、あとは最小木の問題であり、簡単。


最小木をプリム法で実装して、書く->10% Accepted.

つまらないバグだったので直して送信すると、80% Accepted. 2つのテストケースでTLEしてる。


ここから定数倍の工作が始まり、結局隣接行列を隣接リストに変えたら通った。

(今考えると、プリム法ではなくクラスカル法にすることで計算量落ちるんだよね...)


23:50 D

もう一度いろいろ考えてみる...も、思いつかず。

詰まったのでHに移る。


24:10 H

最初の行をみて、書いてある数字の個数で場合分けすればいいっぽい。

1個->B,E (嘘。Bは特別扱いしなければならなかった)

2個->C

3個->F

4個->A/D/G

さらに、A/D/Gについて、2行目の個数が3個ならDであり、4個ならA,Gである。

AとGの区別については、フォーマットとしては全く同一なので、数値の範囲を調べる。

書く->提出。50% Accepted.


なんだろ、と思ってもう一度A~Gの問題文をよく見てみると、AとGでテストケースの上限数が違う!

それを直して提出-> 10% Accepted. バグを直して 90% Accepted.


もう一度、A~Gの問題文をよく見てみるが、バグは見られない。

Bの処理が若干不安になったので、手入力で調べてみると、23-34とかがCとして判断されてる。

どうやら、sscanf("23-34", "%d%d%d%d", ...)は1を返すと思いこんでいたのが、実は2を返しているよう。scanf()のフォーマットに合わなかった時の挙動とか知らないし...

スペース、数字以外の文字があったら強制的にBにするようにして、再提出。->WA. バグを直してAC.


25:20 D

再々チャレンジ。

いくら考えてもわからないので、貪欲でできないかなー、とか思って、貪欲してみる。...書いてる途中でコンテスト終了。ちなみに貪欲は結局WAでした。


Result

RankABCDEFGHScore/Time
17100/2100/1100/6---/----/----/----/-100/7400/688

Review、というか感想というか

D~Gで部分点が取れなかったのが痛かったです。というのも、Hで手こずってたからなんだけど...

次はD~G(レベルの問題)で100点を取れるよう精進します。

というか、高校生の方々がなんかべらぼうに強いですね...


Source

おまけ。提出時のソースです。

A

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
#define rep(i, n) for(int i=0; i<(int)(n); i++)

int calc(int w, int a, int b) {
    int ans=0;
    ans += w/(a+b)+1;
    if(w>=b) ans+=(w-b)/(a+b)+1;
    return ans;
}

int main() {
    int a, b, c, d;
    for(;;) {
        scanf("%d%d%d%d", &a, &b, &c, &d);
        if(a==0) return 0;
        int ansmin = min(calc(abs(c-d), a, b), calc(abs(c-d), b, a))-1;
        if(c==d) ansmin = min(calc(abs(c+d), a, b), calc(abs(c+d), b, a))-1;
        int ansmax = max(calc(abs(c+d), a, b), calc(abs(c+d), b, a));
        printf("%d %d\n", ansmin, ansmax);
    }
}

B

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
#define rep(i, n) for(int i=0; i<(int)(n); i++)

char expr[20000];

int main() {
    for(;;) {
        scanf("%s", expr);
        if(*expr=='#') return 0;
        int ans=0;
        for(char *p=expr; *p; p++) {
            if('0'<=*p && *p<='9' && !('0'<=*(p+1) && *(p+1)<='9')) {
                ans = (ans+*p-'0')%2;
            }
        }
        puts(ans ? "ODD" : "EVEN");
    }
}

C

Sは無視してください。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <utility>
using namespace std;
#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define mp make_pair

int n, m, sig[200], use[200];
vector<pair<int, int> > g[200];
int INF=2000000000;
set<pair<int, int> >::iterator pre[200];

int mintree() {
    int nk=0;
    rep(i, n) nk+=use[i];
    set<pair<int, int> > S;
    rep(i, n) pre[i] = S.end();
    priority_queue<pair<int, int> > q;
    rep(i, n) if(use[i]) {
        //S.insert(mp(0, i));
        q.push(mp(0, i));
        break;
    }
    int ck=0, ans=0;
    while(ck<nk && !q.empty()) {
        pair<int, int> v=q.top();
        q.pop();
        if(use[v.second]==0) continue;
        use[v.second]=0;
        //pre[v.second]=S.end();
        ans-=v.first;
        ck++;
        rep(i, g[v.second].size()) if(use[g[v.second][i].second]) {
            q.push(mp(-g[v.second][i].first, g[v.second][i].second));
        }
    }
    return ck<nk ? INF : ans;
}

int main() {
    for(;;) {
        scanf("%d%d", &n, &m);
        if(n==0) return 0;
        rep(i, n) scanf("%d", sig+i);
        rep(i, n) g[i].clear();
        rep(i, m) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            a--; b--;
            g[a].push_back(mp(c, b));
            g[b].push_back(mp(c, a));
        }
        int sn=0;
        rep(i, n) sn+=sig[i];
        int snn=1<<sn;
        int ans=INF;
        rep(d, snn) {
            int kk=0;
            rep(i, n) {
                if(!sig[i]) use[i]=1;
                else {
                    use[i] = ((1<<kk)&d)!=0;
                    kk++;
                }
            }
            ans = min(ans, mintree());
        }
        printf("%d\n", ans);
    }
}

H

Aの処理は無駄になってます。っていうか'G'っていう出力はありえないよねぇ。

#include <stdio.h>
#include <string.h>

char buf[30000];
int a, b, c, d;

bool is_a_valid() {
    return true;
}

bool is_g_valid() {
    if(a==0 && b==0 && c==0 && d==0) return true;
    if(a<=0 || 100000<a) return false;
    if(b<=0 || 100000<b) return false;
    if(c<=0 || a<c) return false;
    if(d<=0 || a<d) return false;
    return true;
}

int main() {
    for(;;) {
        gets(buf);
        if(buf[0]=='@' && strlen(buf)==20) return 0;
        int count = sscanf(buf, "%d%d%d%d", &a, &b, &c, &d);
        for(char *p=buf; *p; p++) {
            if((*p<'0' || '9'<*p) && *p!=' ') count=0;
        }
        int cl=1;
        char ans='?';
        if(count<=1) {
            while(buf[0]!='@') {
                if(buf[0]=='#') ans='B';
                else ans='E';
                gets(buf);
            }
        }
        else if(count==2) {
            ans = 'C';
        }
        else if(count==3) {
            ans = 'F';
        }
        else if(count==4) {
            bool ca=is_a_valid(), cg=is_g_valid();
            gets(buf);
            while(buf[0]!='@') {
                int ncount = sscanf(buf, "%d%d%d%d", &a, &b, &c, &d);
                cl++;
                if(ncount==3) {
                    ans='D';
                    break;
                }
                else {
                    ca&=is_a_valid();
                    cg&=is_g_valid();
                }
                gets(buf);
            }
            if(cl>21) cg=false;
            if(ans!='D') {
                if(ca && cg) ans='?';
                else if(ca) ans='A';
                else if(cg) ans='G';
            }
        }
        while(buf[0]!='@') gets(buf);
        printf("%c\n", ans);
    }
    return 0;
}