Google Code Jam 2013 Round1B

　Round 1Bがありました。A small、A large、C-smallを解くことができましたが、Round 2には届きませんでした。C-largeはあと1分あれば間に合ったのに、・・・。惜しかった。

ということで、復習しました。最近Javaを練習中なので、Javaで書きます。

A. Osmos

本番はDPでときましたが、Greedyで解けるようです。moteのサイズを昇順にソートした列をxとします。x[i]をremoveして、x[i+1]を吸収できるようにいくつかのmoteを追加するというのは意味がありません。x[i+1]を吸収できるようにしたのなら、x[i]も吸収できるからです。
ということで最適解は、「あるiまでは吸収して、i+1以降はremoveする。」という条件が成り立っているはずです。このiをループで回してあげればOKです。

import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.math.BigInteger.*;
import java.io.*;
import java.util.*;

@SuppressWarnings("unused")
public class A {
 Scanner sc = new Scanner(System.in);

 void solve() {
  int A = sc.nextInt();
  int N = sc.nextInt();
  
  int[] x = new int[N];
  for (int i = 0; i < N; i++)
   x[i] = sc.nextInt();
  
  sort(x);
  
  int ret = Integer.MAX_VALUE;
  for (int i = 0; i <= N; i++) {
   int tmp = N - i;
   
   int sz = A;
   for (int j = 0; j < i; j++) {
    if (sz < 2) {
     tmp = Integer.MAX_VALUE;
     break;
    }
    while (x[j] >= sz) {
     sz = 2 * sz - 1;
     ++tmp;
    }
    sz += x[j];
   }
   
   ret = min(ret, tmp);
  }
  
  System.out.println(ret);
   
 }

 void run() {
  int T = sc.nextInt();
  for (int id = 1; id <= T; id++) {
   System.out.printf("Case #%d: ", id);
   System.err.printf("Solving Case #%d...\n", id);
   solve();
   System.out.flush();
  }
 }

 void debug(Object... os) {
  System.err.println(deepToString(os));
 }

 public static void main(String[] args) {
  new A().run();
 }
}

B. Falling Diamonds

これは本番中はまったく解けませんでした。ダイヤが積もっていくときに層ができますが、何番目の層にあたるのかというのが「原点からのマンハッタン距離 / 2」で計算できます。これで、自分が買おうとしている土地が何層目にあるかわかります。
あとはダイヤを層ごとに積み上げていって、目的のダイヤの層を被うことができれば1.0を返し、その層まで届かなければ0.0を返します。目的の層をすべて被うことはできないけど、途中まで被うことができる場合は、DPで(左、右)に(i, j)個ずつ積もっている確率を計算してあげます。

import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.math.BigInteger.*;
import java.io.*;
import java.util.*;

@SuppressWarnings("unused")
public class B {
 Scanner sc = new Scanner(System.in);

 double solve() {
  int n = sc.nextInt();
  int x = sc.nextInt();
  int y = sc.nextInt();
  
  int m = (abs(x) + abs(y)) / 2;  
  int l = 0;
  int cnt = 1;
  while (n - cnt >= 0) {
   n -= cnt;
   ++l; 
   cnt += 4;
  }
  
  if (m < l) 
   return 1.0;
  if (m > l)
   return 0.0;
  
  double[][] dp = new double[2][5000];
  dp[0][0] = 1.0;
  
  for (int i = 0; i < n; i++) {
   int cur = i&1;
   int nxt = i+1&1;
   
   fill(dp[nxt], 0.0);
   for (int j = 0; j <= i; j++) {
    if (j+1 >= 2*l+1)
     dp[nxt][j] += dp[cur][j];
    else if (i-j+1 >= 2*l+1)
     dp[nxt][j+1] += dp[cur][j];
    else {
     dp[nxt][j+1] += 0.5 * dp[cur][j];
     dp[nxt][j] += 0.5 * dp[cur][j];
    }
   }
  }
  
  double ret = 0;
  for (int i = y+1; i <= n; i++)
   ret += dp[n&1][i];
  
  return ret;
 }

 void run() {
  int T = sc.nextInt();
  for (int id = 1; id <= T; id++) {
   System.out.printf("Case #%d: ", id);
   System.err.printf("Solving Case #%d...\n", id);
   System.out.printf("%.8f\n", solve());
   System.out.flush();
  }
 }

 void debug(Object... os) {
  System.err.println(deepToString(os));
 }

 public static void main(String[] args) {
  new B().run();
 }
}

C. Garbled Email

本番中はDPを使いました。dp[i][j] = （i番目の文字に注目している、直近でミスマッチが起こった場所はj）としていました。これだと9分くらいかかってしまってTLE。
状態数の定義を変更して、dp[i][j] = （i番目の文字に注目している、直近でミスマッチが起こった場所はiよりj+1個前）としてみました。ただし、jが4のときとjが5以上の時は状態としては同じなのでこれをdp[i][4]にまとめました。これで、7分30秒くらい。
さらに、ループの順番を入れ替えてネストを1段浅くして、3分くらいで解けるようになったのが下のコード。

import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.math.BigInteger.*;
import java.io.*;
import java.util.*;

@SuppressWarnings("unused")
public class C {
 Scanner sc = new Scanner(System.in);
 Scanner dictionary;
 String[] words = new String[521196];
 static final int oo = 1 << 28;

 void init() {
  try {

   dictionary = new Scanner(new File("garbled_email_dictionary.txt"));
   for (int i = 0; i < words.length; i++)
    words[i] = dictionary.next();

   debug(words[0]);
   debug(words[words.length - 1]);

  } catch (FileNotFoundException e) {
   e.printStackTrace();
  }
 }

 void solve() {
  String s = sc.next();

  int[][] dp = new int[s.length() + 1][5];
  for (int i = 0; i < s.length() + 1; i++)
   for (int j = 0; j < 5; j++)
    dp[i][j] = oo;

  dp[0][4] = 0;

  for (int i = 0; i < s.length(); i++) {
   for (int k = 0; k < words.length; k++) {
    String w = words[k];
    if (i + w.length() > s.length())
     continue;

    int cnt = 0;
    int tail = -oo;
    int st = 0;
    for (int l = 0; l < w.length(); l++) {
     if (s.charAt(i + l) != w.charAt(l)) {
      ++cnt;
      if (tail == -oo)
       st = max(0, 4 - l);
      
      if (i + l - tail < 5) {
       cnt = oo;
       break;
      }
      tail = i + l;
     }
    }
    if (cnt < oo) {
     for (int j = st; j < 5; j++) {
      int nwTail = (tail == -oo) ? (i - j - 1) : tail;
      nwTail = min(4, i + w.length() - 1 - nwTail);
      dp[i + w.length()][nwTail] = min(dp[i + w.length()][nwTail],
        dp[i][j] + cnt);      
     }
    }
   }
  }

  int ret = oo;
  for (int i = 0; i < 5; i++)
   ret = min(ret, dp[s.length()][i]);

  System.out.println(ret);

 }

 void run() {
  init();
  int T = sc.nextInt();

  for (int id = 1; id <= T; id++) {
   System.out.printf("Case #%d: ", id);
   System.err.printf("Solving Case #%d...\n", id);
   solve();
   System.out.flush();
  }
 }

 void debug(Object... os) {
  System.err.println(deepToString(os));
 }

 public static void main(String[] args) {
  new C().run();
 }
}