Hatena::Grouptopcoder

cafelier@SRM

cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み

スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、

 | 

2009-09-12

Google Code Jam 2009 Round 1A

| 12:44 | はてなブックマーク -  Google Code Jam 2009 Round 1A - cafelier@SRM

GCJ09-R1A の成績・ソース : AC-AC/AC-AC/AC-AC : 八分物語


A開く

  • 『"各桁の数字を二乗して総和を取る"という演算を繰り返して1になれる自然数をhappy numberという。baseによって違うので2進表記ではhappyでも10進だと違ったりする。入力で与えられる全てのbaseでhappyになるような最小の数を答えよう』

  • えーと、happyじゃない場合はどうなるんだ。1にならないでどっかで無限ループか
  • あと、必ずall-happyな数は存在するのかな。問題に書いてないから存在するんだろうな。そういうことにしよう。

  • 入力サイズ
    • baseは2進から10進まで
    • Small: baseは2個か3個与えられる
    • Large: baseは2個から9個まで

  • これは、入力パターンが2^9 = 512通りしかないから、手元で2時間かけて答え全部求めてから即座に表引きで返すような解が作れる…
    • だが断る
    • そうか、だから、"Important Note: Please remember that you must submit all code used to solve the problem." って注意書きがあるのか。そういう解き方をしたら表を作ったソースも忘れずsubmitしろよ、と。

  • さて
    • smallなら地道に、n=2から増やしてって全部でhappyかどうか判定して最初に見つかったのを表示、でいいんじゃないかなあ
    • happy判定は、メモ化 + ループ判定でできる。isHappy?(n,base) =
        • 既に (n,base) の場合が計算済みならそれを返す
        • そうでなければ、とりあえず isHappy?(n,base)==False として計算済みと思いつつ
        • isHappy?(二乗総和(n),base) を再帰呼び出し
        • 返ってきた結果を、改めて isHappy?(n,base) の結果として記憶
      • これで、無駄な最計算はなくなるし、ループしてたら途中の"とりあえずFalse"にヒットしてFalseが返る
  • 組めた

  • サンプルと合った
  • 2,3,4 でも 8,9,10 でも試す。時間は余裕。
  • よしsmall用データをゲット。submit。OK。
  • 次行こう。Largeは取らなくても、Small全取りで十分次のラウンドには進めるはず。

B開く

  • めんどくさい図が見えた。
  • さようなら

C開く

  • 『全部でC枚あるカードをコンプリートしたい。重複なしN枚ずつのセットで売ってくれるのだけど、コンプリートまでに買う必要のあるセット数の期待値は?』
    • Small: C,N<=10
    • Large: C,N<=40
  • Σn=1..∞ (ちょうどnセットかった時に揃う確率)*n
  • が答え
  • 極限を数式で求めるのは…どうすればいいんだー
    • 10000セットくらい買ったときまでシミュレートすれば十分じゃないですかね。誤差10^-5くらいなら。少なくともSmallはそれでいいでしょう。。。
  • 「kセット買ったときそろってる枚数がi枚の確率」みたいなのは行列の掛け算で表すと綺麗。
  • 最初は、v = (0枚そろってる確率=1.0、他=0.0)
  • 次は、N枚そろってる確率=1.0、他=0.0
  • その次は、N枚そろってる確率から 2N枚そろってる確率まで、組み合わせの数に応じて分布
  • ...
  • という1ステップ1ステップの変化を、行列Mで表現できて、
  • Mv、M(Mv)、M(M(Mv))、…で次々求まる。
  • 後は総和をとるだけ
※要するに M は
 (0枚→0枚になる確率  1枚→0枚になる確率  ...  C枚→0枚になる確率)
 (1枚→0枚になる確率  1枚→1枚になる確率  ...  C枚→1枚になる確率)
 ...
 (0枚→C枚になる確率  1枚→C枚になる確率  ...  C枚→C枚になる確率)
こういう「M[i][j] = i枚揃ってる状態で1セット買ったらj枚になる確率」な行列を考えました。
こうすると、v=(今0枚揃ってる確率, 1枚揃ってる確率, ... C枚揃ってる確率) という縦ベクトルに左からMを掛け算すると、もう1セット買った後の揃ってる確率ベクトルになります。各M[i][j]は順列組み合わせの個数を考えて頑張って式を出します

  • (N枚のデッキは重複ないことを忘れていて全然答えが合わず苦戦中…)
  • (あと行列とベクトルの縦横がごっちゃになってて酷い感じ)

  • あー重複ないのか。なんだー
  • 書けた。サンプルは10000回回せばぴったり。
  • 適当に自分でテストケース作ってみても、10000回と12000回ではもう収束しててまったく変わらない。
  • よし!10000回で十分!
  • Smallをsubmit。OK。

