タイトル変更とドメイン設定しました

ブログタイトルを「ありんこ日記」から「ありぺい日記」に変更しました。また、aripei.comを取得したので、ブログをサブドメインのblog.aripei.comにして運用する事にしました。こうなると他のアカウントとかも@aripeiにしたくなるところだが、だいたいすでに取られてる…。

Top Coder SRM 609 Level3 おさらい

今週末もTop Coderに参戦したが、例のごとく最終問題のみ解けなかったので復習した。

今回はGumiとIaとMayuというボーカロイドが音楽アルバムを作りますという若干Geekyなお題でした。以下のような入力値が与えられた時に、すべての曲が必ず一名以上に歌われるようなアルバムのパターンは何種類あるかという問題です（一つの曲を複数人で歌うのはOK）。

入力値(すべて1から50までの整数)

• S: 全曲数
• gumi: Gumiが歌う曲数
• ia: Iaが歌う曲数
• mayu: Mayuが歌う曲数

出力値

• Int: アルバムのパターン数

例えば(3,1,1,1)だと3C1 * 2C1 * 1C1で6パターンとなります。

各曲に対して、各一名ずつ歌う場合（3パターン）、各二名ずつ歌う場合（3パターン）、三人全員が歌う場合（1パターン）の合計7パターンあります。なので7のS乗回試行して条件を満たすものをカウントすればよいのですが、Sが50の場合には1.798465e+42回ほど試行する事になるので残念ながら僕が死ぬまでには計算が終わらなそうです。

この手の問題はどうやら以下の二種類の方法で解けるようです。

• 場合分けをして数学的に解く
• 動的計画法で解く

前者は場合分けを行ってCombinationを駆使して解く方法、後者は分割統治法とメモ化と呼ばれる手法を使って問題を細分化して同じパターンの部分をキャッシュしながら解く方法です。勿論、数学的に解けた方がエレガントではあるのですが、Top Coderでは動的計画法は必須知識らしく、他の多くの問題に応用可能なようなので今回はこちらで解いてみました。

まずは各項が以下の漸化式で求められるという事に気づく必要があります。こちらは前述の通り各曲に対して7パターン存在するということからも分かると思います。

• f(s, g, i, m) = f(s-1, g-1, i, m) + f(s-1, g, i-1, m)  + f(s-1, g, i, m-1)  + f(s-1, g,-1 i-1, m)  + f(s-1, g-1, i, m-1) +  + f(s-1, g, i-1, m-1)  + f(s-1, g-1, i-1, m-1)
• f(0,0,0,0) = 1

後は、各入力値は正の値であるとか、g+i+m > sであるとかの確認をして、この漸化式を満たして、s/g/i/mのパターンをキャッシュしてあげるようなプログラムを実装すればよいです。

できあがりは以下のようなコードになりました。でも、やっぱこのレベルの問題を30分で完璧に解くのはまだまだ無理だなぁ。あ、ちなみに1000000007で割ってるのは問題文に数値がでかすぎるのでこの値の剰余をとるようにって書いてあったから。

import java.util.*;

public class VocaloidsAndSongs {

    long cache[][][][];
    final long MOD = 1000000007L;

    public int count(int S, int gumi, int ia, int mayu) {

        cache = new long[S + 1][gumi + 1][ia + 1][mayu + 1];

        for (int s = 0; s <= S; s++) {
            for (int g = 0; g <= gumi; g++) {
                for (int i = 0; i <= ia; i++) {
                    for (int m = 0; m <= mayu; m++) {
                        cache[s][g][i][m] = -1L;
                    }
                }
            }
        }
        return (int) dp(S, gumi, ia, mayu);
    }

    private long dp(int s, int g, int i, int m) {

        if (s > (g + i + m)) {
            return 0;
        }

        if (s == 0) {
            if (g == 0 && i == 0 && m == 0) {
                return 1L;
            } else {
                return 0L;
            }
        }

        if (g < 0 || i < 0 || m < 0) {
            return 0L;
        }

        if (cache[s][g][i][m] == -1L) {
            cache[s][g][i][m] = dp(s - 1, g - 1, i, m) +
                    dp(s - 1, g, i - 1, m) +
                    dp(s - 1, g, i, m - 1) +
                    dp(s - 1, g - 1, i - 1, m) +
                    dp(s - 1, g - 1, i, m - 1) +
                    dp(s - 1, g, i - 1, m - 1) +
                    dp(s - 1, g - 1, i - 1, m - 1);

        }

        return cache[s][g][i][m] % MOD;
    }

}

