iPhone4(SB) vs iPhone4S(au)で通信速度比較

いろいろ間違えてiPhone4(Softbank)とiPhone4S(au)の2台持ちになってしまったので、簡単に速度比較してみました。
Softbankの方は4Sじゃない点にご注意ください。あと測定アプリが怪しい可能性もあります。

ビックカメラ有楽町店 地下ゲーム売り場 (閉店間際。人はまばら)

左がSoftbankのiPhone4, 右がauです。

平均は、SBが400KB/s, auは1100KB/sくらい。

有楽町駅ホーム (22時過ぎ。やや混雑)

SB 900KB/s, au 1100KB/s。 誤差の範囲か。

田町駅改札前 (22時過ぎ。あまり混んでない)

SB, auともに平均は1000KB/s程度

ヨドバシカメラ前 (早朝 / Vita予約行列内)

SB 1100KB/s, au 1500KB/s

まとめ

「屋内はau、屋外ではバラつき具合に違いがあるもののトータルではそれほど変わらない」っていう評判を追試しただけになってあまり面白い結果ではなかった…
あと、ダウンロードスピードは上記の通りなんですがダウンロードが始まるまでの待ち時間はSoftbankが長いことが多かったです。
これまでSoftbankでストレス感じてたのは主にこの点なので、auも増えてくるとどうなるか分からないけど今のところ満足。

GCJ Japan 決勝 参戦記

ぶっちゃけAしか合ってないので、解き方についてはなんも言えない。
結果は15点/penalty 36:23で162位。なんとか目標のTシャツには届いてた。
参戦しながら考えてたことを参戦記としてだらだら書いてみる。

B. バクテリアの増殖

  • 開始。5問もあることにびびる。点数配分をみて、なんとなくBかCを早めにとけばTシャツいけんじゃないかと根拠の薄い仮説を立てる。
  • Bを読む。ふむふむ。バクテリア増えすぎやろ。宇宙がやばい
  • 多分、周期がありそう。でも周期発見するまでに溢れまくりそうだ。(ab+c)^(ab+c)を展開してmod bに関係ないとこ外さないといかんかな?
  • ああ、数式の展開とか全然できない自分の頭がうらめしい。後回し。ていうか多分できない。
  • 次はCにトライ!するつもりだったけど、なんとなくしょんぼり状態になったので勢い付けたい。Aいこう。(終わってみれば、ここでC行ってたらTシャツもらえないところだった。)

A. アンテナ修復

  • ああ、これは直感的には、長い棒から順に、右に置いて、左において、って感じで長い棒を片方に寄せれば面積最大になりそう。
  • 証明…はいっか。他のやりかた思いつかないし、Aだし引っ掛けもなさそう。それで解いちゃえ
  • #include <iostream>
    #include <vector>
    #include <cmath>
    using namespace std;
    
    const double PI  = acos(-1.0);
    
    double solve(vector<int>& E) {
        sort(E.begin(), E.end());
        // 短い方からE0, E1, E2...とすると、円周上で... E4 E2 E0 E1 E3 ..
        // みたいに並ぶよう並び替える
        vector<int> ordered;
        for (int i = 0; i < E.size(); i++)
            if (i % 2 == 0) ordered.push_back(E[i]);
        for (int i = E.size()-1; i >= 0; i--) 
            if (i % 2 != 0) ordered.push_back(E[i]);
        
        double answer = 0;
        for (int i = 0; i < ordered.size(); i++) {
            double e1 = ordered[i];
            double e2 = i != ordered.size()-1 ? ordered[i+1] : ordered[0];
            answer += e1 * e2 * sin(2 * PI / ordered.size()) / 2;
        }
        return answer;
    }
    
    int main() {
        int T; cin >> T;
        for (int i = 1; i <= T; i++) {
            int K; cin >> K;
            vector<int> E(K);
            for (int j = 0; j < K; j++) cin >> E[j];
    
            double answer = solve(E);
            cout.precision(10);
            cout << "Case #" << i << ": " << answer << endl;
        }
    }
    

C. ワイルドカード