B再び

  • 『交叉点の信号がついたり消えたりするので最短時間で左下の角から右上の角まで歩いてね』
    • はいはいダイクストラダイクストラ。
  • なんでもグラフにしてみる の記事の時刻表の例と全く同じ考え方です
    • (場所) だけじゃなくて (場所,到達時刻) のペアによって行ける行き先が違うので、そういう拡大グラフを念頭に最短路
      • (場所,到達時刻) のペアは普通のDijkstraでもどうせ作るので、あまり拡大グラフとかは意識しないかもしれません。
  • というわけで書くだけ
    • 人間のいられる場所を表すデータとして、座標[y,x]の交叉点の左上が(2y,2x)、右下が(2y+1,2x+1)、のようなペアを使うことに決定
      • (y,x,{NE,SE,NW,SW}) みたいなのは考えるのも面倒だった
    • このエンコーディングの扱いを間違えないように気をつけながらガリガリ書く
    • ところで、嫌な入力ケースってなにがあるかなー
    • 右と上以外考えなくていいと見せかけて、すごく待ちの長い信号を作ることで、実は一時的に左や下に戻らないといけないケース
      • 絶対こういうの入ってる。
      • 戻るケースも忘れずdijkstraの隣接頂点列挙に入れておく
    • あとは…
      • Largeの方、信号点滅の時間が10^7オーダー…。これ全部の和を取ったら32bit越えるかな?念のためlongに。
  • できた。Small-submit。OK。
  • LargeもこれはOKでしょー。submit。
import java.util.*;

public class B
{
   public static void main(String[] arg)
   {
      Scanner sc = new Scanner(System.in);
      int T = sc.nextInt();
      for(int C=1; C<=T; ++C)
      {
         System.out.printf("Case #%d: ", C);
         (new B(sc)).caseMain();
      }
   }

   Scanner sc;
   B( Scanner sc ) { this.sc = sc; }

   void caseMain()
   {
      int Y = sc.nextInt();
      int X = sc.nextInt();
      long[][] S = new long[Y][X];
      long[][] W = new long[Y][X];
      long[][] T = new long[Y][X];
      for(int y=0; y<Y; ++y)
         for(int x=0; x<X; ++x)
         {
            S[y][x] = sc.nextInt();
            W[y][x] = sc.nextInt();
            T[y][x] = sc.nextInt();
         }
      System.out.printf("%d\n", solve(Y, X, S, W, T));
   }

   long solve(final int Y, final int X, long[][] S, long[][] W, long[][] T)
   {
      class State implements Comparable<State>
      {
         long t;
         int y, x;
         int id() { return y*(2*X) + x; }
         State(long t, int y, int x){this.t=t; this.y=y; this.x=x;}

         public int compareTo(State rhs) {
            if( t < rhs.t ) return -1;
            if( t > rhs.t ) return +1;
            if( y < rhs.y ) return -1;
            if( y > rhs.y ) return +1;
            if( x < rhs.x ) return -1;
            if( x > rhs.x ) return +1;
            return 0;
         }
      }

      PriorityQueue<State> Q = new PriorityQueue<State>();
      Q.add( new State(0, 2*(Y-1)+1, 0) );

      Set<Integer> visited = new HashSet<Integer>();

      while( !Q.isEmpty() )
      {
         State s = Q.poll();
         if( visited.contains(s.id()) )
            continue;
         visited.add(s.id());

         if( s.y==0 && s.x==2*(X-1)+1 )
            return s.t; // goal

         int[] dy={-1,+1,0,0};
         int[] dx={0,0,-1,+1};
         for(int i=0; i<4; ++i)
         {
            int y2=s.y+dy[i], x2=s.x+dx[i];
            if( y2<0 || 2*Y<=y2 || x2<0 || 2*X<=x2 )
               continue;
            if( visited.contains(y2*(2*X)+x2) )
               continue;
            long t2 = s.t;
            if( s.x!=x2 && s.x/2!=x2/2 ) t2 += 2;
            else if( s.y!=y2 && s.y/2!=y2/2 ) t2 += 2;
            else if( s.x!=x2 )
            {
               long Si = S[y2/2][x2/2];
               long Wi = W[y2/2][x2/2];
               long Ti = T[y2/2][x2/2] % (Si+Wi) - (Si+Wi);
               long d = (s.t - Ti) % (Si+Wi);
               if( d < Si ) t2 += (Si-d)+1;
               else t2 += 1;
            }
            else //if(y!=y2)
            {
               long Si = S[y2/2][x2/2];
               long Wi = W[y2/2][x2/2];
               long Ti = T[y2/2][x2/2] % (Si+Wi) - (Si+Wi);
               long d = (s.t - Ti) % (Si+Wi);
               if( d < Si ) t2 += 1;
               else t2 += (Si+Wi-d)+1;
            }
            Q.add( new State(t2, y2, x2) );
         }
      }
      return -1;
   }
}

