Hatena::Grouptopcoder

kohyatohの日記

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

2011-12-13

team WAKABAでした練習のまとめ

| 00:32

この記事はCompetitive Programming Advent Calendar 13日目の参加記事です。

ICPC2011にteam WAKABAとして参加し、チームで練習して結構良い感じだったので、そのまとめです。

(1)具体的に何をしたか?、 そして (2)得られた経験則(効率のよい練習/努力の報われない練習について)と続きます。

競技プログラミングにはある程度慣れたけど、伸び悩んでしまった、というような人に読んでもらえると幸いです。


ちなみに、team WAKABAのメンバーは、練習開始時(2010年7月頭)からICPCアジア地区予選直前(2011年11年頭)で、

OgieKako: 2116 -> 2766

rankalee: 1592 -> 2027

kohyatoh: 1548 -> 2314

TopCoderのレートがインフレしたので、割と効果のある練習だったと思います。*1


(1)具体的に何をしたか?

Tracによると、第一回練習は2010年7月11日でした。

夜10時頃にTopCoder上のアリーナに三人集まり、毎回1時間15分+5分+15分の模擬SRMをしました。

これを2011年4月ぐらいまでで計109回やっています。

自分の場合、最初の頃は500は手も足もでなかったのですが、他の人のコードを見たりしながら、だんだんと解ける気がするようになってきました。


その後国内予選が近づくと、日曜日に集まって5時間コンテストを解く方向にシフトしました。

このときはSGUのvirtual contestsを使っています。

時間切れのあと、解けなかった問題を議論したり、自分以外のチームメイトが解いた問題について教えてもらったりしていました。


なんとか国内予選を突破した後は、TCOやらの問題を解いたりしていました。


夏休みは、上海交通大学の地獄の合宿のように追い込みをする絶好の時期ですが、(主に自分のせいで)なかなかチームの予定が合わず、あまり練習できませんでした。申し訳ないです...


本格的にリブートしたのはOB/OG会の夏合宿以降で、ICPC地区予選をかなり意識した練習をやりました。

予定の合う夜には集まって幾何問題を解き、日曜日に本番過去問、OB/OG会の過去問を本番形式(3人でパソコン1台)でやりました。


そして迎えたICPCアジア地区予選、来年は大物チームがでるとの情報もあり、世界に行けるとしたら今年しかない!という覚悟で望みました。

.

.

.

...結果は惨敗。世界は広いのでした。(ていうかレートが3人合計で7500あるチームとか、白い恋人のいるチームとか無理です...)


ただ、個人としては実力を出しきった上での負けだったので、あまり後味は悪くなかったです。

OgieKakoさんはEclipseの件がかなり応えていましたが...


また、上記とは別に、各自個人練習もやってました。

自分はPKUを400問ぐらい?解きましたが、そこまで意味はなかった気がします。(次で述べる「努力の報われない練習」でした。)


(2)効率の良い練習/努力の報われない練習

1年やって痛感したのは、強くなるのに近道はない、ということでした。

地道な練習が実は一番効率がいい練習です。


例えば、わからない問題についてその1問を1日中考える、とかは、一見非効率に見えてとても良い練習でした。これは、結局解けないとしても、答えを見た時の感動or悔しさが半端なく、脳にしっかりと焼き付くからです。

すぐに答えを見てしまうと、「写しただけ」になってしまって記憶に残りません。


また、解けた問題でも、他の人の解答を読み、より良い解を目指して自分のコードを改良する、というのも効果的でした。

解法をチームメイトと議論するのも、解法の理解が深まって良かったです。


逆に努力の報われない練習の極端な例が、「早く、たくさん」問題を解くことです。

この方針は、(心が弱いと)簡単な問題を優先して解く方向に心理的圧力がかかり、難しい問題をあまり解かなくなってしまいます。

簡単な、解けるとわかっている問題を解いても、ただの「確認」にしかならないので、あまり意味がありません。

数学者に百ます計算をやらせるようなもので、たまにはいいかもしれませんが、百ます計算ばかりしていてもある日突然何かの定理が証明できるようになったりはしません

自分にはちょっと無理そうかな、ぐらいの難しめの問題を解いてこそ、実力がアップするみたいです。


