動的計画法のアルゴリズム

動的計画法アルゴリズムは以下の通り。

  1. 最適解の構造を特徴づける
  2. 最適解の値を再帰的に定義する
  3. ボトムアップに最適解の値を求める
  4. 最適解を構成する

1.最適解の構造を特徴づける

問題がより小さい問題に分けることができ、問題の最適解に小さく分けた問題(部分問題)の最適解が含まれる場合は動的計画法により解くことができる。(部分問題最適性)

2.最適解の値を再帰的に定義する

n番目の値を求めたい。n-1番目の値を求める必要がある。

n-1番目の値を求めたい。n-2番目の値を求める必要がある。

n-2番目の値を求めたい。n-3番目の値を求める必要がある。

・・・

2番目の値を求めたい。1番目の値を求める必要がある。

1番目の値を求めたい。

上記のように再帰的に最適解の値を定義する。

3.ボトムアップに最適解を求める

最適解の値は再帰的に定義されるため、

1番目の値を決める。

2番目の値が決まる。

3番目の値が決まる。

・・・

n-1番目の値が決まる。

n番目の値が決まる。

というように最初の値を決めることでボトムアップ的に最適解が求められる。

4.最適解を構成する

どのルートを辿ってきたかを記録しておき、逆順にたどることで最適解の構成がわかる。

SRM 698 DIV2 Medium(500) - RepeatStringEasy

Problem Statement

A string S is called a square if there is some string T such that S = T + T. For example, the strings "", aabaab" and "xxxx" are squares, but "a", "aabb" and "aabbaa" are not.

You are given a String s. Find the longest square string that can be obtained from s by erasing some (possibly none, possibly all) of its characters. In other words, we are looking for the longest square that occurs in s as a subsequence. Return the length of that square.

Note that the answer is well-defined, as the square "" (the empty string) will always occur in s as a subsequence.

Definition

  • Class: RepeatStringEasy
  • Method: maximalLength
  • Parameters: String
  • Returns: int
  • Method signature: int maximalLength(String s) (be sure your method is public)

Limits

  • Time limit (s): 2.000
  • Memory limit (MB): 256

Constraints

  • s will contain between 1 and 50 characters, inclusive.
  • Each character in s will be a lowercase English letter ('a'-'z').

Solution Plan

与えられた文字列をs1とs2の2つの文字列に分解し、LCS(Longest Common Subsequence)を抽出する。 example1を例にすると、分解した文字列とLCSは以下のようになる。

  • S1:f S2:rankfurt LCS:f
  • S1:fr S2:ankfurt LCS:fr
  • S1:fra S2:nkfurt LCS:fr
  • S1:fran S2:kfurt LCS:fr
  • S1:frank S2:furt LCS:r
  • S1:frankf S2:urt LCS:r
  • S1:frankfu S2:rt LCS:r
  • S1:frankfur S2:t LCS:(none)

LCSの求め方

S1のi番目とS2のj番目までを比較したLCS長をLCS(i, j)とすると、以下の3つがわかれば求めることができる。

  • LCS(i-1, j-1)
  • LCS(i, j-1)
  • LCS(i-1, j)

その理由を文字列の最後の文字が一致しているかどうかで場合分けして考えてみる。

最後の文字が一致しているパターン

このパターンでは、LCS(i, j) = LCS(i-1, j-1) + 1となる。
具体例で示すと、
S1:AABBDC
S2:ADDBBC
の場合、AABBDCとADDBBCのLCSはAABBDとADDBBのLCS + 1となる。
最後の文字が一致しているため、その1つ前までのLCSに+1すればOK。

最後の文字が一致していないパターン

