TopCoder Single Round Match 776

　今年はじめてEasyがACできた！　と思ったらシステムテストで落ちて0完。単純なミスだったのでもったいない。

Div1 Easy EncloseArea

　斜めに線を引いて、指定された面積の多角形を作る問題。

　最小の正方形の面積は2で、その一辺を削って、隣に膨らませれば面積は+2される。

　なので、まず50*50の方眼紙の対角線上に斜めに長い長方形を作り、それを一つずつ膨らませる実装をした。一々、辺を増やして減らして……としているためかなり汚い実装になってしまった。

　そして、一番最初、面積2から始めてそこから求める面積まで増やしていく……というように書いてしまったため、面積2のときそのまま出力するのを忘れてしまってシステムテスト落ち。

・最小値・最大値で通るかチェック

　はきちんとしなくてはいけませんね。

　kmjpさんのブログの記事のように頂点に着目すればもっと簡単に実装できます。

　コンテスト中のコードを修正したものなので非常に読みにくいのですが、一応ACしたコードを載せておきます（載せるか迷ったのですが、ACした証拠として）。

class EncloseArea():
    def enclose(self, A):
        if A%2!=0:
            return tuple()
        if A>2402:
            return tuple()

        ANS=[["."]*50 for i in range(50)]

        ANS[0][0]="/"
        ANS[0][1]="\\"
        ANS[1][0]="\\"
        ANS[1][1]="/"
        S=2

        for i in range(1,49):
            if S==A:
                break
            
            ANS[i][i]="."
            ANS[i+1][i+1]="/"
            ANS[i][i+1]=ANS[i+1][i]="\\"
            S+=2

        if S==A:
            A=[]

            for ans in ANS:
                A.append("".join(ans))

            return tuple(A)

        NOWP=[0,1]
        NOWM=[1,0]

        def rewrite1(x,y):
            if ANS[x-1][y]==".":
                ANS[x-1][y]="/"
            else:
                ANS[x-1][y]="."

            ANS[x][y]="."
            ANS[x-1][y+1]="\\"
            ANS[x][y+1]="/"

        def rewrite2(x,y):
            if ANS[x][y-1]==".":
                ANS[x][y-1]="/"
            else:
                ANS[x][y-1]="."

            ANS[x][y]="."
            ANS[x+1][y-1]="\\"
            ANS[x+1][y]="/"
            
        while True:
            x,y=NOWP
            if 0<=x-1<50 and 0<=y+1<50:
                rewrite1(x,y)
                S+=2
            NOWP[0]+=1
            NOWP[1]+=1

            if NOWP[0]==49 or NOWP[1]==49:
                MIN=min(NOWP)
                NOWP[0]-=MIN
                NOWP[1]-=MIN
                NOWP[1]+=2

            if S==A:
                break
                

            x,y=NOWM
            if 0<=x+1<50 and 0<=y-1<50:
                rewrite2(x,y)
                S+=2
            NOWM[0]+=1
            NOWM[1]+=1

            if NOWM[0]==49 or NOWM[1]==49:
                MIN=min(NOWM)
                NOWM[0]-=MIN
                NOWM[1]-=MIN
                NOWM[0]+=2

            if S==A:
                break

        if S==A:
            A=[]

            for ans in ANS:
                A.append("".join(ans))

            return tuple(A)

Div1 Medium StringRings

　kmjpさんのブログの記事を参考にして通した。

　両端赤、両端緑、両端が異なる、のそれぞれのひもの個数をr, g, bとおき、実際に本数を求めてみよう、と式を書いてみたら、自然と再帰的に書け（多分、C++なら再帰のままでもACできる？）、それを整理したらさらに簡単な式になった。

・とりあえず立式

　さえしていればそれほど難しくなかった気がする。

　コンテスト本番では、Easyに時間を取られてしまったので解けなかったけど、ACしたい問題でしたね～。

　以下、ACしたコード。

class StringRings():
    def expectedRings(self, A, B):
        ANS=0
        for i in range(A):
            ANS+=1.0/(2*i+1)

        for i in range(B):
            ANS+=1.0/(A*2+i+1)

        return ANS