minikuraを使ってみた

　minikuraを使ってみた。

minikuraとは、箱で預ける収納サービスで

1. Webで箱を申し込む
2. ダンボールが送られてくる
3. ダンボールに物を詰める
4. Webで集荷を申し込む
5. 宅配業者が自宅にくるのでダンボールを預ける

という手順でものを預けることが出来る。

クラウド上の収納スペースみたいなイメージ。

保管料は月額200円-。

　今回は、冬物衣類を預けた。取り出すときは最短で翌日受け取ることが出来るらしい。なかなか便利なサービスだと思う。Webページのデザインもいい感じだ。

元気が出る動画（1）What would you attempt to do if you knew you could not fail?

TEDでおもしろい動画を見つけた。
落ち込んだあり、元気が無くなったりしたときに見れるように『元気が出る動画』シリーズとしてブログにメモしておこうと思う。

いいなと思ったプレゼンテーションの導入部をディクテーションしてみた。

When you remove the fear of failure, impossible things suddenly become possible.

If you want to know how, ask yourself this question:
What would you attempt to do if you knew you could not fail?

If you really ask yourself this question, you can't help but feel uncomfortable. I feel a little uncomfortable. 

Because when you ask it, you begin to understand how the fear of failure constrains you, how it keeps us from attempting great things.
And life gets dull. Amazing things stop happening.
Sure, good things happen. But amazing things stop happening.

Now, I should be clear. I'm not encouraging failure.
I'm discouraging fear of failure. Because it's not failure itself that constrains us. The path to truly new, never-been-done-before things always has failure along the way. we are tested.
And in part that testing feels an appropriate part of achieving something great. Clemenceau said, "life gets interesting when we fail because it's a sign that we've surpassed ourselves."

Google Code Jam 2014 Round1B New Lottery Game

問題

A, B, Kが与えられる。以下の条件を満たす非負整数(x, y)の組み合わせ数を求めよ。

• x < A
• y < B
• (x & y) < K

ただし、

　1 <= A <= 10^9,

　1 <= B <= 10^9,

　1 <= K <= 10^9.

解法

rng..58さんの解法（LSBを固定して再帰）がとても綺麗で分かりやすかった。こんなにシンプルに書けるのかという感じ。

正答者の多くはビット単位のDPで解いているようだった。何を状態数としてDPしているのか分からなかったのでじっくりと考えてみた。

簡単のため以下のような問題を考える。

正の正数Aが与えられる。x < Aを満たす非負整数xはいくつあるか？

答えはA個なのですが、この問題をわざわざビット単位で処理して解くことを考えてみます。

#include <iostream>

using namespace std;

int main() {
    long long A;
    cin >> A;

    int a[32] = {};
    for (int i = 0; i < 32; i++)
        a[32-1-i] = A >> i & 1;

    for (int i = 0; i < 32; i++)
        cout << a[i] << " ";
    cout << endl;

    int dp[32+1][2] = {};    // dp[bit][LSBs are arbitrary or not?]
    dp[0][0] = 1;

    for (int k = 0; k < 32; k++) {             // k  : bit (notice that we process from MSB to LSB)
        for (int i = 0; i < 2; i++) {              // i  : the next bit is arbitrary or not?
            int jt = i == 1 ? 1 : a[k];            // jt : the maximum next bit
            for (int j = 0; j <= jt; j++) {        // j  : next bit
                dp[k+1][i | a[k] > j] += dp[k][i];
            }
        }
    }

    cout << dp[32][1] << endl;   // how many non-negative integers less than A are there?
                                                   // "less than" means "not used up to A" -> LSBs are arbitrary.
    return 0;
}

MSBからLSBの方向に処理していきます。
状態数を(現在の桁, 次の桁以降を任意の値に出来るか?)とするのがポイントです。

ビットkからビット(k+1)への遷移を考えます。