このパターンでは、LCS(i, j) = Max(LCS(i, j-1), LCS(i-1, j)となる。
こちらも具体例を示すと、
S1:AABBD
S2:ADDBB
の場合は、AABB, ADDBBのLCS(=ABB)とAABBD, ADDBのLCS(=AB)の大きい方をLCS(i, j)とする。

Source Code

public class RepeatStringEasy {

    public int maximalLength(String s) {
        if (s.length() == 1) return 0;
        int max = 0;
        for (int i = 0; i < s.length(); i++) {
            max = Math.max(max, lcs(s.substring(0, i + 1), s.substring(i + 1, s.length())));
        }
        return max * 2;
    }

    private int lcs(String x, String y) {
        int[][] dp = new int[x.length() + 1][y.length() + 1];
        int max = 0;
        for (int i = 1; i <= x.length(); i++) {
            for (int j = 1; j <= y.length(); j++) {
                if (x.charAt(i - 1) == y.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
                max = Math.max(max, dp[i][j]);
            }
        }
        return max;
    }
}

【Java】SRM 698 DIV2 Easy(250) - Initials

Problem Statement

When dealing with long names and phrases, we sometimes use the initial letters of words to form its acronym. For example, we use "JFK" instead of "John Fitzgerald Kennedy", "lgtm" instead of "looks good to me", and so on.

You are given a String name. This String contains a phrase: one or more words separated by single spaces. Please compute and return the acronym of this phrase. (As above, the acronym should consist of the first letter of each word, in order.)

Definition

  • Class: Initials
  • Method: getInitials
  • Parameters: String
  • Returns: String
  • Method signature: String getInitials(String name) (be sure your method is public)

Limits

  • Time limit (s): 2.000
  • Memory limit (MB): 256
  • Stack limit (MB): 256

Constraints

  • name will contain between 1 and 50 characters, inclusive.
  • Each character in s will be a space or a lowercase English letter ('a' - 'z').
  • The first and last character in s will not be a space.
  • No two continuous spaces can appear in s.

Solution Plan

各フレーズの頭文字を連結しなさいという問題なので、以下の方針でプログラムを記述。

  1. スペース区切りで配列に格納
  2. 1で作成した配列をループし、先頭文字を連結

ある程度Javaのプログラムが書けるのであれば、特に問題なく回答が可能なレベル。

Source Code

public class Initials {

    public String getInitials(String name) {
        String ret = "";
        String[] phrase = name.split(" ");
        for (int i = 0; i < phrase.length; i++) {
            ret += phrase[i].charAt(0);
        }
        return ret;
    }

}

【参戦結果】SRM 698 DIV2

Target

  • Coding Phase:SRM 698 DIV2のEasy問題を正答すること ⇒ 達成
  • Challenge Phase:今回は特に目標を設けない ⇒ N/A

Result

Not Rated ⇒ 1157(↑) Green Coder

  • Easy(250):Passed System Test
  • Medium(500):Opened
  • Hard(1000):Unopened

Implessions

Easy(250)については問題なく解くことができた。特にJavaの場合はStringのsplitメソッドを使用することで、スペース区切りで配列に格納することが可能なため、あとは1文字目を連結していけばOK。全文字小文字の条件を見落としていたので、無駄に小文字に変換してしまっていたが・・・。
Medium(500)はなんとなく解き方がイメージできるものの、プログラム化可能なロジックに落とし込むことができず、未提出。他の人の回答を見る限り動的計画法で解くことが可能な様子だった。いずれにせよ、深さ優先探索幅優先探索動的計画法などの基本的なアルゴリズムを実践で使えるレベルまで身に着ける必要がある。
ともあれ初参戦の目標は達成できたので、ひとまず安心。

Next Competition

9/25(SUN) 01:00 - SRM 699 DIV2

【Java】SRM 425 DIV2 Medium(500) - CrazyBot(深さ優先探索)

Problem Statement

An out-of-control robot is placed on a plane, and it takes n random steps. At each step, the robot chooses one of four directions randomly and moves one unit in that direction. The probabilities of the robot choosing north, south, east or west are north, south, east and west percent, respectively.

The robot's path is considered simple if it never visits the same point more than once. (The robot's starting point is always the first visited point.) Return a double containing the probability that the robot's path is simple. For example, "EENE" and "ENW" are simple, but "ENWS" and "WWWWSNE" are not ('E', 'W', 'N' and 'S' represent east, west, north and south, respectively).

Definition

  • Class: CrazyBot
  • Method: getProbability
  • Parameters: int, int, int, int, int
  • Returns: double
  • Method signature: double getProbability(int n, int east, int west, int south, int north) (be sure your method is public)

Limits

  • Time limit (s): 2.000
  • Memory limit (MB): 64

Notes

  • Your return must have relative or absolute error less than 1E-9.

Constraints

  • n will be between 1 and 14, inclusive.
  • east will be between 0 and 100, inclusive.
  • west will be between 0 and 100, inclusive.
  • south will be between 0 and 100, inclusive.
  • north will be between 0 and 100, inclusive.
  • The sum of east, west, south and north will be 100.

Solution Plan

全ルートを探索する必要があるので、深さ優先探索を利用する。

Implementation

public class CrazyBot {

    boolean[][] grid = new boolean[100][100];
    int[] vx = {1, -1, 0, 0};
    int[] vy = {0, 0, -1, 1};

    double[] probability = new double[4];

    public double getProbability(int n, int east, int west, int south, int north) {
        probability[0] = east / 100.0;
        probability[1] = west / 100.0;
        probability[2] = south / 100.0;
        probability[3] = north / 100.0;

        return dfs(n, 50, 50);
    }

    private double dfs(int n, int x, int y) {

        if (grid[x][y]) return 0;
        if (n == 0) return 1;

        grid[x][y] = true;

        double p = 0.0;
        for (int i = 0; i < probability.length; i++) {
            p += probability[i] * dfs(n - 1, x + vx[i], y + vy[i]);
        }
        grid[x][y] = false;

        return p;
    }

}

深さ優先探索と幅優先探索の使い分け

探索における手法に深さ優先探索幅優先探索がある。 最強最速アルゴリズマー養成講座によると、問題を解答するにあたって、どちらの探索手法を使えばよいかの指針は以下の通り。 ※どちらを使ってもよい場合もあるので注意すること。

深さ優先探索を使うケース

  • 全通りを列挙し、結果をまとめる必要がある場合。
  • 文字列などを探索するときに、「辞書順最小(辞書の並び順で、いちばん最初にくるもの)」であることが求められている場合。

幅優先探索を使うケース

  • 始点から最も近いものを求めたいケース。
  • 探索範囲自体は広いものの、ある程度近くに求めたい解が存在することがわかっているケース。
  • 探索範囲が広く、深さ優先探索ではスタックが大量に使われてしまう場合。

SRMのPracticeでSystem Testを実施する方法

TopCoderに参戦している人の中ではおそらく常識なのだろうが、PracticeでSystem Testを実施する方法を発見。 これまではPracticeでSystem Testを実施する方法がわからず、EclipseCoderで自動生成されるテスト(問題中のExamples)を通しているだけだったので、実際に参戦した際にSystem Testが通るのか不安だった。orz。。。

System Test実施手順

ArenaでPractice Options > Run System Test

たったこれだけ。これまで気づかず。。。orz