AtCoder (AtCoder Beginners Selection) [ABC049C]

AtCoderの問題を解いてみます。今回は初心者向けの問題のAtCoder Beginners Selectionの6回目です。

問題

ABC049C – 白昼夢

https://atcoder.jp/contests/abs/tasks/arc065_a

問題概要

文字列Sが入力されます。初期値が空の文字列Tに対して、以下のいずれかの文字を末尾に連結するという操作を任意の回数行い、最終的にSに一致させることができるかを判定する問題です。

  • dream
  • dreamer
  • erase
  • eraser

回答

言語

Java8 (OpenJDK 1.8.0)

コード(一つ目、メモリエラー)

問題に対して、最初に作成したコードが以下です。

public class Main {

    public static void main(String... args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        pw.println(new Main(br).execute());
        pw.flush();

    }

    String S;

    Main(BufferedReader br) throws Exception {
        this.S = br.readLine();
    }

    String execute() {
        boolean result = false;

        String before = S;
        String after = S;
        while (true) {
            after = replace(before);

            if ("".equals(after)) {
                result = true;
                break;
            }

            if (before == after) {
                break;
            } else {
                before = after;
            }
        }

        return result ? "YES" : "NO";
    }

    String replace(String before) {
        String target = before;
        target = checkAndDelete(target, "dream");
        target = checkAndDelete(target, "dreamer");
        target = checkAndDelete(target, "erase");
        target = checkAndDelete(target, "eraser");
        return target;

    }

    String checkAndDelete(String target, String param) {
        if (target.endsWith(param)) {
            return target.substring(0, target.length() - param.length());
        } else {
            return target;
        }
    }
}

これはロジック的にはNGではないはずなのですが、結果としてメモリ制限(256 MB)を超えてしまいエラーとなりました。

解説(概要)

メモリエラーとはなりましたが、ロジック的な部分の考えについて解説しておきます。

まず、以下の組み合わせについてですが、文字列Sを前から見ると考えが難しくなることが分かります。

  • dream
  • dreamer
  • erase
  • eraser

これは「dreamer」という文字があった時、それは「dream + er」と分解できるため

  • 「dreamer」
  • 「dream + erase」の途中
  • 「dream + eraser」の途中

のいずれの可能性もあるためです。

しかし、文字列Sを後ろ(末尾)から見ると(少なくとも今回与えられた文字列については)上記の様な懸念は無くなります。そのため、後ろから条件を満たすかを判定する様なロジックを組みました。

解説(メイン処理)

まず、以下はロジックのメイン処理です。

    String execute() {
        boolean result = false;

        String before = S;
        String after = S;
        while (true) {
            after = replace(before);

            if ("".equals(after)) {
                result = true;
                break;
            }

            if (before == after) {
                break;
            } else {
                before = after;
            }
        }

        return result ? "YES" : "NO";
    }

文字列Sに対して、後述のサブメソッド(対象文字列のいずれかと一致するなら末尾を削るという操作)を実行します。メソッドの戻りが空文字列となった場合、条件をを満たしているのでYESを返却して終了します。メソッドの戻りが実行前と変わらない場合は、それは末尾が対象文字列のいずれとも一致しなかったということなので、条件を満たさなかったと判定し、NOを返却して終了します。メソッドの戻りが変化している場合(さらに空文字でもない場合)は、改めて同じ操作を今度は戻りの文字列に対して行います。これを繰り返して判定を行います。

解説(サブメソッド)

次に以下の部分について説明します。

    String replace(String before) {
        String target = before;
        target = checkAndDelete(target, "dream");
        target = checkAndDelete(target, "dreamer");
        target = checkAndDelete(target, "erase");
        target = checkAndDelete(target, "eraser");
        return target;
    }
    String checkAndDelete(String target, String param) {
        if (target.endsWith(param)) {
            return target.substring(0, target.length() - param.length());
        } else {
            return target;
        }
    }

末尾が一致するならその末尾を削るという操作を対象文字列のそれぞれに対して行う様になっています。

結果

今回の結果は以下のようになりました。

  • 結果:メモリ制限超過
  • 実行時間:408 ms
  • メモリ:346,300 KB

正直、Stringの生成が重いということは把握していたので、実行時間はまずいかもと思っていましたが、GCされずにメモリ超過するとは考慮できてませんでした。

コード(修正版)

修正したコードが以下です。

public class Main {

    private static char[] DREAM = { 'd', 'r', 'e', 'a', 'm' };
    private static char[] DREAMER = { 'd', 'r', 'e', 'a', 'm', 'e', 'r' };
    private static char[] ERASE = { 'e', 'r', 'a', 's', 'e' };
    private static char[] ERASER = { 'e', 'r', 'a', 's', 'e', 'r' };

