2011-10 日記

2011-10-31 (月)

明日は，GDD2011のために早起きしないと…．

*ニコニコPlayer(仮)

しばらく放置してしまってたので，アップデートしました．

あんまり変わってないです．

部署がニコニコ系になってしまったので，非公式アプリを趣味で作るのは少しアレだし，仕事のほうで色々やろうと思うけど．．．どうなるのかなぁ．

2011-10-30 (日)

eldeshと焼肉を食べる．

2011-10-29 (土)

寝た．

秋葉原．

2011-10-28 (金)

夜中から仕事してたので15時過ぎに帰って寝る．ここ３週間くらい仕事しかしていなかった．たぶんこれで少し落ち着くはず．疲れました……．

2011-10-27 (木)

夜仕事しないといけないので，早めに帰って寝ておく．

2011-10-25 (火)

早く起きて12:30に会社に．まだ早朝な気分なのだけど，もうみんな仕事しているのか……．

2011-10-24 (月)

眠い…．

2011-10-23 (日)

会社のVPNの回線が遅くて挫折したので，出かけるついでに会社に寄ってファイルをサーバに置いてくる．

Android SDKとかeclipseのアップデートとかした．あとで4.0のSDKを見てみる．

Android開発はeclipse使ってるけど，もう少し快適なIDEが欲しい．

2011-10-22 (土)

はじめて家に仕事を持ち込んでしまったので，会社のVPN使った．

2011-10-17 (月)

今週は平和．だといいな．

2011-10-16 (日)

今日も休みなのに午前中に目が覚めた．生活のリズムが崩れてる．

2011-10-15 (土)

午前中に起きて，選択とか掃除とか済ませたあと夕方まで昼寝．

夜，スーパーに食材を買いに行く．

体がだるいので早めに寝る．

2011-10-14 (金)

眠い．

2011-10-13 (木)

今日は早めにやっておかないといけない仕事があったので，昼に出社．なんか，最近ギリギリでやばい．

12時出社．25時退社．

それでも今週になって初めて8時間以上連続して寝れそうな時間がある．それにしても，睡眠時間が8時間以下になると，思考力の低下が酷い．

2011-10-12 (水)

昨日のミスが原因で起きてた問題の残りをどうにかするために，朝４時に会社に行く．でも，実際に作業をするのは別の人たちなので，様子見てるだけ……．さすがに，この時間だと心が痛む．

朝帰ってきて，少し寝て，また会社に．

2011-10-11 (火)

久しぶりに，午前中に仕事．

……というか，夜中～昼に作業があるので会社に．

色々ミスった．

大体どうにかなったけど，一部は次の日の早朝に．

2011-10-10 (月)

夕方まで寝た．

日付が変る頃に会社に向かう．

2011-10-09 (日)

今日は妹の結婚式でした．こんな機会でもないと，家族や親戚で集まることもないですね．あとネクタイの結び方が難解すぎる．少なくともCode Jamの問題Aよりは難しい．

昨日の夕方から明け方まで寝て，code jamの問題見直して，少し寝てから会場に．

朝早かったので，帰ってきて少し寝る．

*Code Jam...

Code Jam見直す．ついでに昨日の日記の所々に加筆．

昨日のCode JamのBの問題が気になって仕方ないので他の人のコードと比較していて間違いに気づいた．累乗の指数が周期より小さいときの場合を考慮していなかった．式考えているときは何か怪しいと思ってたのだけど，プログラム書いている間に忘れていた……．

うまく綺麗な式が立てられないので値が小さいときは単純に掛け算するように場合分け．

smallが正しい結果出すようになったので，large用も書き換えたら普通にいけた……．modpow()が遅いので書き直す予定だったけど，そのままでも十分間に合った．(本番だったら心配なので書き直してただろうけど)

最初無意味に再帰してたのだけど，遅すぎるので書き直す．

