Page List

Search on the blog

2013年8月31日土曜日

Codeforces Round #190 Ciel the Commander

問題
節点数Nの木が与えられる。それぞれの節点にはランクが与えられる。ランクはA-Zまでのアルファベットで、若い文字の方がランクが高いとする。ランクが同じ任意の二節点のパス上には、必ずより高いランクを持った節点が少なくとも一つあるようにしたい。各節点にランクを割り振れ。

解法
木の高さがなるべく低くなるように節点vを選ぶ。vにはランクAを与える。節点vを木集合から除くと二つの部分木が得られる。えられた部分木について同様のことを再帰的に繰り返す。これ系のパターンはCodeforcesにはよく出る。DFSを二回すればよくて、一つ目のDFSでは部分木の節点数をカウントし、二つ目のDFSでは最適な根を選ぶ。一つ目のDFSで得られた値をうまく伝搬することで、二つ目のDFSの計算を高速に行うことができる。

ソースコード
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++)  
#define MP(x,y) make_pair(x,y)

int N;
vector<int> edge[100000];
int rank[100000];
int size[100000];
bool cut[100000];

// get the number of nodes in the subset a node v belong to.
void getSize(int v, int par = -1) {
    size[v] = 1;
    REP (i, edge[v].size()) {
        int w = edge[v][i];
        if (w == par || cut[w]) continue;
        getSize(w, v);
        size[v] += size[w];
    }
}

// select an optimal root node from the subset a node v belong to.
pair<int, int> chooseRoot(int v, int par, int total) {
    pair<int, int> ret = MP(1<<30, -1);

    int rm = total;
    int sub = 0;
    REP (i, edge[v].size()) {
        int w = edge[v][i];
        if (w == par || cut[w]) continue;
        ret = min(ret, chooseRoot(w, v, total));
        sub = max(sub, size[w]);
        rm -= size[w];
    }
    sub = max(sub, rm);
    ret = min(ret, MP(sub, v));
    return ret;
}

void dfs(int v, int depth) {
    getSize(v);
    int r = chooseRoot(v, -1, size[v]).second;
    rank[r] = depth;
    cut[r] = true;
    REP (i, edge[r].size()) {
        int w = edge[r][i];
        if (cut[w]) continue;
        dfs(w, depth+1);
    }
}

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

    dfs(0, 0);

    REP (i, N) {
        char c = 'A' + rank[i];
        putchar(c);
        putchar(' ');
    }
    puts("");

    return 0;
}

To Mock a Mockingbird(3)

 Chapter 3読んだ。一気にレベルがあがった感じがする。自力で解けたのは半分くらいな気がする。

ちなみに問題2のWhat  About This Oneは解答が間違ってるので注意。
下のサイトに詳しい解説がある。

http://math.stackexchange.com/questions/189537/to-mock-a-mockingbird-two-barbers-logic-puzzle

2013年8月27日火曜日

To Mock a Mockingbird(2)

 Chapter 2復習しました。
嘘つきと正直者の問題でよくある「あなたは主張Pが正しいと言っちゃうかんじの人ですか?」という例のあれは『the Nelson Goodman Principle』という名前がついてるそうです。

 Chapter 2の問題は、いわゆる嘘つきと正直者の問題が中心ですが「Yes/Noで答えられる問題、かつ、3語以内」という制約が付くので、単純にthe Nelson Goodman Principleを適用して終わり。とはなりません。そこがこの本のおもしろいところ。
特に奥さんの名前を忘れたおっちょこちょいの論理学者の問題がおもしろかった(問題の設定、問題自体ともに)。
 

2013年8月25日日曜日

To Mock a Mockingbird(1)

気分転換に『To Mock a Mockingbird』のchapter 1を読み直しました。
やっぱり面白いですね。


 
 本の中で紹介されていた「Sancho Panza paradox」について少し調べてみました。
Sancho Panzaっていうのは、人の名前らしいです。スペイン人の小説家が書いた「Don Quixote」という物語の中の登場人物です。

Sancho Panzaが橋を渡ろうとしたとき、役人が彼を止めます。そしてこう言います。
「もし本当のことを言えばこの橋を通してやろう。嘘を言えばお前は絞首刑だ。」

まあ普通の人なら「1 + 1 = 2です。」とか言って橋を通るのですが、Sancho Panzaはこう言いました。
「僕は絞首刑になるだろうね。」

Sancho Panzaかっこよすぎるぜ!


2013年8月18日日曜日

Codeforces Round #188 Strings of Power

問題
文字列tが与えられる。tの中に含れる部分文字列のうちheavy*metalにマッチするものの数を求めよ。

