2011年10月1日土曜日

Go言語でGCJJ2011

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
}

2010年5月9日日曜日

Google Code Jam Qualification 2010 C

メモ化に手間取った。
コードが長いなあ。
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

紙で計算してみると、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

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");
}
}
}

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