cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み
スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、
GCJ | |
GCJ09-R1A の成績・ソース : AC-AC/AC-AC/AC-AC : 八分物語
※要するに 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]は順列組み合わせの個数を考えて頑張って式を出します
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; } }
# 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())
-- 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
presented by
cafelier/k.inaba
under
