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;
}};

このように書き換えたら通った。簡単(･∀･)　次のところでハマった。

• 64ビットなので、espではなくrspを使い、C++側の変数も64ビットにする必要がある
• rspは確保した領域の先頭ではなく、末尾を指すようにする必要がある（スタックは上位から下位に使っていくので）

再帰が深くなりすぎる場合、再帰を使わないように書いていたけれど、ここまで簡単にできるならばスタックサイズを増やすのはありかもしれない。

Google Code Jam Round 1B 2014

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;
}};

SRM586

Easy (250)　224.36
Medium (500)　194.50
Hard (1000)　0
Challenge　0
結果　79位　1913→1978

SRM585 Div2 Medium(500) TrafficCongestionDivTwo

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

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

LISNumber

動的計画法。小さい順にn枚のカードを選んだとき、a[i]≧a[i+1]となるiがちょうどk個になる並べ方の数を覚えておく。これは同じ数字のカードを区別した場合の数なので、最後に数字ごとにその数字のカードの枚数の階乗で割る。法Mが素数ならば、1/x = x^M-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