解法
heavyにマッチする部分文字列の位置pと、metalにマッチする部分文字列の位置qをあらかじめ求めておく。
その後、(p, q)の組み合わせを求めればよい。

ソースコード
自分で書いたコード。これは無駄がある。heavyにマッチする位置に来たら今いるところより後にあるmetalの個数を足している。これをやるにはある位置より後にあるmetalの個数を前処理で計算しておかないといけない(sumg[]のところ)。
const int L = 1e6;
char t[L+1];
bool f[L], g[L];
int sumg[L+1];

int main() {
    scanf(" %s", t);
    int len = strlen(t);

    for (int i = 0; i < len; i++) {
        if (strncmp("heavy", t+i, 5) == 0)
            f[i] = true;
    }

    for (int i = 0; i < len; i++) {
        if (strncmp("metal", t+i, 5) == 0)
            g[i] = true;
    }

    for (int i = len-1; i >= 0; i--) {
        sumg[i] = sumg[i+1];
        if (g[i])
            sumg[i]++;
    }

    long long ret = 0;
    for (int i = 0; i < len; i++) {
        if (f[i])
            ret += sumg[i];
    }

    cout << ret << endl;
    
    return 0;
}
逆の発想で、metalにマッチする場所に来たら今より前にあるheavyの個数を足す。という風にプログラミングするとシンプルに書ける。
const int L = 1e6;
char t[L+1];
int flg[L];

int main() {
    scanf(" %s", t);
    int len = strlen(t);

    for (int i = 0; i < len; i++) {
        if (strncmp("heavy", t+i, 5) == 0)
            flg[i] = 1;
    }

    for (int i = 0; i < len; i++) {
        if (strncmp("metal", t+i, 5) == 0)
            flg[i] = -1;
    }

    long long ret = 0;
    int cnt = 0;
    for (int i = 0; i < len; i++) {
        if (flg[i] == 1)
            ++cnt;
        else if (flg[i] == -1)
            ret += cnt;
    }

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

2013年8月13日火曜日

「プロになるためのWeb技術入門」 ――なぜ、あなたはWebシステムを開発できないのか

 『「プロになるためのWeb技術入門」 ――なぜ、あなたはWebシステムを開発できないのか』を読みました。昨年新入社員研修の講師をしていたときに、マネジャーの方が新人たちに勧めていたのでどんなものかなと思って読んでみました。

 インターネットの歴史、インターネットの発展とともにどのような要求が生まれたか、その要求を満たすためにどのような技術が作られたかということがわかりやすく書かれていました。

 だいたい知ってることが多かったですが、よくまとめられていて、これまで学んだことを効率的に復習することができました。

 扱っているトピックは、
  • クライアントとサーバー
  • URLとURI
  • GETとPOST
  • CGIとサーブレット
  • HTTPプロトコルについて
  • Cookieとセッション
  • 三層構成(Webサーバー、アプリケーションサーバー、DBサーバー)
  • MVCモデルを実現するフレームワーク(Struts 1を例に)
  • O/Rマッピング(iBATISを例に)
  • セキュリティ(SQLインジェクション、XSS、セッションハイジャック、CSRFなど)

と多岐に渡り、最低限知っておくべきことはほぼ網羅されているのかなと思います。

そしてこの本の一番いいところは、「今の業界ではこうするのが常識だ!」、「この技術を使いなさい!」と押し付けるのではなく、

  • なぜその技術を使用する必要があるのか?
  • その技術が生まれる前はどのような問題があったのか?
  • その技術のおかげでどのようなメリットがえられるのか?

をきちんと説明してくれるところです。この価格で、扱ってるテーマも広いのに、ここまで丁寧に説明してくれる本はなかなかないのではと思います。エンジニア一年生に勧めるべき最高の本です。

サーバー奮闘記(25) AJPを使ってTomcatとApacheの連携

ひさびさにサーバー奮闘記を書きます。
今日はAJPモジュールを用いたTomcatとApacheの連携をやってみました。
と言っても設定するだけなので簡単です。

参考にしたサイト:

Ubuntuの場合は下の方のサイトが参考になると思います。

ふー、これでJavaで作ったウェブアプリケーションをサーバー上で動かせるようになった。

strutsを使ってhello world的なものを書いてみました。以下の手順でサーバーにデプロイしました。
  1. ローカルマシンのEclipseでコーディング
  2. 作成したプロジェクトをwarファイル形式でエクスポート
  3. warファイルをサーバーの$CATALINA_BASE/webapps/配下に置く
  4. Tomcatを再起動

出来たもの(というほどのものじゃないが。。):
http://kenjih.com/tmc/SayHello.do