Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-03-08SRM497(DIV1)

CssRules

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

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

この問題は2つのパートに分かれている。

  • 与えられたxhtmlパースする
  • 最小ルール適用回数を求める

本番中ではパースするコードが正しく書けなくて撃沈。

与えられたxhtmlパースする

正規表現を使ってタグを切り分けていく。

各タグにつき、タグ名、タグID、目的の色、および含まれるタグの一覧を記憶。

最小ルール適用回数を求める

各idのタグにおいて、8 * 8 * 8 通りのCSSパターンが考えられる。

その各パターンにおいて子のタグにそのCSSが適用できるかどうかを調べ、

タグが子を持つ場合は再度 8 * 8 * 8 通りのCSSパターンを試す。

正しく探索する方針が思いつかず、editorialを見て理解。

こんなんどう考えたら思いつくの・・・?


import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Stack;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class CssRules {

	public List<Tag> tagList = new ArrayList<Tag>();

	public List<Tag> parentTagList = new ArrayList<Tag>();

	public HashMap<Tag, Integer> countMap = new HashMap<Tag, Integer>();

	public int id = -1;

	public int colorToInt(String c){
		if ("black".equals(c)) {
			return 1;
		}
		if ("blue".equals(c)) {
			return 2;
		}
		if ("gray".equals(c)) {
			return 3;
		}
		if ("green".equals(c)) {
			return 4;
		}
		if ("red".equals(c)) {
			return 5;
		}
		if ("white".equals(c)) {
			return 6;
		}
		if ("yellow".equals(c)) {
			return 7;
		}
		return -1;
	}

	private class Tag {
		int id;
		char name;
		int color;
		String hid;
		List<Tag> inner;

		Tag(int _id, char _name, String _hid, String _color) {
			name = _name;
			id = _id;
			hid = _hid;
			color = colorToInt(_color);
			inner = new ArrayList<Tag>();
		}
		public String toString() {
			return name + " id=" + hid + " color=" + color;
		}
	}

	public int[][][][] memo;

	public int getMinimalCssRuleCount(String[] xthml) {
		String xhtml = "";
		for (String line : xthml) {
			xhtml += line;
		}
		System.out.println(xhtml);

		Pattern tagPattern = Pattern.compile("<([bui]) id='([a-z]+)' style='color:([a-z]+)'>");
		Matcher tagMatcher = tagPattern.matcher(xhtml);

		String left = xhtml;
		Stack<Tag> tagStack = new Stack<Tag>();
		while (tagMatcher.find()) {
			String full = tagMatcher.group();
			left = left.split(full, -1)[1];
			id++;
			Tag tag = new Tag(id, tagMatcher.group(1).charAt(0), tagMatcher.group(2), tagMatcher.group(3));
			if (tagStack.size() > 0) {
				tagStack.peek().inner.add(tag);
			} else {
				parentTagList.add(tag);
			}
			tagStack.push(tag);
			tagList.add(tag);

			String endTag = "</" + tagStack.peek().name + ">";
			while (left.startsWith(endTag)) {
				tagStack.pop();
				String l[] = left.split(endTag, 2);
				if (l.length > 0) {
					left = l[l.length - 1];
				} else {
					break;
				}
				if (tagStack.size() == 0) {
					break;
				}
				endTag = "</" + tagStack.peek().name + ">";
			}
		}

		memo = new int[100][8][8][8];
		for (int t = 0 ; t < 100 ; t++) {
			for (int b = 0 ; b <= 7 ; b++) {
				for (int u = 0 ; u <= 7 ; u++) {
					for (int i = 0 ; i <= 7 ; i++) {
						memo[t][b][u][i] = -1;
					}
				}
			}
		}

		int count = 0;
		for (Tag tag : parentTagList) {
			count += search(tag, 0, 0, 0);
		}
		return count;
	}

	public int search(Tag tag, int bc, int uc, int ic) {
		int needs = 0;

		if (memo[tag.id][bc][uc][ic] >= 0) {
			return memo[tag.id][bc][uc][ic];
		}

		switch (tag.name) {
			case 'b':
				if (tag.color != bc) {
					needs++;
				}
				break;
			case 'u':
				if (tag.color != uc) {
					needs++;
				}
				break;
			case 'i':
				if (tag.color != ic) {
					needs++;
				}
				break;
		}
		if (tag.inner.size() == 0) {
			memo[tag.id][bc][uc][ic] = needs;
			return needs;
		}

		int min = 999999999;
		for (int b = 0 ; b <= 7 ; b++) {
			for (int u = 0 ; u <= 7 ; u++) {
				for (int i = 0 ; i <= 7 ; i++) {
					int count = 0;
					int bcc = b == 0 ? bc : b;
					int ucc = u == 0 ? uc : u;
					int icc = i == 0 ? ic : i;
					if (bcc != bc) count++;
					if (ucc != uc) count++;
					if (icc != ic) count++;
					for (Tag childTag : tag.inner) {
						count += search(childTag, bcc, ucc, icc);
					}
					min = Math.min(min, count);
				}
			}
		}
		memo[tag.id][bc][uc][ic] = needs + min;

		return needs + min;
	}
}