GCJ2011 Qualification Round B Magicka

Java プログラミング

GCJ当時，twitterでGCJの問題マギカらしいよ！というのが流れていたのを思い出した．
http://code.google.com/codejam/contest/dashboard?c=975485#s=p1

問題

  • まどマギとは関係ない（ぉ
  • 8つの基本となるエレメントがあり，それぞれ1文字で{Q, W, E, R, A, S, D, F}
  • あるエレメントを呼び出すと，エレメントリストに付け加えられる
  • たとえば，Wを呼び出した後にAを呼び出すと，エレメントリストは[W, A]になる
  • 基本ではない他の18文字は基本エレメントのペアで指定される．たとえばQとFでTになる．つまり，[A, Q, F]や[A, F, Q]は[A, T]になる．
  • 相反する基本エレメントのペアが存在する．相反するエレメントが呼び出され，他のエレメントと結合することがないとき，そのリストの全要素がクリアされる．
  • 入力データは(C, D, N)となっている．Cは3文字で表され，2つの基本エレメントから別のエレメントをつくることを表す．Dは2文字で表され相反するエレメントとなっている．Nは順番に呼び出されるエレメントである．
  • 最終的にエレメントのリストはどのようになるか？

プログラム

import java.util.*;
import java.io.*;

public class Qualifer_02_2011 {
	public void solve() throws Exception {
		Scanner sc = new Scanner(new FileReader("./input/B-large-practice.in"));
		PrintWriter pw = new PrintWriter(new FileWriter("./output/Q02_2011output.txt"));
		int caseCnt = sc.nextInt();
		for (int caseNum = 0; caseNum < caseCnt; caseNum++) {
			pw.print("Case #" + (caseNum + 1) + ": ");
			//combinationを配列に
			int combCnt = sc.nextInt();
			boolean[][] isComb = new boolean[26][26];
			char[][] comb = new char[26][26];
			for (int i=0; i < combCnt; i++) {
				String s = sc.next();
				isComb[s.charAt(0) - 'A'][s.charAt(1) - 'A'] = true;//配列の何番目がcombか？
				isComb[s.charAt(1) - 'A'][s.charAt(0) - 'A'] = true;
				comb[s.charAt(0) - 'A'][s.charAt(1) - 'A'] = s.charAt(2);//できあがる文字列を配列に
				comb[s.charAt(1) - 'A'][s.charAt(0) - 'A'] = s.charAt(2);
			}
			//opposedを配列に
			int oppCnt = sc.nextInt();
			boolean[][] isOpp = new boolean[26][26];
			for (int i=0; i < oppCnt; i++) {
				String s = sc.next();
				isOpp[s.charAt(0) - 'A'][s.charAt(1) - 'A'] = true;
				isOpp[s.charAt(1) - 'A'][s.charAt(0) - 'A'] = true;
			}

			int N = sc.nextInt();

			String s = sc.next();

			List<Character> cur = new ArrayList<Character>();

			for (char c : s.toCharArray()) {
				cur.add(c);
				if (cur.size() > 1) {
					char p = cur.get(cur.size() - 2);
					if (isComb[p-'A'][c-'A']) {
						cur.remove(cur.size() - 1);
						cur.remove(cur.size() - 1);
						cur.add(comb[p-'A'][c-'A']);
					} else {
						for (int i=0; i < cur.size() - 1; i++) {
							char x = cur.get(i);
							if (isOpp[x-'A'][c-'A']) {
								cur = new ArrayList<Character>();
								break;
							}
						}
					}
				}
			}

			pw.print("[");
			for (int i=0; i < cur.size(); i++) {
				if (i >= 1) pw.print(", ");
				pw.print(cur.get(i));
			}
			pw.println("]");
		}
		pw.flush();
		pw.close();
		sc.close();
	}

	public static void main(String[] args) throws Exception {
		new Qualifer_02_2011().solve();
	}
}

基本的には前から順に，combinationになる組合せをチェック，その場合は新規文字に変換，次にopposedになる組合せをチェックし，リストを初期化するのいう処理を行えばいいわけですね．ま，いろんな方の解答を参考にしたわけですが（汗）