Google Code Jam 2010 Qualification Round (code)

GCJ

ついでにソースコードも晒し上げ。

  • テンプレートは省略しました。

A. Snapper Chain

int main(){
  ll n,k,C;
  cin >> C;
  REP(CC,C){
    cin >> n >> k;
    n=(1<<n)-1;
    printf("Case #%d: %s\n", CC+1, (k&n)==n ? "ON" : "OFF");
  }
}

B. Fair Warning

  • 落ちた原因は、GCDを求めるところでv.size-1.times{ ... } とやってたところでした。
    • (v.size-1).times{ ... } とやんないとダメ。
    • ばーかばーか。
    • 2 <= N <= 3 なので、それでもsmallは普通に通ってしまうという酷い罠。
  • 下のは全面的に書き直したものです。 
def gcd(a,b)
  return b!=0 ? gcd(b,a%b) : a 
end

def main()
  c = gets.to_i
  c.times{ |cc|
    v = gets.split.map{ |e| e.to_i }[1..-1].uniq.sort
    u = (0 ... v.size-1).to_a.map{ |i| v[i+1]-v[i] }
    g = u.inject(u[0]){ |a, b| gcd(a, b) }
    puts "Case ##{cc+1}: #{(g-v[0]%g)%g}"
  }
end

main()

C. Theme Park

  • いろんな人のブログを見ると、みんなループを検出してショートカットしてる。
    • 全然気づかなかった。みんな天才すぎる。
    • O(N2 + log(R)) を考えた人他にいないの？
    • Analysisでも触れられてなかったし。
    • なんかちょっと寂しい。
  • 自分の書いた O(N2 + R) って、もしかしてPCの性能に頼ったセコい解法なのだろうか。
    • でも8分もあれば一昔前のPCでだって十分間に合うと思うんだけどなぁ。
      • 後で試してみよう。
const int N=1024;

ll solve(ll r,ll k, ll v[],ll n){
  static ll next[N];
  static ll earn[N];

  REP(i,n){
    ll cnt=v[i], pos=(i+1)%n;
    REP(j,n){
      if(cnt+v[pos]>k || pos==i) break;
      cnt+=v[pos];
      pos++; pos=pos%n;
    }
    next[i]=pos; earn[i]=cnt;
  }

  ll ans=0, pos=0;
  REP(i,r) ans+=earn[pos], pos=next[pos];
  return ans;
}

int main(){
  int C;
  cin >> C;
  REP(CC,C){
    ll r,k,n;
    static ll v[N];
    cin >> r >> k >> n;
    REP(i,n) cin >> v[i];

    printf("Case #%d: %lld\n",CC+1, solve(r,k,v,n));
  }
}