Page List

Search on the blog

2012年12月31日月曜日

デザインパターン(8) Abstract Factory

まとめ
  • オブジェクト生成のためのデザインパターン。
  • クライアントはabstract factoryを通してオブジェクトの生成を行う。
  • クライアントは生成されたオブジェクトの具体的な実装は知らない。
  • abstract factoryを継承したconcrete factoryをシステム変数やプロパティファイル、実行引数などで指定することにより、使用される具体的な工場を変えることができる。
  • 具体的な工場の種類によって生成されるオブジェクト(concrete object)の具体的な実装は異なる。
  • 新しい種類のconcrete factory / concrete objectをクライアントへの影響なく追加できる。

疑問点
Factory Method Patternとの違いがよく分かっていないような気がする。

参考[2]によると、「Factory methodは単なるメソッド。Factory methodを実装しているクラスの本来の役割はオブジェクトの生成ではない。これに対して、Abstract Factoryはオブジェクト生成のためのクラス。異なる工場では異なる製品が作成される。」とある。

Factory MethodってAbstract Factoryと同じようなことをするイメージを持っていたけど、もっと単純なものという認識でいいのだろうか。。単純にそのクラスで使いたいオブジェクトを生成するときにnewせずにcreateInstanceみたいなメソッドを使うぞ!と決めたらそれがFactory Methodになるんだろうか・・。

 お、いい説明を見つけた。Factory methodのエッセンスは、
Define an interface for creating an object, but let the classes that implement the interface decide which class to instantiate. The Factory method lets a class defer instantiation to subclasses.」 (参考[3])

ふむふむ。なんか分かってきた。逆にAbstract Factoryのエッセンスは、
Provide an interface for creating families of related or dependent objects without specifying their concrete classes.」 (参考[1])

やべっ。超分かりやすい。なんか分かったような気がする。

Factory methodの場合は、使いたいオブジェクトを生成するためのメソッドがスーパークラスで定義されているので、それを実装して具体的にどのクラスを使うか決めてください。オブジェクトを作りたいときは、newじゃなくてそのメソッド(Factory method)を使ってください。

Abstract Factoryの場合は、オブジェクトの使用者クラスは、newしてそのオブジェクトを生成するのではなく、コンストラクタで受け取った(またはグローバルにアクセスできる部分に存在する)factoryさんにオブジェクトの生成を委譲してください。ただしfactoryさんの具体的な実装については使用者は知る必要はありません。実行環境ごとにfactoryさんの具体的な実装は異なっており、生成されるオブジェクトの具体的な実装も異なりますが、使用者はこれを意識する必要はありません。

と、こういうことかな。間違っていたらご指摘いただけると嬉しいです。

参考URL
[1] http://en.wikipedia.org/wiki/Abstract_factory_pattern
[2] http://stackoverflow.com/questions/5739611/differences-between-abstract-factory-pattern-and-factory-method
[3] http://en.wikipedia.org/wiki/Factory_method_pattern

2012年12月29日土曜日

Codeforces Round #152 Robo-Footballer

Problem Statement
A robot is playing soccer. To get a point, the robot shoots the ball in a way that the ball bounces off the wall once and goes into the goal net. If the ball touches goal posts or the wall more than once, it is caught by the opponent's goal keeper. The ball is considered to touch another object if the distance between the object and the center of the ball is less than the radius of the ball. Can the robot make the goal? If so, print the coordinates of the point the robot aims at.

Approach
Look at the figure below. It's self-explaining. The key techniques are:
  1. not consider the reflection -- just go through the wall! --
  2. consider only the "edge" case where the ball almost touches a goal post.


Source Code
#include <iostream>
#include <cstdio>
#include <complex>

using namespace std;

#define EPS (1e-8)
typedef complex<double> point;

double cross(point a, point b) {
    return a.real() * b.imag() - a.imag() * b.real();
}

double distanceLnPt(point a, point b, point c) {
    return abs(cross(b-a, c-a)) / abs(b-a);
}

point intersectionLn(point a1, point a2, point b1, point b2) {
    point a = a2 - a1;
    point b = b2 - b1;
    return a1 + a * cross(b, b1-a1) / cross(b, a);
}

int main() {
    int y1, y2, yw, xb, yb, r;

    cin >> y1 >> y2 >> yw >> xb >> yb >> r;

    yw -= r;
    point a(xb, yb);
    point b(0, 2*yw-(y1+r));
    point c(0, 2*yw-y2);

    double d = distanceLnPt(a, b, c);
    point pw = intersectionLn(a, b, point(0, yw), point(1, yw));

    if (d + EPS > r)
        printf("%.18lf", pw.real());
    else
        puts("-1");

    return 0;
}

2012年12月19日水曜日

Server-side Java(3) Servletのライフサイクル

サーブレットのライフサイクル
ざっくりまとめると、
  • コンテナ上にあるサーブレットのインスタンスは一つだけ
  • リクエスト毎にスレッドを作って処理を実行
  • インスタンスはコンテナが終了した場合(または一定時間アクセスされなかった場合)に破棄される
という感じ(だと理解している)[1]。 言葉だけ聞くとふーんって感じだけど、いろいろ遊べそうなのでごくごく簡単なコードを書いて実験してみた。やったことは、
  1. インスタンスが一つしかないことを確認
  2. スレッドセーフではないようなコードを実行してみる
  3. 2.をスレッドセーフにして動作確認
  4. デッドロックを発生させてみる

1. インスタンスが一つしかないことを確認
以下のサーブレットにアクセスすると、cntがカウントアップされていく。ブラウザを閉じたり、他のブラウザからアクセスしたりした場合もcntの値はどんどんカウントアップされていく。cntはクラス変数では無く、インスタンス変数なのに。。。ということで、インスタンスはコンテナ上に一つしかないのだなと確認できる。
package jp.blogspot.techtipshoge;

import java.io.IOException;
import java.io.PrintWriter;

import javax.servlet.ServletException;
import javax.servlet.annotation.WebServlet;
import javax.servlet.http.HttpServlet;
import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;

/**
 * Servlet implementation class threadTest1
 */
@WebServlet("/threadTest1")
public class threadTest1 extends HttpServlet {
    private static final long serialVersionUID = 1L;

    int cnt;

    @Override
    public void init() {
        cnt = 0;
    }

    protected void doGet(HttpServletRequest request,
            HttpServletResponse response) throws ServletException, IOException {
        response.setContentType("text/html; charset=UTF-8");
        PrintWriter out = response.getWriter();

        out.println("<html>");
        out.println("<body>");

        out.println("cnt = " + cnt++);

        out.println("</body>");
        out.println("</html>");
    }
}


2. スレッドセーフではないようなコードを実行してみる
こんなサーブレットを書いて同時アクセスするとどうなるか試した。
package jp.blogspot.techtipshoge;

import java.io.IOException;
import java.io.PrintWriter;

import javax.servlet.ServletException;
import javax.servlet.annotation.WebServlet;
import javax.servlet.http.HttpServlet;
import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;

/**
 * Servlet implementation class threadTest2
 */
@WebServlet("/threadTest2")
public class threadTest2 extends HttpServlet {
    private static final long serialVersionUID = 1L;

    int cnt;

    @Override
    public void init() {
        cnt = 0;
    }