A再び

  • 全部の答えを前計算するのはやりたくないなー。
  • なんとか賢く8分以内で…
    • 思いつかない間手が暇だったのでちょっとPythonっぽくyieldなど使うソースに書き換えてみたり
  • とりあえずさっきのsmall解で2,3,4,5,6,7,8,9,10の最悪ケースが何分かかるか計ってみる
    • 2分33秒、これは…

  • テストケース500個あるので一見500倍するとダメそうに見えるけど…
  • 全部メモ化でisHappy判定がキャッシュされるので、2個目移行のケースはそれなりに早いはず。~1000万回程度の辞書引き
    • 2,3,4,5,6,7,8,9,10を2個並べてみたら2個目は3秒くらい。
  • 3秒×500はまだダメそうに見えるけど…
    • 全部最悪ケースで埋めるなんて無体なことはしないと信じよう
    • もうスコアはRound1通過には十分だし、ドキドキ気分を味わいたい

  • Largeダウンロード
  • 実行開始
  • ...
  • ...
  • ...
  • 6分30秒経過...
    • 出力ファイルチラ見。250ケースまで進んでる…!
  • ...
  • ...
  • 7分40秒くらい
    • 解けた!submit!!!!!勝利!!!!!!
  • やばいこれは楽しい
# Python 2.6 (提出後ちょっと整頓した版)

memo = [dict() for _ in range(0,11)]
def isHappy(n, b):
   if n == 1:       return True
   if n in memo[b]: return memo[b][n]

   s = 0
   i = n
   while i > 0:
      s += (i%b)*(i%b)
      i //= b

   memo[b][n] = False
   v = isHappy(s, b)
   memo[b][n] = v
   return v

def happyGen(bases, i=0):
   if i == len(bases):
      n = 2
      while True:
         yield n
         n = n+1
   else:
      for n in happyGen(bases,i+1):
         if isHappy(n, bases[i]):
            yield n

### main ###

import sys

CN = int(sys.stdin.next())
for C in range(1, CN+1):
   bases = map(int, sys.stdin.next().split(" "))
   print "Case #%d: %d" % (C, happyGen(bases).next())

C再び

  • C,N<=10 が C,N<=40に増えても、気にせず10000回も回せば収束しているみたい。
  • ただ、10000だと1ケース15秒くらい。100ケースあるそうなので、これは間に合わない。タイムリミットは480秒。
    • 逆に言うと、1ケース4.8秒くらいまで回して収束してればそれで十分
      • 念のため4秒くらいかかるステップ数(3000回)で実験
      • うん、収束している
  • というわけでLargeダウンロード
  • 実行開始!
  • ...
  • ...
  • ...
  • 6分20秒経過...
    • 解けた!submit!!!!!勝利!!!!!!
-- Lua 5.1.2 (行列の縦横をsubmitした版と逆にした版)

function comb(N,k)
   v = 1
   for i=0, k-1, 1 do
      v = v * (N-i) / (k-i)
   end
   return v
end

function matmult(m, v, n)
   u = {}
   for i=0, n, 1 do
      u[i] = 0
      for j=0,n,1 do
         u[i] = u[i] + m[i][j] * v[j]
      end
   end
   return u
end

function makeM(C, N)
   m = {}
   for to=0, C, 1 do
      m[to] = {}
      for fr=0, C, 1 do
         if N<=to and fr<=to and to<=fr+N then
            m[to][fr] = comb(C-fr,to-fr) * comb(fr,N-(to-fr)) / comb(C,N)
         else
            m[to][fr] = 0.0
         end
      end
   end
   return m
end

function makeV(C)
   v = {}
   v[0] = 1.0
   for i=1, C, 1 do
      v[i] = 0.0
   end
   return v
end

function solve(C, N)
   m = makeM(C, N)
   v = makeV(C)

   e = 0
   for t=1, 3000, 1 do
      u = matmult(m, v, C)
      e = e + t*(u[C]-v[C])
      v = u
   end
   return e
end

-- main
CN = io.stdin:read("*n")
for CID=1, CN, 1 do
   C, N = io.stdin:read("*n","*n")

   io.stdout:write( string.format("Case #%d: %.8f\n", CID, solve(C,N)) )
end

感想

  • AとCはあとでマジメに考えます!Aはこれで正解のような気もするけどCはもう少し何かありそう
    • ああそうかー。Cは期待値で連立方程式になるだけかー。あるいはほとんど遷移関係がdagなのでローカルな方程式だけ使ってDPっぽく。なるほどなあ
トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20090912
 | 

presented by cafelier/k.inaba under CC0