TopCoderのスタックサイズの増やし方
なるほど……。試してみよう。
#include <string> #include <vector> #include <utility> #include <set> #include <cstdlib> using namespace std; set<pair<int,int> > S; void f1(int a, int b, int x, int y) { if (a==0 || b==0) { S.insert(make_pair(x,y)); return; } S.insert(make_pair(a,b)); if (a<b) f1(a, b-a, x, y); else f1(a-b, b, x, y); } int f2(int c, int d) { if (c==0 || d==0) return -1; if (S.count(make_pair(c,d)) > 0) return c+d; return c<d ? f2(c, d-c) : f2(c-d, d); } class PairGame{public: int maxSum( int a, int b, int c, int d ) { f1(a, b, 1234567, 1234567); return f2(c, d); }};
このプログラムは、TopCoder SRM 620 Div1 Easy PairGameを再帰で書いたもの。f1の引数のx,yを消せば通るけど、引数が増えるとスタックの消費量も増えてスタックオーバーフローで落ちる。単に引数を追加するだけだと最適化で消えてしまったので、最後に意味もなくSに追加している。
int a, b, c, d, r; long long esp_org, esp_new; class PairGame{public: int maxSum( int a, int b, int c, int d ) { // 新しいスタック領域を確保する const int size = 128*1024*1024; void *p = malloc(size); esp_new = (long long)p + size - 1; // スタック上の変数を待避 ::a = a, ::b = b, ::c = c, ::d = d; // スタックを置き換える __asm__("mov %rsp, esp_org"); __asm__("mov esp_new, %rsp"); // メインの処理 f1(::a, ::b, 1234567, 1234567); r = f2(::c, ::d); // スタックを元に戻す __asm__("mov esp_org, %rsp"); return r; }};
このように書き換えたら通った。簡単(･∀･) 次のところでハマった。
再帰が深くなりすぎる場合、再帰を使わないように書いていたけれど、ここまで簡単にできるならばスタックサイズを増やすのはありかもしれない。
Google Code Jam Round 1B 2014
A. The Repeater
文字列の組が与えられたとき、a→aaやaa→aという操作を繰り返して、全ての文字列を等しくする最小手数は？
各文字ごとに何文字に揃えるのかを全探索。
※↓このコードはLarge落ちた。提出ミスだった。
def minify(s): r = "" for i in range(len(s)): if i==0 or s[i-1]!=s[i]: r += s[i] return r def toarray(s): a = [] for i in range(len(s)): if i==0 or s[i-1]!=s[i]: a += [1] else: a[-1] += 1 return a def solve(S): if len(set(minify(s) for s in S)) > 1: return "Fegla Won" A = [toarray(s) for s in S] ans = 0 for p in range(len(A[0])): a = 99999999 for x in range( min(a[p] for a in A), max(a[p] for a in A)+1): a = min(a, sum(abs(a[p]-x) for a in A)) ans += a return ans for i in range(input()): N = input() S = [raw_input() for _ in range(N)] a = solve(S) print "Case #%s: %s" % (i+1, a)
B. New Lottery Game
正数A, B, Kに対して、a
xがXより小さいとは、Xのiビット目が1で、xのiビット目が0で、iより上位のビットではXとxが等しいというiが存在することである。A, B, Kそれぞれに対してそのようなビットの位置を決め、それを満たす(a,b)が何通りあるかを数えた。場合分けが煩雑になってしまったが、GCJではまずはナイーブなプログラムでSmallを通し、LargeのプログラムはSmallの入出力でテストするという手が使える。
Small
def solve(A, B, K): r = 0 for a in range(A): for b in range(B): if (a&b)<K: r += 1 return r for t in range(input()): A, B, K = map(int, raw_input().split()) print "Case #%s: %s" % (t+1, solve(A,B,K))
Large
def solve(A, B, K): r = 0 for a in range(32): if A>>a&1: for b in range(32): if B>>b&1: for k in range(32): if K>>k&1: t = 1 for i in range(32): if i<k: if i<a and i<b: t *= 4 elif i<a or i<b: t *= 2 else: t *= 1 else: x = K>>i&1 if i==k: x = 0 if i<a and i<b: t *= [3, 1][x] elif i<a or i<b: if i<a: y = 0 if i==b else B>>i&1 else: # i<b y = 0 if i==a else A>>i&1 if x==0 and y==0: t *= 2 elif x==0 and y==1: t *= 1 elif x==1 and y==0: t *= 0 elif x==1 and y==1: t *= 1 else: y = (0 if i==a else A>>i&1) & (0 if i==b else B>>i&1) if x==y: t *= 1 else: t *= 0 r += t return r for t in range(input()): A, B, K = map(int, raw_input().split()) print "Case #%s: %s" % (t+1, solve(A,B,K))
C. The Bored Traveling Salesman
問題文の条件が分かりづらいけど、要は、
グラフの全域木を辿り行きがけ順で各ノードに与えられた文字列を連結する。辞書順最小の文字列を答えよ
どのノードを根としても当然全域木は得られるので、根は文字列が一番小さいノードを選べば良い。辞書順最小の文字列を答えるので、あとは移動可能なノードのうち文字列が最小のものを選んで行けば良い。移動可能なノードとは、現在地点からの帰り道の途中から移動できて、そのノードに移動したとしても残りの全てのノードを辿れるもの。残り全てのノードを辿れるかどうかは、これまでに通ったノードのうち帰り道以外のものを全て削除して、グラフが連結かどうかを調べれば良い。
import itertools def solve(N, Z, F): p = Z.index(min(Z)) ans = Z[p] S = [p] V = [False]*N V[p] = True for _ in range(N-1): next = -1 for p in range(N): if V[p]: continue s = S[:] while len(s)>0 and not F[s[-1]][p]: s.pop() if len(s)==0: continue s += [p] v = V[:] c = [False]*N while len(s)>0: q = s.pop() v[q] = True for i in range(N): if F[q][i] and not v[i]: s += [i] c[q] = True ok = True for i in range(N): if not v[i] and not V[i]: ok = False if ok and (next<0 or Z[p]<Z[next]): next = p ans += Z[next] while not F[S[-1]][next]: S.pop() S += [next] V[next] = True return ans for t in range(input()): N, M = map(int, raw_input().split()) Z = [raw_input() for _ in range(N)] F = [[False]*N for _ in range(N)] for _ in range(M): a, b = map(lambda x: int(x)-1, raw_input().split()) F[a][b] = F[b][a] = True print "Case #%s: %s" % (t+1, solve(N,Z,F))
SRM614
オーバーフローでSmallを落としたorz
MinimumSquare
正方形の位置とサイズを与えられた点から決めて含まれる点の個数を調べる。サイズを二分探索することで高速化。
#include <string> #include <vector> #include <algorithm> #include <climits> using namespace std; class MinimumSquare{public: long long minArea( vector <int> x, vector <int> y, int K ) { int n = (int)x.size(); long long ans = LLONG_MAX; for (int xi=0; xi<n; xi++) for (int yi=0; yi<n; yi++) { long long x0 = x[xi]-1; long long y0 = y[yi]-1; vector<long long> s; for (int i=0; i<n; i++) { if (x[i]+1>x0) s.push_back(x[i]+1-x0); if (y[i]+1>y0) s.push_back(y[i]+1-y0); } sort(s.begin(), s.end()); int l=0; int r=(int)s.size()-1; auto check = [&](int p) -> bool { int c = 0; for (int i=0; i<n; i++) if (x0<x[i] && x[i]<x0+s[p] && y0<y[i] && y[i]<y0+s[p]) c++; return c >= K; }; if (!check(r)) continue; while (r-l>1) { int m = (l+r)/2; (check(m)?r:l) = m; } ans = min(ans, s[r]*s[r]); } return ans; }};
CycleColoring
小さいサイクルには点線の辺が2本生えている。その2本が同じ色になる場合と異なる色になる場合が何通りあるかを求め、それを使って答えを求める。小さいサイクルも大きいサイクルも、始点と同じ色になる場合と異なる色になる場合を覚えておいて動的計画法。
#include <string> #include <vector> using namespace std; // a^b mod m long long powm(long long a, long long b, long long m) { long long r=1,t=a; for(;b>0;t=t*t%m,b>>=1)if(b&1)r=r*t%m; return r; } class CycleColoring{public: int countColorings( vector <int> vertexCount, vector <int> fromVertex, vector <int> toVertex, int K ) { const int M = 1000000007; int N = (int)vertexCount.size(); vector<long long> S(N); // fromとtoが同じ色になる場合の数 vector<long long> D(N); // fromとtoが異なる色になる場合の数 for (int i=0; i<N; i++) { // type=0ならS[i]を、type=1ならD[i]を計算する for (int type=0; type<2; type++) { long long s = 1; long long d = 0; int n = vertexCount[i]; int dist = (fromVertex[i] - toVertex[(i-1+N)%N] + n) % n; if (dist==0 && type==1) { D[i] = 0; continue; } for (int j=1; j<n; j++) { long long ps = s; long long pd = d; s = pd; d = (ps*(K-1) + pd*(K-2))%M; // toの位置を0としてfromの位置になったら色が条件を満たすか確認 if (j==dist) (type==0 ? d : s) = 0; } (type==0 ? S[i] : D[i]) = d; } } long long s = K; long long d = 0; long long Ki = powm(K-1,M-2,M); // 1/(K-1) for (int i=0; i<N; i++) { long long ps = s; long long pd = d; s = (ps*S[i] + pd*D[i]%M*Ki) % M; d = (ps*D[i] + pd*D[i]%M*Ki%M*(K-2)%M + pd*S[i]%M) % M; } return (int)s; }};
SRM585 Div2 Medium(500) TrafficCongestionDivTwo
class TrafficCongestionDivTwo: def theMinCars(self, treeHeight): T = [1,1] while len(T)<=treeHeight: T += [(T[-1]+2*T[-2])] return T[treeHeight]
SRM585 Div2 Easy(250) LISNumberDivTwo
class LISNumberDivTwo: def calculate(self, seq): return sum(seq[i]>=seq[i+1] for i in range(len(seq)-1))+1
SRM585 Div1 Medium(500) LISNumber
動的計画法。小さい順にn枚のカードを選んだとき、a[i]≧a[i+1]となるiがちょうどk個になる並べ方の数を覚えておく。これは同じ数字のカードを区別した場合の数なので、最後に数字ごとにその数字のカードの枚数の階乗で割る。法Mが素数ならば、1/x = xM-2になる。Pythonならば、pow(x,M-2,M)で高速に計算できる。
class LISNumber: def count(self, cardsnum, K): M = 1000000007 S = sum(cardsnum) if K>S: return 0 T = [1]+[0]*S l = 0 for c in cardsnum: for i in range(c): P = T T = [0]*(S+1) for k in range(S): T[k] = (T[k]+P[k]*(k-i+1))%M T[k+1] = (T[k+1]+P[k]*(l-k+i))%M l += 1 ans = T[K-1] for c in cardsnum: t = reduce(lambda a,b: a*b%M, range(1,c+1)) ans = ans*pow(t,M-2,M)%M return ans
