2009年9月4日金曜日

Google Code Jam 2009 C C#でといてみた

正直、これで解けるんだと感動。
DPはすごいな。
というか数列か。

class C
{
int NM;
public void Run()
{
List res = new List();
int line = 0;
//var ss = File.ReadAllLines("C-small-attempt0.in");
var ss = File.ReadAllLines("testcc.txt");
NM = ss[0].ToInt();
line++;
for (int i = 0; i <>
{
var str = ss[line];
var mon = "welcome to code jam";
line++;
var len = str.Length;
var total = new int[mon.Length, len];
for (int k = 0; k <>
{
total[0, k] = str.Substring(0, k + 1).ToCharArray().Count(x => x == 'w');
}
for (int j = 1; j <>
{
total[j, 0] = 0;
}
for (int j = 1; j <>
{
var sm = mon.Substring(0, j + 1);
for (int k = 1; k <>
{
var sstr = str.Substring(0, k + 1);

int r = total[j, k - 1];
if (str[k] == mon[j])
{
r += total[j - 1, k - 1];
}
total[j, k] = r % 10000;
}
}

res.Add("Case #{0}: {1}".FormatWith(i + 1, total[mon.Length - 1, str.Length - 1].ToString().PadLeft(4, '0')));
}
File.WriteAllLines("Ans.txt", res.ToArray());
Console.Write(res.ToArray().Join(Environment.NewLine));
Console.ReadKey();
}
}

Google Code Jam 2009 B C#でといてみた

長いのが悔しい。
けどわかりやすい再帰。

class B
{
public enum Dir
{
Nothing,
North,
West,
East,
South
}
public class Cell
{
public Dir Direction;
public int Label;
public int Alt;
}
int H;
int W;
int T;
public void Run()
{
List res = new List();
int line = 0;
var ss = File.ReadAllLines("B-large.in");
T = ss[0].ToInt();
line++;
for (int i = 0; i <>
{
res.Add("Case #{0}:".FormatWith(i + 1));
int maxlabel = 1;
var s = ss[line].Split(' ');
line++;
H = s[0].ToInt();
W = s[1].ToInt();
var map = new Cell[H, W];

for (int h = 0; h <>
{
for (int w = 0; w <>
{
map[h, w] = new Cell();
}
}
for (int h = 0; h <>
{
var m = ss[line].Split(' ');
line++;
for (int w = 0; w <>
{
map[h, w].Alt = m[w].ToInt();
}
}
for (int h = 0; h <>
{
for (int w = 0; w <>
{
Dir dir;
var jibun = map[h, w].Alt;
var na = h == 0 ? int.MaxValue : map[h - 1, w].Alt;
var wa = w == 0 ? int.MaxValue : map[h, w - 1].Alt;
var ea = w == W - 1 ? int.MaxValue : map[h, w + 1].Alt;
var sa = h == H - 1 ? int.MaxValue : map[h + 1, w].Alt;
var min = new[] { jibun, na, wa, ea, sa }.Min();
if (jibun == min)
dir = Dir.Nothing;
else if (na == min)
dir = Dir.North;
else if (wa == min)
dir = Dir.West;
else if (ea == min)
dir = Dir.East;
else
dir = Dir.South;
map[h, w].Direction = dir;
}
}
for (int h = 0; h <>
{
for (int w = 0; w <>
{
if (map[h, w].Label == 0)
{
Check(map, h, w, maxlabel);
maxlabel++;
}
}
}
for (int h = 0; h <>
{
var r = new string[W];
for (int w = 0; w <>
{
r[w] = ((char)(map[h, w].Label + ((int)'a') - 1)).ToString();
}
res.Add(r.Join(" "));
}
}

File.WriteAllLines("Ans.txt", res.ToArray());
Console.Write(res.ToArray().Join(Environment.NewLine));
Console.ReadKey();
}
public void Check(Cell[,] map, int h, int w, int label)
{
if (map[h, w].Label > 0)
return;
map[h, w].Label = label;
if (h > 0 && (map[h,w].Direction == Dir.North || map[h - 1, w].Direction == Dir.South))
Check(map, h - 1, w, label);
if (w > 0 && (map[h, w].Direction == Dir.West || map[h, w - 1].Direction == Dir.East))
Check(map, h, w - 1, label);
if (h + 1 < direction ="=" direction ="=">
Check(map, h + 1, w, label);
if (w + 1 < direction ="=" direction ="=">
Check(map, h, w + 1, label);
}
}

Google Code Jam 2009 A C#でといてみた

正規表現だ。けどなぜか上位者の回答を見ると
ごりごり自分でアルゴリズムを書いている。
問題をすぐ見て思いついてしまうんだろうな。

class A1
{
public static void Run()
{
List res = new List();
int line = 0;
var ss = File.ReadAllLines("b.in");
var s0 = ss[0].Split(' ');
var L = s0[0].ToInt();
var D = s0[1].ToInt();
var N = s0[2].ToInt();
List words = new List();
List patterns = new List();
line++;
for (int i = 0; i <>
{
words.Add(ss[line]);
line++;
}
for (int i = 0; i <>
{
string pattern = ss[line];
line++;

pattern = "^" + pattern.Replace('(', '[').Replace(')', ']') + "$";
int m = 0;
foreach (var word in words)
{
if (Regex.IsMatch(word, pattern))
m++;
}
res.Add("Case #{0}: {1}".FormatWith(i + 1, m));
}
File.WriteAllLines("Ans.txt", res.ToArray());
Console.Write(res.ToArray().Join(Environment.NewLine));
Console.ReadKey();
}
}