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が身に付けば早く解けるようになってもう少しスコアがあがるはず。