もし、ビットkの時点で次の桁以降を任意に決められるのであれば、x[k+1]のビットは{0, 1}のどちらでも選べます。もし、ビットkの時点で次の桁以降を任意に決められないのであれば、x[k+1]のビットは、a[k+1]の値まで選べます。このx[k+1]のビットの最大値が上のソースコードのjtです。

jtが決まると、[0, jt]まででループを回して、x[k+1]のビットの値を決めます。
もし、ビットkの時点で次の桁以降の値を任意に決められるのであれば、k+1以降も同様に次の桁以降の値を任意に決めることが出来ます。
ビットkの時点で次の桁以降の値を任意に決められない場合は、
a[k+1] = 1、かつ、x[k+1] = 0
とした場合に次の桁以降の値を任意に決められることになります。
上のソースコードの dp[k+1][i | a[k] > j] += dp[k][i]; の部分がそれに対応します。

base caseは、dp[0][0] = 1とします。次の桁は任意に決められないので2つ目の添字は0です。
問題の解は、dp[32][1]になります。これはx < Aなので、ぎりぎり目一杯Aに寄っておらずもし次のビットが存在していれば、任意に決められるという意味で2つ目の添字は1にします。ちなみにdp[32][0] = 1です。これはa[k] = 1となるビットすべてでx[k] = 1としたことを意味しています。

状態数の取り方が特殊で難しいですが、おもしろいパターンのDPです。ここまで分かれば、元々の問題はこれの応用で解けます。

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define MP(x,y) make_pair(x,y)
#define REP(i,n) for(int i=0; i<(int)(n); i++)

void solve() {
    int A, B, K;
    cin >> A >> B >> K;

    int ar[32], br[32], kr[32];  // bit expression: ar[0] = MSB, ar[31] = LSB

    for (int i = 0; i < 32; i++) {
        ar[31-i] = A >> i & 1;
        br[31-i] = B >> i & 1;
        kr[31-i] = K >> i & 1;
    }

    long long dp[32+1][2][2][2] = {};
    dp[0][0][0][0] = 1;
    
    for (int d = 0; d < 32; d++) {
        for (int i = 0; i < 2; i++) {           // next ar bit is arbitrary?
            for (int j = 0; j < 2; j++) {       // next br bit is arbitrary?
                for (int k = 0; k < 2; k++) {   // next kr bit is arbitrary?
                    if (dp[d][i][j][k] == 0)
                        continue;

                    int at = i == 1 ? 1 : ar[d];
                    int bt = j == 1 ? 1 : br[d];

                    for (int a = 0; a <= at; a++) {      // next ar bit
                        for (int b = 0; b <= bt; b++) {  // next br bit
                            int kk = a & b;              // next kk bit
                            if (k == 0 && kk > kr[d])
                                continue;

                            dp[d+1][i | ar[d] > a][j | br[d] > b][k | kr[d] > kk] += dp[d][i][j][k];
                        }
                    }
                }
            }
        }
    }
    
    cout << dp[32][1][1][1] << endl;
}

int main() {
    ios_base::sync_with_stdio(0);
    
    int T;
    cin >> T;
    REP (i, T) {
        cerr << "Case #" << i+1 << ": " << endl;
        cout << "Case #" << i+1 << ": ";
        solve();
    }

    return 0;
}

OpenCV日記（12）Dense Sampling

　SURFを使うと、画像の中から特徴的な領域をkeypointとして抽出することが出来る。このkeypointを使うと、異なる視点から同一の物体を見たときにどの点がどの点に対応しているかというマッピングを調べることが出来る。よって複数の写真をつなげてパノラマ写真を作りたいというような用途には適している。

　しかし、SURFが抽出したkeypointを使って画像識別を行いたい場合は以下のようにいくつかの問題がある。

• 画像から抽出されるkeypointの数は一定でない。
• 統計処理を行うのに必要な数のkeypointが選ばれないことがある。
• コントラストが小さい画像の場合keypointが一つも選ばれないこともある。

