初めて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個ずつ埋めたい。
ただし、縦横連続する3マスが昇順または降順になることが無いようにしたい。
一部のマスはすでに数字が埋まっている。
条件を満たす残りのマスの埋め方は何通りあるか。
25マスのうち埋まっているかどうかをbitmaskで表現し、bitDPで1から順に埋めていくことを考える。
仮に今bマス埋まっているとき、(b+1)の数字をどこに埋めるか考える。
もし(b+1)の数字が初期状態で埋まっている場合、埋める候補はそこ1択となる。
そうでない場合、数字がまだ埋まっていない全マスが埋める交互になる。
その際、上下左右両隣のうち、片方だけ埋まっている場合、そこに数字を埋めてはいけない。
なぜなら、その後逆隣のマスにより大きな数値が来ると3つ数字が昇順に並んでしまうからである。
なお、ここでは配る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とは。