zorioの日記

■Google DevFest 2010 Japan Quizの回答（パッチワーク）

もうはてな記法を忘れてしまうほど何も書いてないので、この前書いたコードでもさらすことにする。

問題

"A" または "B" という文字のみを含む 600 桁、600 行のテキストがあります。これを 600 x 600 の升目状に並べ、上下左右に同じ文字がある部分をつながっているとみなします。

まず、最も多くの文字がつながっている領域をすべて "_" で塗りつぶしてください。 最も多くの文字がつながっている領域が複数存在するならば、それらすべての領域を "_"で塗りつぶすこととします。

そして、各行ごとに "_" が何個含まれているかを数え、それらの数値を改行区切りのテキスト（600 行）として答えてください。

以下の例1を見てください。この入力には単一の文字4つでつながった領域が3箇所あります。これらすべてが「最も多くの文字がつながっている領域」なので、全て"_"で塗りつぶし、その数を数えています。

例1:

入力

    ABAAB
    BABAA
    BAABB
    ABABB
    BABAA

塗りつぶしたところ.

    AB__B
    B_B__
    B____
    AB___
    BABAA

答え

    2
    3
    4
    3
    0

例2:

入力

    AAAABABBAB
    AABAAABBAB
    ABBAABABAA
    BABBAAAAAB
    AAABBBBAAB
    BBBBAABABB
    BAABABBABA
    BBBAABBABA
    BBAABBBAAB
    BAABAABAAB

塗りつぶしたところ.

    ____B_BB_B
    __B___BB_B
    _BB__B_B__
    BABB_____B
    AAABBBB__B
    BBBBAAB_BB
    BAABABB_BA
    BBBAABB_BA
    BBAABBB__B
    BAABAAB__B

答え

    6
    6
    6
    5
    2
    1
    1
    1
    2
    2

回答

Visual Studioを起動していたので、そのままC#で書いた。

• AかBかをValueTypeというenumで表す
• 一文字をCellというclassにする
• Cellを一行分集めたものをRowというclassにする
• 繋がっている領域をGroupとする
• Cellは一つのGroupと、一つのRowに属する

というクラス構造。

処理は

• 左上から右下に向けて順にCellを作る。
• Cellを作るつど、上のCellとValueTypeを比較して同じならGroupをマージする。左のCellとも同様。
• 全部終わったらメンバー数が最大のGroupを探す。
• 各Rowに属するCellのGroupをチェックし、メンバー数最大のGroupに属するCellの数を数える。

という感じ。

1分以上かかる遅いプログラムだが、まあ答えは出た。

あと、HashSetというものが存在する事は昨日知ったのでここでは使ってない。

using System;
using System.Collections.Generic;
using System.IO;

namespace ConsoleApplication1
{
	enum ValueType
	{
		A,
		B
	}
	class Group
	{
		static Dictionary<ValueType, int> counter = new Dictionary<ValueType, int>();
		static List<Group> Groups = new List<Group>();
		static Group()
		{
			counter[ValueType.A] = counter[ValueType.B] = 0;
		}

		public static Group Create(ValueType valueType)
		{
			Group group = new Group(valueType);
			Groups.Add(group);
			return group;
		}

		public static List<Group> GetMaxGroups()
		{
			int max = 0;
			List<Group> maxGroups = new List<Group>();
			foreach (Group group in Group.Groups) {
				if (group.Members.Count > max) {
					max = group.Members.Count;
					maxGroups.Clear();
					maxGroups.Add(group);
				} else if (group.Members.Count == max) {
					maxGroups.Add(group);
				}
			}
			return maxGroups;
		}


		readonly ValueType ValueType;
		readonly int Number;
		internal readonly List<Cell> Members = new List<Cell>();

		private Group(ValueType valueType)
		{
			this.ValueType = valueType;
			this.Number = counter[valueType]++;
		}

		public void Add(Cell cell)
		{
			if (cell.Group != null) {
				cell.Group.Remove(cell);
			}
			if (!Members.Contains(cell)) {
				Members.Add(cell);
			}
			cell.Group = this;
		}

		public void Remove(Cell cell)
		{
			Members.Remove(cell);
			cell.Group = null;
		}

		public void Merge(Group counterPart)
		{
			if (this == counterPart) return;
			if (Number > counterPart.Number) {
				counterPart.Merge(this);
				return;
			}
			foreach (Cell cell in counterPart.Members.ToArray()) {
				Add(cell);
			}
			Groups.Remove(counterPart);
		}
	}
	class Cell
	{
		internal Group Group;
		internal readonly ValueType ValueType;
		internal readonly Row Row;
		public Cell(ValueType valueType, Row row)
		{
			ValueType = valueType;
			Row = row;
			Group = Group.Create(valueType);
			Group.Add(this);
		}
	}
	class Row : List<Cell>
	{
		internal Row PrevRow;
		private Cell prevCell;
		public Cell Create(ValueType valueType)
		{
			Cell cell = new Cell(valueType, this);
			if (prevCell != null && prevCell.ValueType == cell.ValueType) {
				prevCell.Group.Merge(cell.Group);
			}
			if (PrevRow != null && PrevRow[Count].ValueType == cell.ValueType) {
				PrevRow[Count].Group.Merge(cell.Group);
			}
			prevCell = cell;
			Add(cell);
			return cell;
		}
	}

	class Rows : List<Row>
	{
		public new void Add(Row row)
		{
			if (Count > 0) {
				row.PrevRow = this[Count - 1];
			}
			base.Add(row);
		}
	}

	class Program
	{
		static void Main(string[] args)
		{
			Rows rows = new Rows();
			string[] lines = File.ReadAllLines("input.txt");
			foreach (string line in lines) {
				Row row = new Row();
				rows.Add(row);
				foreach (char c in line) {
					if (c == 'A') {
						row.Create(ValueType.A);
					} else if (c == 'B') {
						row.Create(ValueType.B);
					}
				}
			}
			GetResult(rows);
		}

		private static void GetResult(Rows rows)
		{
			List<Group> maxGroups = Group.GetMaxGroups();
			List<string> results = new List<string>();
			foreach (Row row in rows) {
				int count = 0;
				foreach (Cell cell in row) {
					if (maxGroups.Contains(cell.Group)) {
						count++;
					}
				}
				results.Add(count.ToString());
			}
			File.WriteAllLines("output.txt", results.ToArray());
		}
	}
}

Permalink | コメント(0) | トラックバック(0) | 14:56