topcoderの過去問 - ABC

今日すること

こんにちはふるてつです。
今日は Topcoder の過去問です。

問題について

今日の問題は ABC。
引数で数 N と数 K が与えられます。
もとめる文字列は "A"、"B"、"C" 3 種の文字を組合わせて作ります。
引数 N は文字列の桁数です。
引数 K はその文字列の中で "A" ⇒ "B" 、 "B" ⇒ "C" 、"A" ⇒ "C"の順にならぶ組合わせの総数です。
その総数が引数にちょうど一致する文字列を返します。

英語の原文はこちらです

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', 'B' or 'C'.
The string s has exactly K pairs (i, j) (0 <= i < j <= N-1) such that s[i] < s[j].
If there exists a string that satisfies the conditions, find and return any such string. Otherwise, return an empty string.

Definition
Class: ABC
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 3 and 30, inclusive.
- K will be between 0 and N(N-1)/2, inclusive.
Examples
0)
3
3
Returns: "ABC"
This string has exactly three pairs (i, j) mentioned in the statement: (0, 1), (0, 2) and (1, 2).
1)
3
0
Returns: "CBA"
Please note that there are valid test cases with K = 0.
2)
5
10
Returns: ""
Five characters is too short for this value of K.
3)
15
36
Returns: "CABBACCBAABCBBB"
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 という問題を解きましたが、それを少し変えただけでできました。
基本的に総当たりで1文字づつ変え条件にあう文字列を地道に探します。

package practice;

public class ABC {

    private static final String CHAR_A = "A";
    private static final String CHAR_B = "B";
    private static final String CHAR_C = "C";

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

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

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

            if (countABC(abc) == K) {
                System.out.println("HIT ABC:");
                return String.join("", abc);
            }

            incrementAB(abc, N);
        }
        return "";
    }

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

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

    private int countABC(String[] abc) {
        int count = 0;

        for (int i = 0; i < abc.length; i++) {

            for (int j = i + 1; j < abc.length; j++) {

                if (CHAR_A == abc[i] && CHAR_B == abc[j]) {
                    count++;
                } else if (CHAR_A == abc[i] && CHAR_C == abc[j]) {
                    count++;
                } else if (CHAR_B == abc[i] && CHAR_C == abc[j]) {
                    count++;
                }

            }

        }
        System.out.println("count:" + count);

        return count;
    }

}

下はテストコードです。

package test;

import static org.hamcrest.CoreMatchers.*;
import static org.junit.Assert.*;
import org.junit.jupiter.api.Test;
import practice.ABC;

class ABCTest extends ABC {
    @Test
    void test1() {
        assertThat(createString(3, 3), is("ABC"));
    }
    @Test
    void test2() {
        assertThat(createString(3, 0), is("AAA"));
    }
    @Test
    void test3() {
        assertThat(createString(5, 10), is(""));
    }
    @Test
    void test4() {
        assertThat(createString(15, 36), is("CABBACCBAABCBBB"));
    }
}

今日の感想

今日の問題の難易度は「Hard」でしたが、以前解いた AB の解答を少し変えただけですぐにできました。
とはいえこの問題1000ポイントのところ、わたしのコードでは300点しか取れませんでした。
もっと点の高い回答があったに違いないと感じています。
しかし今日もいい頭の体操になりました。

ではまた。