最後に、PKUなんかで明らかにめんどくさそうな問題(誤差ゲーの幾何とか、実装問題とか、枝刈り探索とか)を開いた時、見なかったことにしてそっと閉じるのも良くないです。同種の問題が本番で出たときに死ぬほど後悔するハメになります。


(3)まとめのまとめ
  • 競技プログラミング未経験者の方: この記事見ても尻込みはしないでください! 問題解くの楽しいですよ?
  • ICPC世界大会に出場されるみなさん: 頑張ってください!
  • 来年のICPCに出場されるみなさん: また来年に向けて一緒に頑張りましょう!

team WAKABAで結構チーム練習の良さを感じたので、ICPCチーム内だけじゃなくて、他の人とも一緒に練習できたらいいなぁ、とか思ってます。

興味のある方は@kohyatohまでよろしく!

*1:その後落ちてんじゃん、とかのツッコミはなしで...

2011-05-04

SRM505

| 03:36

ソース・成績(要ログイン)

Easy300RectangleAreaOpened数学ではない
Medium500SetMultiplesOpenedsqrt
Hard1000PerfectSequences2Unopened-

惨敗。

負けるとブログに書く事は少なくなります。


20:15 Easy

n*m+1個の連立方程式で、未知数がn+m+α個で...とか考え出した時点で死亡。


20:55 Medium

Easyを諦めて開くも、計算量の計算をミスって死亡。


21:20 Challenge

300で正解のコードに対して反例を探していて死亡。


結果

Opened/Opened/Unopened +0/-0

0 + 0 + 0 + 0 = 0 306位 (部屋9位)

2253 -> 2118

黄色に戻りました。


反省

ここのところ簡単な回が続いていたので、なんか甘く見ていた気がする。

この300は解ける気がしないけど、500は解けるべき。

なんか全体的に思考がバグってた気がする。

2011-04-28

CodeChef April Cook-Off

| 07:33

結果

AThe Grand Cook OffAC (02:24)確率
BProduct of Digits AgainWA/TLE数学?
CInternet Media TypesAC (00:44)やるだけ
DFrosting CupcakesOpened??
EA Prime ConjectureAC (00:52)やるだけ


00:45

@nico_shindanninさんのツイートで存在を知り、CodeChefに登録。


01:00 A (WA)

とりあえずAから。

期待値の問題だけど、線形性は使えないタイプ。

それぞれの事象の確率を求めることを考える。


参加者を、ブロックAとブロックBに分けて、ブロックAの優勝者とブロックBの優勝者の得点の差を求める、と置き換えて良い。

ブロックAの優勝者の得点が分かれば、それを全体から引くことでブロックBの優勝者の得点も分かる。

なので、

dp[a] := ブロックAの優勝者の得点がaになる場合の数

とかやればよさそう。

で、これはDPで求められる。

書く...サンプル合わない。


サンプルを紙に書いて確かめたところ、ブロックAの参加者の数によって、行われる試合の場合の数が異なるのを考慮に入れないといけないらしい。

手計算では、(ブロックAの参加者の数)!*(ブロックBの参加者の数)!を掛ければよさそう。(適当)


書き直す...サンプル通った。

提出...WA.

仕方がないので他の問題へ。


01:35 C, E

この辺はやるだけ。


02:00 B (WA/TLE)

BとDを見て、まだBのほうがとっつきやすそうだったのでBを考える。


基数を決めれば、それで与えられた文字列をデコードし、因数分解してそれを生み出す最小の整数を求めることはできる。

そこは書けて、サンプルもあったけど、基数の範囲を決める方法がわからず。

適当に1500までとか決め打ちで投げて、WATLEを行ったり来たりしていた。


03:00 A

もう一度再検討してみる。

直感的にはよさそう。どこが間違えてるのか...

全体の場合の数は結構大きい数になるので、誤差が出ているのかな...と思って、計算の順序とかいじってみたけど相変わらずWA.


終了直前にダメもとでdp部分をlong longからdoubleに変えたら通った!

参加者の数が最大で100人であることをすっかり忘れてlong long溢れしていた。ひどい。


結果

AC/WA/AC/Opened/AC

1 + 0 + 1 + 0 + 1 = 3 16位