int calc(int a,int b, int c) {
    for (int i=1;i<=c;i++) {
        mm[0][i] = a%i;
    }
    int aa = a;
    for (int i=1;i<=b;i++) {
        for (int tc=1;tc<=c;tc++) {
            int ta = mm[i-1][tc];
            auto cc = n(ta,tc);
            int r = mm[i-1][cc.second];
            r = (r-cc.first + cc.second) % cc.second + cc.first;

            if (aa < tc) r = aa;
            mm[i][tc] = modpow(ta,r,tc);
        }
        
        if (aa <= 1000) {
            int td = aa;
            aa = 1;
            for (int tt=0;tt<td;tt++) {
                if (aa > 1000) break;
                aa*=td;
            }
        }
    }
    return mm[b][c];
}

A(small+large),B(small+large),C(small),D(small)あたりが出来れば良かったんだけどなぁ．

Dのlargeもよく考えたらクローゼットのサイズ2x1だしマップは5列かないし，2行ずつ決めてけば大丈夫だな…．

2011-10-08 (土)

12時半くらいに起きて，コンビニ行ってcode jam．

掃除とか洗濯とかしておく．

眠いので夕方寝たら今日が終わっていた．

LenovoでノートPC買おうと思ったのだけど，最後の注文ボタンを押すとエラーになってしまって買えない……．Javaの例外クラス名がそのまま出るのってどうなんだろ？

*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-10-07 (金)

明日から三連休だけど予定が埋まってて憂鬱になる．べつに嫌なことをするわけでもないのに，予定表に何か書かれていると憂鬱になる病気なのかも．

2011-10-06 (木)

会社いったら，もうほとんど人がいなかったので神保町へ．

カレー食べる．

会社に戻る帰りに，秋葉原寄ってスーツ受け取る．

2011-10-05 (水)

雨．

色々忙しい．

2011-10-04 (火)

cssとHTML書いたりした．

スマートフォン用のcssに切り替えるのは，max-widthの値とかじゃなくて，ポインティングデバイスが何なのかで切り替えたい．一応，Firefoxには -moz-system-metric(touch-enabled) みたいなのがあるみたいだけど，他のブラウザもやってくれないかなぁ．

2011-10-03 (月)

眠い…．

2011-10-02 (日)

最近，休みはいつも秋葉原にいる気がするけど，気のせいだと思いたい．

夜はgotoと秋葉原のルノアールに行って，コード書いたりする．

ルンバで遊ぶ予定だったけど，結局触れなかった…．

2011-10-01 (土)

Code Jamやったり，服買ったりする日．

*Google Code Jam Japan 2011 予選

Tシャツ欲しいのでやりました．

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

この日記読んでも雰囲気が伝わるかすら怪しいので，気になる人は自分で問題読むことをお勧めします．問題はcode jamのサイトで誰でも見れます．

13時開始だったけど，目が覚めて時計を見ると14時過ぎ……．まだ眠かったけど，14:20くらいに問題読み始める．

予選なので問題は簡単．しかも日本語だし楽勝．と思ったけど，Bで結構時間かかってしまった．

終わったのが15:48．

コンテスト終了後にスコア見たけど，全問大丈夫だった．始めたのが遅かったので順位は56位．来週も頑張れば一応Tシャツもらえそうだな．

A イカサマシャッフル

カードを指定された通りにシャッフルした場合，ある場所のカードが元々どこにあったかを答える問題．

カードの枚数が，10億(10^9)枚まであり得るので，実際にカードに番号を振って操作するのは危険．ただ，答えるのは指定された１枚なので，シャッフルが終わった状態から逆順に辿れば簡単．

最初に1引いておいて最後に1足しているのは，カードの番号が1から始まるのが気持ち悪かったからってだけです．

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