(※ 以下は最初から問題取り違えたまま右往左往した記録でありなんの参考にもなりません)

  • 気を取り直してCをオープン。なんか昨日チャレンジブックで読んだしゃくとり法が使えそうな気がする!
  • しゃくとり法で、Bには存在しなくてかつできるだけ短いAの部分文字列を見つける。なんとか実装。sample通ったのでsmall提出。不正解。
  • A:dz, B:ddzzのパターンうまくいってない。解が見つかってない様子。dzはBの部分文字列だけど、*がないdzはBから識別可能なのか。最初と最後の文字は区別する必要あるのね。
  • AとBの文字列それぞれの頭と終わりに文字をくっつけるアプローチ。A’:SdzE, B’:SddzzEに変換して部分文字列を見つける処理にする。さっきのパターンは通ったけど不正解
  • A:fmmfmmfmm, B:fmmfmmのパターンでうまくいってない。正解は*fmm*だけど、fmmがBの部分文字列になってるので見つかってない。頭と終わりに文字くっつけるのじゃだめか。じゃあ頭と終わりを大文字にする A’:FmmfmmfmM, B’:FmmfmMとやる。これでこのパターンは正しくなったけどやっぱり不正解。
  • A:ororor, B:or のパターンでうまくいってない。正解は*orだけどor*になってる。*o*がAを識別できるために、しゃくとり的にoが削られて最後のorが繋がってくれてない。あれ?しゃくとり法したのが間違い?
  • 〜Cで2時間経過〜 あと30分だ!シャツのためには、どれかSmall総当たりで解けそうな問題さがして稼いどいたほうがいいかな? -> あれ、A-large合ってれば大丈夫そう。このままCがんばろう
  • 下記の解法のまま時間切れ。不正解。
  • #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    string solve(string A, string B) {
        // A/B:twitter -> A'/B': TwitteR
        string A_dash = A;
        A_dash[0] = toupper(A_dash[0]);
        A_dash[A_dash.size()-1] = toupper(A_dash[A_dash.size()-1]);
        string B_dash = B;
        B_dash[0] = toupper(B_dash[0]);
        B_dash[B_dash.size()-1] = toupper(B_dash[B_dash.size()-1]);
    
        // しゃくとり法でA'の部分文字列を取り出して、B'の部分文字列になっていないものを探す
        int head = 0;
        int tail = 0;
        int curAstahNam = 0;
        string curPattern = A_dash;
        while(tail < A_dash.size()) {
            string subsec(A_dash, head, tail-head+1); // subsec: subsequence of A
            if (B_dash.find(subsec) == string::npos) {
                // pattern: *aaa* みたいな最終的な識別パターン。
                string pattern = (head == 0 ? "" : "*") + subsec + (tail == A.size()-1 ? "" : "*");
                for (int i = 0; i < pattern.size(); i++) pattern[i] = tolower(pattern[i]);
                int astahNum = (head == 0 ? 0 : 1) + (tail == A.size()-1 ? 0 : 1);
                string prevResult = curPattern;
                // patternを、問題の優先順位に従って更新
                if (pattern.size() < curPattern.size() ||
                        (pattern.size() == curPattern.size() && astahNum < curAstahNam) ||
                        (pattern.size() == curPattern.size() && astahNum == curAstahNam && pattern < curPattern)) {
                    curPattern = pattern;
                    curAstahNam = astahNum;
                }
                head++;
            } else {
                tail++;
            }
        }
        return curPattern;
    }
    
    int main() {
        int T; cin >> T;
        string A, B;
        for (int i = 1; i <= T; i++) {
            cin >> A >> B;
            string answer = solve(A, B);
    
            cout << "Case #" << i << ": " << answer << endl;
        }
    }
    

反省

  • ワイルドカードは空文字を含むって部分を読んでなかった。その時点で正解する可能性は無かった。問題はちゃんと読もう。おちつけ。
  • しゃくとり法がやりたくて飛びついてしまった感。そもそも、50文字までなら部分文字列も総当たりできた。ちゃんと問題のサイズを見て考えられるアルゴリズムを検討するべき。おちつけ。
  • a*cみたいに文字の間にワイルドカードが入るケースをなんとなくで簡単に切り捨ててた。おちつけ。
  • D,E読んでないのもいくなかった。せっかく日本語なんだから、点とれたかわからないけどとりあえず全部読んで、総当たりでSmall解けそうかぐらいは考えてみるべきだった。

