前回に引き続いて、今回は 2～3 問目の解説です。

(2) ABC 143 C – Slimes (難易度 34) 解答例 (Java 8, JavaScript)

同じ色を持つ隣接するスライムが融合すると、最終的に存在するスライムは何匹となるか。

同じ文字が連続した区間の数だけをカウントします。SQL でいうところの distinct に近いのですが、文字列全体に対しての distinct ではなく、連続した部分だけ distinct する必要があります。

方針としては、1文字ずつ読み込んで、直前と異なる文字ならカウントすればよいです。これを実現するために以下の方法が考えられます。

• 直前の文字を変数にキャッシュして比較
• 各 i に対して s[i] と s[i – 1] を比較 (範囲に注意)

前者は少し長くなるので後者だけコードを示します。
for 文を使う人が多いとは思いますが、今回もやはり Java で Stream を使います。( import java.util.stream.*; )
Java で String から char を取り出すには、charAt メソッドまたは toCharArray メソッドを使います。

char[] s = sc.next().toCharArray();
System.out.println(IntStream.range(1, s.length).filter(i -> s[i - 1] != s[i]).count() + 1);

※ sc.next() に文字列が渡されます。

他の考え方として、

• “xxx…xxx” を “x” に置き換える

という方針でもできます。
Ruby では、このように連続した部分だけ distinct できる squeeze メソッドがあるためとても簡単に書けます。実は Java でも、正規表現のパターンに一致した文字列を置換する replaceAll メソッドを使えば同様のことができます。

System.out.println(sc.next().replaceAll("(.)\\1*", "$1").length());

(3) CF 2017 A – AKIBA (難易度 42) 解答例 (Java 8, JavaScript)

与えられた文字列の好きな位置に好きなだけ文字 "A" を挿入して "AKIHABARA" に変えることはできるか。

この問題では多くの解法が考えられます。
適合するケースが 2⁴ = 16 通りしかないことがわかれば効率的に全探索することも可能です。

• 1文字ずつ比較してなんやかんや
• わからん読めん
• 16通りを全列挙
• “KIHBR”, “KIHBRA” などを直書き
• 16通りを全探索
• 4重ループ
• 正規表現
• 処理速度は落ちるが圧倒的な保守性

1文字ずつ比較する方針の人が多かったです。しかしこの解法では人によってコードの違いが大きすぎて、本人以外はコードの意味を理解できないという状態に陥りました。
業務でこのタイプの要件が現れたら、他に単純化する方法がない限りは正規表現を利用することをお薦めします。

System.out.println(sc.next().matches("^A?KIHA?BA?RA?$") ? "YES" : "NO");

他の考え方として、

• “A” があるはずのところに “A” を挿入してみて、最終的に “AKIHABARA” となるか

という方針でもできます。つまり「1文字ずつ比較しながら “A” を挿入」の代わりに「”A” を挿入してみて、最後に全体を比較」と考えても同じです。

StringBuilder sb = new StringBuilder(sc.next());
int[] ai = { 0, 4, 6, 8 };
for (int i : ai) {
    if (i < sb.length() && sb.charAt(i) != 'A' || i == sb.length()) {
        sb.insert(i, "A");
    }
}
System.out.println(sb.toString().equals("AKIHABARA") ? "YES" : "NO");

次回は 4～5 問目の解説です。