kmjp's blog

競技プログラミング参加記です

AtCoder ABC #025 : Python練習編

ARC

初めて400pt取れず…。
http://abc025.contest.atcoder.jp/assignments

A - 25個の文字列

5個の文字が与えられる。
ここから2種類を使って作れる文字列のうち、辞書順N番目のものを答えよ。

1文字目に(N-1)/5個目、2文字目に(N-1)%5個目のものを用いればよい。

S=raw_input()
N=input()-1

print S[N/5]+S[N%5]

B - 双子とスイカ割り

東西に無限に続く場所で、以下の通りN回移動する。
毎回東西方向と移動距離dが与えられるのでその分移動する。
ただしd＜Aの時はA、d＞Bの時はBだけ移動する。
最終的な位置を求めよ。

愚直にシミュレートすればよい。

N,A,B=map(int,raw_input().strip().split(" "))
X=0

for i in range(N):
	S,DD=raw_input().strip().split(" ")
	D=min(B,max(int(DD),A))
	
	if S == 'East':
		X += D
	else:
		X -= D

if X==0:
	print 0
elif X > 0:
	print "East %d" % X;
elif X < 0:
	print "West %d" % -X;

C - 双子と○×ゲーム

3*3のマスを使い、交互に○×を置きあうゲームを行い。
通常の○×ゲームを異なり、全マスを埋めるまでゲームが続く。
ゲーム終了時、隣接マスが同じ記号の場合は先手に、異なる記号の場合は後手に、それぞれ位置に応じた得点が入る。
共に最適手を取ったとき、両者の得点はどうなるか。

DFSやnext_permutationで全探索すればよい。
Pythonの場合9!通り総当たりすると間に合わないので、メモ化再帰を併用すると良い。

B=[[0 for i in range(3)] for j in range(3)]
C=[[0 for i in range(3)] for j in range(3)]
T=[0 for i in range(9)]
memo={}



def dodo(turn):
	st=""
	for i in range(9):
		st += chr(ord('0')+T[i])
	if st in memo:
		return memo[st]
	
	p = [-1,-1]
	did = 0
	for y in range(3):
		for x in range(3):
			if T[y*3+x]!=0:
				continue
			
			did = 1
			T[y*3+x] = turn
			res = dodo(3-turn)
			T[y*3+x] = 0
			
			if res[turn-1] > p[turn-1]:
				p=res
	
	if did == 0:
		p = [0,0]
		for y in range(2):
			for x in range(3):
				if T[y*3+x]==T[y*3+x+3]:
					p[0] += B[y][x]
				else:
					p[1] += B[y][x]
		
		for y in range(3):
			for x in range(2):
				if T[y*3+x]==T[y*3+x+1]:
					p[0] += C[y][x]
				else:
					p[1] += C[y][x]
					
	memo[st]=p
	return p


B[0][0],B[0][1],B[0][2]=map(int,raw_input().strip().split(" "))
B[1][0],B[1][1],B[1][2]=map(int,raw_input().strip().split(" "))
C[0][0],C[0][1]=map(int,raw_input().strip().split(" "))
C[1][0],C[1][1]=map(int,raw_input().strip().split(" "))
C[2][0],C[2][1]=map(int,raw_input().strip().split(" "))

p=dodo(1)
print p[0]
print p[1]

D - 25個の整数

5*5のマスに1～25の数字を1個ずつ埋めたい。
ただし、縦横連続する３マスが昇順または降順になることが無いようにしたい。
一部のマスはすでに数字が埋まっている。
条件を満たす残りのマスの埋め方は何通りあるか。

25マスのうち埋まっているかどうかをbitmaskで表現し、bitDPで1から順に埋めていくことを考える。
仮に今bマス埋まっているとき、(b+1)の数字をどこに埋めるか考える。
もし(b+1)の数字が初期状態で埋まっている場合、埋める候補はそこ１択となる。
そうでない場合、数字がまだ埋まっていない全マスが埋める交互になる。

その際、上下左右両隣のうち、片方だけ埋まっている場合、そこに数字を埋めてはいけない。
なぜなら、その後逆隣のマスにより大きな数値が来ると３つ数字が昇順に並んでしまうからである。

なお、ここでは配るDP(bマス埋まった状態から(b+1)マスの状態に組み合わせ数を加算する)と、もらうDP(bマス埋まった状態の組み合わせを求めるのに、(b-1)マスの状態を探索する)の両方が考えられる。

今回のケースでは一部のマスがすでに埋まっているため、あり得ない状態のbitmaskが何通りも生じる。
そのため配るDPにした方がそのような状態の処理をスキップして高速化できる。

今回PythonではTLEで通らなかったのでC++でのみACした。
以下のコードは配るDPで0.3sで通しているが、コメント部のもらうDPだと4.3sかかる。
恐らく全マス未確定ならどちらも4.3sになると推測する。

ll mo=1000000007;
int A[25];
int fix[26];
int dp[1<<25];
vector<int> V;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(fix);
	FOR(i,25) {
		cin>>A[i];
		if(A[i]==0) V.push_back(i);
		else fix[A[i]]=i;
	}
	
	dp[0]=1;
	for(int mask=0;mask<(1<<25)-1;mask++) if(dp[mask]) {
		int b=__builtin_popcount(mask)+1;
		if(fix[b]>=0) {
			r=fix[b];
			y=r/5,x=r%5;
			if((mask&(1<<r))==0) {
				if(y>0 && y<4 && ((mask>>(r-5))^(mask>>(r+5)))&1) continue;
				if(x>0 && x<4 && ((mask>>(r-1))^(mask>>(r+1)))&1) continue;
				dp[mask ^ (1<<r)] += dp[mask];
				if(dp[mask ^ (1<<r)]>=mo) dp[mask ^ (1<<r)]-=mo;
			}
		}
		else {
			FORR(r,V) {
				y=r/5,x=r%5;
				if((mask&(1<<r))==0) {
					if(y>0 && y<4 && ((mask>>(r-5))^(mask>>(r+5)))&1) continue;
					if(x>0 && x<4 && ((mask>>(r-1))^(mask>>(r+1)))&1) continue;
					dp[mask ^ (1<<r)] += dp[mask];
					if(dp[mask ^ (1<<r)]>=mo) dp[mask ^ (1<<r)]-=mo;
				}
			}
		}
	}
	
	/*
	for(int mask=1;mask<1<<25;mask++) {
		int b=__builtin_popcount(mask);
		if(fix[b]>=0) {
			y=fix[b]/5,x=fix[b]%5;
			if((mask&(1<<fix[b])) && dp[mask ^ (1<<fix[b])]) {
				if(y>0 && y<4 && ((mask>>(fix[b]-5))^(mask>>(fix[b]+5)))&1) continue;
				if(x>0 && x<4 && ((mask>>(fix[b]-1))^(mask>>(fix[b]+1)))&1) continue;
				dp[mask] = dp[mask ^ (1<<fix[b])];
			}
		}
		else {
			ll ret=0;
			FORR(r,V) {
				y=r/5,x=r%5;
				if((mask&(1<<r)) && dp[mask ^ (1<<r)]) {
					if(y>0 && y<4 && ((mask>>(r-5))^(mask>>(r+5)))&1) continue;
					if(x>0 && x<4 && ((mask>>(r-1))^(mask>>(r+1)))&1) continue;
					ret += dp[mask ^ (1<<r)];
				}
			}
			dp[mask] = ret%mo;
		}
	}*/
	
	cout<<dp[(1<<25)-1]<<endl;
}

まとめ

Beginnerとは。