予選、決勝と楽しかった!今回で競技プログラミングやる人増えたはずだし、また日本語のCodeJamやって欲しいな。スキルと落ち着きを身につけて次回はもっといい順位とりたい。チャレンジブックとGCJ過去問とTopCoderで鍛えよう

ありがとう スティーブ・ジョブズ

そんなに心酔してた自覚はなかったんだけど。

今日は朝iPhoneでニュースを見てから、なんか未来が失われたみたいな喪失感でぼーっとしてた。僕がまだ知らないイノベーションに満ちた未来はジョブズの頭の中には既に存在してると思ってたのかな。

あとに続く感情はただただ感謝。Appleの製品は僕の生活を変え、ワクワクを提供し続けてくれた。僕も、ものづくりに関わるエンジニアとして、使ってくれた人からありがとうって言ってもらえるものを作りたいと強く思いました。

今日買ったMacBook Air、上手に使っていいものを作ります。
ありがとう。

自宅サーバをシャットダウン

Amazonの東京データセンターが開設された時からやろうやろうとは思ってたんだけど、ようやくAmazon EC2/S3に乗り換えて自宅サーバをシャットダウンしました。

USにしかデータセンター無かった頃は、SSHでちょっと入ってみてレスポンスが悪すぎて「これはないわ…」って思ってたんだけど、さすがに東京だとほとんど家に置いてあるサーバと変わらない。
多分月4000円くらいの負担にはなるんだけど、45Wの自宅サーバもそれはそれで電気代月500円以上かかってたはずだし、データの多重化とかハードの修理サポート代金と思えば差額もどうということはないかと。AWSは使い慣れときたいし、ハードウェアリソースをAPI経由で得られるのはほんとに便利。GDDのスライドパズルを一時的に100インスタンスくらい立ち上げて力技で解いてみたいとか妄想膨らむ。

自宅サーバは2TのHDD積んどきながら全く使わなかったので、余生はたまに起動してファイルをバックアップするお仕事をしてもらいます。

Google Code Jam Japan 2011 予選

うまいこと全部あってた!
前も予選は良かったんです、予選は。

A. カードシャッフル

Largeの規模からすると全カードの状態は記憶できないので、目的のカードの状態だけ追う。
最後にW番目にあるカードについてだけ知りたいので、そこから逆の操作をしていって最初にどこにいるかを求める。

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

int solve(int M, int C, int W, vector<int>& A, vector<int>& B) {
    for (int i = C - 1; i >= 0; i--) {
        if (W <= B[i]) {
            W += A[i] - 1;
        } else if (W <= A[i] + B[i] - 1) {
            W -= B[i];
        }
    }
    return W;
}

int main() {
    int T, M, C, W, tmpA, tmpB;
    cin >> T;
    for (int i = 1; i <= T; i++) {
        cin >> M >> C >> W;
        vector<int> A;
        vector<int> B;
        for (int j = 0; j < C; j++) {
            cin >> tmpA >> tmpB;
            A.push_back(tmpA);
            B.push_back(tmpB);
        }
        int answer = solve(M, C, W, A, B);
        cout << "Case #" << i << ": " << answer << endl;
    }
}

C. ビット数

貪欲法。与えられた数字の下位ビットから順に見て行って、
・0だったら1と1に分割する。元の数字は繰り下げ(?)が起こる(答えは2増える)
・1だったら0と1に分割(答えは1増える)
とやる手順が答えを最大にするはず。証明はわからない。

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

int solve(unsigned long long N) {
    int result = 0;
    while (N != 0) {
        if (N & 1) {
            result += 1;
        } else {
            result += 2;
            N -= 2;
        }
        N = (N >> 1);
    }
    return result;
}

int main() {
    int T;
    cin >> T;
    for (int i = 1; i <= T; i++) {
        unsigned long long N;
        cin >> N;
        int answer = solve(N);
        cout << "Case #" << i << ": " << answer << endl;
    }
}

B. 最高のコーヒー

