Hatena::Grouptopcoder

tsubosakaの日記

2010-06-27

Topcoder Open Round 2

21:10

350人通過のところ335位でRound 3に進出となりました。

250

問題にある入力はすべて一筆書きができる状況になってるけど、かけない時にどうすればいいのかがわからない。

いろいろとグラフを書いてみるとどうも全て一筆書きできるように見える。そこで"有向グラフ 一筆書き"で検索してみると今回の入力のような入次数と出次数が同じグラフは必ず一筆書きできるということが分かった。

こうなると問題は非常に簡単で0から見てすべての枝が連結していることをチェックして、していれば枝の重みの合計を返せばよい。

public class SnowPlow {
  boolean connect(int adj[][]){
    int N = adj.length;
    int st = 0;
    Queue<Integer> q = new LinkedList<Integer>();
    q.add(st);
    boolean vis[] = new boolean[N];
    vis[st] = true;
    while(!q.isEmpty()){
      int cp = q.poll();
      for(int i = 0 ; i < N ; ++i){
        if(adj[cp][i] > 0){
          if(vis[i])continue;
          vis[i] = true;
          q.add(i);
        }
      }
    }
    for(int i = 0 ; i < adj.length ; ++i){
      if(vis[i])continue;
      int deg = 0;
      for(int a : adj[i])
        deg += a;
      if(deg != 0){
        return false;
      }
    }
    return true;
  }
  public int solve(String[] roads) {
    int N = roads.length;
    int adj[][] = new int[N][N];
    int total = 0;
    for(int i = 0 ; i < adj.length ; ++i){
      for(int j = 0 ; j < N ; ++j){
        adj[i][j] = roads[i].charAt(j) - '0';
        total += adj[i][j];
      }
    }
    return connect(adj) ? total : -1;
  }
}

500

とりあえず1億はrepresentable numberなので入力が1億のときはそのまま1億を返すことにして8桁以内の範囲で考えることにする。

totally oddとなる数は488280なのでrepresentable numberを列挙しようとすると488280^2かかる。ただしAを固定するとBの候補はX-Aより大きいものの中で最小のもので一意に決まるので二分探索を使えば計算量はO(488280 * lg 488280)ぐらいに収まる。

public class RepresentableNumbers {
  public int solve(int array[], int X) {
    int ret = 100000000;
    for(int i = 0 ; i < array.length ; ++i){
      int a = array[i];
      int b = X - a;
      int pos = Arrays.binarySearch(array , b);
      if(pos >= 0)return X;
      else ret = Math.min(a + array[-pos-1], ret);
    }
    return ret;
  }  
  static void generateAllOdd(int val, int len, List<Integer> list) {
    if(len == 0)list.add(val);
    else{
      for (int i = 1; i <= 9; i += 2) {
        generateAllOdd(val * 10 + i, len - 1, list);
      }      
    }
  }  
  public int getNext(int X){
    if (X == 100000000)return X;
    List<Integer> list = new ArrayList<Integer>();
    for (int len = 1; len <= 8; ++len)
      generateAllOdd(0, len, list);    
    Collections.sort(list);
    int arr[] = new int[list.size()];
    for (int i = 0; i < arr.length; ++i)
      arr[i] = list.get(i);
    return solve(arr, X);
  }
}

二分探索したけど以下の尺取メソッドのほうを使えば線形時間で実行できる。

  public int solve(int array[] , int X){
    int ret = 100000000;
    int j = array.length - 1;
    for(int i = 0 ; i < array.length ; ++i)
      while(j >= 0 && array[i] + array[j] >= X)        
      ret = Math.min(ret, array[i] + array[j--]);
    return ret;
  }

2010-06-06

Google Code Jam Round 2

23:36

475位でぎりぎり通過

A

問題の意味を何となく理解。

ダイアモンドの大きさは2倍程度にしかならなそうなのでk <= K <= 2kぐらいの範囲のKでダイアモンドを含む図形が成立するか試せば良さそう。

実装が重そうだったので次へ

B

Smallの制約がどう効いてくるのかいまいち不明。Stat見るとC Smallを解いてる人が多かったのでそっちへ

C

ライフゲーム。左と上が生きてないと生成が起きないので盤面の外側にセルがはみ出すことはない。左上からどんどん消えてくので100ターンぐらいで終わるはず。

愚直なシミュレートを書いたところ通る。

B

Mの値をいろいろ変えたときにどうなるか紙の上でいろいろと計算する。図の絵をひっくり返したrooted treeを考えたときに自分の親のノードのチケットを何個パスしたかが分かれば、その子ノードであとなんかいパスしてよいかが分かるので、現在のノードの位置と親ノードでチケットを買わなかった回数を状態とすれば状態は2^P P個しかないのでメモ化再帰で解ける。

D

図をみただけでやる気をなくす

A

とりあえず書いたけど通らない。終了間際に入力を左詰めしてたけどそれだと題意を満たさないことに気づく、修正を試みるも間に合わず。

終了時には520位台だったので終わったと思ったけどSystem testでLargeが何人か落ちたため、Round 3へ行けた。