naoya_t@topcoder

Google Code Jam: Qualification Round 2010

14:59 |

http://code.google.com/codejam/

暫定99点→C-Largeを落として76点 （暫定76位→1510位）。たぶん通過。

参加者10492名、予選通過者(Score≧33)は8523名。

	問題名	small	large	備考
A	Snapper Chain	0:46:06(WAx2)	0:47:05
B	Fair Warning	1:25:56	1:26:37
C	Theme Park	1:52:19	1:55:55(WA)

Qualification Roundの基本戦略

• Largeが通るコードを最初から書く
  • Largeが（自分の頭基準で）無理ゲーな場合は仕方がないけどQRでそれはないだろう
• 時間制限は有って無いようなものなのでA,B,Cの順で解く
  • でもスコアシステム的には解ける問題をさっさと解いたほうが高得点なんだよね！
• 言語の縛りはないので解きやすそうな言語で
  • とか言っても結局C++とかScheme(Gauche)とかで書いてる

問題A: Snapper Chain

• 問題よみにくい。
  • bothって何と何？？とか暫く悩んだ
• 解けたと思って自信もって提出した答えはランプのon/offではなくスイッチのon/offだった件
  • えーおかしい合ってるはずなのにー、もしかして入力ファイルを出しちゃったのか？とか思ってまた投稿。当然WA
• ああ勘違い。恥ずかしい。問題文わかりにくいけどこれは自分の責任…
• 三度目の正直でsmall通過。引き続きlargeも提出

解法

• 幾ステップか手動でやってみた。（←こういうのとかプログラム書いてやればいいのに…）スイッチのon/offがスナップした回数の２進数表記になってることが分かった
• ランプのon/off状態（通電状態）はLSBから見て最初の0の手前までがon、それ以降がoffなはず
• スナップ回数を２進表記して、LSBから数えて指定ビット目までに0があるか見ればよいですね

#include <iostream>
using namespace std;
#define rep(var,n)  for(int var=0;var<(n);var++)
main(){
  int T;cin >> T; //1-10000
  rep(t,T){
    int N,K; cin >> N >> K;

    // Nは電球の位置, Kはスナップ回数
    // スイッチのon/off状態はK自体が現しているので計算不要

    // LSB側から見て最初に現れる0のビットの位置を探す※
    int b,m;
    for(m=1,b=0;b<=30;b++,m<<=1){
      if ((K & m)==0) break;
    }

    // 通電範囲のビットを立てたものを用意
    int rec = (1 << (b+1))-1;

    // 電球が点いているかどうか。
    // K & rec == K な気もするが放っとけ
    int on = (K & rec) & (1 << (N-1));
    printf("Case #%d: %s¥n", 1+t, on?"ON":"OFF");
  }
}

• ~x & (x+1)で最右の0のビットだけが立った数が得られるので、rec は (~x & (x+1))-1 なはず。ということは

  int T; cin >> T;
  for(int t=1; t<=T; t++) {
    int N, K; cin >> N >> K;
    bool on = (~K & (K+1))-1 & (1 << (N-1));
    printf("Case #%d: %s¥n", t, on?"ON":"OFF");
  }

とかそのくらいの話ですね…

あるいは on = (~x & (x+1)) >= (1 << N)

教訓とか

• パターン見るのに手描きでステップを追うのは卒業したい
• ビット操作系で悩んだらHacker's delightを参照

問題B: Fair Warning

• 2^50じゃなくて10^50か…
• C++で自作Bignumライブラリ使ってでも解けるけど怖いな
• 多倍長整数演算がデフォルトで使える言語の中で一番慣れ親しんだSchemeで行くことにする
• 最初からlargeが通るはずのコードなので躊躇わずsmall/large連続投稿

解法

• 周期がある整数の倍数になっているイベントについて、これまでの発生時刻がわかっているので次に起こるとしたら最短でいつか
• 発生時刻同士の差を総当たりで取って、その最大公約数を最後のイベント発生時刻に足すとかそんな感じでどうでしょう
• Schemeで書いたけれどdotimesとか破壊的代入を使ってて邪道。もっとSchemeらしいコードを書かないとネタとしてお粗末