これすごい苦しんだ…
まず解法を思いつくまで手こずってた。
初日から順に何らかの基準でコーヒー選びたいんだけど、パラメータ多すぎてがわけが分からない。ナップサック問題的な感じ?とか右往左往。
で、おやつ食べてトイレ行ってたら、あれ逆から埋めればいいんじゃね?って気付いた。これも貪欲法か。
未来になればなるほど賞味期限の関係で飲めるコーヒーが狭まるので、未来の方から順に、その日に飲めるコーヒーの中から一番いいコーヒーを飲んで行ったらトータルでMAX満足になるはず。
証明はわからない。
で、それが分かったはいいけど実装が重い…
バグりまくったけどなんとか通した。

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

struct Coffee {
    long long c; // このコーヒーの残りのカップ数
    long long t; // 賞味期限
    int s; // 満足度
    Coffee(long long c, long long t, int s) :
        c(c), t(t), s(s) {}
};

bool GreaterT(const Coffee& lhs, const Coffee& rhs) {
    return lhs.t > rhs.t;
}

// {days}日間で、{coffee}配列の先頭{availableNum}個の種類の中から、
// 満足度が高い順に飲んでいってトータルの満足度を返す
long long consume(int availableNum, vector<Coffee>& coffee, long long days) {
    long long score = 0;
    long long remainDays = days;
    long long remainigCups = 0;
    for (int i = 0; i < availableNum; i++) remainigCups += coffee[i].c;
    // コーヒー飲んでない日が無くなるか、コーヒーが無くなるまで
    // 満足度MAXのコーヒー探して飲めるだけ飲む
    while (remainDays != 0 && remainigCups != 0) {
        int maxS = 0;
        int indexForMaxS = 0;
        for (int i = 0; i < availableNum; i++) {
            if (coffee[i].c != 0 && coffee[i].s > maxS) {
                maxS = coffee[i].s;
                indexForMaxS = i;
            }
        }
        long long cupsToDrink = min(remainDays, coffee[indexForMaxS].c);
        remainDays -= cupsToDrink;
        remainigCups -= cupsToDrink;
        coffee[indexForMaxS].c -= cupsToDrink;
        score += coffee[indexForMaxS].s * cupsToDrink;
    }
    return score;
}

// 貪欲法。期間内のおしりの方から順に満足度高いコーヒーを埋めていく。
long long solve(int N, long long K, vector<Coffee>& coffee) {
    long long score = 0;
    // 期限が遠い順にコーヒーのリストをソート
    sort(coffee.begin(), coffee.end(), GreaterT);

    // 未来の方から、「n日間はi種類のコーヒーが飲める」
    // という区間を取り出して、その期間内でどれだけ満足
    // できるかをconsume()関数で計算する
    long long curT = coffee[0].t;
    int startIndex = 0;
    int availableNum;
    for (int i = 0; i < coffee.size(); i++) {
        // i番目のコーヒーは期限が違う場合、
        // i-1番目までのi種類のコーヒーを飲めた期間を計算して、
        // その期間内でいいやつから飲んだ場合の満足度を足しこむ
        if (coffee[i].t != curT) {
            curT = coffee[i].t;
            long long days = coffee[startIndex].t - coffee[i].t;
            score += consume(i, coffee, days);
            startIndex = i;
        }
        // 初日を含む期間も同じ要領
        if (i == coffee.size() - 1) {
            long long days = coffee[startIndex].t;
            score += consume(coffee.size(), coffee, days);
        }
    }
    return score;
}

int main() {
    int T;
    cin >> T;
    for (int i = 1; i <= T; i++) {
        // read parameter from standard input
        int N;
        long long K;
        cin >> N >> K;
        vector<Coffee> coffee;
        for (int j = 0; j < N; j++) {
            long long c, t; int s;
            cin >> c >> t >> s;
            Coffee cof(c, t, s);
            coffee.push_back(cof);
        }
        // solve and print answer to standard output
        long long answer = solve(N, K, coffee);
        cout << "Case #" << i << ": " << answer << endl;
    }
}

いつものことだけど、ほんと上位陣ハンパない。
問題Bが10分とか、どうなってんの…
10分経過時点なんて、ようやく問題文読み終わってコーヒーカップの落書きしてる頃。
答え知ってる状態でもう一回実装するだけでも倍はかかる自信ある。頭の中見てみたいな