ということで、あらかじめ決めておいたグリッド上の点をkeypointとして選ぶdense samplingという手法がよく使われるらしい。dense samplingで選んだ点に対してSURFでdescriptorを計算するということをやってみた。

ソースコード

#include <stdio.h>
#include <iostream>

#include "opencv2/core/core.hpp"
#include "opencv2/features2d/features2d.hpp"
#include "opencv2/highgui/highgui.hpp"
#include "opencv2/nonfree/nonfree.hpp"

using namespace cv;

static void help() 
{
    printf("Usage:\n dense_sample <image> \n");
}

int main(int argc, char** argv)
{
    if(argc != 2)
    {
        help();
        return -1;
    }

    Mat img = imread(argv[1], CV_LOAD_IMAGE_GRAYSCALE);

    if(img.empty())
    {
        printf("Can't read an image.x\n");
        return -1;
    }

    DenseFeatureDetector detector(
        4.0,    // initFeatureScale (keypoints' diameter)
        2,      // featureScaleLevels (how many time apply detector with changing image scale)
        0.5,    // featureScaleMul (scale factor)
        1,      // initXyStep (distance between two keypoints)
        0,      // initImgBound (start axis of keypoints)
        false,  // varyXyStepWithScale
        false   // varyImgBoundWithScale
    );

    // detecting keypoints
    vector<KeyPoint> keypoints;
    detector.detect(img, keypoints);
    
    // computing descriptors
    SurfDescriptorExtractor extractor;
    Mat descriptors;
    extractor.compute(img, keypoints, descriptors);

    // show info
    std::cout << "keypoints of img: " << keypoints.size() << std::endl;
    std::cout << "descriptors of img: " << descriptors.size() << std::endl;

    return 0;
}

メモ書き

DenseFeatureDetectorというOpenCVのクラスを使うと簡単にdense samplingが出来た。keypointの半径が何を意味しているのかよく分かっていない。勾配ベクトルのヒストグラムを計算するときの領域サイズとかだろうか？？SURFのアルゴリズムをもう少し詳しく調べないといけない気がする。

とりあえず、これで同じサイズの画像からは同じサイズの特徴ベクトルを抽出できるようになった。descriptorをクラスタリングして、各クラスタに属するdescriptorの数をヒストグラムで表したものを特徴量として扱う手法が有名みたいなので今度はそれをやってみようと思う。

OpenCV日記（11）SURF特徴量

　SURF特徴量のデモを動かしてみた。

SURF特徴量とは?

• アフィン変換（スケーリング/回転/平行移動）によって変わりにくい特徴量。
• keypoint（画像の中の特徴的なポイント）と各keypointのdescriptor（特徴）によって特徴量が決まる。
• descriptorの計算には勾配ベクトルの情報を使用する。

SURFを実装するわけではなく、SURFを使いたいだけなのであまり深入りしないようにします。大切なのはアフィン変換の影響を受けにくいことと、画像によってkeypointの数が異なるため特徴ベクトルのサイズが一定ではないというところです。

ソースコード

サンプルコード: /samples/cpp/matcher_simple.cppを使いました。
気になったところをメモしておきます。

• SurfFeatureDetectorのコンストラクタには、パラメータhessianThresholdを渡す。このパラメータが高いほど抽出されるkeypointの数は少なくなる。
• SurfDescriptorExtractor.computeの結果は、特徴点の数 * 64のサイズの行列に格納される。行列のビット深度は32F、チャネル数は1。

結果

ABCという文字をペイントで書きました。これをimage1とします。 次にimage1の画像を90度回転させて、画像サイズを拡大してimage2を作りました。 これらのファイルを入力としてサンプルを動かしました。

Google Code Jam 2014 Round1A

　本番は風邪ひいてて出れなかったけど、次の1Bに向けて練習で解いてみた。

Aは20分くらい、Bは25分くらいで解けた。Cは難しそうだから読んでない。Round 1は突破できそうかなという手応え。