int main() {
    int T;
    cin >> T;
    
    for (int i=0;i<T;i++) {
        int m,c,w;
        cin >> m >> c >> w;
        
        vector<int> aa,bb;
        for (int j=0;j<c;j++) {
            int a,b;
            cin >> a >> b;
            aa.push_back(a-1);
            bb.push_back(b);
        }
        
        w -= 1;
        while (aa.size()) {
            int a = aa.back();
            int b =  bb.back();
            aa.pop_back();
            bb.pop_back();

            if (w<b) {
                w += a;
            } else if (w < a+b) {
                w -= b;
            }
        }

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

    return 0;
}

B 不老不死な人のコーヒーの悩み

複数種類のコーヒーについて，賞味期限と満足度と何杯分飲めるかが与えられて，１日一杯ずつ飲んだときの，満足度の合計の最大値を求める問題．

しかし，２兆(=2*10^12)日くらいコーヒーを飲み続ける不老不死な人が抱える問題のようなので32ビット整数に収まらないし，1日ごとに計算してたら間に合わない気がします．

２兆日っていうと，そろそろ太陽が燃え尽きて地球が無くなってるころですね．確かにたとえ不老不死であっても地球が無いとコーヒー飲んでる場合ではない……．

特に方針を決めないまま書き始めたら，少し面倒なプログラムになってしまった．コーヒーを飲むことが出来なくなる最期の日から，まだ飲めるコーヒーのうち満足度が最大なものを調べて，その前に賞味期限が切れるコーヒーと比べつつ，どの期間にどのコーヒーを飲むか決めるだけのプログラム．

事前に賞味期限と満足度でソートしたほうが多少短くなったかも．

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

int main() {
    int T;
    cin >> T;
    
    for (int i=0;i<T;i++) {
        unsigned long long n,k;
        cin >> n >> k;
        
        struct Coffee {
            unsigned long long c,t;
            int s;
        };
        vector<Coffee> cc;
        for (int j=0;j<n;j++) {
            Coffee c;
            cin >> c.c >> c.t >> c.s;
            cc.push_back(c);
        }
        
        unsigned long long d = k;
        long long ss = 0;
        while (d>0) {
            int ms = 0;
            int pos = 0;
            for (int j=0;j<n;j++) {
                if (cc[j].c > 0 && cc[j].t>=d && cc[j].s > ms) {
                    ms = cc[j].s;
                    pos = j;
                }
            }

            if (ms==0) {
                unsigned long long  md = 0;
                for (int j=0;j<n;j++) {
                    if (cc[j].c > 0 && cc[j].t < d && cc[j].t>md ) md = cc[j].t;
                }
                d = md;
                continue;
            }

            unsigned long long dd = d ,md = 0;
            for (int j=0;j<n;j++) {
                if (cc[j].c > 0 && cc[j].t<d && cc[j].t> md) {
                    dd = d-cc[j].t;
                    md = cc[j].t;
                }
            }
            
            if (dd > cc[pos].c) {
                dd = cc[pos].c;
            }
            if (dd > d) {
                dd = d;
            }
            
            ss += cc[pos].s * dd;
            cc[pos].c -= dd;
            d-=dd;
        }
        
        cout << "Case #" << (i+1) << ": " << ss << endl;
    }

    return 0;
}

C 64ビット整数扱えない言語とかもう使ってないよね？

整数 N が与えられて，a+b=N を満たす 0 以上の整数 a,b を選んで，aとbを２進表記した場合に1がたくさん含まれるようにする問題．

二進法の計算できるかというだけ？

A～Cの中で妙に簡単というか，本当にこれで良いのか疑って問題を何度も見直してしまった．

#include <iostream>
using namespace std;

int main() {
    int T;
    cin >> T;
    
    for (int i=0;i<T;i++) {
        int b = 0;
        unsigned long long n;
        for (cin>>n;n;n >>=1) {
            if ((n&1) == 0) {
                n--;
                b++;
                if (n&1) b++;
            } else {
                b++;
            }
        }
        cout << "Case #" << (i+1) << ": " << b << endl;
    }

    return 0;
}

*秋葉原

結婚式に着ていく礼服を買うために，秋葉原のAOKIに．

よく分からないので，店員に薦められるまま一式買う．結局８万くらいかかってしまったけど，どうなんだろ？

木曜日に出来るらしいので，取りに行かないと．

肉食べた．