残念。でも楽しかったです。


ソース

A

#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define mp make_pair
#define foreach(it, c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
typedef long long Int;
#define INF MY_INFINITY

int n;
double cnt[101][101];

double C(int n, int k) {
    double r = 1.0;
    rep(i, k) r = r*(n-i)/(i+1);
    return r;
}

int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        memset(cnt, 0, sizeof(cnt));
        cnt[0][0] = 1;
        scanf("%d", &n);
        int sum = 0;
        rep(i, n) {
            int a;
            scanf("%d", &a);
            for(int j=i; j>=0; j--) for(int k=100-a; k>=0; k--) {
                cnt[j+1][k+a] += cnt[j][k];
            }
            sum += a;
        }
        LOG(sum);
        double ans = 0;
        for(int i=1; i<n; i++) {
            rep(j, 101) ans += (double)abs(j-(sum-j))*cnt[i][j]/C(n, i);
        }
        printf("%.6f\n", ans/(n-1));
    }
    return 0;
}

C

#define mp make_pair
#define foreach(it, c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
typedef long long Int;
#define INF MY_INFINITY

int N, Q;

int main() {
    cin >> N >> Q;
    map<string, string> types;
    rep(i, N) {
        string ex, t;
        cin >> ex >> t;
        types[ex] = t;
    }
    rep(i, Q) {
        string f;
        cin >> f;
        unsigned ix = f.rfind('.');
        if(ix==string::npos) cout << "unknown" << endl;
        else {
            string ex = f.substr(ix+1);
            LOG(ex);
            if(types.find(ex)!=types.end()) cout << types[ex] << endl;
            else cout << "unknown" << endl;
        }
    }
    return 0;
}

E

#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define mp make_pair
#define foreach(it, c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
typedef long long Int;
#define INF MY_INFINITY

int nop[1000000];

int main() {
    vector<int> ps(1, 2);
    for(int i=3; i<1000000; i+=2) if(nop[i]==0) {
        ps.push_back(i);
        if(i<1000) for(int j=i*i; j<1000000; j+=i) nop[j]=1;
    }
    LOG(ps.size());
    rep(i, 5) LOG(ps[i]);
    for(;;) {
        int a;
        scanf("%d", &a);
        if(a==0) return 0;
        bool found = false;
        for(int i=0; ps[i]*ps[i]*ps[i]<a; i++) {
            int b = a-ps[i]*ps[i]*ps[i];
            for(int j=0; ps[j]*ps[j]<b; j++) {
                if(binary_search(ps.begin(), ps.end(), b-ps[j]*ps[j])) {
                    printf("%d %d %d\n", b-ps[j]*ps[j], ps[j], ps[i]);
                    found = true;
                    goto end;
                }
            }
        }
end:
        if(!found) printf("%d %d %d\n", 0, 0, 0);
    }
}

2011-04-25

Codeforces Beta Round #69

| 11:46

結果

AHeroesAC (00:15)総当り
BFalling AnvilsAC (00:42)受験数学
CBeavermuncher-0xFFAC (01:06)貪欲
DDomino CarpetAC (01:55)2段DP
EMartian Food--

今更ながら。


A Heroes

3^7を総当りするだけ。


B Falling Anvils

テストででそうな問題。

これ日本人有利なんじゃね?とか思いながら解いてだしたけど、

aまたはbが0のときの例外処理を忘れてて3回ぐらい撃墜された。


C Beavermuncher-0xFF

木構造なので、親より子を先に計算するタイプっぽい。


巣がA-B-Cとあって、ビーバーが余っている場合、A・B間の往復を優先しても、B・C間の往復を優先してもスコアは一緒。

なのでビーバーが余った場合、親・子間より子・孫間の方を優先させてよい。

あとは子が複数の場合とか、ビーバーが足りない場合とかに対処する。


D Domino Carpet

横向きのダイスは縦方向にずれて重ならない、という条件があるので、縦に区切ってDPすればよい。


E Martian Food

見てない。


結果

AC/AC/AC/AC/Unopened +0/-0

470 + 682 + 1104 + 1030 + 0 + 0 = 3286 21位 (部屋2位)

2069 -> 2168


ソース

なんか最近ソースが適当すぎ..

A Heroes

