Hatena::ブログ(Diary)

赤コーダーになりたい

2014-05-10

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は確保した領域の先頭ではなく、末尾を指すようにする必要がある(スタックは上位から下位に使っていくので)

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

2014-05-03

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<Aかつb<Bかつ(a&b)<Kを満たす(a,b)は何個あるか。

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))

2014-03-29

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

2013-08-01

SRM586

Easy (250) 224.36

Medium (500) 194.50

Hard (1000) 0

Challenge 0

結果 79位 1913→1978

2013-07-19

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 = 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

SRM585 Div1 Easy(250) TrafficCongestion

TrafficCongestion

A001045

class TrafficCongestion:
    def theMinCars(self, treeHeight):
        T = [1,1]
        while len(T)<=treeHeight:
            T += [(T[-1]+2*T[-2])%1000000007]
        return T[treeHeight]

SRM585

Easy (250) 219.37

Medium (500) 0

Hard (1000) 0

Challenge 0

結果 227位 1911→1913

SRM584

Easy (250) 236.65

Medium (600) 0

Hard (900) 0

Challenge 0

結果 113位 1867→1911

SRM583

Easy (250) 198.76

Medium (500) 0

Hard (950) 0

Challenge 0

結果 412位 1934→1867

2013-06-14

SRM582 Div2 Easy(250) SemiPerfectSquare

SemiPerfectSquare

#include <string>
using namespace std;

class SemiPerfectSquare{public:
string check( int N )
{
    for ( int a=1; a<=N; a++ )
        for ( int b=a+1; b<=N; b++ )
            if ( a*b*b==N )
                return "Yes";
    return "No";
}};

SRM582 Div1 Easy(250) SpaceWarDiv1

SpaceWarDiv1

疲労度で二分探索。最大の疲労度が与えられたとき、魔法少女が敵を倒せるかどうかは、弱い魔法少女をなるべく弱い敵に貪欲に割り当てて行けば分かる。

#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

bool check( vector<int> girl, vector<int> enemy, vector<long long> count, long long f )
{
    for ( int i=0; i<(int)girl.size(); i++ )
    {
        long long t = f;
        for ( int j=0; j<(int)enemy.size(); j++ )
        if ( girl[i]>=enemy[j] )
        {
            long long n = min(t,count[j]);
            t -= n;
            count[j] -= n;
        }
    }

    for ( int i=0; i<(int)enemy.size(); i++ )
        if ( count[i]>0 )
            return false;
    return true;    
}

class SpaceWarDiv1{public:
long long minimalFatigue( vector <int> magicalGirlStrength, vector <int> enemyStrength, vector<long long> enemyCount )
{
    sort( magicalGirlStrength.begin(), magicalGirlStrength.end() );
    vector<pair<int,long long> > T;
    for ( int i=0; i<(int)enemyStrength.size(); i++ )
        T.push_back(make_pair(enemyStrength[i],enemyCount[i]));
    sort(T.begin(),T.end());
    for ( int i=0; i<(int)enemyStrength.size(); i++ )
        enemyStrength[i] = T[i].first,
        enemyCount[i] = T[i].second;

    if ( !check(magicalGirlStrength,enemyStrength,enemyCount,1LL<<62) )
        return -1;

    long long ans = (1LL<<62)-1;
    for ( long long b=1LL<<61; b>0; b>>=1 )
        if ( check(magicalGirlStrength,enemyStrength,enemyCount,ans-b) )
            ans -= b;
    return ans<(1LL<<62)-1 ? ans : -1;
}};

SRM582

Easy (250) 210.74

Medium (600) 0

Hard (1000) 0

Challenge 0

結果 114位 1885→1933

2013-05-25

SRM580 Div1 Easy(250) EelAndRabbit

EelAndRabbit

それぞれの鰻の頭の位置を試せば充分。

#include <vector>
using namespace std;

class EelAndRabbit{public:
int getmax( vector <int> l, vector <int> t )
{
    int n = (int)l.size();
    int ans = 0;
    for ( int i=0; i<n; i++ )
    for ( int j=0; j<n; j++ )
    {
        int c = 0;
        for ( int k=0; k<n; k++ )
            if ( t[k]<=t[i] && t[i]<=t[k]+l[k] ||
                 t[k]<=t[j] && t[j]<=t[k]+l[k] )
                c++;
        ans = max( ans, c );
    }
    return ans;
}};

SRM580

Easy (250) 188.92

Medium (600) 0

Hard (1000) 0

Challenge 0

結果 425位 1942→1885

orz orz orz