    public static void main(String... args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        pw.println(new Main(br).execute());
        pw.flush();

    }

    private final char[] s;

    Main(BufferedReader br) throws Exception {
        this.s = br.readLine().toCharArray();
    }

    String execute() {
        boolean result = false;
        int beforeSize = s.length;
        int afterSize = beforeSize;
        while (true) {
            afterSize = next(beforeSize);
            if (afterSize == 0) {
                result = true;
                break;
            }
            if (beforeSize == afterSize) {
                break;
            } else {
                beforeSize = afterSize;
            }
        }
        return result ? "YES" : "NO";
    }

    private int next(int size) {
        size = deleteEndsWith(size, DREAM);
        size = deleteEndsWith(size, DREAMER);
        size = deleteEndsWith(size, ERASE);
        size = deleteEndsWith(size, ERASER);
        return size;
    }

    private int deleteEndsWith(int currentSize, char... checkStr) {
        if (endsWith(currentSize, checkStr)) {
            return currentSize - checkStr.length;
        } else {
            return currentSize;
        }
    }

    private boolean endsWith(int currentSize, char... checkStr) {
        int checkSize = checkStr.length;
        int nextSize = currentSize - checkSize;
        if (currentSize < checkSize) {
            return false;

        }
        for (int j = 0; j < checkSize; j++) {
            if (s[nextSize + j] != checkStr[j]) {
                return false;
            }
        }
        return true;
    }
}

解説(概要)

個別の説明(解説)は後述しますが、先に全体的な変更点を説明しておきます。

まず、メモリ超過の原因は生成したインスタンスが破棄されないまま次のループに進むためです。Javaのインスタンスの破棄はプログラマ側でコントロールできないため、インスタンスがループのたびに生成されない様に修正しています。JavaのStringは不変クラスでありインスタンスが生成されてしまうため、Stringからcharの配列に変更しました。

解説(メイン処理)

以下はロジックのメイン処理です。

    String execute() {
        boolean result = false;
        int beforeSize = s.length;
        int afterSize = beforeSize;
        while (true) {
            afterSize = next(beforeSize);
            if (afterSize == 0) {
                result = true;
                break;
            }
            if (beforeSize == afterSize) {
                break;
            } else {
                beforeSize = afterSize;
            }
        }
        return result ? "YES" : "NO";
    }

基本的な考えは最初のコードと同様ですが、今回は配列のサイズをベースに判定しています。配列のサイズが0になる場合は、問題の条件を満たすのでYESを返却します。配列のサイズがサブメソッド実行の前後で変化がない場合は、条件を満たさないので、NOを返却します。配列のサイズに変化がある場合は次のループに続きます。

なお、サブメソッドの説明はこの後しますが、正確には配列を生成し直す訳ではないので、配列のインデックスをサイズに見立てて返却しています。

解説(サブメソッド)

以下はサブメソッドの部分です。DREAMやDREAMERなどはcharの配列で定義しています。

    private int next(int size) {
        size = deleteEndsWith(size, DREAM);
        size = deleteEndsWith(size, DREAMER);
        size = deleteEndsWith(size, ERASE);
        size = deleteEndsWith(size, ERASER);
        return size;
    }

    private int deleteEndsWith(int currentSize, char... checkStr) {
        if (endsWith(currentSize, checkStr)) {
            return currentSize - checkStr.length;
        } else {
            return currentSize;
        }
    }

endsWithメソッドで末尾が指定のものと一致するかを判定し、一致する場合は配列のサイズを引いて返却しています。

そしてendsWithメソッドは以下の様になっています。

    private boolean endsWith(int currentSize, char... checkStr) {
        int checkSize = checkStr.length;
        int nextSize = currentSize - checkSize;
        if (currentSize < checkSize) {
            return false;

        }
        for (int j = 0; j < checkSize; j++) {
            if (s[nextSize + j] != checkStr[j]) {
                return false;
            }
        }
        return true;
    }

チェック対象のSのchar配列の方がチェックするchar配列(DREAMなど)のサイズより小さい場合は、末尾が一致することはありえないので、falseを返却しています。サイズ的に問題ない場合は、それぞれのchar(文字)が一致するかを順番にチェックしています。すべて一致している場合はtrueを返却し、いずれかの文字が一致しない場合はfalseを返却しています。

結果

今回の結果は以下のようになりました。

  • 実行時間:97 ms
  • メモリ:24,532 KB

作成物

今回の作成物は以下に置いています。

https://github.com/masaki-code/java/tree/master/atcoder

コメント

タイトルとURLをコピーしました