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();

}

}

koはakoの省略形

koはタガログ語ではng形、akoはang形でまったく違うものですが、

セブアノ語では、

akoが1Classで、その省略形がkoです。

2Classはnakoです。

ただ、nakoを省略してもkoになるとある本に書いてありました。

実際上は、akoを省略している場合が多いと思います。

ちょっと混乱しそう。

naa と wala

Naaはある。

Walaはない。

Naa koy higala. わたしには友達がいる。

Wala koy higala. わたしには友達がいない。

Wala は Wa と省略することができます。

Naa ka bay higala? あなたはには友達がいますか？

Wa. いないよ。

higala はもともとセブアノ語です。

同じ意味の単語で、スペイン語から来た amigo (男性)、amiga (女性) も使えます。

Google Wave の 制約

waveの中にwaveletがある。

waveletにparticipantとそれぞれの権限を決める。

waveletの中にはdocumentがあり、そのdocumentはxml documentとannotationで構成される。

というわけで、

participant(権限含む)とドキュメントの組みをwaveletととしている。

一つのwaveletがwaveの基本単位です。

waveletの中に複数の権限を持つことができません。

これは、OT(Operational Transform)を過度に繁雑にしないためです。

しかし、これには当然制約も出てきます。

Blip(xml documentの中にある)に、inline blipがあるが、それをまったく隠すことはできない。

また、annotationについても同様で、まったく隠すことはできない。

言い換えると、そのデータ自体をほかのwaveletに保存して(waveletにはparticipantとaccess controlがあるから)、そこに全員に公開したくないデータを置くことができるが、それが存在しているという事実はすべての人に明らかとなる。

これはそれほど大きな問題ではないだろうが、一つの制約と言えるのではないだろうか。

htmlでいえば、リンク先のページはパスワードをかけて見せないようにできるが、どこにリンクが張られているかは隠せないということと同じです。

これでいいのかな？

セブアノ語の疑問詞

unsa 何

asa, diin どこ

kanus-a いつ

kinsa だれ

3Classと2Class

Akong ihatag nimo ni.

を以前述べました。

タガログの感覚で言うとnimoではなくkanimoを使うような気がしますが、nimoを使うんですね。セブアノではこのように3Classではなく2Classを使うことがよくあります。なぜかは？まだよくわかりません。

リンカー

タガログ語のリンカーはnaと-ngですが、

セブアノ語のリンカーはngaと-ngです。

つまり、母音で終わるときはタガログ語と同じですが、

子音で終わるときはngaになります。

タガログ語でngaは強調を表す小辞ですので、ちょっと混乱するかもしれません。

そして、タガログ語では、yで終わるときはnaになりますが、

セブアノ語では、yで終わるときは-ngになります。

yは半母音ですので、母音としてとらえるか、子音としてとらえるか言語によって違うんですね。

例

Kini maoy tinuod nga balay.

これが本当の家です。

Kita angayng moadto.

私たちは行かなければなりません。

Maayo Kaayo

私の一番好きなセブアノ語表現は、

Maayo kaayo. とてもよい。

です。

褒め言葉でありながら、韻を踏んでいるのが気持ちいですよ。

使えるセブアノ語

セブアノ語とは、フィリピンのセブ島などで話されている言語です。

ビサヤ語の一部です。

私は一カ月ボホル島に行ってセブアノ語を勉強してきたのですが、

フィリピンの方に言わせると、ボホルはセブアノではなくボホラノだといわれます。

実際には方言程度でほとんど変わらないと思うのですが。

以下、まず覚えておくとよい表現を並べます。

Lingkod. 座って。

Akong ihatag nimo ni. あなたにこれを差し上げます。

Salamat. ありがとう。

Salamat kaayo. とてもありがとう。

Maayong buntag. おはよう。

Maayong hapon. こんにちは。

Maayong gabii. こんばんは。

lingkodは、タガログ語では「仕える、しもべ」という意味があるので最初に聞いた時は

面喰いましたが、よく使う表現です。

maayoは、goodという意味です。

ayoがルートワードですね。

maをつけて形容詞になるのはタガログ語と同じです。