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分経過時点なんて、ようやく問題文読み終わってコーヒーカップの落書きしてる頃。
答え知ってる状態でもう一回実装するだけでも倍はかかる自信ある。頭の中見てみたいな

Google Code Jam Japan 2011 練習問題解いた

ちゃんと3つとも解いた!
これで予選の準備は万端… だといいな。

書いたコードはこっち(GitHub)です。以下は簡単な解説。

A: 数珠つなぎ

スナッパーのOFF/ON状態を0/1で表すと、 0000 -> 0001 -> 0010 -> 0011 -> 0100 みたいになってて、増えていく2進数と同じ形になるので、Kの数を2進数表現したときに下位Nビットが立っているかを調べればOK.

B: 数の集合

多分2つ知ってないといけないことがあると思う。1つは素数のリストの作り方で、これはエラトステネスのふるいっていうのを使った。もう一つは集合を効率よく結合していく方法で、Union-Findっていうアルゴリズムが有名らしい。チャレンジブックで習った。その2つが使えれば、あとはP以上の素数ごとに区間内からその素数の倍数を探して、属してる集合を結合していくだけ。区間の長さを超える素数は2つ以上倍数が見つかる可能性が無いので用は無いです。

C: 遊園地

計算結果をメモしておく工夫と周期的な動きを利用する工夫で計算量を減らせる問題。「iグループ目が先頭の状態でコースターが来たら、何人乗れて、次はどのグループが先頭になるのか」を先に計算しておいて再利用する方法でlargeが10秒くらい。「iグループ目が先頭の状態からいくつかコースターが来たらまたiグループ目が先頭になった」というループ状態を見つけて、その部分の計算をはしょると、largeが0.05秒くらいでした。

解くの時間かかったけど、勉強になるなぁ

GCJ Japan 2011 練習問題/数の集合

職場の先輩がLargeの答えが合わないって言ってたので僕も解いてみた。

やり方は、例えばsampleの通り10-20の区間でP=3の場合、

  1. 3の倍数12,15,18を取り出す。この段階でグループ数は-3
  2. 取り出した数は全部独立してたので、新たにグループが1つできる。グループ数+1
  3. 5の倍数10,15,20を取り出す。この段階でグループ数は-2。(15は独立してないので取り出してもグループが減らない。だから-3じゃない。)
  4. 既にグループに入ってる15を含むので、新たにグループは出来ない(統合される)。グループ数+0

みたいな感じの操作を繰り返す。
どの数がどうグルーピングされるかは気にせず、数の増減だけ見る形で、実行時間は10秒くらい。

結果… ぜんぜん違うアルゴリズムの先輩と答えが一致して、GCJのシステムからは不正解いただきました。
あっれー?二人してなんか特殊なケースを見落としてるのかな。

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

static const int MAX_PRIME_NUMBER = 1000000;

int solve(vector<int>& primes, long long A, long long B, int P) {
    int result = B - A + 1;
    vector<bool> grouped(B - A + 1, false);
    for (int i = 0; i < primes.size(); i++) {
        int divisor = primes[i];
        if (divisor >= P && divisor < B - A + 1) {
            int remNum = 0;
            int addNum = 0;
            bool isInOtherGroup = false;
            int first = (A % divisor == 0 ? 0 : (divisor - A % divisor));
            for (int j = first; j < grouped.size(); j += divisor) {
                if (!grouped[j]) {
                    remNum++;
                    grouped[j] = true;
                } else {
                    isInOtherGroup = true;
                }
            }
            if (!isInOtherGroup) {
                addNum = 1;
            }
            result -= remNum - addNum;
        }
    }
    return result;
}


int main() {
    // prepare prime numbers
    vector<int> primes;
    vector<bool> temp(MAX_PRIME_NUMBER + 1, true);
    for (int i = 2; i <= MAX_PRIME_NUMBER; i++) {
        if (temp[i]) {
            primes.push_back(i);
            for (int j = i; j <= MAX_PRIME_NUMBER; j += i) {
                temp[j] = false;
            }
        }
    }

    // read cases from standard input and print result to standard out
    int N, P;
    long long A, B;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> A >> B >> P;
        int result = solve(primes, A, B, P);
        cout << "Case #" << i << ": " << result << endl;
    }

    return 0;
}

任意のサイトを検索結果からブロックするPersonal Blocklist (Chrome Extension)

最近、Googleの検索結果に意味不明な機械翻訳ページがやたらひっかかってうざかった。
たとえば、ここ (w3support.net)。Stack Overflowの内容を持ってきてるみたい。

