Hatena::Grouptopcoder

minus9dの記録

2013-11-20

EmacsでTopCoder

| 23:46 | EmacsでTopCoder - minus9dの記録 を含むブックマーク はてなブックマーク - EmacsでTopCoder - minus9dの記録

Eclipseがどうにも使いにくいので、EclipseCoderを捨ててEmacsでコーディングすることにした。手順は以下。

  • 401 Unauthorizedに従い設定
    • ただし、これらの項目をすべて行った後、Options→Editorにて「CodeProcessor」のDefaultにチェックを入れる必要があった
  • Arenaで問題を選んだら、テストケース付きソースコードが、自分の指定したディレクトリに自動生成される。そのソースコードを、Emacsに限らず好きなエディタで編集すればよい。

自分用のC++のテンプレートは以下。

#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>

#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

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


class $CLASSNAME$ {
public:
  $RC$ $METHODNAME$($METHODPARMS$) {
    $RC$ result;
    return result;
  }

  $TESTCODE$
};

// BEGIN CUT HERE
int main() {
  $CLASSNAME$ ___test;
  ___test.run_test(-1);
}
// END CUT HERE

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;
}

2013-10-15

AtCoder Beginner Contest #001

| 23:37 | AtCoder Beginner Contest #001 - minus9dの記録 を含むブックマーク はてなブックマーク - AtCoder Beginner Contest #001 - minus9dの記録

5ヶ月記録をさぼった後、何事もなかったかのように更新。この間AtCoderの初心者版として始まったAtCoder Beginner Contestの第一回に出場した。

公式解説はこちら

D - 感雨時刻の整理

雨の降っていた期間がいくつか与えられるので、それを統合して出力する。

アホなことに60進数の処理をするのを忘れていて解けなかった。

全然思いつかなかった解答がこちら

まず、(区間の開始時刻, 1)というペアと、(区間の終了時間, 2)というペアをvectorにつっこんで昇順にソートする。

その後ペアを順番に取り出して、区間が始まるたびカウンタを+1、区間が終わるたびカウンタを-1する。カウンタが0になったときに統合された区間をprintする。


今後ABCでは、普段使わない言語の練習をすることを目標にしたい。

2013-05-19

Google Code Jam 2013 Round1A

| 00:12 | Google Code Jam 2013 Round1A - minus9dの記録 を含むブックマーク はてなブックマーク - Google Code Jam 2013 Round1A - minus9dの記録

Round1A 1059位(36pt), 1B 4679位(0pt), 1C 1584位(27pt)で敗退が決定。モチベーションも上がらないけど、Round1を復習することにする。

今回はRound1Aの復習。本番ではA-*, B-smallが解けて1059位。終了後10分でC-smallが解けていただけに惜しかった。2013 Round 1Aのページはこちら。真剣に復習するとえらい時間がかかった。

A. Bullseye

幅1の黒い円状の帯と白い円状の帯が交互になるように、黒い円状の帯をペンキで塗っていく。ペンキがtあるときに、いくつ黒い帯を塗れるかを答える。

まず紙と鉛筆で、各黒帯の面積を計算。最初の黒い帯の面積は\pi(2r+1), 次の黒い帯の面積は\pi(2r+5), その次は\pi(2r+9), と法則があることが分かる。

Smallでは、単に順番に黒い帯の面積を足していって、与えられたペンキの量を超えたところでストップすればよい。

