Topcoderの過去問 - AB

今日すること

こんにちはふるてつです。
今日はちょっとしたネタです。
わたしは職場に1時間ほど早く来て、その時間で少しずつ topcoder の過去問を解いています。
過去問のページは表示に時間がかかり、朝早くでないとまともに見れないので早起きします。
ちなみにわたしのペースだと、1問解けるまでに1～2週間ほどかかります。

Topcoderのサイトです。
https://www.topcoder.com/

過去問の一覧はこのような画面です。

下は問題文と回答を登録する画面です（上半分が問題、下半分が回答）

問題について

今日の問題はABです。
ランダムなAとBの文字の組み合わせの中から、引数で渡した条件に合うAB文字列を返すメソッドを作れという問題です。
引数は下記2つです。
int N：AB文字列の桁数
int K：文字列中でAが左でBが右に並ぶ組み合わせ数

戻り値はstringで上記引数を満たすAB文字列を返します。
例えば、"AAB" だとか、"ABBA" だとか。

英語の原文はこちらです

Problem Statement
You are given two s: N and K. Lun the dog is interested in strings that satisfy the following conditions:

The string has exactly N characters, each of which is either 'A' or 'B'.
The string s has exactly K pairs (i, j) (0 <= i < j <= N-1) such that s[i] = 'A' and s[j] = 'B'.
If there exists a string that satisfies the conditions, find and return any such string. Otherwise, return an empty string.

Definition
Class: AB
Method: createString
Parameters: int, int
Returns: String
Method signature: String createString(int N, int K)
(be sure your method is public)
Limits
Time limit (s): 2.000
Memory limit (MB): 256
Constraints
- N will be between 2 and 50, inclusive.
- K will be between 0 and N(N-1)/2, inclusive.
Examples

0)
3
2
Returns: "ABB"
This string has exactly two pairs (i, j) mentioned in the statement: (0, 1) and (0, 2).

1)
2
0
Returns: "BA"
Please note that there are valid test cases with K = 0.

2)
5
8
Returns: ""
Five characters is too short for this value of K.

3)
10
12
Returns: "BAABBABAAB"
Please note that this is an example of a solution; other valid solutions will also be accepted.
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

わたしの解答

わたしの解答コードは下記になります。
結局文字列の組み合わせを総当たりでチェックして、
引数で渡された条件に合った場合にAB文字列を返すようにしました。

public class AB {
    private static final String CHAR_A = "A";
    private static final String CHAR_B = "B";

    /**
     *
     * @param N 桁数
     * @param K 一致数
     * @return ABの組合せ文字列
     */
    public String createString(int N, int K) {

        String AB[] = new String[N];
        setUpAB(N, AB);

        for (int i = 0; i < Math.pow(2, N); i++) {
            System.out.println(String.join("", AB));

            if (countAB(AB) == K) {
                System.out.println("HIT AB:");
                return String.join("", AB);
            }
            incrementAB(AB, N);
        }
        return "";
    }

    private void setUpAB(int N, String[] AB) {
        for (int i = 0; i < N; i++) {
            AB[i] = CHAR_A;
        }
    }

    private void incrementAB(String[] ab, int N) {
        for (int i = ab.length - 1; i >= 0; i--) {
            if (CHAR_A == ab[i]) {
                ab[i] = CHAR_B;
                return;
            }
            ab[i] = CHAR_A;
        }
    }

    private int countAB(String[] ab) {
        int count = 0;

        for (int i = 0; i < ab.length; i++) {
            if (CHAR_B == ab[i]) {
                continue;
            }
            for (int j = i + 1; j < ab.length; j++) {
                if (CHAR_B == ab[j]) {
                    count++;
                }
            }
        }
        System.out.println("count:" + count);
        return count;
    }
}

下はテストコードです。

import static org.hamcrest.CoreMatchers.*;
import static org.junit.Assert.*;

import org.junit.jupiter.api.Test;

import practice.AB;

class ABTest extends AB {

    @Test
    void testCreateString() {
        assertThat(createString(3, 2), is("AAB"));

        assertThat(createString(2, 0), is("AA"));

        assertThat(createString(5, 8), is(""));
    }

}

今日の感想

AB問題はわたしにとっては結構難しかったのですが、難易度は低く「easy」とのことでした。
難しい難易度の問題を解ける方はすごいですね。
わたしは頭の体操として少しずつ解いていきたいと思います。
あと反省ですが、Stream APIを使って今風に書いたほうが良かったかしらと思いました。

では、今日もお疲れ様でした。