;; in Gauche http://practical-scheme.net/gauche/index.html
(use srfi-1)

(define (gcd a b)
  (if (zero? b) a (gcd b (remainder a b))))

(define (calc-T ds)
  (let loop ((g (car ds)) (rest ds))
    (if (null? rest) g
        (let1 r (car rest)
          ;; 値の大小関係がわかっているところで無用なsortをしてるが放っとけ
          (loop (apply gcd (sort (list g r)))
                (cdr rest))))))

(let1 c (x->number (read))
  (let loop ((i 1))
    (when (<= i c)
      (let* ([n (read)]
             [v (make-vector n)]
             [h (make-hash-table 'eqv?)])
        (dotimes (i n) 
          (vector-set! v i (x->number (read))))
        (dotimes (i n)
          (dotimes (j n)
            (when (< i j)
              (hash-table-put! h (abs (- (vector-ref v i) (vector-ref v j))) #t))))
        (let* ([last (car (sort (vector->list v)))]
               [T (calc-T (sort (hash-table-map h (lambda (k v) k))))]
               [rem (remainder last T)])
          ;;(print "T=" T)
          ;;(print "rem=" rem)
          (format #t "Case #~d: ~d¥n" i
                  (if (zero? rem) 0 (- T rem))))
        (loop (+ i 1))))))

教訓とか

• C++でもBignum使い慣れておいた方がよいかも
• あるいは全部Schemeで書いてはどうか（そしたら問題Cでの悲劇も防げただろうに）

問題C: Theme Park

• これは比較的わかりやすい

解法

• 列の1組目〜N組目のそれぞれから載せて行ってk人を超える以前に何組何人乗せられるかあらかじめ調べておく。高々1000000通り。
• 答えはR*k≦1e17なのでintに収まらない
• 何週もしてると同じパターンが循環するはずで、そこを端折るともっと速くなるだけど、最悪ケースを回してみて大して時間がかからなかったのでそこまで頑張らなくてもいいかなと

#include <iostream>
#include <vector>
using namespace std;
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()
typedef long long ll;

main(){
  int T; cin >> T; //1-50
  rep(t,T){
    int R, k, N; cin >> R >> k >> N; // 1-1e8, 1-1e9, 1-1000
    vector<int> g(N); rep(i,N) cin >> g[i]; // 1-1e7
    int ans = 0;
    vector<int> gg(all(g)); gg.insert(gg.end(),all(g));
    vector<int> acc(N*2+1,0); ///※ OOPS.. accsはvector<long long>であるべし
    vector<int> hi(N), len(N);
    rep(i,N*2){
      acc[i+1] = acc[i] + gg[i];
    }
    rep(i,N) {
      int lo=acc[i], lim=lo+k, j; ///※ ここもlong longであるべし
      for(j=1;j<=N;j++){
        if (acc[i+j] > lim) { j--; break; } ///※ intでオーバーフローするとこの不等式が想定しない意味を持つ
      }
      if (j>N) j=N;
      hi[i] = acc[i+j] - lo; len[i] = j;
    }

    int at=0; ll earn=0LL;
    rep(r,R){
      earn += hi[at];
      at = (at + len[at]) % N;
    }
    printf("Case #%d: %lld¥n", 1+t, earn);
  }
}

教訓とか

• 最初の（100万通りの）下調べの際に、1組目から1000組目までの累計を用いたサーチをしているが、累計値はk*N≦1e12なのでintに収まらない。
• こんな下らない（というかいつも通りの）ミスで落とすのが勿体無くて自分の詰めの甘さにがっかりして心が折れた。青と黄色を往復する原因もこういう事なので。
• それぞれの変数に入るであろう値の範囲ぐらいしっかり考えること。

結果

当然ながらC-largeがWAで99点→76点。

多分通ってると思うけどがっかりです…

次回(Round 1)は5/22〜23に３チャンス。頑張るぞー！（おー！）