2011-09 << 2011-10 >> 2011-11

2011-10-08 (土)

*Google Code Jam Japan 2011

http://code.google.com/codejam/japan/

眠い．そして微妙．69位なので一応Tシャツはもらえる？

  • Aをやる→なぜか答え合わない
  • Bをやる→意外と面倒で嵌る
  • Aをやる→通った
  • Bのデバッグ＞どこ間違ってるのか分からず
  • 順位が200位ギリギリな事に気づいてCのsmallだけやる
  • Bを書き直してみる…が残り時間が無いのでDに
  • Dのsmallだけ解こうとする＞あとちょっとのところで終了

問題Bに3時間中1時間半以上使ってしまった．Dはたぶん解けると思ったのに，ぜんぜん時間が足りなかった．

何かやろうとする度に，自分の想像以上にプログラム書けなくなってるのがとても気がかり．分かっていたけど，仕事してコード書いた気になっているのがいけない気がする……．

A

最初， t1>=t2 の条件を間違っていていた．面積の差とかを比較してたけど，よく考えたら大きい三角形を順番に作っていくだけで良かった．

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;

int main() {
    int T;
    cin >> T;
    
    for (int i=0;i<T;i++) {
        int k;
        cin >> k;
        
        vector<int> ee;
        for (int j=0;j<k;j++) {
            int e;
            cin >> e;
            ee.push_back(e);
        }
        
        sort(ee.begin(),ee.end());

        double a = 0.0;
        
        int t1 = ee.back();
        int t2 = ee.back();
        ee.pop_back();

        double sindeg = sin(2* 3.141592653589793 / k);
        while (ee.size()) {
            if (t1>=t2) {
                a += t1*ee.back()*sindeg /2;
                t1 = ee.back();
            } else {
                a += t2*ee.back()*sindeg /2;
                t2 = ee.back();
            }
            ee.pop_back();
        }
        a += t1*t2*sindeg /2;
        

        cout << "Case #" << (i+1) << ": "<< setprecision(10) << a << endl;
    }

    return 0;
}

B

3時間中2時間使ってしまった…．そして，結局出来なかった．

A^x mod C の周期を計算すれば簡単に解けると思ったけど，意外と面倒なことに．

最初C++で書いていたけど，rubyならsmallは多倍長整数仕えれば楽だなと思ってちょっと書いたけど，smallだけやっても仕方ない気がして途中で引き返す．

終了後に，試しにsmallだけ解けるように書き直してみたけど，まだどこか怪しい．他の人のプログラムの出力とのdiff取ったら，なぜか500個中1個だけ出力が違ったので，何か特殊な場合を見逃してたっぽいなぁ．

一応書きかけのコード貼り付けておくけど，正しい答えが出ないです．

#include <iostream>
#include <map>
using namespace std;

typedef pair<int,int> CC;

CC n(int a,int m) {
    int cycle[1024]={0};
    int p=0;
    int t = 1;
    for(;;) {
        if (cycle[t]) return CC(cycle[t]-1,p-cycle[t]+1);
        cycle[t] = p + 1;
        t = t*a%m;
        p++;
    }
}

int modpow(int a,int p,int m) {
    int t = 1;
    // fixme
    for (int i=0;i<p;i++) {
        t = t * a % m;
    }
    return t;
}

int mm[1024][1024];

int calc(int a,int b, int c) {
    if (b == 1) return modpow(a,a,c);
    if (b == 2) {
        // bug...
        int tt = modpow(a,a,c);
        auto cc = n(tt,c);
        int r = modpow(a,a,cc.second);
        r = (r+cc.second-cc.first) % cc.second + cc.first;
        //int p = modpow(tt,cc.first,c);
        //cout << p  << ","<< cc.first << "," << cc.second << endl;
        //cout << r1 << a << endl;

        return modpow(tt,r,c);
    }
    
    for (int i=0;i<1024;i++) {
        for (int j=0;j<1024;j++) {
            mm[i][j]=-999;
        }
    }
        
    return mm[b][c];
}

int main() {
    int T;
    cin >> T;

    for (int i=0;i<T;i++) {
        int a,b,c;
        cin >> a >> b >> c;

        int ans = calc(a,b,c);;
        cout << "Case #" << (i+1) << ": " << ans << endl;
    }

    return 0;
}

C

smallだけ．largeは実装に時間かかりそうなのであきらめて無心で．

#include <iostream>
#include <string>
using namespace std;

bool match(const char *a,const char *b,long long mask) {
    if (*a == 0 && *b == 0) return true;

    if (mask&1) { // *
        mask >>= 1;
        a++;
        if (match(a,b,mask)) return true;
        while(*b) {
            b++;
            if (match(a,b,mask)) return true;
        }
        return false;
    }
    if (*a == *b) {
        return match(a+1,b+1,mask>>1);
    }

    return false;
}

int count(long long mask){
    int c = 0;
    while (mask) {
        if (mask&1) {
            c++;
            mask >>= 1;
            while(mask&1) {
                mask >>= 1;
            }
        } else {
            mask>>=1;
        }
    }
    return c;
}