Top Coder SRM 608 Level3 おさらい

昨日、Top Coder SRMに二回目の参加をしてみたのですが、Level 3が解けなくて悔しかったので復習してみた。

問題は要約するとN個のノードからなる有効グラフが渡された時にステップ数Lからなる経路の数が多項式P(L)で表されるか判別するプログラムを書くというのが問題です。本番では英語だし若干複雑なので理解するのに若干時間がかかりましたが…。 

入力値は個々のエッジを表すYとNの文字の羅列が以下のようにStringのArrayとして渡される。配列長と文字数はグラフの頂点の数と同じです。

String[] graph = new String[]{"NYN","NNY","YNN"};

また、出力は多項式解が存在する場合には"Bounded"、存在しない場合には"Unbounded"をリターンするだけです。

この問題は本番時にはコード以前にそもそもどういうアルゴリズムにすれば解けるのかが思いつきませんでした。終了後に以下のようにホワイトボードを使って精査したらやっとひらめいた。




NPがNon Polynomial(多項式解なし)でPがPolynomial(多項式解あり)を表しています。どうやら循環して自分に戻ってくるような経路を二つ以上もつノードがある場合に多項式解がなくなるようです。赤のラインで循環を示しているのですが、このラインが一つのノードから2つ以上出ている場合に多項式解がなくなります。例えば循環経路がM、自分に戻ってくるまでにNステップかかると経路数の計算は「Mの(L / N)乗」になるはずです。という訳でMが1の場合には多項式解、Mが2以上の時には多項式では解けないはず。

ルールさえ分かってしまえばコードはこんな感じで簡単に書けました。単純に一つ一つのノードをイテレートして循環が2つ以上ないか確認するだけです。

import java.util.*;

public class BigOEasy {
    static final String UNBOUNDED = "Unbounded";
    static final String BOUNDED = "Bounded";

    boolean[][] edges;
    public String isBounded(String[] graph) {

        // edges as boolean 2d array
        edges = new boolean[graph.length][graph.length];
        for (int i = 0; i < graph.length; i++) {
            for (int j = 0; j < graph[i].length(); j++) {
                edges[i][j] = (graph[i].charAt(j) == 'Y');
            }
        }

        // each vertex
        for (int currentVertex = 0; currentVertex < edges.length; currentVertex++) {
            int num_of_circle = 0;

            // each edge
            for (int nextVertex = 0; nextVertex < edges[currentVertex].length; nextVertex++) {
                // check if circular
                if (edges[currentVertex][nextVertex]) {
                    if(checkCircular(currentVertex, nextVertex, new boolean[edges.length])){
                        num_of_circle++;
                    }
                }

                // unbounded if more than one circulars
                if(num_of_circle > 1){
                    return UNBOUNDED;
                }
            }
        }
        return BOUNDED;
    }

    private boolean checkCircular(int startVertex, int currentVertex, boolean visited[]) {
        visited[currentVertex] = true;
        for(int nextVertex = 0; nextVertex < edges.length; nextVertex++){
            if(edges[currentVertex][nextVertex]){
                if(startVertex == nextVertex){
                    return true;
                }else if(visited[nextVertex]){
                    continue;
                }else{
                    if(checkCircular(startVertex, nextVertex, visited)){
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

ただ、Level 1で10分、Level 2で20分程度は消費すると考えるとLevel 3に費やせる時間は30分程度しかありません。ちょっと本番でこのレベルの問題がでたらかなりラッキーじゃないと時間内に解ける気がしませんね。今のところは確実にLevel 1とLevel 2を片付けることを目標とするか。忘れかけたJavaをググりながら書いているので、この辺りのTipsが身に付けば早く解けるようになってもう少しスコアがあがるはず。