言語を楽しもう

Go言語でGCJJ2011

2011-10-01T22:31:00.003+09:00

Golangで解いた。

A問題

最終カットから1つずつ遡っていく。


package main

import (
 "bufio"
 "os"
 "strings"
 "strconv"
 "fmt"
)

func main() {
 reader:=bufio.NewReader(os.Stdin)
 line,_:=reader.ReadString('\n')
 T,_:=strconv.Atoi(strings.TrimSpace(line))
 for i:=0;i<T;i++ {
  line,_=reader.ReadString('\n')
   ss := strings.Split(strings.TrimSpace(line), " ")
//  M,_:=strconv.Atoi64(ss[0])
  C,_:=strconv.Atoi(ss[1])
  W,_:=strconv.Atoi64(ss[2])
  ans := W
  A := make([]int64, C, C)
  B := make([]int64, C, C)
  for j:=0;j<C;j++ {
   line,_=reader.ReadString('\n')
   ab := strings.Split(strings.TrimSpace(line), " ")
   a,_:=strconv.Atoi64(ab[0])
   b,_:=strconv.Atoi64(ab[1])
   A[j], B[j] = a, b
  }
  for j:=C-1;j>=0;j-- {
   if ans <= B[j] {
    ans = A[j] + ans - 1
   } else if ans - B[j] < A[j] {
    ans = ans - B[j]
   }
  }
  fmt.Printf("Case #%d: %d\n", i+1, ans)
 }
}

B問題

最終日から貪欲法。
sortパッケージを使うときに、
sort.Interfaceに適合するように型を作らないといけないのが
面倒。


package main

import (
 "bufio"
 "os"
 "strings"
 "strconv"
 "fmt"
 "sort"
)
type Coffee struct {
 c, t int64
 s int
}
type Coffees []Coffee

func (c Coffees) Len() int {
 return len(c)
}
func (c Coffees) Less(i, j int) bool {
 return c[i].s < c[j].s
}
func (c Coffees) Swap(i, j int) {
 c[i], c[j] = c[j], c[i]
}

type Int64Slice []int64

func (p Int64Slice) Len() int           { return len(p) }
func (p Int64Slice) Less(i, j int) bool { return p[i] < p[j] }
func (p Int64Slice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }


func main() {
 reader:=bufio.NewReader(os.Stdin)
 line,_:=reader.ReadString('\n')
 T,_:=strconv.Atoi(strings.TrimSpace(line))
 for i:=0;i<T;i++ {
  line,_=reader.ReadString('\n')
   ss := strings.Split(strings.TrimSpace(line), " ")
  N,_:=strconv.Atoi(ss[0])
  //K,_:=strconv.Atoi64(ss[1])
  ans := uint64(0)
  coffee := make([]Coffee, N, N)
  ts := make([]int64, N+2, N+2)
  for j:=0;j<N;j++ {
   line,_=reader.ReadString('\n')
   s1 := strings.Split(strings.TrimSpace(line), " ")
   a1,_:=strconv.Atoi64(s1[0])
   a2,_:=strconv.Atoi64(s1[1])
   a3,_:=strconv.Atoi(s1[2])
   coffee[j] = Coffee{a1,a2,a3}
   ts[j] = a2
  }
  ts[N] = 0
  ts[N+1] = 0
  sort.Sort(Int64Slice(ts))
  sort.Sort(Coffees(coffee))
  for j:=N;j>=0;j-- {
   t := ts[j+1]-ts[j]
   for k:=N-1;k>=0;k-- {
    if t == 0 { break }
    if coffee[k].t >= ts[j+1] {
     n := coffee[k].c
     if n > t {
      n = t
     }
     coffee[k].c -= n
     t -= n
     ans += uint64(n) * uint64(coffee[k].s)
     //fmt.Printf("ans:%d t:%d %d n:%d k:%d coffee:%v", ans, ts[j+1], ts[j], n, k, coffee[k])
    }
   }
  }
  fmt.Printf("Case #%d: %d\n", i+1, ans)
 }
}