string mk(string a,long long mask) {
    string s;
    auto p = a.begin();
    while (p != a.end()) {
        if (mask&1) {
            s.push_back('*');
            ++p;
            mask >>= 1;
            while(mask&1 && p != a.end()) {
                mask >>= 1;
                ++p;
            }
        } else {
            s.push_back(*p);
            mask>>=1;
            ++p;
        }

    }
    return s;
}

// a:old b:new
bool comp(string a,string b) {
    if (a.size() < b.size()) return false;
    if (a.size() > b.size()) return true;
    
    int ca=0,cb=0;
    for (auto p = a.begin();p!=a.end();++p) {
        if (*p == '*') {
            ca++;
        } 
    }
    for (auto p = b.begin();p!=b.end();++p) {
        if (*p == '*') {
            cb++;
        } 
    }
    if (cb>ca) return false;
    if (cb<ca) return true;
    
    auto ap = a.begin();
    auto bp = b.begin();
    while(ap!=a.end()) {
        if (*ap > *bp) return true;
        if (*ap < *bp) return false;
        ++ap; ++bp;
    }
    return true;
}

int main() {
    int T;
    cin >> T;
    
    for (int i=0;i<T;i++) {
        string a,b;
        cin >> a >> b;
        
        int n = 1 << a.length();
        string s = a;
        for (long long mask=0;mask<n;mask++) {
            if (!match(a.c_str(),b.c_str(),mask)) {
                string t = mk(a,mask);
                if (comp(s,t)) {
                    s = t ;
                    //cout << mask << " " << s << endl;
                }
            }
        }

        cout << "Case #" << (i+1) << ": " << s << endl;
    }

    return 0;
}

D

smallだけならギリギリ書けると思ったけど，提出する前に時間切れに…．もう10分早くBを諦めるべきだった．

smallだけなら，総当りで簡単に解けるサイズなので問題ない．largeは一生懸命枝を刈ればどうにかなるのか，頭の良いアルゴリズムがあるのかよく分からない．

#include <iostream>
using namespace std;

int w,h;
char map[40][10];
char map2[40][10];

int dx[] = {-1,1,0,0}, dy[] ={0,0,1,-1};
int dx2[] = {-1,1,1,-1}, dy2[] ={1,-1,1,-1};

int check_rest = 0;

bool check_(int x,int y) {
    char t=map2[y][x];

    if (t=='D') check_rest--;
    map2[y][x] = 'X';
    if (check_rest==0) return true;
    
    for (int i=0;i<4;i++) {
        if (map2[y+dy[i]][x+dx[i]]=='X') continue;
        check_(x+dx[i],y+dy[i]);
    }
    return check_rest==0;
}

bool check() {
    int xx=0, yy=0, rest=0;
    for (int y = 0; y<= h+1; y++ ) {
        for (int x = 0; x<= w+1; x++ ) {
            map2[y][x] = map[y][x];
            if (map[y][x]=='D') {
                yy=y;xx=x;
                rest++;
            }
        }
    }
    check_rest = rest;
    return check_(xx,yy);
}

int solv(int x, int y) {
    x++;
    if (x>w) {x=1;y++;}
    if (y>h) return 0;

    int max = 0;
    if (map[y][x] == '.') {
        map[y][x] = 'X';
        for (int i=0;i<4;i++) {
            if (map[y+dy[i]][x+dx[i]] != '.') continue;
            char tt = map[y+dy2[i]][x+dx2[i]];
            if (tt == 'X') continue;
            map[y+dy[i]][x+dx[i]] = 'X';
            map[y+dy2[i]][x+dx2[i]] = 'D';
            if(check()) {
                int t = solv(x,y) + 1;
                if (t>max) {
                    max = t;
                }
            }
            map[y+dy[i]][x+dx[i]] = '.';
            map[y+dy2[i]][x+dx2[i]] = tt;
        }
        map[y][x] = '.';
    }

    int t = solv(x,y);
    if (t > max) {
        max = t;
    }
    return max;
}

int main() {
    int T;
    cin >> T;
    
    for (int i=0;i<T;i++) {
        cin >> h >> w;

        for (int y = 0; y<= h+1; y++ ) {
            for (int x = 0; x<= w+1; x++ ) {
                map[y][x] = 'X';
            }
        }
        for (int y = 1; y<= h; y++ ) {
            for (int x = 1; x<= w; x++ ) {
                cin >> map[y][x];
            }
        }
        int a = solv(0,1);

        cout << "Case #" << (i+1) << ": " << a << endl;
    }

    return 0;
}

E

無限平面を埋め尽くすパターンといえばヒルベルト曲線が有名で，説明の図もヒルベルト曲線の一部に見えないことも無いけれど，問題読んだだけで考えてない．

条件と雰囲気からフラクタル的な図形になるのは間違い無さそうなので，うまくすれば長さが一気に出せそう．

2011-09 << 2011-10 >> 2011-11