なんとかならんかと思ったら、任意のサイトをブロックできるChrome Extensionでてた。
https://chrome.google.com/webstore/detail/nolijncfnkgaikbjbdaogikpmpbdcdef

この類のサイトは「コンテンツファーム」っていうらしい。
このExtensionでブロックしたサイトはGoogleに送信されるらしいので、せめて大元のサイトより前に引っかからなくなることを祈りつつ…

久しぶりのTopCoder (SRM 505 div2)

ものすごく久しぶりのTopCoder.

250

あわてんぼさんが
“this is merely an example. be careful. this is a new sentence.”
みたいに頭文字を大文字にしないで書いた文がinputとして与えられるので、
“This is merely an example. Be careful. This is a new sentence.”
と正しくCapitalizeした文を返しなさい

シンプルにCapitalize必要かどうかフラグ持ちながら走査。

class SentenceCapitalizerInator {
public:
    string fixCaps(string paragraph) {
        string result = paragraph;
        bool needCapitalize = true;
        REP(i, SZ(result)) {
            if (needCapitalize && result[i] != ' ') {
                result[i] = result[i] + ('A' - 'a');
                needCapitalize = false;
            } else if (result[i] == '.') {
                needCapitalize = true;
            }
        }
        return result;
    }
};

人の解答見てtoUpperCaseの存在を思い出した///
一応Pass。

500

{1, 3, 2} という数列は1 + 3 + 2 = 1 * 3 * 2 積と和が等しくなっていて、こういうのをPerfect Sequenceと呼ぶ。
ある数列が与えられた時、そのうちの1つだけ数字を変えて完全数列が作れるかどうかを”Yes”/”No”で返せ
例えば、{1, 3, 4} は最後の要素を2に変えればPerfect SequenceなのでYes
{1, 4, 2, 4, 2, 4}はどの要素を変えてもPerfect SequenceにならないのでNo
{1, 2, 3} はすでにPerfect Sequenceになっててどれかを変えると崩れてしまうのでNo

やっかいなのが、数列の要素数は50個以下ながら、数列の各要素が0以上10^9以下なこと。
ふつうに積を求めてるとすぐオーバーフローするので、それに気をつけながら提出したつもりながら、

{1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000}

っていう典型的な境界テストで正しい答えを返せずあえなく撃沈…

class PerfectSequences {
public:
    string fixIt(vector <int> seq) {

        if (SZ(seq) == 1) return "Yes";
        
        int sum = 0;
        REP(i, SZ(seq)) sum += seq[i];

        int curPro = 1;
        REP(i, SZ(seq)) {
            curPro *= seq[i];
            if (curPro > sum) break;
        }
        if (curPro == sum) return "No";

        REP(i, SZ(seq)) {
            int curSum = sum - seq[i];
            int product = 1;
            REP(j, SZ(seq)) {
                if (i != j) {
                    if (seq[j] == 0) {
                        if (curSum == 0)
                            return "Yes";
                        else
                            goto LAST;
                    } else {
                        product *= seq[j];
                        if (product > curSum) goto LAST;
                    }
                }
            }
            if (product == 1) {
                continue;
            } else {
                if (curSum % (product - 1) == 0) {
                    return "Yes";
                }
            }
LAST:
            cerr << curSum << "/" << product << endl;
        }
        return "No";
    }
};

コーナーケースの処理をいかにきっちり書けるかが問われてるのか、それともスマートな解法があるのか…
後で考えてみよー

900
開かず。

スコアは243.29(250) + 0(500) + 0(900) – 25.00(チャレンジ失敗w) = 218.29
Ratingは 835 -> 833
J2生活はまだまだ続く

Android勉強中

まずは初歩から…

ということで、初歩からわかるAndroid最新プログラミングを購入して順々にNexus Sで動かしながら勉強中。
この本すごくいいと思ったんだけど、それは主に以下の2点。

  1. サンプルのプログラムが結構魅力ある。短いコード行数なのに結構楽しげなアプリができるので、早く自分でも何か作ってみたくなる
  2. 説明が丁寧。しかもその説明が主にコード中に描いてある。あまりコードに紙面を割いてる本は身構えちゃう事が多いんだけど、これはソースでの説明が丁寧なので、頭からまっすぐ読んでいけるメリットが大きい。

で、今マルチタッチのところまで読んだんだけど、ちょっと気になる点が…
本の通りにコーディングしても、どうもマルチタッチの時の画面の反応が悪い。気になったのはonTouchEvent()内のここ

// タッチ数を取得
int pointer_count = event.getPointerCount();

