Hatena::Grouptopcoder

minus9dの記録

2013-10-20

Round #207 Div2

| 17:54 | Round #207 Div2 - minus9dの記録 を含むブックマーク はてなブックマーク - Round #207 Div2 - minus9dの記録

ox---。苦手な問題セットだった。


B. Flag Day

問題

n人のダンサーがいる。各ダンサーは赤か白か青かのドレスを着ている。ダンスがm回開かれ、各ダンスでは3人のダンサーが異なる色のドレスを着ているようにしたい。ただし、各ダンスでは、過去に踊ったことがあるダンサーは最大でも1人。各ダンサーのドレスの色を決定する。

本番

3彩色問題?と思って、同じダンスで踊るダンサー同士にエッジを張り、深さ優先探索で色を付けていくも処理が終わらず。

後で

「各ダンスでは、過去に踊ったことがあるダンサーは最大でも1人」という強い制約のことをよく理解できていなかった。後で書き直したコードは以下。

#include <iostream>
#include <sstream>
#include <string>
#include <cmath>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <numeric>

using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define FOREACH(i, n) for (__typeof((n).begin()) i = (n).begin(); i != (n).end(); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

#define pb push_back
#define mp make_pair

pair<int, int> other_color(int n){
    pair<int, int> ret;
    if (n == 1) {
        ret.first = 2;
        ret.second = 3;
    }
    else if (n == 2) {
        ret.first = 1;
        ret.second = 3;
    }
    else if (n == 3) {
        ret.first = 1;
        ret.second = 2;
    }
    return ret;
}

int main(void)
{
    int people, dances;
    cin >> people >> dances;

    vector<int> color(people+1);

    REP(i, dances){
        int l, m, n;
        cin >> l >> m >> n;

        if (color[l]){
            pair<int, int> others = other_color(color[l]);
            color[m] = others.first;
            color[n] = others.second;
        }
        else if (color[m]){
            pair<int, int> others = other_color(color[m]);
            color[l] = others.first;
            color[n] = others.second;
        }
        else if (color[n]){
            pair<int, int> others = other_color(color[n]);
            color[l] = others.first;
            color[m] = others.second;
        }
        else{
            color[l] = 1;
            color[m] = 2;
            color[n] = 3;
        }
    }

    FOR(i, 1, people+1){
        printf("%d", color[i]);
        if (i == people){
            printf("\n");
        }
        else{
            printf(" ");
        }
    }

    return 0;
}

C. Knight Tournament

問題

n人のナイトがm回戦って優勝者を決める。各戦いでは、l番目のナイトからr番目のナイトまでが戦ってx番目のナイトが勝ったという事実が与えられる。各ナイトが誰に負けたのかを出力する。

本番

どんなデータ構造を使えばよいのかさっぱり思いつかない。

後で

解説には2つの方法が示されている。1つ目は、std::set()を使って生き残っている兵士を管理する方法。2つ目は、生き残っている兵士をnext配列で繋ぐ方法。このとき経路圧縮を使って探索スピードを上げる。どちらも目から鱗である。

後者の方法を実装。最後のナイトの処理をうまく行う必要がある。今回は番兵を使った。

#include <iostream>
#include <sstream>
#include <string>
#include <cmath>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <numeric>

using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define FOREACH(i, n) for (__typeof((n).begin()) i = (n).begin(); i != (n).end(); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

#define pb push_back
#define mp make_pair


// 次に見に行くべきインデックスを保持
vector<int> next;

int getNext(int v){
    if(next[v] == v) return v;
    return next[v] = getNext(next[v]);
}

int main(void)
{
    int people, fight;
    cin >> people >> fight;

    // 最後の一個は番兵
    next.resize(people+2);
    FOR(i, 1, people+2){
        next[i] = i;
    }

    vector<int> answer(people+1);
    
    REP(f, fight){
        int l, r, x;
        cin >> l >> r >> x;

        int cur = getNext(l);

        while(cur <= r){
            if(cur == x){
                ++cur;
            }
            else{
                answer[cur] = x;
                next[cur] = cur + 1;
            }

            cur = getNext(cur);
        }
    }

    FOR(i, 1, people+1){
        cout << answer[i];
        cout << ((i == people) ? "\n" : " ");
    }

    return 0;
}

D. Xenia and Hamming

問題

文字列Xをn回繰り返した文字列と、文字列Yをm回繰り返した文字列とのハミング距離を求める

後で

具体例としてXが8文字(lenX = 8)、Yが6文字(lenY = 6)とする。

lenXとlenYとの最小公倍数は24。この24文字の間でのハミング距離をまず求める。

Xのi番目の文字と、Yのj番目の文字とがぶつかる条件は、以下の式で表せる。

i ≡ j (mod g)  (g は lenX と lenYの最大公約数)

文字列Yの文字列の各文字y_j (j = 0, ..., 5)について、r = j mod g を計算して、配列count[r][y_j]でカウントする。

文字列Xの文字列の各文字x_i (i = 0, ..., 7)について、r = i mod g を計算して、配列count[r][x_i]の数字を見て、ハミング距離をうまいこと計算する。

完全に理解できてないので、説明もうまくできない。

あとで書いたコードは以下

#include <iostream>
#include <sstream>
#include <string>
#include <cmath>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <numeric>

using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define FOREACH(i, n) for (__typeof((n).begin()) i = (n).begin(); i != (n).end(); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

#define pb push_back
#define mp make_pair

long long getGcd(long long a, long long b)
{
    while(1)
    {
        if (a == 0){
            return b;
        }
        b %= a;
        if (b == 0){
            return a;
        }
        a %= b;
    }
}


int main(void)
{
    ll n, m;
    cin >> n >> m;

    string x, y;
    cin >> x >> y;

    ll lenX = x.size();
    ll lenY = y.size();

    // gはlenXとlenYの最大公約数
    ll g = getGcd(lenX, lenY);
    // LはlenXとlenYの最小公倍数
    ll L = lenX * (ll)lenY / g;
    ll ans = L;

    vector< vector<int> > count(g);
    REP(i, g){
        count[i].resize(26, 0);
    }

    REP(j, lenY){
        count[ j % g ][ y[j] - 'a' ]++;
    }

    REP(i, lenX){
        ans -= count[i % g][x[i] - 'a'];
    }
    cout << (ans * (n * lenX / L)) << endl;
    
    return 0;
}

2012-08-19

Round #134 Div2

| 09:27 | Round #134 Div2 - minus9dの記録 を含むブックマーク はてなブックマーク - Round #134 Div2 - minus9dの記録

ooo--。R1593→R1677。解ける問題だけ早めに解けて87位と好順位。レーティングは順調にジグザグを刻んでいる。

A. Mountain Scenery

答が複数ありえるってところを読み落としていてどう解くのか分からなかったけど、それが分かれば難しくない。

Submission #2024048 - Codeforces

B. Airport

運賃がもっとも高くなる場合の運賃と、運賃がもっとも安くなる場合の運賃とを求める。シミュレーションすれば間違いがない。運賃がもっとも安くなる場合の運賃を求める場合、うっかり空席のない飛行機のチケットを買おうとしないよう注意。

他の人のコードを見ると、何やってるのか全然わからないのにもかかわらずシステムテストは通っているものがいくつかあった。Hackしなくてよかった…

Submission #2025169 - Codeforces

C. Ice Skating

新たにsnow driftを設置することなしに行き来することのできるsnow drift同士をすべて繋いで塊を作る。この操作でできた塊の数から1を引いたものが、新たに設置する必要のあるsnow driftの最小数となる。

Submission #2026237 - Codeforces

D. Blackboard Fibonacci

フィボナッチ数列の変則バージョン。全然分からなかったので総当りをやってみるができるわけない。

2012-07-03

Round #127 (Div. 2)

| 07:04 | Round #127 (Div. 2) - minus9dの記録 を含むブックマーク はてなブックマーク - Round #127 (Div. 2) - minus9dの記録

全然解けなかった回。

ox--- R1678→R1593(-85)。

A. LLPS

ある文字列が与えられる。この文字列から生成される、回文になっている部分文字列のうち、もっとも辞書順で最後に来る部分文字列を答える。

本番では総当たりで求めてしまったが、実際はもっと簡単に求めることができた。以下はSTLをうまく活用している例。

引用元:http://codeforces.com/contest/202/submission/1838706

int main()
{
    string s;
    cin >> s;
    char c = *max_element(s.begin(), s.end());
    int cnt = count(s.begin(), s.end(), c);
    while (cnt--) cout << c;
    cout << endl;

    return 0;
}

B. Brand New Easy Problem

実装するだけの問題…に思えたけど、以下のケースのときのnumber of inversionsを正しく計算できておらず、WA

4
a b c d
1
10 b c a b a d d d a a

いくつか解答を見た限りでは、Lesha's problemに含まれる単語をシャッフルしてできる並びのすべてについて、それが各Archiveの部分文字列になっているかどうかを判定し、部分文字列になっている場合にそのnumber of inversionを数えるのがよくある方針らしい。それに沿ってコードを書いたが、異常なはまり方をして1時間くらいかかってしまった…

http://codeforces.com/contest/202/submission/1848974

C. Clear Symmetry

問題文"Let's call matrix A clear if no two cells containing ones have a common side."で定義されるclearの意味がわからなくて、手をつけられず。結局、clearの意味は、行列の隣合う2つの要素が両方1になることはない、という意味だったようだ。

D. Guess That Car!

素朴にやると絶対時間が足りないのは分かるが、良い解法が浮かばず。計算量の大切さがよく分かる問題だった。あとでnodchipさんの解答(http://topcoder.g.hatena.ne.jp/nodchip/20120630)を参考にコーディング。しかしまあ自分で書くと何と無駄の多いことか。表記法もばらばらすぎて泣けてくる。

http://codeforces.com/contest/202/submission/1849141

2012-06-27

Round #124 (Div. 2)

| 22:00 | Round #124 (Div. 2) - minus9dの記録 を含むブックマーク はてなブックマーク - Round #124 (Div. 2) - minus9dの記録

A問題を盛大に勘違いして放棄したため低迷。

  • ooo-- R1644→R1582(-62)。

A. Plate Game

矩形のテーブルに、1人目と2人目が順番に円形のお皿を置く。皿を置けなかった方が負け。この問題では、それぞれの人が皿を置くのは1回のみなのだが、なぜか皿を交互に何度でも置くものだと勘違いしてしまった。なんでAでこんな難しい問題が出るんだろうと疑問には思ったけど、思い違いには気づかず放棄してしまった。

B. Limit

極限値を求める。高校数学を思い出して丁寧に実装。

http://codeforces.com/contest/197/submission/1789093

C. Lexicographically Maximum Subsequence

ある文字列が与えられる。ここから、辞書順でもっとも後ろになるような部分文字列を作成する。図を使って説明する。

f:id:minus9d:20120627215504p:image

(1) 与えられる文字列をczabzcbwqwqとする。ポインタの初期位置を左端にセットする。

(2) 矢印から右にある文字の中で、もっとも辞書順で後にくる文字を探す。この場合はz。矢印を一つずつ右に移動させ、zが存在すればそれを拾う。矢印は一番最後に現れるzの直後でストップさせる。

(3) (2)と同様のことをする。この場合矢印から右にある文字の中で、もっとも辞書順で後にくる文字はwなので、wを拾いつつ矢印を移動させる。

(4) (2)と同様のことをする。この場合はqしか残っていないのでこれを拾うだけ。

最後に拾った文字をつなげると、求めるべき部分文字列zzwwqが得られる。

http://codeforces.com/contest/197/submission/1790692

D. Infinite Maze

サイズn x mの盤面が与えられる。これをタイル状に敷き詰めた時、スタート地点から無限に遠くに行ける場合はYes、行けない場合はNoを出力する。提出期限の3分後に出来上がったコードが一発OKだったのが非常に残念だった問題。

f:id:minus9d:20120627215505p:image

盤面を敷き詰めると上図のようになる。敷き詰めた盤同士を区別するため、最初のスタート地点を含む盤面を(0, 0)とし、その右隣を(0, 1), 下隣を(-1, 0), などとおく。こうすると、探索中の場所は、n x m盤面中の位置(2次元)に加えて、盤面盤のうちのどの盤かという2次元の、計4次元で表される。

最初の位置から敷き詰めた盤面上を探索していく。例えば最初の位置を(n0, m0, 0, 0)としたとき、探索途中に(n0, m0, x, y) (x != 0またはy != 0)が現れればYes。現れないまま探索が終了すればNo。


提出したコード:http://codeforces.com/contest/196/submission/1796373

Round #125 (Div. 2)

| 22:00 | Round #125 (Div. 2) - minus9dの記録 を含むブックマーク はてなブックマーク - Round #125 (Div. 2) - minus9dの記録

B問題の割に提出率の低い幾何問題が一応解けて71位と好順位。ooo-- R1582→R1678(+96)。

A. Hexadecimal's theorem

フィボナッチ数であることが保証されている数nが与えられる。この数字を任意のフィボナッチ数3個(重複を許す)で表すことができる場合、その3つの数を出力する。表すことができない場合は"I'm too stupid to solve this problem"と屈辱的な文を出力する。

n番目のフィボナッチ数F_nは、n >= 3のとき

F_n = F_(n-1) + F_(n-2)
       = (F_(n-2)+F_(n-3)) + F_(n-2)
       = 2 * F_(n-2) + F_(n-3)

と変形できる。なので、F_(n-2), F_(n-2), F_(n-3)を出力すればよい。

n = 0, 1, 2のときはそれぞれ個別に考えればよい。

http://codeforces.com/contest/199/submission/1814841

B. Special Olympics

2つのドーナツ状の輪っかが与えられる。2つの輪っかの外周、内周をあわせた計4個の円のうち、もう一方の輪っかに邪魔されていない完全な円の数を数える。

きれいな解き方が思いつかなかったので、円上に数万個分の点をとり、それらの点の中で、もう一方の輪っかの黒い部分に入っている点の数を数えた。黒い部分に入っている点がほとんどなければ、その円は完全な円であると判定した。

http://codeforces.com/contest/199/submission/1819054

C. About Bacteria

ある時点でx個のバクテリアは、1秒後にkx+b個になる性質がある。最初の実験で、1個のバクテリアがn秒後にz個になったことがわかっている。最初にt個のバクテリアがあるとき、このバクテリアがz個以上に増えるのに必要な秒数を求める。

下図を参照。tの範囲が[1, k+b)のときはn秒かかる。tの範囲が[k+b, k^2+kb+b)のときはn-1秒かかる。以下同様。

f:id:minus9d:20120627215506p:image

http://codeforces.com/contest/199/submission/1816793

2012-06-18

TopCoderとCodeforcesのレーティングの相関に、GCJ2012の結果を足しあわせてみる

| 23:54 | TopCoderとCodeforcesのレーティングの相関に、GCJ2012の結果を足しあわせてみる - minus9dの記録 を含むブックマーク はてなブックマーク - TopCoderとCodeforcesのレーティングの相関に、GCJ2012の結果を足しあわせてみる - minus9dの記録

以前、TopCoderCodeforcesとの間で、レーティングの相関グラフを作ってみた(リンク)。ふと、これらのレーティングとGoogle Code Jam2012の結果とでどれくらい関係があるかを可視化してみたくなった。

調べ方は以下の通り。

  1. TopCoderCodeforcesの両方に登録している日本の参加者をJapanese Codeforces participantsから抽出(データは2012年6月12日に入手したものを使用)
  2. GCJ2012に登録している日本の参加者を403 Forbiddenから抽出
  3. 両方に名前のある参加者を抽出。ただし、若干の手作業で、私が把握してる分の名前の異なる方を名寄せ
  4. Rでプロット

結果はこんな感じになった。●の色がGCJの結果を表している。凡例は以下の通り。

 赤:オンサイトへ進出
 黄:Round 3へ進出
 青:Round 3への進出は逃すもTシャツ入手(Round 2 501位〜1000位 )
 緑:Round 2へ進出
 灰:Round 1へ進出
 黒:Qualで敗退

f:id:minus9d:20120618235211p:image

やはり一発勝負なので、必ずしもレーティング順通りではなく多少の逆転があるのが面白い。特に、TopCoderのDiv1下位でもTシャツをもらえる可能性は十分ありそうなことがわかり、ちょっとやる気が出る。ただ、もしかするとTopCoderでは使用言語が限られていて力が出せない方が、GCJで実力を出しているだけかもしれないけど。

CodeforcesTopCoderのレーティング間で線形近似すると

Codeforces = 935 + 0.480 * TopCoder

と出た。

換算表を作るとこんな感じ。

TopCoderCodeforces
5001175
6001223
7001271
8001318
9001366
10001414
11001462
12001510
13001558
14001606
15001654
16001702
17001750
18001798
19001846
20001894
21001942
22001990
23002038
24002086
25002134
26002182
27002230
28002278
29002326
30002373
31002421
32002469
33002517
34002565
35002613