#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define mp make_pair
#define foreach(it, c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
typedef long long Int;
#define INF (1LL<<60)

char heroes[7][16] = {"Anka", "Chapay", "Cleo", "Troll", "Dracul", "Snowy", "Hexadecimal"};
int of(const string& s) {
    rep(i, 7) if(s==heroes[i]) return i;
    return -1;
}

int g[8][8], to[8], cnt[3], ex[3], dx[3];

int main() {
    int n;
    cin >> n;
    rep(i, n) {
        string a, b, _;
        cin >> a >> _ >> b;
        int aix=of(a), bix=of(b);
        g[aix][bix] = 1;
    }
    rep(i, 3) cin >> ex[i];
    int nn = 1;
    rep(i, 7) nn *= 3;
    LOG(nn);
    Int minx=INF, maxy=0;
    rep(b, nn) {
        int p = b;
        rep(i, 7) {
            to[i] = p%3;
            p /= 3;
        }
        rep(i, 3) cnt[i] = 0;
        rep(i, 7) cnt[to[i]]++;
        int ok=1;
        rep(i, 3) if(cnt[i]==0) ok=0;
        if(!ok) continue;
        rep(i, 3) dx[i] = ex[i]/cnt[i];
        sort(dx, dx+3);
        int x=dx[2]-dx[0];
        int y=0;
        rep(i, 7) rep(j, 7) if(g[i][j] && to[i]==to[j]) y++;
        if(minx>x || (minx==x && maxy<y)) {
            minx = x;
            maxy = y;
        }
    }
    cout << minx << " " << maxy << endl;
    return 0;
}

B Falling Anvils

#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define mp make_pair
#define foreach(it, c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
typedef long long Int;
#define INF MY_INFINITY

int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        double a, b;
        scanf("%lf%lf", &a, &b);
        if(b==0) {
            printf("%.9f\n", 1.0);
            continue;
        }
        if(a==0) {
            printf("%.9f\n", 0.5);
            continue;
        }
        double ans = a*b;
        if(a<=b*4) {
            ans += a*a/8.0;
        }
        else {
            ans += a*b-2*b*b;
        }
        LOG(ans);
        LOG(a*b*2);
        printf("%.9f\n", ans/(a*b*2));
    }
    return 0;
}

C Beavermuncher-0xFF

#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define mp make_pair
#define foreach(it, c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
typedef long long Int;
#define INF MY_INFINITY

int n, s[101000], r[101000];
vector<int> g[101000];

Int rec(int at, int pre) {
    vector<Int> v;
    rep(i, g[at].size()) if(g[at][i]!=pre && r[g[at][i]]>0) {
        r[g[at][i]]--;
        v.push_back(rec(g[at][i], at));
    }
    Int cur = 0;
    if(r[at] < (int)v.size()) {
        sort(v.begin(), v.end());
        reverse(v.begin(), v.end());
        rep(i, r[at]) cur+=v[i]+2;
        r[at] = 0;
    }
    else {
        rep(i, v.size()) cur+=v[i]+2;
        r[at] -= v.size();
        rep(i, g[at].size()) if(g[at][i]!=pre) {
            Int df = min(r[at], r[g[at][i]]);
            r[at] -= df;
            cur += df*2;
        }
    }
    return cur;
}