// イベントの種類で条件分岐
// タッチされた指がスライドされたことを表すイベント
if (action_type == MotionEvent.ACTION_MOVE)
{
    // MOVEイベントの場合のみ、処理の重さに応じて
    // 処理がスキップされヒストリーに保存されている
    // ヒストリー数(過去のイベント情報をどれだけ保存しているか)を取得
    int history_count = event.getHistorySize() / pointer_count;

    // ヒストリーはインデックスが若いものほど古いので、古い順に処理する
    for (int i = 0; i < history_count; i++)
    {
        // 2箇所分のタッチイベントを検出する
        for (int j = 0; j < 2; j++)
        {
            int idx = event.findPointerIndex(j);

            // タッチされていなければ、findPointerIndexが-1を返す
            if (idx >= 0)
            {
                // タッチ座標を取得
                int x = (int) event.getHistoricalX(idx, i);
                int y = (int) event.getHistoricalY(idx, i);
                mainView.setTouchXY(j, x, y);
                mainView.setTouchFlag(j, true);
            }
            else
            {
                mainView.setTouchFlag(j, false);
            }
        }
    }
}

これ、こんな感じにしないといけないんじゃないかなぁ…

if (action_type == MotionEvent.ACTION_MOVE) {
    // historyに追いやられてるTouchイベントを処理する
    for (int h = 0; h < event.getHistorySize(); h++) {
        for (int j = 0; j < 2; j++) {
            int idx = event.findPointerIndex(j);
            if (idx >= 0) {
                int x = (int)event.getHistoricalX(idx, h);
                int y = (int)event.getHistoricalY(idx, h);
                mainView.setTouchXY(j, x, y);
                mainView.setTouchFlag(j, true);
            } else {
                mainView.setTouchFlag(j, false);
            }
        }                    
    }
    // 今回のTouchイベントを処理する
    for (int j = 0; j < 2; j++) {
        int idx = event.findPointerIndex(j);
        if (idx >= 0) {
            int x = (int)event.getX(idx);
            int y = (int)event.getY(idx);
            mainView.setTouchXY(j, x, y);
            mainView.setTouchFlag(j, true);
        } else {
            mainView.setTouchFlag(j, false);
        }
    }
}

Documentはちゃんと読めてないけど、実機の挙動見る限り

  • onTouchEventが呼ばれた時、最新のTouchイベントはHistoryに入ってない。つまり指をゆっくり動かしてて余裕ある時はHistoryはずっと0件。最新のTouchイベントも処理しないといけない
  • event.getHistorySize()で帰ってくるサイズをevent.getPointerCount()で割る必要はなさそう。History1個の中にPointerCount分の情報入ってる

っていう風に見えたのでそこを直しました。間違ってたらごめんなさい。

ただ今のところそこだけでコードの品質も高そう。本屋でいくつかAndroidの入門書を立ち読みした限り、最初に読む一冊としては一番良い印象でした。

続きを読む Android勉強中

色んな言語でHello World!

Blogにsyntax highlighterのプラグインを入れたので、動作確認兼ねて色々なHello Worldを書いてみる。

C

#include <stdio.h>

int main(int argc, char **argv)
{
    printf("Hello, World!n");
    return 0;
}

C++

#include <iostream>

int main(int argc, char* argv[])
{
    std::cout << "Hello, World!" << std::endl;
}

JavaScript

document.write('Hello, World!');

Java

public class Hello {
    public static void Main(String[] args) {
        System.out.println("Hello, World!");
    }
}

C#

public class Hello
{
   public static void Main()
   {
      System.Console.WriteLine("Hello, World!");
   }
}

Python

import sys

sys.stdout.write('Hello World!n')

Haskell

main = putStrLn "Hello World!"

Scala

object HelloWorld {
  def main(args: Array[String]) {
    println("Hello World!")
  }
}

Objective-C

#include <Foundation/NSObject.h>
#include <stdio.h>

@interface HelloWorld : NSObject
- (void) hello;
@end

@implementation HelloWorld
- (void) hello{
  printf("Hello World!n");
}
@end

int main(int argc, char **argv){
  id obj = [HelloWorld alloc];
  [obj hello];

  return 0;
}

Hello Worldくらいじゃ特徴出ないか。Objective-Cなんか素直に書いたらCと全く同じになっちゃうし。HelloWorldには謎のワクワク感がある。言語に関しては、ここに挙げた言語をそれぞれ、コンパイラ/インタプリタの挙動がイメージできる程度までちゃんと覚えるのが目標です。