Div1 Easy EncloseArea
斜めに線を引いて、指定された面積の多角形を作る問題。
最小の正方形の面積は2で、その一辺を削って、隣に膨らませれば面積は+2される。
なので、まず50*50の方眼紙の対角線上に斜めに長い長方形を作り、それを一つずつ膨らませる実装をした。一々、辺を増やして減らして……としているためかなり汚い実装になってしまった。
そして、一番最初、面積2から始めてそこから求める面積まで増やしていく……というように書いてしまったため、面積2のときそのまま出力するのを忘れてしまってシステムテスト落ち。
・最小値・最大値で通るかチェック
はきちんとしなくてはいけませんね。
kmjpさんのブログの記事のように頂点に着目すればもっと簡単に実装できます。
コンテスト中のコードを修正したものなので非常に読みにくいのですが、一応ACしたコードを載せておきます(載せるか迷ったのですが、ACした証拠として)。
コンテスト中のコードを修正したものなので非常に読みにくいのですが、一応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
両端赤、両端緑、両端が異なる、のそれぞれのひもの個数をr, g, bとおき、実際に本数を求めてみよう、と式を書いてみたら、自然と再帰的に書け(多分、C++なら再帰のままでもACできる?)、それを整理したらさらに簡単な式になった。
・とりあえず立式
さえしていればそれほど難しくなかった気がする。
コンテスト本番では、Easyに時間を取られてしまったので解けなかったけど、ACしたい問題でしたね~。
以下、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
0 件のコメント:
コメントを投稿