int main() {
    scanf("%d", &n);
    rep(i, n) scanf("%d", s+i);
    rep(i, n) r[i] = s[i];
    rep(i, n-1) {
        int a, b;
        scanf("%d%d", &a, &b);
        a--, b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int st;
    scanf("%d", &st);
    cout << rec(st-1, -1) << endl;
    return 0;
}

D Domino Carpet

#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define mp make_pair
#define foreach(it, c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
typedef long long Int;
#define INF MY_INFINITY
#define MOD (1000000007LL)

char vonly[][3][4] = {
    {"..O","...","O.."},
    {"..O",".O.","O.."},
    {"O.O","O.O","O.O"},
};
char honly[][3][4] = {
    {"O..","...","..O"},
    {"O..",".O.","..O"},
    {"OOO","...","OOO"},
};

int n, m;
char fie[1020][1020];
int of[250][250];
Int dp[300], dp2[300];
bool canv[300];

int main() {
    scanf("%d%d", &n, &m);
    rep(i, 4*n+1) rep(j, 4*m+1) scanf(" %c", fie[i]+j);
    rep(i, n) rep(j, m) {
        int v=2, h=1;
        rep(k, 3) {
            int ma=1;
            rep(x, 3) rep(y, 3) if(vonly[k][x][y]!=fie[4*i+1+x][4*j+1+y]) ma=0;
            if(ma) h=0;
        }
        rep(k, 3) {
            int ma=1;
            rep(x, 3) rep(y, 3) if(honly[k][x][y]!=fie[4*i+1+x][4*j+1+y]) ma=0;
            if(ma) v=0;
        }
        of[i][j] = v|h;
    }
    /*
    rep(i, n) {
        rep(j, m) printf("%d", of[i][j]);
        puts("");
    }
    */
    dp[0] = 1;
    rep(i, m) {
        dp[i+1] = 0;
        canv[i] = n%2==0;
        rep(j, n) if(of[j][i]==1) canv[i]=false;
        if(i==0) {
            if(canv[i]) dp[i+1] = dp[i];
        }
        else {
            dp2[0] = 1;
            rep(j, n) {
                dp2[j+1] = 0;
                if((of[j][i]&1) && (of[j][i-1]&1)) dp2[j+1] = dp2[j];
                if(j>0) {
                    if((of[j][i]&2) && (of[j][i-1]&2)
                        && (of[j-1][i]&2) && (of[j-1][i-1]&2)) {
                        dp2[j+1] = (dp2[j+1]+dp2[j-1])%MOD;
                    }
                }
            }
            LOG(dp2[n]);
            dp[i+1] = (dp2[n]*dp[i-1])%MOD;
            if(canv[i]) {
                dp[i+1] = (dp[i+1]+dp[i])%MOD;
                if(canv[i-1]) {
                    dp[i+1] = (dp[i+1]-dp[i-1]+MOD)%MOD;
                }
            }
        }
        LOG(dp[i+1]);
    }
    cout << dp[m] << endl;
    return 0;
}

2011-04-18

SRM 503

| 10:16

ソース・成績(要ログイン)

Easy250ToastXToastAC (24min)気づくだけ(それが一番...)
Medium500KingdomXCitiesandVillagesAC (26min)期待値の線形性
Hard1000KingdomXEmergencyStaircaseOpened?


25:00 部屋割り

Room 21.

普通。


25:05 Medium

別に、心を入れ替えたとかそんなのじゃなくて、普通にマウス操作をミスってMediumを開いてしまった...


問題を読むと、「期待値の線形性」を知っていればさくっとできそうな問題。

一つ一つの村に対し、その村のために建設される道路の長さの期待値を求め、合計すればいい。

ある村に対し、他の村が前にくる確率は対称性より1/2。

それを累乗すればいい...と思ったら答えが違う。


村が3つの場合について書き出して調べてみる。確率の計算が思ったほど簡単ではない。

(自分にしては)頑張って数式を導き出し、直して提出。300点。


もう少し、数学的直感力みたいなのを身につけたいなぁ...


25:30 Easy

他の人のスコアを見る限り、そんなに簡単そうではない。


読む...ややこしい!

DPっぽい...それとも貪欲?

とりあえず貪欲書く->サンプルの最後のが合わない。

え、これ何で2になるの? 3じゃないの...


......結構時間がかかって、ようやく意味がわかる。

トーストの種類は高々2で良い。

なので、答えが-1と1になる条件のみ調べればいい。


書く->提出。160点。あちゃ..


26:00 Hard

いやいくら何でも15分でHardはムリでしょう。とか思いながら。

時間切れ。


26:20 Challenge

250で、{4},{4}とか入れたら結構落ちるんじゃないかなぁ、と思いながら探す。

案の定いたので投入したら、入力がinvalidだとか言われた。

問題親切だな...


その他は落とすケースが見つからず。


結果

AC/AC/Opened 0/0

160.68 + 309.76 + 0 + 0 = 470.44 79位(部屋2位)

2217 -> 2253


停滞中。


復習

まだまだ解くのが遅い。


250とか、もっと簡単に解けるだろー、とか疑ったほうがいいかもしれない。