Javaの解答例：ABC049C - 白昼夢 , AtCoder Beginners Selection

はじめに

自分用の備忘録。逆から読むとすべて違う文字になるのがポイント。だから、後ろから解いていこう。でも、プログラム的には後ろからってめんどくさい。だったら、もともとのやつと、選択肢をリバース、前後逆にすればよくね？って発想で、問題が解かれていきます.

注意点

出力の形式に注意。よくある問題はYesまたはNoを出力せよだが、今回はYESまたはNOだ！。大文字で出力しよう。結構、間違える。対策として考えられるのは、与えられた文字列（問題文中の文字）、はできるだけコピーアンドペーストで使用することですかね。。

問題文と公式の解答（C++）

問題文 atcoder.jp

公式の解答 qiita.com

解答例

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String S = sc.next();

        String[] divide = {"dream", "dreamer", "erase", "eraser"};

        // 後ろから解くかわりにすべての文字列を「左右反転」する
        S = new StringBuilder(S).reverse().toString();
        for (int i = 0; i < 4; ++i) {
            divide[i] = new StringBuilder(divide[i]).reverse().toString();
        }

        // 端から切っていく
        boolean can = true;
        for (int i = 0; i < S.length();) {
            boolean can2 = false; // 4 個の文字列たちどれかで divide できるか
            for (int j = 0; j < 4; ++j) {
                String d = divide[j];
                if (S.startsWith(d, i)) { // d で divide できるか
                    can2 = true;
                    i += d.length(); // divide できたら i を進める
                }
            }
            if (!can2) { // divide できなかったら
                can = false;
                break;
            }
        }

        if (can) System.out.println("YES");
        else System.out.println("NO");
    }
}

メモ

これは Greedy アルゴリズムの一種で。 という一説が、公式の解説にはありました。ふむふむ。

日本語では貪欲法と呼ばれるみたいですね。問題を複数の部分に分解する。部分において最適なものを選択する。全体最適じゃなくて、局所最適を図っていった結果、いつの間にか問題を解けていたって感じ。

意外と大事なのが、startwithの部分。これじゃなくて、substringで書こうとすると、普通にStringIndexOutOfBoundsExceptionのエラーが出てきちゃいますね笑. 要するに、ないところを参照してるよーって教えてくれます。例えば、文字の長さが10しかないのに、i と d.length() の合計が15とかになったら、いや、15とか普通にねーよって言われるんですよね。