AKIBA [CODE FESTIVAL 2017 Final A]

atcoder.jp

文字列 S の好きな場所に好きなだけ "A" を挿入して "AKIHABARA" を作れるならYES、作れないならNOを出力せよ、という問題です。

"A" を好きな場所に好きなだけ挿入して "AKIHABARA" にできるような S とは、以下のような構造のものです。

・[0個もしくは1個のA] + KIH + [同左] + B + [同左] + R +[同左]

この構造を満たす S として "AKIHBR", "KIHBARA" などが考えられます。構造を満たさない S としては、"AAAKIHAAABARA", "KIHBRAA" などが考えられます。

構造を満たす S は、4か所の挿入位置全てにおいて "A" が0個か1個であるような文字列なので、その総パターン数は 2^4=16通り となり、全列挙が可能です。ということで、例によってビット全探索を使用します。最近登場回数が多いですね。ビット全探索で構造を満たす S を全列挙し、そのうちの1つでも入力と一致すればYES、どれとも一致しなければNOを出力するプログラムを組みました。

import java.util.*;

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

		String s = sc.next();

		for (int i=0; i<(Math.pow(2,4)); i++) {

			String temp = String.format("%4s", Integer.toBinaryString(i)).replace(" ","0");
			StringBuilder sb = new StringBuilder();

			sb.append(temp.charAt(0)=='1'? "A" : "");
			sb.append("KIH");
			sb.append(temp.charAt(1)=='1'? "A" : "");
			sb.append("B");
			sb.append(temp.charAt(2)=='1'? "A" : "");
			sb.append("R");
			sb.append(temp.charAt(3)=='1'? "A" : "");

			if (sb.toString().equals(s)) {
				System.out.println("YES"); return;
			}
			
		}

		System.out.println("NO");

	}
}

String.format で数値をN桁になるまで0埋めする場合は、以前書いたように

・String.format(%0Nd, num)

でいいのですが、文字列をN桁になるまで0埋めする場合は、今回のコードにあるように

・String.format(%Ns, str).replace("","0");

というふうにして空文字を経由する必要があるみたいです。いや～勉強になりますね。