Largeでは一工夫する。まず、1個目の黒帯からn個目の黒帯までの面積の合計S_nを計算する。高校数学で出てくる等差数列の和の公式を使うと、S_n=\pi{2n^2+(2r-1)nと求まる。あとは2分探索で、与えられたペンキで塗ることのできる最大の帯の数を求めればよい。

B. Manage your Energy

あなたはエネルギーEをもっている。各タスクのそれぞれについて、今あるエネルギーのうち任意の整数分のエネルギー(0以上)を使うと、その[タスクの価値]*[使用したエネルギー分]のgainを得る。タスクを1つこなすごとにエネルギーがR回復する。gainを最大化したときの値を求める。

B-SmallはDPで解けた。dp[現在のタスク番号][現在のエネルギー]でループを回す。

B-Largeは解説を見た。以下の手続きを繰り返せばO(N^2)で解けるとのこと。

  1. まだ注ぎこむエネルギー量を決めていないタスクの中から、もっともタスクの価値の高い仕事aを見つける
  2. 仕事aに、注ぎ込めるすべてのエネルギーを注ぎ込むことを決める
  3. それにより、仕事aより前に位置する仕事には、「仕事aに注ぎ込むエネルギー分を残しておく」という制約が、また仕事aより後に位置する仕事には「使用できるエネルギーの上限が、仕事aから何個のタスクをこなしたかにより制限される」という制約が付く
  4. 1.に戻る

この解説の方法を実装したコードはこちら

C. Good Luck

問題

2からMまでの数字がかかれたカードの中から、等確率でN枚のカードを選ぶ。

以下のことをK回繰り返す。

  • N枚のカードのそれぞれを0.5の確率で取り出したサブセットを作る
  • サブセットに含まれるカードの数字の積を書き出す

N, Mと数字の積から、N枚のカードの数字が何だったかを当てる。

解答

くどいくらいじっくりと具体例で考えてみた。例として、2から5までの数字の中から等確率で2枚のカードを選ぶことを考える。今回、サブセットを作る作業を3回繰り返し、その積が順に4, 4, 1だったとする。

これを数式で定式化して考える。「サブセットの積が4, 4, 1という情報が与えられたとき、2枚のカードが[A,B]だった確率」を

Pr( [A,B] | サブセットの積が4, 4, 1)

と書くことにする。これを最大化する[A,B]を求めるのが今回の問題。

これを簡単に解くテクニックとして、ベイズの定理を使うと、上式は以下のように変換できる。

Pr( [A,B] | サブセットの積が4, 4, 1) = Pr( [A,B] )  * Pr(サブセットの積が4, 4, 1 | [A,B]) / Pr( サブセットの積が4, 4, 1 )

上式を最大化するするためには、分母のPr( サブセットの積が4, 4, 1 )は無視してよい。結果、今回の問題は

Pr( [A,B] )  * Pr(サブセットの積が4, 4, 1 | [A,B])  …(1)

を最大化する[A,B]を求める、という問題になった。

Pr( [A,B] ) を求めると以下のようになる。[2,3]と[3,2]は区別しない。

  • Pr([2,2]) = 1/16
  • Pr([2,3]) = 1/8
  • Pr([2,4]) = 1/8
  • Pr([2,5]) = 1/8
  • Pr([3,3]) = 1/16
  • Pr([3,4]) = 1/8
  • Pr([3,5]) = 1/8
  • Pr([4,4]) = 1/16
  • Pr([4,5]) = 1/8
  • Pr([5,5]) = 1/16

Pr(サブセットの積が4, 4, 1 | [A,B]) は、Pr(サブセットの積が4 | [A,B) * Pr(サブセットの積が4 | [A,B) * Pr(サブセットの積が1 | [A,B])と分解できる。Pr(サブセットの積がn | [A,B])の一部を抜粋すると以下のようになる。


  • Pr(サブセットの積が1|[2,2]) = 1/4
  • Pr(サブセットの積が2|[2,2]) = 1/2
  • Pr(サブセットの積が4|[2,2]) = 1/4
  • Pr(サブセットの積が1|[2,4]) = 1/4
  • Pr(サブセットの積が2|[2,4]) = 1/4
  • Pr(サブセットの積が4|[2,4]) = 1/4
  • Pr(サブセットの積が8|[2,4]) = 1/4
  • Pr(サブセットの積が1|[4,4]) = 1/4
  • Pr(サブセットの積が4|[4,4]) = 1/2
  • Pr(サブセットの積が16|[4,4]) = 1/4

ここまで準備すると(1)が計算できる。

Pr( [2,2] )  * Pr(サブセットの積が4, 4, 1 | [2,2]) = (1/16) * (1/4) * (1/4) * (1/4) = 1/1024
Pr( [2,4] )  * Pr(サブセットの積が4, 4, 1 | [2,4]) = (1/8) * (1/4) * (1/4) * (1/4) = 1/512
Pr( [3,4] )  * Pr(サブセットの積が4, 4, 1 | [3,4]) = (1/8) * (1/4) * (1/4) * (1/4) = 1/512
Pr( [4,4] )  * Pr(サブセットの積が4, 4, 1 | [4,4]) = (1/16) * (1/2) * (1/2) * (1/4) = 1/256
Pr( [4,5] )  * Pr(サブセットの積が4, 4, 1 | [4,5]) = (1/8) * (1/4) * (1/4) * (1/4) = 1/512

その他のPr( [A,B] ) * Pr(サブセットの積が4, 4, 1 | [A,B])はすべて0となる。

上記の確率のもっとも高いものを選ぶと[4,4]となる。よって、2枚のカードが[4,4]、というのがもっともありそうなカードの選び方、ということが分かった。


Small 2も上記の考え方で解ける。まず事前にPr( N枚のカードの選び方 ) とPr( サブセットの積 | カードの選び方 )を全計算しておく。後は上記と同じ方法で最尤推定して、もっともありそうなカードの選び方を求める。

とはいえ、どうやってこれらの計算を効率よくできるのかが分からなかったので上位陣のコードを見た。1位のMyth5氏のコードでは、dfsですべてのカードの選び方を列挙してうまいことやっていた。自分ではこのように綺麗には書けそうにない。ただ、Small 2を実行すると実行時間が4分程度かかる。もっと良い方法があるのかも。

Myth5氏のコードをもとに注釈をつけたコードはこちら

2013-05-08

Google Code Jam 2013 Qual

| 23:24 | Google Code Jam 2013 Qual - minus9dの記録 を含むブックマーク はてなブックマーク - Google Code Jam 2013 Qual - minus9dの記録

今更ながらの記録。A-*, B-*, C-{small, large1}を解いたつもりがA-largeとC-large1を落としてしまい、60pt、10829位でぎりぎりの通過。猛省するしかない。

スコアボード:https://code.google.com/codejam/contest/2270488/scoreboard?c=2270488

A. Tic-Tac-Toe-Tomek

oxゲームを4x4に拡張。かつ'T'がワイルドカードとして使用される。盤面が与えられた時、どちらが勝ったか、または引き分けか、またはまだ勝負がついていないか、を答える。

Smallが通ったのでLargeも同じコードで通るだろうと思ったら落ちた…。4つのセルを順番に見るときに、最初のセルが’T'の場合を考慮できていなかった。Smallはテストケースが10個しかなかったので、Smallの結果だけではなくもっとちゃんと確かめるべきだった。

あとで書きなおしたコードはこちら

B. Lawnmower

長さ100mmの芝生が生えている矩形状の芝生がある。カットの長さを変えられる芝刈り機で縦または横に芝生を刈り取ることができる。刈り取り後の芝生の状態が与えられた時、その状態が芝刈り機で達成できるかどうか答える。

自分は、与えられた芝生の状態を少しずつ巻き戻していって、最初の長さ100mmの芝生の状態にたどりつけるかどうかを調べる、という方針をとった。手続きで書くと以下。

  1. 芝生の長さがもっとも短いセルをすべて見つける。この長さをmとする
  2. 1.で見つけたすべてのセルが、以下の条件を満たすかどうか調べる。一つでも条件を満たさないものがあれば"NO"を出力
    • そのセルを含む列または行の少なくともどちらかが、すべてmである
  3. 芝生の長さがmであるすべてのセルについて、長さを+1する
  4. すべてのセルの芝生の長さが等しくなれば"YES"を出力する
  5. 1.に戻る

これでも一応解けたが、GCJの解説はよりスマートな方法を紹介しており感動した。GCJの解説の方法では、私がとった方法とは逆に、最初の長さ100mmの芝生から、与えられた芝生の状態を作れるかどうかを試している。

  1. 与えられた芝生の各行について、もっとも長さの長い芝生を見つける。長さ100mmの芝生の対応する各行を、その長さで刈る。
  2. 各列について同じことをする。
  3. 与えられた芝生の状態と、刈ってできた芝生の状態とが同じであれば"YES", 異なれば"NO"を出力する。

この解説の方法を実装したコードはこちら

C. Fair and Square

以下の条件をすべて満たす自然数をFair and Squareと定義する。

  • Palindrome(回文)である
  • ある自然数nの2乗である
  • nもまたPalindromeである

AとBが与えられたとき、範囲[A, B]に含まれるFair and Squareな数を求める。

SmallとLarge1については、1*10^14以下のFair and Squareな数をあらかじめ全列挙しておくことで解けることに気づいていた。しかし、int型を使ったためにオーバーフロー発生、というアホなことに気付かずLarge1を落とした。

Large2についてはBが大きく単純に全列挙はできない。解説を読んで勉強。

あるPalindromeな自然数nに対してn*nを計算するとき、どの桁でも繰り上がりが発生しなければ、n*nもPalindromeになるらしい。繰り上がりが発生しないためには、nの各桁には0, 1, 2, 3のどれかしか現れ得ず、かつ1以上の数字はたくさんは現れない。この制約からnの候補を大きく絞ることができる。

rngさんのBigIntegerを使ったJavaコードをベタにPythonに移植してみたが、Large2の答を出力するのに5分かかってしまった。Pythonに慣れていないので、あほなことをやっているかもしれない。コードはhttp://ideone.com/UqoSgs:title:=こちら]。

D. Treasure

コンテスト終了後、Smallのみ解いた。ベタに全探索。その際、なるべく番号の若いChestから先に開けるようにする。

糞コードはこちら。Smallを解くのに30秒くらいかかる。合っているのか自信なし…

mimanamimana2013/05/11 15:31こんにちは。
Cの問題はpypyで実行するとだいぶ速くなると思いますよー。
根本的な解決にはなってないかもしれないですけど…。

minus9dminus9d2013/07/26 22:05コメントありがとうございます。気付くのが遅くなり申し訳ありません。
確かに普通のPythonでしか実行していないので、次回はpypyを試してみたいと思います。