Hatena::Grouptopcoder

tsubosakaの日記

2010-05-09

Google Code Jam Qualification Round

21:33

Problem C

ケース数が50以下,Rが1億までなので50 * 1億なら間に合いそうということでO(N^2 + R)の解を提出

package gcj.qround;

import java.util.Scanner;

public class C {
  static long solve(long round , long capacity , long groups[]){
    long sum = 0;
    for(long g : groups){
      sum += g;
    }
    if(sum <= capacity){
      return round * sum;
    }
    int N = groups.length;
    long rewards[] = new long[N];
    int offsets[] = new int[N];
    for(int i = 0 ; i < N ; ++i){
      long s = 0;
      for(int j = 0 ; j < N ; ++j){
        if(s + groups[(i + j) % N] > capacity){
          offsets[i] = j;
          break;
        }
        s += groups[(i + j) % N];
      }
      rewards[i] = s;
    }
    long reward = 0;    
    int off = 0;
    for(int i = 0 ; i < round ; ++i){
      reward += rewards[off];
      off += offsets[off];
      off %= N;
    }
    return reward;
  }
  
  public static void main(String[] args) throws Exception{
    Scanner sc = new Scanner(System.in);
    int T = sc.nextInt();
    for(int cn = 1 ; cn <= T ; ++cn){
      long R = sc.nextLong();
      long k = sc.nextLong();
      int N = sc.nextInt();
      long gs[] = new long[N];
      for(int i = 0 ; i < gs.length ; ++i){
        gs[i] = sc.nextLong();
      }
      System.out.printf("Case #%d: %d\n", cn , solve(R , k , gs));
    }
  }
}

B

javaなのでBigInteger使って終了

package gcj.qround;

import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;

public class B {
  static String solve(BigInteger ts[]){
    int N = ts.length;
    BigInteger diffs[] = new BigInteger[N - 1];
    for(int i = 0 ; i < N - 1; ++i){
      diffs[i] = ts[i + 1].subtract(ts[i]);
    }
    BigInteger T = diffs[0];
    for(int i = 1 ; i < diffs.length ; ++i){
      T = T.gcd(diffs[i]);
    }
    BigInteger cur = ts[0];
    BigInteger m   = cur.divide(T);
    cur = cur.subtract(m.multiply(T));
    while(cur.compareTo(BigInteger.ZERO) > 0){
      cur = cur.subtract(T);
    }    
    return cur.negate().toString();
  }
  
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int C = sc.nextInt();
    for(int cn = 1 ; cn <= C ; ++cn){
      int N = sc.nextInt();
      BigInteger ts[] = new BigInteger[N];
      for(int n = 0 ; n < N ; ++n){
        ts[n] = sc.nextBigInteger();
      }
      Arrays.sort(ts);
      System.out.printf("Case #%d: %s\n", cn , solve(ts));
    }    
  }
}

A

とりあえず問題の意味を読み取るのに苦労した。A-smallは問題の解釈が正しいことを確かめるため愚直にk回シミュレートするコードを提出。変なところでbreakを入れてたせいで2 Wrong Answerになってしまった。でA-largeはOKの部分を表示してみるとN=1,2,3,4...に対してK=1,3,7,15...のところでOKになっており、Kが2^N - 1 + T * 2^Nの形になっていればよいことが分かったのでそのまま実装。

よくよく考えるとK+1が2^Nの倍数であるかどうか調べるだけでよかった。

package gcj.qround;

import java.util.Scanner;

public class A {
  static boolean solveSmall(int N , long K){
    boolean states[] = new boolean[N];
    for(int k = 0 ; k < K ; ++k){
      for(int i = 0 ; i < N ; ++i){
        if(states[i]){
          states[i] = false;
        }else{
          states[i] = true;
          break;
        }
      }
    }
    for(int i = 0 ; i < N ; ++i){
      if(!states[i])return false;
    }
    return true;
  }
  
  static boolean solveBig(int N , long K){
    long allOn = (1 << N) - 1;
    if(K < allOn){
      return false;
    }
    return (K - allOn) % (1 << N) == 0;
  }
  
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int T = sc.nextInt();
    for(int cn = 1 ; cn <= T ; ++cn){
      int N = sc.nextInt();
      long K = sc.nextLong();
      System.out.printf("Case #%d: %s\n", cn , solveBig(N , K) ? "ON" : "OFF");
    }
  }
}