C問題

試行錯誤の末。
2^n-1の時は特別なケース。


package main

import (
 "bufio"
 "os"
 "strings"
 "strconv"
 "fmt"
)
func main() {
 reader:=bufio.NewReader(os.Stdin)
 line,_:=reader.ReadString('\n')
 T,_:=strconv.Atoi(strings.TrimSpace(line))
 for i:=0;i<T;i++ {
  line,_=reader.ReadString('\n')
  N,_:=strconv.Atoui64(strings.TrimSpace(line))
  fmt.Printf("Case #%d: %d\n", i+1, keta2(N))
 }
}

func keta2(i uint64) int {
 ret := 0
 b := false
 for i != uint64(0) {
  if i & 1 == uint64(1) {
   if b {
    ret++
   }
  } else {
   b = true
  }
  ret++
  i = i >> 1
 }
 if b { ret-- }
 return ret
}

Google Code Jam Qualification 2010 C

2010-05-09T23:08:00.003+09:00

メモ化に手間取った。

コードが長いなあ。

3問解くのに3時間もかかってしまった。1,2時間で解けるはずとGoogleは言っているのに。

public void run(String file) throws Exception {

Scanner scan = new Scanner(file);

int T = scan.nextInt();

for (int testcase = 0; testcase <>

int R = scan.nextInt();

int k = scan.nextInt();

int N = scan.nextInt();

int[] gs = new int[N];

for (int i = 0; i <>

gs[i] = scan.nextInt();

}

long[] memmoney = new long[N];

int[] memfreq = new int[N];

Arrays.fill(memmoney, -1L);

Arrays.fill(memfreq, -1);

int cur = 0;

int freq = 0;

long summoney = 0;

int i = 0;

for (i = 0; i <>

if (memfreq[cur] == -1) {

memmoney[cur] = summoney;

memfreq[cur] = freq;

} else {

break;

}

int cap = k;

int stop = 0;

while (cap >= gs[cur] && stop <>

cap -= gs[cur];

cur = (cur+1) % N;

stop++;

}

freq++;

summoney += k - cap;

}

long ans = 0;

if (i == R) {

ans = summoney;

} else {

int f = freq - memfreq[cur];

long fmoney = summoney - memmoney[cur];

int repeated = (int)((R - memfreq[cur]) / f);

int remain = R - memfreq[cur] - (int)((R - memfreq[cur]) / f) * f;

ans = memmoney[cur] + fmoney * repeated;

long plus = -1L;

for (int j = 0; j <>

if (memfreq[j] == memfreq[cur] + remain) {

plus = memmoney[j] - memmoney[cur];

}

assert(plus >= 0L);

ans += plus;

}

write("Case #" + (testcase+1) + ": " + ans + "\n");

}

Google Code Jam Qualification 2010 B

2010-05-09T23:05:00.002+09:00

紙で計算してみると、t1-t2, t2-t3, t(n-1) - t(n)のgcdをTとして、
t1+yがTの倍数となる最小のyを計算すればよさそうだが、数学的に証明ができない。
まあ、正解だったから、解説が出るまで待ってみよう。

public void run(String file) throws Exception {
Scanner scan = new Scanner(file);
int T = scan.nextInt();
for (int testcase = 0; testcase < T; testcase++) {
int N = scan.nextInt();
BigInteger[] ts = new BigInteger[N];
for (int i = 0; i < N; i++) {
ts[i] = new BigInteger(scan.next());
}
BigInteger[] ds = new BigInteger[N-1];
for (int i = 0; i < N-1;i++) {
ds[i] = ts[i+1].subtract(ts[i]).abs();
}
BigInteger gcd = ds[0];
for (int i =1; i < ds.length;i++) {
gcd = gcd.gcd(ds[i]);
}
//debug(ts, ts[0], gcd);
BigInteger ans = gcd.subtract(ts[0].mod(gcd)).mod(gcd);
write("Case #%d: %s\n", testcase+1, ans.toString());
}
}

Google Code Jam Qualification 2010 A

2010-05-09T23:02:00.001+09:00

Aはまずは簡単でした。

ビット演算を使えば綺麗だったか。

public void run(String file) throws Exception {

Scanner scan = new Scanner(file);

int T = scan.nextInt();

for (int testcase = 0; testcase <>

int N = scan.nextInt();

int K = scan.nextInt();

boolean ok = true;

for (int i = 0; i <>

if (K % 2 == 1) {

K = K / 2;

} else {

ok = false;

break;

}

if (ok) {

write("Case #" + (testcase + 1) + ": ON\n");

} else {

write("Case #" + (testcase + 1) + ": OFF\n");

}

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

2009-09-04T23:52:00.001+09:00

正直、これで解けるんだと感動。

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#でといてみた

2009-09-04T23:50:00.000+09:00

長いのが悔しい。

けどわかりやすい再帰。

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#でといてみた

2009-09-04T23:47:00.001+09:00

正規表現だ。けどなぜか上位者の回答を見ると

ごりごり自分でアルゴリズムを書いている。

問題をすぐ見て思いついてしまうんだろうな。

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の省略形

2009-08-20T00:09:00.002+09:00

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

セブアノ語では、

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

2Classはnakoです。

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

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

ちょっと混乱しそう。

naa と wala

2009-08-20T00:05:00.001+09:00

Naaはある。

Walaはない。

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

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

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

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

Wa. いないよ。

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

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

Google Wave の制約

2009-07-13T00:49:00.005+09:00

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

これでいいのかな？

セブアノ語の疑問詞

2009-03-05T12:43:00.001+09:00

unsa 何

asa, diin どこ

kanus-a いつ

kinsa だれ

3Classと2Class

2009-03-02T12:34:00.002+09:00

Akong ihatag nimo ni.

を以前述べました。

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

リンカー

2009-03-01T22:36:00.002+09:00

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

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

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

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

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

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

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

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

例

Kini maoy tinuod nga balay.

これが本当の家です。

Kita angayng moadto.

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

Maayo Kaayo

2009-02-25T13:10:00.001+09:00

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

Maayo kaayo. とてもよい。

です。

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

使えるセブアノ語

2009-02-23T13:59:00.003+09:00

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

ビサヤ語の一部です。

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

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

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

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

Lingkod. 座って。

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

Salamat. ありがとう。

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

Maayong buntag. おはよう。

Maayong hapon. こんにちは。

Maayong gabii. こんばんは。

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

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

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

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

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

String.Emptyの意外な使い方

2008-03-13T19:24:00.001+09:00

String.Emptyは私たちが最もよく使うヌルオブジェクトの一つです。これは "" と同じです。"" と書くより見やすいですね。
String.Emptyの面白い使い方を見つけました。
たとえば、'a'を10個並べた文字列を作りたい場合皆さんでしたらどうされますか？

internal sealed class RegexFCD {
internal static RegexPrefix Prefix(RegexTree tree) {
string pref = String.Empty.PadRight(curNode._m, curNode._ch);
}
}

この作り方を見てください。
PadRightとは、指定された文字列の長さになるまである文字でもとの文字列を埋める関数です。
"3.1".PadRight(5, '0')とすれば"3.100"が帰ります。このように数字のゼロ埋めの際によく用いる関数ですが、
上のように用いることができるとはちょっと意外です。
curNode._m個のcurNode._chが並んだ文字列がprefになります。
ですから、先ほどの問題の答えは、
String.Empty.PadRight(10, 'a')
となります。もちろん、
String.Empty.PadLeft(10, 'a')
としてもかまいません。

ヌルオブジェクトの導入

2008-03-10T19:11:00.001+09:00

ヌルオブジェクトの導入

RegexGroupCollection.cs

namespace System.Text.RegularExpressions {

public class Group : Capture {

internal static Group _emptygroup = new Group(String.Empty, new int[0], 0);

internal Group GetGroup(int groupnum) {
if (_captureMap != null) {
Object o;

o = _captureMap[groupnum];
if (o == null)
return Group._emptygroup;
//throw new ArgumentOutOfRangeException("groupnum");

return GetGroupImpl((int)o);
}
else {
//if (groupnum >= _match._regex.CapSize || groupnum < 0)
// throw new ArgumentOutOfRangeException("groupnum");
if (groupnum >= _match._matchcount.Length || groupnum < 0)
return Group._emptygroup;

return GetGroupImpl(groupnum);
}
}
}
}

ここで、ヌルオブジェクトが作られているがどれかわかるでしょうか？
そう、_emptygroupです。staticで作るのがポイントで、そうすると、Group._emptygroupとクラス名から呼び出すことができる。this._emptygroupと呼び出すことはしていないことに注意してください。ヌルオブジェクトは一つで十分なので、このようにするのが常套手段です。

はじめは例外を投げるコードが描かれているが、Group._emptygroupを返すように変えられています。
なぜでしょうか？

このGetGroup関数は、以下の2か所で使われています。
public Group this[int groupnum]
{
get {
return GetGroup(groupnum);
}
}

public Group this[String groupname] {
get {
if (_match._regex == null)
return Group._emptygroup;

return GetGroup(_match._regex.GroupNumberFromName(groupname));
}
}

2番目のStringが入ってきた場合のプロパティの中身を見てください。
GroupNumberFromNameとは何でしょう？
関数の中身を以下に示します。

public class Regex : ISerializable {

/*
* Given a group name, maps it to a group number. Note that nubmered
* groups automatically get a group name that is the decimal string
* equivalent of its number.
*
* Returns -1 if the name is not a recognized group name.
*/
///
///
/// Returns a group number that corresponds to a group name.
///
///
public int GroupNumberFromName(String name) {
int result = -1;

if (name == null)
throw new ArgumentNullException("name");

################################(1)
// look up name if we have a hashtable of names
if (capnames != null) {
Object ret = capnames[name];

if (ret == null)
return -1;

return(int)ret;
}

################################(2)
// convert to an int if it looks like a number
result = 0;
for (int i = 0; i < name.Length; i++) {
char ch = name[i];

if (ch > '9' || ch < '0')
return -1;

result *= 10;
result += (ch - '0');
}

// return int if it's in range
if (result >= 0 && result < capsize)
return result;

return -1;
}
}

(1)で、名前付きキャプチャが存在するときにはそのテーブルの中から探しています。
しかし、名前付きキャプチャが存在しないときには(2)で、入ってきたStringが数字かもしれないとしてパースしています。数字だったらその数字を返すのです。
これはいかにも不格好な実装だと思うかもしれません。確かにそうです。
しかしながら、正規表現というのはもともと文字列のみで表現するものです。そのなかに名前でキャプチャされた文字列を取り出す場合と数字で取り出す場合があり、.NETの正規表現ではどちらも同じ表記法を取っているため、致し方ないといえるでしょう。
そうすると、たまたま検索された文字列中にキャプチャされないグループがあった場合、それを検索しようとして例外が発生されてはユーザも困ってしまいます。そのため例外を発生させるのではなく、_emptyGroupというヌルオブジェクトを返すようにしているのです。
この例から、ヌルオブジェクトを使う一つの指針が出てきます。

揺れた表記を受け入れるときにヌルオブジェクトを使う

ちょうど強い型付けのプログラミング言語を使っていて、それくらいわかってよ！と言いたくなる時に動的型付けの言語が恋しくなるように、そんなところで例外を発生させないでよ！というときにヌルオブジェクトを使うといいのです。

言語を楽しもう

Go言語でGCJJ2011

Google Code Jam Qualification 2010 C

Google Code Jam Qualification 2010 B

Google Code Jam Qualification 2010 A

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

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

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

koはakoの省略形

naa と wala

Google Wave の 制約

セブアノ語の疑問詞

3Classと2Class

リンカー

Maayo Kaayo

使えるセブアノ語

String.Emptyの意外な使い方

ヌルオブジェクトの導入

Google Wave の制約