2009-09-27

■ [GCJ]Google Code Jam 2009 Round2 21:25 はてなブックマーク - Google Code Jam 2009 Round2 - TopCoderの学習のお時間

2009-09-26 25:00 - 27:30（JST）

3000人→500人。

問題

ID タイトル small large 問題タイプ
A Crazy Rows AC AC greedy
B A Digging Problem Opened - 碁盤目ゲーム、DP
C Stock Charts TLE - グラフ、最大マッチング
D Watering Plants AC Opened 平面幾何、円

ログ

  • A読む
    • 下三角成分に含まれる1の数を最大化する（上三角部分に1が残ることもある）という問題だと誤読
    • とりあえずsmall通すかとnext_permutationとか書き始めたがそれじゃswap回数わからんではないか
    • ううー、わからん。後回し
  • B読む
    • とりあえずsmall通すかとBFS書き始めたが、単純にやると状態数多すぎなことに気づいて中断
    • 後回し
  • C読む
    • すぐには何も浮かばないので問題の把握だけして後回し
  • D読む
    • えっsmallではN<=3!?　それってめっちゃ簡単なのでは…
    • Nで場合分けしてとりあえずsmall通した。少し落ち着いた
  • Aに戻る
    • こんなにたくさんの人が通してるのだからそんなに難しいはずがないと思って問題文を読み直す
    • 勘違いに気づいた
    • 上三角部分に1が入っちゃいけないのか…
    • ならば条件がきつい上の行から順に、条件に当てはまる行のうち一番近いところにあるやつを貪欲に持ってくればよい
    • 境界条件ミスって一度WAしたがsmall、largeとも正解。
  • 次にsmallの点数が小さいCを考える
    • 各折れ線の組に対して交わっているかどうかで無向グラフを作って、それを完全グラフに分割したときの最小分割数を求める、という問題に帰着させた
      • どうもこれは過度な一般化だったらしい。この段階でもう負けでした
    • largeではN=100だからきっと最大流かマッチングだよなーと思って考えるも、どうやったらフローやマッチングを利用できる形になるのか思いつかない
    • とりあえずsmallを力づくで通そうとする。N=16だからO(2^N)でOK。
    • しかしO(2^(N^2))な感じのアルゴリズムしか書けなかった！　4分では終わりません。
  • Bは、状態遷移が多くて書いたところでバグりまくりそうなので捨て
  • D-largeは、最高点数だからきっと難しいし3円に接する円の中心点を算出する方法がすぐ思い浮かばずはまってしまいそうだしということで捨て

結果

  • 21pt/100pt
  • 903位/3000人

実力どおりの結果だったと思います。

反省

  • 問題文の誤読はどうしてもやってしまうものではあるが、正解者数の状況を見て本番中に落ち着いて修正できたのは収穫
  • Bのような、ゲーム的な状態遷移があるのはBFSで解けるやつしかやったことがない。DPを使うタイプのものにも慣れないと
  • グラフは、最近ようやく最大流とか二部グラフ最大マッチングが使えるようになったものの、もろにそのアルゴリズムが適用できることがわかる問題しか経験したことがない。もっと多様な課題に対して、手持ちのどの道具を適用できるか？　ということを考える訓練が要ります

【追記】

  • C-smallはビットDPやるとO(N^2*2^N)でできました。実行時間10秒弱。これは気づきたかったなぁ…。本当に、一般のグラフの問題にしてしまったのがだめだった

以下C-smallのコード 

import java.io.File;
import java.io.FileWriter;
import java.util.Arrays;
import java.util.Scanner;

public class C {

  public static void main(String[] args) throws Exception {
    String fileName = "C-small-practice";
    Scanner sc = new Scanner(new File("bin\\" + fileName + ".in"));
    FileWriter writer = new FileWriter(new File("bin\\" + fileName + ".out"));
    int T = sc.nextInt();
    for (int i = 0; i < T; ++i) {
      int N = sc.nextInt();
      int K = sc.nextInt();
      int[][] p = new int[N][K];
      for (int j = 0; j < N; ++j) {
        for (int k = 0; k < K; ++k) {
          p[j][k] = sc.nextInt();
        }
      }
      boolean[][] g = new boolean[N][N]; // iの上側にjを置けない場合 g[i][j] == true
      for (int j = 0; j < N; ++j) {
        g[j][j] = true;
      }
      for (int j = 1; j < K; ++j) {
        for (int k = 0; k < N; ++k) {
          for (int l = k + 1; l < N; ++l) {
            if ((long)(p[k][j - 1] - p[l][j - 1]) * (long)(p[k][j] - p[l][j]) <= 0) {
              g[k][l] = g[l][k] = true;
            }
          }
        }
      }
      for (int k = 0; k < N; ++k) {
        for (int l = k + 1; l < N; ++l) {
          if (!g[k][l]) {
            if (p[k][0] < p[l][0]) {
              g[l][k] = true;
            } else {
              g[k][l] = true;
            }
          }
        }
      }
      int[][] dp = new int[1 << N][N]; // dp[これまで使った折れ線][最後に使った折れ線]
      for (int[] a : dp) {
        Arrays.fill(a, Integer.MAX_VALUE);
      }
      for (int s = 1; s < (1 << N); ++s) {
        for (int j = 0; j < N; ++j) {
          if ((s & (1 << j)) == 0) {
            continue;
          }
          int prev = s - (1 << j);
          for (int k = 0; k < N; ++k) {
            if ((prev & (1 << k)) == 0) {
              continue;
            }
            int cand = dp[prev][k];
            if (g[k][j]) {
              ++cand;
            }
            dp[s][j] = Math.min(dp[s][j], cand);
          }
          if (dp[s][j] == Integer.MAX_VALUE) {
            dp[s][j] = 1;
          }
        }
      }
      int result = Integer.MAX_VALUE;
      for (int j = 0; j < N; ++j) {
        result = Math.min(result, dp[(1 << N) - 1][j]);
      }
      writer.write("Case #" + (i + 1) + ": " + result + "\n");
    }
    writer.close();
  }
}