Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-21SRM343, SRM344 (Practice)

SRM 344 QuantumAlchemy

|  SRM 344 QuantumAlchemy - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 344 QuantumAlchemy - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7540

  • 逆から考えていけばいいのではと思った
    • つまり、'X' だけの状態から反応を逆向きにして戻していく
  • 終了条件は、文字列が initial の subset になること。
  • TLEが不安だが他に思いつかないのでこのまま出してしまおう。

後で

  • wataさんのコード見た
    • 基本的な考え方は同じっぽい・・・
    • よく見ると、一度展開した文字は再度展開しないようにしてる
      • 無限に展開されるのを防ぐためか
    • また、状態を文字列そのものではなく残り必要な文字数で管理している
      • うまいなぁ

通ったコード

en

TLEするコード

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

public class QuantumAlchemy {
	class Rea {
		String from;
		int flen;
		char to;
		Rea(String f, char t) {
			from = f;
			flen = from.length();
			to = t;
		}
		
		public String toString() {
			return from + ":" + to;
		}
	}
	
	class State implements Comparable<State> {
		String now;
		int step;
		State(String n, int s) {
			char[] arr = n.toCharArray();
			Arrays.sort(arr);
			now = String.valueOf(arr);
			step = s;
		}
		public int compareTo(State arg0) {
			return step - arg0.step;
		}
	}

	public int minSteps(String initial, String[] reactions) {
		int len = reactions.length;
		Rea[] r = new Rea[len];
		Rea[] reamap = new Rea[512];
		for (int i = 0 ; i < len ; i++) {
			String[] data = reactions[i].split("->");
			
			char o = reactions[i].charAt(reactions[i].length()-1);
			r[i] = new Rea(data[0], o);
			reamap[o] = r[i];
		}
		
		int al = initial.length();
		Queue<State> q = new PriorityQueue<State>(10000000);
		int[] iniset = new int[26];
		for (int i = 0 ; i < al ; i++) {
			iniset[initial.charAt(i)-'A']++;
		}
		
		
		Map<String, Integer> dp = new HashMap<String, Integer>();
		q.add(new State("X", 0));
		dp.put("X", 0);
		
		while (q.size() >= 1) {
			State s = q.poll();
			int bl = s.now.length();
			
			int[] chcnt = new int[26];
			for (int i = 0 ; i < bl ; i++) {
				chcnt[s.now.charAt(i)-'A']++;
			}
			
			boolean isans = true;
			for (int c = 0 ; c < 26 ; c++) {
				if (chcnt[c] >= 1 && iniset[c] < chcnt[c]) {
					isans = false;
				}
			}
			if (isans) {
				return s.step;
			}
			
			for (int i = 0 ; i < bl ; i++) {
				char c = s.now.charAt(i);
				if (reamap[c] != null) {
					if (bl - 1 + reamap[c].flen > al) {
						continue;
					}
					
					StringBuffer tob = new StringBuffer();
					for (int j = 0 ; j < bl ; j++) {
						if (j == i) {
							tob.append(reamap[s.now.charAt(i)].from);
						} else {
							tob.append(s.now.charAt(j));
						}
					}

					String to = tob.toString();
					int ts = s.step + 1;
					if (!dp.containsKey(to)) {
						dp.put(to, ts);
						q.add(new State(to, ts));
					} else {
						int beststep = dp.get(to);
						if (beststep > ts) {
							dp.put(to, ts);
							q.add(new State(to, ts));
						}
					}
				}
			}
		}
		return -1;
	}
}