    protected void doGet(HttpServletRequest request,
            HttpServletResponse response) throws ServletException, IOException {
        response.setContentType("text/html; charset=UTF-8");
        PrintWriter out = response.getWriter();

        out.println("<html>");
        out.println("<body>");

        out.println("cnt = " + cnt);
        try {
            Thread.sleep(3000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        ++cnt;

        out.println("</body>");
        out.println("</html>");
    }

}
まず、普通に以下のページにアクセスする。表示するのに3秒くらいかかる。
次に2つのタブを開いてサーブレットに(ほぼ)同時アクセスしてみる。「一つ目のスレッドが更新する前に、二つ目のスレッドがcntの値を読み込むので、2つ目のスレッドの表示で2インクリメントされるべきところが1しかインクリメントされない」という状況を予想したが、そうならなかった。(ブラウザはGoogle Chrome 23.0を使用。)
確かスレッドはリクエスト単位じゃなくて、クライアント単位みたいな話をどこかで見たような。。と思ってググってるとそれらしいのを見つけた。
TomcatやJBossではApache httpdのMaxClientsと同じく、リクエスト単位ではなくクライアント単位(ソケット単位)でスレッドを割り当てる。このモデルでは、例えばmaxThreads="20"とかにしたら常に同時に20個のリクエストをさばいてくれる、という仮定は成り立たない。クライアントがkeep aliveで接続している間はスレッドも待ち続けるので、21番目のリクエストは先に接続した20のクライアントがkeep aliveを終了してコネクションを切断するまで処理されない。[2]
おそらく異なるタブでアクセスしても同一のクライアントとして扱われたのでスレッドが生成されなかったのだろう。

じゃ、ChromeとFirefoxでサーブレットに同時アクセスしてみるか。お、出来た。出来た。想定どおりのスレッドセーフではない現象が見られた。

3. 2.をスレッドセーフにして動作確認
以下のサーブレットにChromeとFirefoxを使って同時アクセスしてみた。先にcnt読み込み処理に入ったスレッドがこのサーブレットインスタンスをロックするので、他のサーブレットからはcntにアクセスできなくなってしまう。cntは期待どおりにインクリメントされた。2.のスレッドセーフじゃないバージョンは後から微妙に遅れてサーブレットにアクセスしたUAのレスポンスは3秒くらいだったが、3.のスレッドセーフバージョンの場合は6秒くらい待たされることになる。

package jp.blogspot.techtipshoge;

import java.io.IOException;
import java.io.PrintWriter;

import javax.servlet.ServletException;
import javax.servlet.annotation.WebServlet;
import javax.servlet.http.HttpServlet;
import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;

/**
 * Servlet implementation class threadTest3
 */
@WebServlet("/threadTest3")
public class threadTest3 extends HttpServlet {
    private static final long serialVersionUID = 1L;

    int cnt;

    @Override
    public void init() {
        cnt = 0;
    }

    protected void doGet(HttpServletRequest request,
            HttpServletResponse response) throws ServletException, IOException {
        response.setContentType("text/html; charset=UTF-8");
        PrintWriter out = response.getWriter();

        out.println("<html>");
        out.println("<body>");
        
        synchronized (this) {
            out.println("cnt = " + cnt);
            try {
                Thread.sleep(3000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            ++cnt;            
        }

        out.println("</body>");
        out.println("</html>");
    
    }

}


4. デッドロックを発生させてみる
とりあえずデッドロックしそうなコードを苦し紛れに書いてみた。奇数番目のアクセスはhogeから、偶数番目のアクセスはfugaからロックするというふうにしてみた。
ChromeとFirefoxで同時アクセスするとデッドロックした。
package jp.blogspot.techtipshoge;

import java.io.IOException;
import java.io.PrintWriter;

import javax.servlet.ServletException;
import javax.servlet.annotation.WebServlet;
import javax.servlet.http.HttpServlet;
import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;

/**
 * Servlet implementation class threadTest4
 */
@WebServlet("/threadTest4")
public class threadTest4 extends HttpServlet {
    private static final long serialVersionUID = 1L;

    private static class Clazz {
        
    }
    
    Clazz hoge;
    Clazz fuga;
    int flip;
    
    @Override
    public void init() {
        flip = 0;
        hoge = new Clazz();
        fuga = new Clazz();
    }

    protected void doGet(HttpServletRequest request,
            HttpServletResponse response) throws ServletException, IOException {
        response.setContentType("text/html; charset=UTF-8");
        PrintWriter out = response.getWriter();

        out.println("<html>");
        out.println("<body>");
        
        ++flip;
        try {
            if (flip % 2 == 1) {
                synchronized (hoge) {
                    out.println("hoge locked.<br/>");
                    out.flush();
                    Thread.sleep(3000);
                    synchronized (fuga) {
                        out.println("fuga locked.<br/>");
                        out.flush();
                        Thread.sleep(3000);
                    }
                }
            } else {
                synchronized (fuga) {
                    out.println("fuga locked.<br/>");
                    out.flush();
                    Thread.sleep(3000);                    
                    synchronized (hoge) {
                        out.println("hoge locked.<br/>");
                        out.flush();
                        Thread.sleep(3000);
                    }
                }
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        
        out.println("</body>");
        out.println("</html>");
    }

}

引用
[1] http://www.javadrive.jp/servlet/ini/index5.html
[2] http://d.hatena.ne.jp/nekop/20120424/1335254637

2012年12月9日日曜日

Server-side Java(2) Servletのフィルタを使う

フィルタとは?
あるServletが実行される直前に別の処理を埋め込む機能。どのServletに対して処理を埋め込むかは、servlet-mappingのurl-patternと同様に正規表現を使って指定することができる。
もともとフィルタの設定はweb.xmlに記述していたが、Servlet 3.0からはアノテーションで設定することができるようになった。
これは便利!AOPとほぼ同じに見えるんだけど、違いは何だろう。。

サンプル
Tomcat Version 7.0.33で動作確認。
/MainServletにアクセスすると、FilterServletの処理が実行されます。その後、MainServletの処理が実行されます。

[MainServlet.java]
import java.io.IOException;
import java.io.PrintWriter;

import javax.servlet.ServletException;
import javax.servlet.annotation.WebServlet;
import javax.servlet.http.HttpServlet;
import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;

/**
 * Servlet implementation class MainServlet
 */
@WebServlet("/MainServlet")
public class MainServlet extends HttpServlet {
    private static final long serialVersionUID = 1L;

    /**
     * @see HttpServlet#doGet(HttpServletRequest request, HttpServletResponse
     *      response)
     */
    protected void doGet(HttpServletRequest request,
            HttpServletResponse response) throws ServletException, IOException {
        
        response.setContentType("text/html; charset=UTF-8");
        PrintWriter out = response.getWriter();

        out.println("<html>");
        out.println("<head>");
        out.println("<title>Filter Test</title>");
        out.println("</head>");
        out.println("<body>");

        out.println("<p>MainServletの処理です。</p>");

        out.println("</body>");
        out.println("</html>");
    }
}

[FilterServlet.java]
import java.io.IOException;

import javax.servlet.Filter;
import javax.servlet.FilterChain;
import javax.servlet.FilterConfig;
import javax.servlet.ServletException;
import javax.servlet.ServletRequest;
import javax.servlet.ServletResponse;
import javax.servlet.annotation.WebFilter;

/**
 * Servlet Filter implementation class FilterServlet
 */
@WebFilter(filterName="FilterServlet", urlPatterns="/*")
public class FilterServlet implements Filter {
    /**
     * @see Filter#destroy()
     */
    public void destroy() {
    }

    /**
     * @see Filter#doFilter(ServletRequest, ServletResponse, FilterChain)
     */
    public void doFilter(ServletRequest request, ServletResponse response, FilterChain chain) throws IOException, ServletException {
        response.setContentType("text/html; charset=UTF-8");
        response.getWriter().println("Filterの処理です。");
        chain.doFilter(request, response);
    }

    /**
     * @see Filter#init(FilterConfig)
     */
    public void init(FilterConfig fConfig) throws ServletException {
    }

}

Server-side Java(1) Servletでセッションを使う

使用機能
HttpSession HttpServletRequest#getSession(boolean create) セッションを取得。引数にtrueを指定すると、セッションが取得できなかった場合に新しいセッションを作成する。
void HttpSession#setAttribute(String name, Object value) セッションに値を格納する。
Object HttpSession#getAttribute(String name) セッションから値を取り出す。

サンプル
Tomcat Version 7.0.33で動作確認。アクセス回数をカウントアップしていきます。
import java.io.IOException;
import java.io.PrintWriter;

import javax.servlet.ServletException;
import javax.servlet.annotation.WebServlet;
import javax.servlet.http.HttpServlet;
import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;
import javax.servlet.http.HttpSession;

/**
 * Servlet implementation class SessionServlet
 */
@WebServlet("/SessionServlet")
public class SessionServlet extends HttpServlet {
    private static final long serialVersionUID = 1L;
    /**
     * @see HttpServlet#doGet(HttpServletRequest request, HttpServletResponse
     *      response)
     */
    protected void doGet(HttpServletRequest request,
            HttpServletResponse response) throws ServletException, IOException {
        
        response.setContentType("text/html; charset=Shift_JIS");
        PrintWriter out = response.getWriter();
        HttpSession session = request.getSession(true);

        out.println("<html>");
        out.println("<head>");
        out.println("<title>Session Test</title>");
        out.println("</head>");
        out.println("<body>");

        int cnt = 1;
        Object visCnt = session.getAttribute("visit");
        if (visCnt != null)
            cnt = (int) visCnt + 1;
        
        out.println(cnt + "-th visit!!");
        session.setAttribute("visit", cnt);

        out.println("</body>");
        out.println("</html>");
    }
}

2012年12月1日土曜日

Dropboxを入れてみた

最近、競技プログラミングの問題をカテゴライズして、各問題ごとに直近で解いた日時、解いた回数を管理するような簡易アプリを作りました。
特にWEB上に公開するようなつもりは無くて、ローカルPCにApacheを入れてLANからのみ見れるようにしました。

1ヶ月間くらい使ってみて、問題がたまってきたので、バックアップを取りたいなと思いました。で、手軽にできるものが無いかなと考えていたところ、Dropboxを使うと簡単にできそうなのでやってみました。

やりたいこと
  • ローカルPCが壊れても、復旧できるようにしたい。
  • バックアップ対象は、DBのデータとPHPのソース。
  • バックアップの頻度は、3日に1回程度。
やったこと
まず、Dropboxをインストール。
すると、HOMEディレクトリにDropboxというディレクトリができる。
ここにファイルを入れるとDropboxのサーバーに自動で保存されるので、バックアップ完了という流れ。

あとは、自動でDBのdumpと、ソースコードをまとめてtar化するようなスクリプトを書けばいいだけ。
#!/bin/sh

data_backup_file="/home/kenjih/Dropbox/backup/procom/data/dump.sql"
src_backup_file="/home/kenjih/Dropbox/backup/procom/src/app.tar"
src_dir="/home/kenjih/dev/procom/src/app"
log="/home/kenjih/Dropbox/backup/procom/backup.log"

today=`date '+%s'`
updated_date=`stat -c '%y' ${data_backup_file}`
expire_date=`date -d "${updated_date} 3 days" '+%s'`

if [ $today -gt $expire_date ]; then
    mysqldump -u usr -ppasswd procom >${data_backup_file}
    tar -cf ${src_backup_file} ${src_dir} 2>/dev/null
    echo "backup files saved at `date '+%Y/%m/%d %T'`." >>${log}
fi

で、cronを設定。
# m h  dom mon dow   command
0 23 * * * /home/kenjih/dev/procom/src/app/Console/backup.sh

2012年11月28日水曜日

C++でハフマン符号にチャレンジ

 蟻本のコラムに載っていた「ハフマン符号」がおもしろそうだったのでチャレンジしてみました。
アルゴリズム自体はとてもシンプルですが、コーディングにハマってしまいました。
priority_queueのコンテナの中にポインタ変数を突っ込みたいとき、どうするの? 「・・・・・」 そういや、やったことないな。。木を構築するときにnewするのはやめて、あらかじめ確保したメモリプール(vertexの配列)から値を取ってきて、left、rightには配列の添字を入れるという技で対応しようかと思いましたが、比較関数用のFunctor作ってあげればいいだけみたいです。

 比較関数を自分で定義しなくても、priority_queue<vertex *>でコンパイルエラーが出なかったのがハマってしまった原因でした。ポインタ変数なので、operator<が定義されてたってことか。。

アルゴリズム
wikipedia参照。

ソースコード
※今回はアルファベット小文字のみをエンコーディング対象としました。
#include <iostream>
#include <queue>
#include <map>
#include <cstdio>

using namespace std;

struct vertex {
    char c;
    vertex *left;
    vertex *right;
    int cost;

    vertex(char _c, vertex *_left, vertex *_right, int _cost) 
        : c(_c), left(_left), right(_right), cost(_cost) {}
};

struct vertexComp {
    bool operator()(const vertex *x, const vertex *y) const {
        return x->cost > y->cost;
    }
};

void getEncode(map<char, string> &encode, vertex *vp, string s) {
    if (vp == NULL)
        return;
    if (vp->c)
        encode[vp->c] = s;
    getEncode(encode, vp->left, s+'0');
    getEncode(encode, vp->right, s+'1');
}

void huffmanCoding(int cnt[]) {
    priority_queue<vertex*, vector<vertex *>, vertexComp> Q;
    for (int i = 0; i < 26; i++)
        Q.push(new vertex((char)('a'+i), NULL, NULL, cnt[i]));

    while (Q.size() > 1) {
        vertex *v1 = Q.top(); Q.pop();
        vertex *v2 = Q.top(); Q.pop();
        Q.push(new vertex(0, v1, v2, v1->cost + v2->cost));
    }
    
    map<char, string> encode;
    getEncode(encode, Q.top(), "");

    for (map<char, string>::iterator itr = encode.begin(); itr != encode.end(); itr++)
        printf("%c [%6d] -> %10s\n", itr->first, cnt[itr->first-'a'], itr->second.c_str());
}

int main() {
    int c, cnt[26] = {0};
    while ((c = getchar()) != EOF) {
        if ('a' <= c && c <= 'z')
            ++cnt[c-'a'];
    }

    huffmanCoding(cnt);
 
    return 0;
}

実行結果
適当なWEBページの文章を読み込んで、符号化してみました。頻度が高いものほど、コードが短くなっていることが確認できました。
a [  3255] ->       1101
b [   702] ->     010111
c [  2845] ->       1010
d [  1712] ->      11100
e [  4337] ->        001
f [   715] ->     110000
g [   855] ->     111110
h [  1760] ->      11101
i [  2962] ->       1011
j [   236] ->   11000101
k [   300] ->   11111111
l [  2022] ->       0100
m [  1563] ->      11001
n [  2700] ->       0111
o [  2664] ->       0110
p [  1869] ->      11110
q [    43] ->  110001000
r [  2734] ->       1000
s [  2801] ->       1001
t [  4153] ->        000
u [  1242] ->      01010
v [   666] ->     010110
w [   514] ->    1111110
x [   282] ->   11111110
y [   511] ->    1100011
z [    45] ->  110001001

連鎖行列積を動的計画法で解く

連鎖行列積の問題を解きました。
両端の距離が小さい部分問題から解がうまっていくタイプのDPの典型問題です。

問題
Optimal Array Multiplication Sequence

ソースコード
const long long INF = 1LL<<60;
int n;
int r[16], c[16];
int mid[16][16];
long long dp[16][16];

inline string toString(int x) {
    ostringstream os;
    os << "A" << x;
    return os.str();
}

string printResult(int left, int right) {
    if (right - left == 0)
        return toString(left+1);
    return "(" + printResult(left, mid[left][right]) + " x " + printResult(mid[left][right]+1, right) + ")";
}

void solve(int &t) {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            dp[i][j] = INF;
    
    for (int i = 0; i < n; i++)
        dp[i][i] = 0;
    
    for (int k = 1; k < n; k++) {
        for (int i = 0; i + k < n; i++) {
            int j = i + k;
            for (int m = i; m < j; m++) {
                long long tmp = dp[i][m] + dp[m+1][j] + r[i] * c[j] * c[m];
                if (dp[i][j] > tmp) {
                    dp[i][j] = tmp;
                    mid[i][j] = m;
                }
            }
        }
    }
    
    cout << "Case " << ++t << ": " << printResult(0, n-1) << endl;
}

int main() {
    int t = 0;
    while (scanf("%d", &n) == 1) {
        if (n == 0)
            break;
        
        for (int i = 0; i < n; i++)
            scanf("%d %d", r+i, c+i);
        
        solve(t);
    }
    
    return 0;
}

2012年11月23日金曜日

Pythonでnext_permutation

PythonにもC++のnext_permutationと同等の標準ライブラリ関数がある。

import itertools

for x in itertools.permutations("abcd"):
    print x

とすると、

('a', 'b', 'c', 'd')
('a', 'b', 'd', 'c')
・・・・・
('d', 'c', 'a', 'b')
('d', 'c', 'b', 'a')
と表示される。

2012年11月18日日曜日

知ってると便利なSTL(10) set_intersection, set_union, set_difference

何をするものか?
2つの集合の和集合、積集合、差集合を計算し、別のコンテナに格納します。

使い方
演算対象となる2つの集合はソート済みでなければいけません。(ソートされていなければ、まずソートしてください。)
それぞれ以下のように使います。まずは、積集合を計算するset_intersectionの使用例。第5引数には結果の出力先となるコンテナのイテレータを指定します。back_inserter(v)とすると、vの最後尾に結果が挿入されます。
// set_intersection
int main() {
    int x[] = {2, 4, 6, 8, 10, 12, 14};
    int y[] = {3, 6, 9, 12, 15, 18};

    vector<int> v;
    set_intersection(x, x+7, y, y+6, back_inserter(v));
    
    for (int i = 0; i < (int)v.size(); i++)
        cout << v[i] << endl;     // 6 12

    return 0;
}

次に、和集合を計算するset_unionの使用例。
// set_union
int main() {
    int x[] = {2, 4, 6, 8, 10, 12, 14};
    int y[] = {3, 6, 9, 12, 15, 18};

    vector<int> v;
    set_union(x, x+7, y, y+6, back_inserter(v));
    
    for (int i = 0; i < (int)v.size(); i++)
        cout << v[i] << endl;    // 2 3 4 6 8 9 10 12 14 15 18

    return 0;
}

最後に、差集合を計算するset_difference。
// set_difference
int main() {
    int x[] = {2, 4, 6, 8, 10, 12, 14};
    int y[] = {3, 6, 9, 12, 15, 18};

    vector<int> v;
    set_difference(x, x+7, y, y+6, back_inserter(v));
    
    for (int i = 0; i < (int)v.size(); i++)
        cout << v[i] << endl;   // 2 4 8 10 14
 
    return 0;
}

2012年11月16日金曜日

Codeforces Round #141 The Road to Berland is Paved With Good Intentions

最近、蟻本で学習したばかりの2-SATの問題を解いてみました。

問題概要
ある国にはN個の町がある。また、M本の道路があり、それぞれの道路は2つの町を結んでいる。道路にはアスファルト舗装されている道路と、されていない道路がある。
国王が、「ある町xに繋がる道路をすべてアスファルト舗装せよ。」と命令をすると、労働者(海外からの移民で現地の言葉をうまく理解できない)たちは、アスファルト舗装されていない道をアスファルト舗装し、アスファルト舗装されている道からアスファルトを剥ぎ取る。 すべての道路をアスファルト舗装することはできるか?できるなら国王はどの町を工事対象として選べばよいかを出力せよ。

方針
以下では、町xを工事対象にすることをx、工事対象としないことを¬xと表す。
すべての道路をアスファルト舗装するためには、
(i)初期状態で道路(v, w)がアスファルト舗装済みだった場合は、
  • v → w
  • ¬v → ¬w
  • w → v
  • ¬w → ¬v
(ii)初期状態で道路(v, w)がアスファルト舗装されていなかった場合は、
  • v → ¬w
  • ¬v → w
  • w → ¬v
  • ¬w → v
が成り立たなければならない。
ということで、2-SATが使えます。

・・・・・

と普通に解いてしまいましたが、よく考えると2-SATなので、和積標準形の形じゃないとダメなのでは?何でうまくいったのだろう?と少し考えてみました。

・・・・・

そうか、a → b と ¬a∨bの真理値表は同じだから和積標準形に直せますね。

ソースコード
強連結成分分解の実装は、省略。
int n, m;

int main() {
    cin >> n >> m;

    V = 2*n;
    REP (i, m) {
        int a, b, c;
        cin >> a >> b >> c;
        --a, --b;

        if (c == 1) {
            add_edge(a, b);
            add_edge(a+n, b+n);
            add_edge(b, a);
            add_edge(b+n, a+n);
        }
        else {
            add_edge(a, b+n);
            add_edge(a+n, b);
            add_edge(b, a+n);
            add_edge(b+n, a);
        }
    }

    scc();

    REP (i, n) {
        if (cmp[i] == cmp[i+n]) {
            puts("Impossible");
            return 0;
        }
    }

    vector<int> cities;
    REP (i, n) {
        if (cmp[i] < cmp[i+n])
            cities.push_back(i+1);
    }

    cout << cities.size() << endl;
    REP (i, cities.size())
        cout << cities[i] << " ";
    cout << endl;

    return 0;
}

2012年11月13日火曜日

Codeforces #149 XOR on Segment

問題概要
n個の正数a1, a2, ..., anからなる配列aに対して、以下の2種類のクエリーが複数回投げられるので高速に処理せよ。
  1. (l, r)が与えられるので、[al, ar]の和を求める。
  2. (l, r, x)が与えられるので、ai := ai xor x, i = l, l+1, ..., rのようにaの値を更新する。
タイプ1.のクエリについてのみ結果を出力せよ。

方針
とりあえず、雰囲気的にセグメント木を使うのは分かる。あとビット毎に独立して処理すればいいのも分かった(TopCoderで似たような問題といたため)。更新系の処理をうまく書く方法がすぐには浮かばなかったけど、
  • 小さなセグメントにupdateをかけて、それを含む大きなセグメントにreadが投げられたらどうするか?
  • 大きなセグメントにupdateをかけて、それに含まれる小さなセグメントにreadが投げられたらどうなるか?
を考えて、うまく行くようにいろいろ書いていたら、出来てた。
セグメント木、得意ではないですが好きです。

ソースコード
#include <iostream>

using namespace std;

int n, m;
int segsum[30][1<<18];
int segflip[30][1<<18];

void update(int pos, int k, int l, int r, int a, int b) {
    if (r <= a || b <= l)
        return;
    if (a <= l && r <= b) {
        segflip[pos][k] ^= 1;
        segsum[pos][k] = r-l-segsum[pos][k];
    } 
    else {
        int c = (l+r) >> 1;
        update(pos, 2*k+1, l, c, a, b);
        update(pos, 2*k+2, c, r, a, b);
        segsum[pos][k] = segsum[pos][2*k+1] + segsum[pos][2*k+2];
        if (segflip[pos][k])
            segsum[pos][k] = r-l-segsum[pos][k];
    }
}

int read(int pos, int k, int l, int r, int a, int b) {
    if (r <= a || b <= l)
        return 0;
    if (a <= l && r <= b)
        return segsum[pos][k];
    int c = (l+r) >> 1;
    int ret = 0;
    ret += read(pos, 2*k+1, l, c, a, b);
    ret += read(pos, 2*k+2, c, r, a, b);
    if (segflip[pos][k])
        ret = min(r, b) - max(l, a) - ret;
    return ret;
}

void insert(int pos, int k, int l, int r, int x) {
    if (x < l || r <= x)
        return;
    if (r - l == 1)
        segsum[pos][k]++;
    else {
        int c = (l+r) >> 1;
        insert(pos, 2*k+1, l, c, x);
        insert(pos, 2*k+2, c, r, x);
        segsum[pos][k] = segsum[pos][2*k+1] + segsum[pos][2*k+2];
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        long long a;
        cin >> a;
        for (int j = 0; j < 30; j++) {
            if (a & 1 << j)
                insert(j, 0, 0, n, i);
        }
    }
    
    cin >> m;
    while (m--) {
        int type, l, r, x;
        cin >> type;
        if (type == 1) {
            cin >> l >> r;
            long long ret = 0;
            for (int k = 0; k < 30; k++)
                ret += (long long)read(k, 0, 0, n, l-1, r) << k;
            cout << ret << endl;
        }
        else {
            cin >> l >> r >> x;
            for (int k = 0; k < 30; k++)
                if (x & 1 << k)
                    update(k, 0, 0, n, l-1, r);
        }
    }

    return 0;
}

2012年11月10日土曜日

codeforces #148 World Eater Brothers

問題概要
n個の節点がn-1個の有向枝で結ばれている。枝の方向を考えなければこのグラフは連結である。節点集合から2つの節点を選び、その2点を始点とすればすべての節点へ到達できるようにしたい。2つの節点を最適に選んだときに、向きを変更しなければならない枝の数の最小値を求めよ。

方針
節点集合をVとして、Vを2つの集合に分ける。これをU, Wとする。 Uから最適な節点を選び、その節点からU内のすべての節点へ到達できるようにした場合にかかるコスト(変更すべき枝の向き)を計算する。Wも同様のことをする。
すべてのV -> {U, W}分割について上記を行い、(Uにかかるコスト + Wにかかるコスト)の最小値を求めればよい。
問題のグラフは辺の方向を考えなければ木なので、V -> {U, W}の分割の方法は枝の数だけある。
U, Wからそれぞれ最適な頂点を選ぶ処理は、O(|U|), O(|W|)なので、全体として、O(n2)で計算できる。

ソースコード
int n;
vector<pair<int, int> > G[3000];

int dfs(int v, int p) {
    int ret = 0;

    REP (i, G[v].size()) {
        int u = G[v][i].first;
        int dir = G[v][i].second;

        if (u == p)
            continue;

        ret += dfs(u, v) + (dir == -1);
    }
    return ret;
}

int chRoot(int v, int p, int acc) {
    int ret = acc;
    
    REP (i, G[v].size()) {
        int u = G[v][i].first;
        int dir = G[v][i].second;

        if (u == p)
            continue;
        
        ret = min(ret, chRoot(u, v, acc + dir));
    }

    return ret;
}

int solve() {
    if (n < 3)
        return 0;

    int ret = 1<<30;
    REP (v, n) REP(i, G[v].size()) {
        int u = G[v][i].first;
        int acc1 = dfs(v, u);
        int acc2 = dfs(u, v);
        
        ret = min(ret, chRoot(v, u, acc1) + chRoot(u, v, acc2));
    }
    return ret;
}

int main() {
    cin >> n;
    REP (i, n-1) {
        int a, b;
        cin >> a >> b;
        G[--a].push_back(make_pair(--b, 1));
        G[b].push_back(make_pair(a, -1));
    }

    cout << solve() << endl;

    return 0;
}

2012年10月31日水曜日

Codeforces Round #147 Build String

問題概要
文字列tとn個の文字列s1, s2, ...., snが与えられる。sを用いてtを作る。一回の操作で
  1. s1, s2, ...., snの中から任意の文字列を一つを選ぶ。
  2. 1.で選んだ文字列から任意の一文字を選び、紙に書く。
  3. 選んだ文字列から選んだ文字を消去する。
この操作を複数回行い、紙に書かれた文字列がtと等しくなるようにする。ただし、それぞれのsi, i = 1,2, ..., nについて使用できる回数が決まっている。i番目の文字列を使用するとコストがiかかる。tを作るために必要な最小コストを求めよ。


方針
最小費用流を使う。
乱択を使った解法でシステムテスト通過している人がいて、おもしろいなぁと思って同じようなことやってみたけど、以下のケースで落とせるじゃん。。ただ、この考え方は覚えておいて損は無さそうだ。
abcdefghijklmnopqrstuvwxyz        
26
abcdefghijklmnopqrstuvwxyz 1
abcdefghijklmnopqrstuvwxy  1
abcdefghijklmnopqrstuvwx   1
abcdefghijklmnopqrstuvw    1
abcdefghijklmnopqrstuv     1
abcdefghijklmnopqrstu      1
abcdefghijklmnopqrst       1
abcdefghijklmnopqrs        1
abcdefghijklmnopqr         1
abcdefghijklmnopq          1
abcdefghijklmnop           1
abcdefghijklmno            1
abcdefghijklmn             1
abcdefghijklm              1
abcdefghijkl               1
abcdefghijk                1
abcdefghij                 1
abcdefghi                  1
abcdefgh                   1
abcdefg                    1
abcdef                     1
abcde                      1
abcd                       1
abc                        1
ab                         1
a                          1


ソースコード
上が最小費用流を使った解法、下が乱択を使った解法。
using namespace std;

int V;
int main()
{
    string tar;
    int n;

    cin >> tar >> n;
    vector strs(n);
    vector caps(n);

    REP(i, n) 
        cin >> strs[i] >> caps[i];

    V = 1 + n + 26 + 1;
    REP (i, n) {
        add_edge(0, 1+i, caps[i], 0);
        REP (j, 26) {
            int cnt = count(strs[i].begin(), strs[i].end(), (char)(j+'a'));
            if (cnt)
                add_edge(1+i, 1+n+j, cnt, i+1);
        }
    }

    REP (i, 26) {
        int cnt = count(tar.begin(), tar.end(), (char)(i+'a'));
        if (cnt)
            add_edge(1+n+i, 1+n+26, cnt, 0);
    }

    cout << min_cost_flow(0, 1+n+26, tar.length()) << endl;

    return 0;
}

const int INF = 1<<30;
string tar;
int n;
vector strs;
vector caps;
vector pri;

int calc(vector &x, vector &y, char c) {
    REP (i, n) { 
        if (y[i] == 0) 
            continue;
        REP (j, x[i].length()) {
            if (x[i][j] == c) {
                x[i][j] = ' ';
                y[i]--;
                return i+1;
            }
        }
    }
    return INF;
}

int main() {
    cin >> tar >> n;
    strs.assign(n, "");
    caps.assign(n, 0);
    pri.assign(tar.length(), 0);

    REP(i, n)
        cin >> strs[i] >> caps[i];
    REP(i, tar.length())
        pri[i] = i;
    
    int ret = INF;
    while (clock() < 1.8*CLOCKS_PER_SEC) {
        random_shuffle(pri.begin(), pri.end());

        vector _strs = strs;
        vector _caps = caps;

        int total = 0;
        REP (k, tar.length()) {
            char c = tar[pri[k]];
            
            int cost = calc(_strs, _caps, c);
            if (cost == INF) {
                total = INF;
                break;
            } else {
                total += cost;
            }
        }
        ret = min(ret, total);
    }

    if (ret == INF) 
        cout << -1 << endl;
    else
        cout << ret << endl;

    return 0;
}

2012年10月30日火曜日

読書「ボッコちゃん」

星 新一の「ボッコちゃん」を読みました。50作のSF短篇小説が入っています。 個人的には鏡が一番おもしろかったです。

2012年10月27日土曜日

Codeforces Round #146 Let's Play Osu!

問題概要
Osuと呼ばれるゲームをする。連続するx個の○についてx2の得点が与えられる。 n文字の文字列が与えられるので、得点の期待値を求める。ただし、i番目の文字が○である確率はpiである。

方針
n2 = 2 * nC2 + n
という関係から以下のような問題の読み替えができる。
「連続する○について○の長さの2乗が加点される。」→ 「一つの○につき1点加点し、○のペアについて間に×が一つもなければ2点加点する。」
これを利用して期待値を計算する。後半のペアうんぬんのところは動的計画を使って計算する。

ソースコード
using namespace std;

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

int main() {
    int n;
    static double p[100000];
    cin >> n;

    REP(i, n) scanf("%lf", p+i);

    double ret = 0;
    double q = 0;
    REP (i, n) {
        ret += p[i];
        if (i > 0)
            q = (q + p[i-1]) * p[i];
        ret += 2*q;
    }

    printf("%.8lf\n", ret);
    return 0;
}

Codeforces Round #141 Fractal Detector

問題概要
ある規則によって作成されるフラクタルが、与えられた平面上にいくつかるか数える。

方針
フラクタルかどうかは分割統治で判定できる。メモ化して高速化する。実装ややこしそうと思ったけど、以外と簡単に書けた。

ソースコード
using namespace std;

#define REP(i,n) for(int i=0; i<(int)(n); i++)

string bd[512];
bool dp[1<<4][10][512][512];
int r, c;

int main() {
    cin >> r >> c;

    REP (i, r) cin >> bd[i];
    
    // base case
    for (int i = 0; i + 1 < r; i++) {
        for (int j = 0; j + 1 < c; j++) {
            int mask = 0;
            mask |= (bd[i][j] == '*');
            mask <<= 1;
            mask |= (bd[i][j+1] == '*');
            mask <<= 1;
            mask |= (bd[i+1][j] == '*');
            mask <<= 1;
            mask |= (bd[i+1][j+1] == '*');
            dp[mask][1][i][j] = true;
        }
    }

    int size = 2;
    for (int k = 2; k < 10; k++) {
        size *= 2;
        for (int i = 0; i + size - 1 < r; i++) {
            for (int j = 0; j + size - 1 < c; j++) {
                for (int p = 0; p < 16; p++) {
                    dp[p][k][i][j] = true;
                    for (int q = 0; q < 4; q++) {
                        int x = i;
                        int y = j;

                        if ((q & 1) == 0) y += size / 2;
                        if (q / 2 == 0) x += size / 2;

                        if (p & 1 << q)
                            dp[p][k][i][j] &= dp[15][k-1][x][y];
                        else
                            dp[p][k][i][j] &= dp[p][k-1][x][y];
                    }
                }
            }
        }
    }

    int ret = 0;
    for (int i = 0; i < 512; i++)
        for (int j = 0; j < 512; j++)
            for (int p = 0; p < 16; p++)
                for (int q = 2; q < 10; q++)
                    ret += dp[p][q][i][j];

    cout << ret << endl;
    
    return 0;
}

2012年10月6日土曜日

読書「スティーブ・ジョブズ 驚異のプレゼン」

会社の人に勧められて読みました。以下のいずれかに当てはまる人は読んでおいた方がいいと思います。実践すれば誰でもプレゼンがうまくなるテクニックが盛り沢山です。
  • 営業職の人
  • 人に何かを教える職業に就いている人
  • 学会発表をする人
  • 面接を受ける人
  • スティーブ・ジョブズのスピーチを聞いて感動したことがある人


 

特に印象に残ったところだけ紹介します。

習得には1万時間が必要
どのようなことであれ、世界的な達人というレベルに熟達するには1万時間の練習が必要。1日3時間を10年続けること。

バケツ方式
尋ねられる可能性が高い質問をリストアップし、カテゴライズしておく。実際に質問されたら用意しておいたバケツにあてはまる回答をする。7種類バケツを用意しておけば十分。

なぜ気にかける必要があるか
なぜ気にかける必要があるのかを話す。自分自身にメリットがない話を聞きたいと思う人はいない。

2012年10月1日月曜日

サーバー奮闘記(24) SCPでファイル転送

sshの設定が以下のような場合、どのようにオプションを書けばいいかメモしておく。
  • 秘密鍵で認証(以下の例では秘密鍵は~/.ssh/id_rsaに格納されているとする。)
  • ポートはデフォルトの22番ではない(以下の例では1234番のポートを使用しているとする。)

リモートからローカルへファイル転送
scp -P1234 -i ~/.ssh/id_rsa user@host:source_file_path destination_file_path

ローカルからリモートへファイル転送
scp -P1234 -i ~/.ssh/id_rsa source_file_path user@host:destination_file_path

2012年9月27日木曜日

フィボナッチ数列の最大公約数について

Codeforces#140「Anniversary」で出てきた
(Fib(x), Fib(y)) = Fib((x, y))
を簡単に導出してみようと思います。

隣り合うフィボナッチ数は互いに素
隣り合うフィボナッチ数が互いに素ではなかったと仮定します。そのとき、

(Fib(x), Fib(x+1)) = d, d>0
となるようなdが存在します。このとき、フィボナッチ数の定義より、

Fib(x-1) = Fib(x+1) - Fib(x)
なので、d | Fib(x-1) となります。これを繰り返すと、d| Fib(1)となりますがこれはFib(1) = 1と矛盾します。 よって背理法より、隣り合うフィボナッチ数は互いに素となります。

フィボナッチ数の加法定理
x>2,   y>1について、
Fib(x+y) = Fib(x)Fib(y+1) + Fib(x-1)Fib(y)
という性質が成り立ちます。数学的帰納法を使うと証明できるそうですが、ここでは簡単に上の定理が正しいことを説明します。

Fib(x)は階段を1段ずつ、または1段飛ばしで登っていき、x段目に辿り着いたときの上り方のパターン数と考えることができます。Fib(x+y)はx+y段目まで登るとき(最下段からx+y-1段登ったとき)のパターン数です。
最下段からx+y-1段登るときのパターン数を、x段目を通るか通らないかに場合分けすると、
(x+y-1段登るときのパターン数)
= (x段目を通るパターン数) + (x段目を通らないパターン数)
= (x-1段登ったあと、y段登るパターン) + (x-2段登った後、1段飛ばしをして、y-1段登るパターン)
= (x-1段登るパターン数 * y段登るパターン数) + (x-2段登るパターン数 * y-1段登るパターン数)
ということで、まさにこれが加法定理と同じです。

(Fib(x), Fib(y)) = Fib((x,y))
さて、いよいよ目的の定理を考えます。まずは、Fib(x)とFib(x+y)の最大公約数を考えてみます。
(Fib(x), Fib(x+y))
= (Fib(x), Fib(x)Fib(y+1) + Fib(x-1)Fib(y))     (∵加法定理より)
= (Fib(x), Fib(x-1)Fib(y))     (∵ Fib(x) | Fib(x)Fib(y+1)より)
= (Fib(x), Fib(y))     (∵ (Fib(x), Fib(x-1)) = 1より)

はい、来ました。 (Fib(x), Fib(x+y)) = (Fib(x), Fib(y))
です。これを再帰的に繰り替えしていくとユークリッドの互除法(の引き算バージョン)によって、
(Fib(x), Fib(x+y)) = Fib((x, x+y))
となります。よって、目的の定理が成り立ちます。

2012年9月23日日曜日

Codeforces #139 Unsolvable

問題概要
z = [x/2] + y + xy, z > 0
を満たす正の整数x, yが存在しないようなzのうち、n番目に小さなものをMOD 1000000007で答えよ。ただし、[a]はaの整数部を表す。

方針
こういう数論系の問題は好きです。Editorialのように式変形していくと、メルセンヌ素数と関連する値になることがわかります。


ソースコード
const long long MOD = 1000000007LL;
int mers[] = {
    2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607,
    1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941,
    11213, 19937, 21701, 23209, 44497, 86243, 
    110503, 132049, 216091, 756839, 859433,
    1257787, 1398269, 2976221, 3021377, 6972593,
    13466917, 20996011, 24036583
};

int main() {
    int n;

    cin >> n;
    int x = mers[n-1];
    long long ret = 1;

    REP(i, x-1) {
        ret <<= 1;
        ret %= MOD;
    }

    cout << (ret+MOD-1)%MOD << endl;
    
    return 0;
}
おまけ
2^p - 1が素数となるためには、pは素数でなくてはいけません。1023とかパッと見、素数っぽいですが、2^10 - 1で10は素数ではないため、1023は素数ではありません。
いや、、こんなことしなくても、1023は3で割れることが一目瞭然なので、素数じゃないのは明らかか。。

Codeforces #139 Snake

問題概要
蛇がN*Mサイズのブロックを動き回る。りんごに辿り着くまでに蛇が移動しなければならない最小移動数を求めよ。

方針
(蛇の頭の座標、蛇の体部の相対座標)を状態数にしてBFSする。この「相対座標を状態数にとる」という発想はおもしろいと思いました。各部位について、相対座標は2bitで表現します。蛇の体部は最大で8つの部位から成り立っているので、全体として2^16あれば頭以外の部分の位置を表現できます。

ソースコード
#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  

typedef pair<int, pair<int, int> > pii;

const int INF = 1<<30;
int r,c;
string bd[16];
int vis[16][16][1<<16];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
vector<pii> snake;

struct status {
    int x;     // x of snake's head
    int y;     // y of snake's head
    int dir;   // directions of snake's body
};

int getDir(int sx, int sy, int tx, int ty) {
    if (sy == ty) {
        if (sx < tx) return 0;
        return 2;
    }
    else {
        if (sy < ty) return 3;
        return 1;
    }
    return -1;
}

bool hitBody(int x, int y, int dir) {
    int hx = x;
    int hy = y;

    int N = snake.size();
    int mask = (N-2)*2;
    FOR (i, 1, N) {
        int d = dir >> mask & 3;

        if (d == 0) ++x;
        else if (d == 1) --y;
        else if (d == 2) --x;
        else ++y;
                 
        if (x == hx && y == hy)
            return true;

        mask -= 2;
    }
    return false;
}

int main() {
    cin >> r >> c;
    REP(i, r) cin >> bd[i];
    
    REP(i, r) REP(j, c) if ('1' <= bd[i][j] && bd[i][j] <= '9') {
        snake.push_back(make_pair(bd[i][j]-'0', make_pair(i, j)));
    }

    sort(snake.begin(), snake.end());
    int dir = 0;
    FOR (i, 1, snake.size()) {
        dir <<= 2;
        pair<int, int> p1 = snake[i-1].second;
        pair<int, int> p2 = snake[i].second;

        dir += getDir(p1.first, p1.second, p2.first, p2.second);
    }

    int ret = -1;
    queue<status> q;
    pair<int, int> head = snake[0].second;
    q.push((status){head.first, head.second, dir});
    memset(vis, -1, sizeof(vis));
    vis[head.first][head.second][dir] = 0;

    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int dir = q.front().dir;
        
        if (bd[x][y] == '@') {
            ret = vis[x][y][dir];
            break;
        }

        q.pop();
        
        REP(k, 4) {
            int xx = x + dx[k];
            int yy = y + dy[k];

            if (xx < 0 || xx >= r) continue;
            if (yy < 0 || yy >= c) continue;
            if (bd[xx][yy] == '#') continue;

            int dir_t = dir >> 2;
            dir_t += getDir(xx, yy, x, y) << 2 * (snake.size()-2);
            if (hitBody(xx, yy, dir_t)) continue;
            
            if (vis[xx][yy][dir_t] == -1) {
                vis[xx][yy][dir_t] = vis[x][y][dir] + 1;
                q.push((status){xx, yy, dir_t});
            }
        }
    }

    cout << ret << endl;

    return 0;
}

2012年9月22日土曜日

JSONView

Google Chromeに「JSONView」を入れました。これで、ブラウザから綺麗にインデントされたJSONを見ることができます。日本語もエスケープされていない状態で表示されます。

インストールは以下のページで「ADD TO CHROME」を押すだけです。



便利すぎる。もっと早く入れておけばよかった。。

2012年9月9日日曜日

gitチートシート

自分用メモ。

glossary
  • working tree: 実際にローカルで編集しているリソース
  • staging area(index): コミットする予定のリソースを格納する場所
  • local repository: 自分のPCにあるレポジトリ
  • remote repository: リモートにあるレポジトリ
  • HEAD: 最新のコミット
checkout
  • hoge.txtをindexの状態に戻す。→git checkout hoge.txt
  • カレントディレクトリ配下をindexの状態に戻す。→git checkout .
  • hoge.txtをHEADの状態に戻す。→git checkout HEAD hoge.txt
commit
  • 直前のコミットを修正する。(ログのコメントも修正可)→git commit --amend
config
  • デフォルトのエディタを変更する。→ git config --global core.editor emacs
diff
  • 空白文字の変量を無視して差分を取る。→ git diff -b
  • working treeとindexの差分をとる。 → git diff
  • working treeとHEADの差分を取る。→ git diff HEAD
  • working treeと1つ前のコミットの差分を取る。→git diff HEAD^
  • indexとHEADの差分を取る。→git diff --cached
  • 色を付けてdiffを見やすくする。→git diff --color
  • ファイルの内容は表示せず、ファイル名のみ表示する。→ git diff --name-only
reset
  • 直前のコミットを取り消す。(working treeには何もしない)→ git reset --soft HEAD^
  • 直前のコミットを取り消す。(working treeの内容もHEAD^の状態に戻す)→ git reset --hard HEAD^

2012年9月1日土曜日

Codeforces Round #136 (Div. 2)

結果
ひさびさにプロコンに参加した。最近は(Java, Eclipse)ばっかりだったので、(C++, Emacs)でうまく書けるか不安だったが思ったより鬼は黒くなかった。 3/5AC、160位/1925人だった。(配列の最大要素数をミスってて問題DはRuntime Errorで死んでいた。それがなかったら20位くらいだった。もったいない。)

 問題D、Eがおもしろかった。解答は以下のとおり。

D. Little Elephant and Array
[l, r]区間に現れる回数がちょうどxとなるような正の整数xの個数を求める問題(1 <= l <= r <= n)。xの候補となるような正の整数はたかだか√n個程度になることに気付くかどうかがポイント。[1, y]区間にそれぞれのxが何回現れるかをメモリ上に保持すると(1 <= y <= n)、1クエリーがO(√n)で捌ける。
using namespace std;

const int MAX_LEN = (int)1e5;

int xs[MAX_LEN];
int nums[500][MAX_LEN+1];

int main() {
    int n, m;
    cin >> n >> m;
    
    map<int, int> cnt;
    for (int i = 0; i < n; i++) {
        cin >> xs[i];
        cnt[xs[i]]++;
    }
    
    vector<int> vs;
    for (map<int, int>::iterator itr = cnt.begin(); itr != cnt.end(); itr++) {
        if (itr->second >= itr->first)
            vs.push_back(itr->first);
    }
    
    int l = vs.size();
    memset(nums, 0, sizeof(nums));
    for (int i = 0; i < l; i++) {
        for (int j = 0; j < n; j++) {
            nums[i][j+1] = nums[i][j];
            if (vs[i] == xs[j])
                nums[i][j+1]++;
        }
    }
    
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        
        int ret = 0;
        for (int j = 0; j < l; j++) {
            if (nums[j][b] - nums[j][a-1] == vs[j])
                ++ret;
        }
        cout << ret << endl;
    }
    
    return 0;
}
E. Little Elephant and Shifts
長さnの順列a, bが与えられる。bのn個の巡回シフト集合に対して、それとaの距離を求める。2つの順列の距離は、 minimum |i - j|, that ai = bjと定義される。multisetをうまく使うと解ける。multisetまでは分かったんだけど、lower_bound使うってのが閃かなかった。データ構造の使い方を問う良問。
using namespace std;

#define REP(i, n) for(int i=0; i<(int)(n); i++)
#define FOR(i, s, e) for (int i = (int)(s); i < (int)(e); i++)

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

    vector<int> a(N);
    vector<int> b(N);

    REP(i, N) cin >> a[i];
    REP(i, N) cin >> b[i];

    vector<int> x(N);
    vector<int> y(N);

    // set postions of a[i] and b[i]
    REP(i, N) x[--a[i]] = i;
    REP(i, N) y[--b[i]] = i;
    
    multiset<int> dis;
    REP(i, N) dis.insert(y[i]-x[i]);
    
    REP(k, N) {
        int ret = 0x7fffffff;
        __typeof(dis.begin()) itr = dis.lower_bound(k);
        ret = min(ret, *itr-k);
        if (itr != dis.begin())
            ret = min(ret, abs((*--itr)-k));
        cout << ret << endl;
        int head = b[k];
        dis.erase(dis.find(y[head]-x[head]));
        dis.insert(N-1-x[head]+k+1);
    }

    return 0;
}

2012年8月31日金曜日

デザインパターン(7) Builder

まえおき
以下の書籍でBuilderパターンについて勉強した。


まとめ
  • 構造を持ったインスタンスを組み上げるときに利用する。
  • Builder、ConcreteBuilder、Director、Clientによって構成される。
疑問点
  • Builderパターンはオブジェクト生成のためのデザインパターン。Factory Methodパターンと何が違うのか?
Factory Methodパターンは異なる種類のオブジェクトを生成するときのパターンで、Builderパターンはオブジェクトの生成手順をきれいにまとめるためのパターンなので、目的がまったく違う。以下のような記述が参考サイト[1]にあった。
The rule of thumb I noticed after some time was the following: Consider a restaurant. The creation of "Todays Meal" is a factory pattern, because you tell the kitchen "get me todays meal" and the kitchen/factory decides what object to generate. based on hidden critereas.

The builder appears if you ordered a custom pizza. In this case, the waiter tells the chef/builder "I need a pizza, add cheese, cheese, onions and bacon to it!". Thus, the builder exposes what attributes the generated object should have, but hides how to set them.
  • パッと見、Template Methodパターンと同じに見えるんだけど、何が違うのか?
これは明確な違いが自分ではよく分からなかった。Builderパターンの方が抽象度や独立性が高いような気がする。Template Methodパターンだと親-子クラスという関係があるし、同じ部品を別の処理フローでテンプレート化したいときに処理フローの数だけ親-子のペアを毎回書かないといけないような気がする。それに比べて、Builderパターンの方はdirector-builder間の関係が移譲なのでそれぞれの独立性が高いのかなと思う。参考サイト[2]になんとなくしっくりくるような説明があった。

Template method is really just a way to define some methods that each subclass must define.

The builder pattern is used to construct a more complex object.

Lets say that we want to construct different Saab (car brand) models. Each model has different engines,lights etc.

If we were to use the template method pattern we had to create one class for each single combination of cars or use some nasty inheritance hierarchies. A lot of those methods would also contain duplicate code.

With the build pattern we can instead take different parts and compose those together to a complete car. Hence we can reuse a engine for every model if needed and we can also customize each part of the car.

その他
  • 書籍の練習問題がおもしろかった。久しぶりにswingでGUIを書いた。今度簡単なゲームか何か書いてみようかな。
参考サイト
  1. When would you use the Builder Pattern? [closed]
  2. Differences between builder pattern vs template method

2012年8月29日水曜日

Spring Framework -Aspect Oriented Programming-

Spring特集第3弾。Aspect Oriented Programming(以下AOP)について書きます。

AOPとは?
共通的な機能を後から付け加える仕組みです。 具体的に言うと、
  1. ロギング
  2. キャッシング
  3. セキュリティ
  4. 認証
などの共通的に利用される機能をビジネスロジックから切り離して、後から横断的に追加できるような仕組みのことです。

Before AdviceとAfter Advice
まずは、一番簡単なBefore AdviceとAfter Adviceの例を書きます。Adviceとは、AOPの用語で追加する共通処理のことです。何をやっているかは以下のサンプルを見れば一目瞭然です。
// src/cc/co/goodpreparations/Person.java
package cc.co.goodpreparations;

public class Person {
    public void smile() {
        System.out.println("s/he is smiling.");
    }
    
    public void cry() {
        System.out.println("s/he is crying.");        
    }
}
<?xml version="1.0" encoding="UTF-8"?>
<!-- // src/Beans.xml -->
<beans xmlns="http://www.springframework.org/schema/beans"
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:aop="http://www.springframework.org/schema/aop"
    xsi:schemaLocation="http://www.springframework.org/schema/beans
    http://www.springframework.org/schema/beans/spring-beans-3.0.xsd 
    http://www.springframework.org/schema/aop 
    http://www.springframework.org/schema/aop/spring-aop-3.0.xsd ">

    <aop:config>
        <aop:aspect id="myaop" ref="aoptest">
            <aop:pointcut id="all"
                expression="execution(* cc.co.goodpreparations.*.*(..))" />            
            <aop:pointcut id="smile"
                expression="execution(* cc.co.goodpreparations.*.smile(..))" />
            <aop:before pointcut-ref="all" method="beforeAdvice" />
            <aop:after pointcut-ref="smile" method="afterAdvice" />
        </aop:aspect>
    </aop:config>

    <bean id="person" class="cc.co.goodpreparations.Person">
    </bean>

    <bean id="aoptest" class="cc.co.goodpreparations.AOPTest" />
</beans>
// src/cc/co/goodpreparations/AOPTest.java
package cc.co.goodpreparations;

import org.aspectj.lang.ProceedingJoinPoint;

public class AOPTest {

    public void beforeAdvice() {
        System.out.println("@This is a before advice.");
    }

    public void afterAdvice() {
        System.out.println("@This is an after advice.");
    }
}
// src/cc/co/goodpreparations/Main.java
package cc.co.goodpreparations;

import org.springframework.context.ApplicationContext;
import org.springframework.context.support.ClassPathXmlApplicationContext;

public class MainApp {
   public static void main(String[] args) {
      ApplicationContext context = 
             new ClassPathXmlApplicationContext("Beans.xml");

      Person person = (Person) context.getBean("person");
      
      person.smile();
      System.out.println("---------------------------------");
      person.cry();
   }
}
ポイントとなる設定ファイルの書き方を説明します。AOPの設定は、aop:config要素の中に書きます。aop:aspectの中に、Aspectの設定を書きます。Aspect=Advice + (処理を埋め込む場所)です。ちなみに(処理を埋め込む場所)のことをPointcutと呼びます。
Aspect = Advice + Pointcut
と覚えておくとよいです。設定ファイルの説明に戻ります。簡単に設定箇所を纏めると以下のようになります。
  1. aop:aspect要素のid属性にAspectのIDを、ref属性にAdviceが定義されたクラスのBean IDを書きます。
  2. aop:pointcut要素のid属性にPointcutのIDを、expression属性に共通処理を埋め込みたい場所を正規表現で書きます。
  3. aop:before要素のpointcut-ref属性に使用するPointcutのIDを、method属性に1.で指定したBeanのメソッド名を書きます。(このメソッドがAdviceになる)
  4. aop:after要素もaop:before要素と同様に書きます。
実行結果は、以下のようになります。
@This is a before advice.
s/he is smiling.
@This is an after advice.
---------------------------------
@This is a before advice.
s/he is crying.
このようにAOPを利用すると、任意の処理を任意の場所に後から埋め込むことができます。

その他のAdvice
Before Advice、After Adviceの他にもAdviceはあります。以下にAdviceの種類を纏めます。
種類 用途
Before Advice 処理をメソッドの実行前に追加したい場合。
After Advice 処理をメソッドの実行後に追加したい場合。
Around Advice 処理をメソッドの実行前後に追加したい場合。
After-returning Advice 処理をメソッドが正常終了した後に追加したい場合。
After-throwing Advice 処理をメソッドが異常終了した(例外がスローされた)後に追加したい場合。
このように、どのタイミングでAdviceを挿入したいかに応じて様々な種類のAdviceを使うことができます。それぞれのAdviceの使用方法はSpringSource.orgのreferenceを参照してください。

まとめ
DIがオブジェクト間の依存性を外部に掃き出し、それを後から注入する機能だと考えると、AOPはオブジェクトと共通機能の依存性を外部に掃き出し、それを後から注入する機能だと考えることができます。AOPを使うことで機能追加/変更に強いソースコードを書くことができます。

2012年8月28日火曜日

Spring Framework -Dependency Injection-

Spring FrameworkのDependency Injection(以下DI)の機能について書きます。

"bought a bracelet"

DIとは?
いい例が浮かばなかったのですが、例えば以下のようなプログラムを考えてみてください。
// src/cc/co/goodpreparations/Investor.java
package cc.co.goodpreparations;

public class Investor {
    public void buy() {
        GoodCalculator calculator = new GoodCalculator();
        
        // do something

    }
}
// src/cc/co/goodpreparations/GoodCalculator.java
package cc.co.goodpreparations;

public class GoodCalculator {

    public double calculate() {
        // do difficult calculations
        
        return 0;
    }
}
何かに投資するInvestorクラスがあって、投資するために複雑な計算をします。その計算にGoodCalculatorというクラスを使おうというシチュエーションです。
上のように書いてしまうと、InvestorクラスはGoodCalculatorクラスが無いと使用できません。つまり、InvestorクラスはGoodCalculatorクラスに依存しています。一般にクラスが別のクラスに依存していると、

  • クラスの独立性が低いため、再利用しにくい
  • 独立したテストが行い辛い
というデメリットがあります。

Investorの例に戻ります。もし、今使われているGoodCalculatorより優秀なBetterCalculatorが開発されて、BetterCalculatorを使おう。となったらどうでしょう?GoodCalculatorを使っている場所をすべて書き直さなければなりません。使われている場所が1ヶ所だけならいいですが、何10箇所、何100箇所もあったら大変です。

以下のようにするとどうでしょうか?
// src/cc/co/goodpreparations/Calculator.java
package cc.co.goodpreparations;

public interface Calculator {
    public double calculate();
}
// src/cc/co/goodpreparations/GoodCalculator.java
package cc.co.goodpreparations;

public class GoodCalculator implements Calculator {

    @Override
    public double calculate() {
        // do difficult calculations
        
        return 0;
    }
}
// src/cc/co/goodpreparations/Investor.java
package cc.co.goodpreparations;

public class Investor {
    Calculator calculator = null;
    
    public Investor(Calculator calculator) {
        this.calculator = calculator;
    }
    
    public void buy() {
        // do something with the given calculator

    }
}
こうすると、Investorは中身がどのように実装されているかは知りませんが、Calculatorインターフェースを実装した何らかのクラスを使うことになります。GoodCalculatorがBetterCalculatorに変更されても、そもそもGoodCalculatorというクラス名を直接ソースコード上に書いていないので変更は生じません。もしBetterCalculatorがcalculateメソッドを実装していなければ、Adapterデザインパターンを使ってCalculatorインターフェースを実装するクラスを作ればいいでしょう。
さて、実際にどのCalculatorを使用するかですが、設定ファイルに記述してSpring Frameworkに具体的なクラスを注入してもらいましょう。このように、ソースコードからクラス間の依存性を取り除き、外部から依存性を注入することをDIと呼びます。以下では、
  1. コンストラクタによるDI
  2. setterによるDI
の2種類のDIを説明します。

コンストラクタによるDI
全章の後半で導入したように、コンストラクタで使用するCalculatorを渡す場合は以下のようにすればDIができます。ポイントはXML設定ファイルのinvestorのbean定義のconstructor-arg要素の部分です。この部分でコンストラクタに渡す具体的なクラスを指定しています。注入する具体的なクラスを変えたい場合は、この部分を変更するだけでOKです。
// src/cc/co/goodpreparations/Main.java
package cc.co.goodpreparations;

import org.springframework.context.ApplicationContext;
import org.springframework.context.support.AbstractApplicationContext;
import org.springframework.context.support.ClassPathXmlApplicationContext;

public class Main {
    public static void main(String[] args) {
        ApplicationContext context = new ClassPathXmlApplicationContext("Beans.xml");
        
        Investor investor = (Investor)context.getBean("investor");
        investor.buy();
    }
}
<?xml version="1.0" encoding="UTF-8"?>
<!-- src/Beans.xml -->

<beans xmlns="http://www.springframework.org/schema/beans"
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="http://www.springframework.org/schema/beans
    http://www.springframework.org/schema/beans/spring-beans-3.0.xsd">
    
   <bean id="goodCalculator" class="cc.co.goodpreparations.GoodCalculator"></bean>
   <bean id="investor" class="cc.co.goodpreparations.Investor">
            <constructor-arg ref="goodCalculator"/>
   </bean>
</beans>
setterによるDI
同様にsetterを利用して、具体的なクラスを注入することができます。
// src/cc/co/goodpreparations/Investor.java
package cc.co.goodpreparations;

public class Investor {
    Calculator calculator = null;
    
    public void setCalculator(Calculator calculator) {
        this.calculator = calculator;
    }
    
    public void buy() {
        // do something with the given calculator
    }
}
<?xml version="1.0" encoding="UTF-8"?>
<!-- src/Beans.xml -->

<beans xmlns="http://www.springframework.org/schema/beans"
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="http://www.springframework.org/schema/beans
    http://www.springframework.org/schema/beans/spring-beans-3.0.xsd">
    
   <bean id="goodCalculator" class="cc.co.goodpreparations.GoodCalculator"></bean>
   <bean id="investor" class="cc.co.goodpreparations.Investor">
           <property name="calculator" ref="goodCalculator"/>
   </bean>
</beans>
setterを利用したDIでは、まず引数なしコンストラクタでInvestorクラスをインスタンス化した後、setterでcalculatorを設定しています。使用するcalculatorを変えたい場合は、investorのbean定義のproperty要素のref属性を変更すればOKです。

どちらを使うべきか?
コンストラクタを使用したDIとsetterを使用したDIを説明しました。「で、どっち使えばいいの?」という疑問が浮かぶと思いますが、必須の依存性を注入したい場合はコンストラクタによるDI、オプショナルな依存性を注入する場合はsetterを使用したDI、という使い分けをするのが一般的です。必要に応じて両方同時に使うことも可能です。