簡単な解説とソースコードをはっておく。

A. Charging Chaos

問題: https://code.google.com/codejam/contest/2984486/dashboard#s=p0

解法: すべてのデバイスが充電できるとする。このときデバイス[0]はコンセント[0], コンセント[1], ..., コンセント[N]のいずれかとマッチングするはずである。デバイス[0]とコンセント[0]がマッチしたとする。すると、どのスイッチを押し方は一意に決定することが出来る。同様にコンセント[i]がデバイス[0]とマッチしたと考えるとスイッチの押し方は一意にきまる。
よってデバイス[0]がどのコンセントにマッチしたかをループし、スイッチの押し方を求め、完全マッチするかどうか調べればよい。完全マッチする場合は押す必要のあるスイッチの個数を更新する。L=40なので64bit整数の各ビットでスイッチを表現すればよい。

ソースコード:

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define MP(x,y) make_pair(x,y)
#define REP(i,n) for(int i=0; i<(int)(n); i++)

const int INF = 1e6;

long long readLong() {
    string s;
    cin >> s;
    long long ret = 0;

    REP (i, s.length()) ret = 2 * ret + s[i] - '0';
    return ret;
}

void solve() {
    int n, l;
    cin >> n >> l;

    vector<long long> a(n), b(n), c(n);
    REP (i, n) a[i] = readLong();
    REP (i, n) b[i] = readLong();
    sort(a.begin(), a.end());

    int ret = INF;
    REP (i, n) {
        long long x = a[0] ^ b[i];
        REP (j, n) c[j] = b[j] ^ x;
        sort(c.begin(), c.end());
        if (a == c)
            ret = min(ret, __builtin_popcountll(x));
    }

    if (ret == INF)
        cout << "NOT POSSIBLE" << endl;
    else
        cout << ret << endl;
}

int main() {
    ios_base::sync_with_stdio(0);
    int T;
    cin >> T;
    REP (i, T) {
        cerr << "Case #" << i+1 << ": " << endl;
        cout << "Case #" << i+1 << ": ";
        solve();
    }

    return 0;
}

B. Full Binary Tree

問題: https://code.google.com/codejam/contest/2984486/dashboard#s=p1

解法: ルートを固定すると、1回のDFSで自分の子の数、それぞれの子を採用したときにえられる完全二分木のサイズを調べる事が出来る。子が1つ以下の場合は、自分以下の部分木で構築出来る完全二分木のサイズは1となる（自身のノードのみからなる木）。もし子が2つ以上の場合は、もっとも大きなサイズの部分木を作れるノードを2つ選べばよい。

ソースコード:

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define MP(x,y) make_pair(x,y)
#define REP(i,n) for(int i=0; i<(int)(n); i++)

const int INF = 1e6;
int N;

vector<int> edges[1000];

int dfs(int v, int par = -1) {
    int lch = 0;
    int rch = 0;

    REP (i, edges[v].size()) {
        int w = edges[v][i];
        if (w == par) 
            continue;

        int cnt = dfs(w, v);
        if (cnt > lch) swap(lch, cnt);
        if (cnt > rch) swap(rch, cnt);
    }

    if (!lch || !rch)   // this node only
        return 1;

    return 1 + lch + rch;   // has two children
}

void init() {
    REP (i, 1000) edges[i].clear();
}

void solve() {
    cin >> N;
    REP(i, N-1) {
        int v, w;
        cin >> v >> w;
        --v, --w;
        edges[v].push_back(w);
        edges[w].push_back(v);
    }

    int ret = N-1;
    REP (k, N) ret = min(ret, N-dfs(k));
    cout << ret << endl;

}

int main() {
    ios_base::sync_with_stdio(0);
    int T;
    cin >> T;
    REP (i, T) {
        cerr << "Case #" << i+1 << ": " << endl;
        cout << "Case #" << i+1 << ": ";
        init();
        solve();
    }

    return 0;
}