AtCoder ABC #032 : Python練習編

ABC032は不参加。今後A,B,Cの記載は簡潔にします。
http://abc032.contest.atcoder.jp/assignments

A - 高橋君と青木君の好きな数

LCM(A,B)の倍数でN以上のものを求める。

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a%b)

A=input()
B=input()
N=input()

X=A*B/gcd(A,B)

print (N+X-1)/X*X

B - 高橋君とパスワード

setでsubstringを管理するだけ。

S=raw_input().strip()
K=input()

SS=set()
for i in range(len(S)):
	if i+K <= len(S):
		SS.add(S[i:(i+K)])

print len(SS)

C - 列

S[i]=0なiがあればNが解。それ以外は尺取法をする。

N,K=map(int,raw_input().strip().split(" "))
S=[]
P0 = 0

for i in range(N):
	S.append(input())
	if S[-1] == 0:
		P0 = 1

if P0==1:
	print N
	
else:
	ma = 0
	P = 1
	y = -1
	for x in range(N):
		while y+1 < N and P*S[y+1] <= K:
			y += 1
			P *= S[y]
		
		ma=max(ma,y-x+1)
		
		if y >= x:
			P /= S[x]
		else:
			y = x
	
	print ma

D - ナップサック問題

N個の荷物があり、各重さはw[i]、価値はv[i]である。
複数の荷物を組み合わせたとき、重さの総和がW以下で実現できる最大の価値はいくらか。

教育的問題らしく、N,v,wの大小が異なる３通りの構成が与えられるので、それぞれ解いていこう。

• Nが小さい場合：半分全列挙。
• wが小さい場合：重さの総和に対する価値の最大値を更新するDP。
• vが小さい場合：価値に対し、それを実現する重さの総和の最小値を更新するDP。

なお、Pythonでは後ろ２つのケースが間に合わなかったのでC++で解いた。

int N,MW;
ll V[2020],W[2020];
ll dp[2000002];

void go1() {
	int i,j,k,x,y,mask;
	vector<pair<ll,ll>> V1,V2;
	
	int a=min(N,15);
	FOR(mask,1<<a) {
		ll tv=0,tw=0;
		FOR(i,a) if(mask&(1<<i)) tv+=V[i], tw+=W[i];
		if(tw<=MW) V1.push_back({tw,tv});
	}
	a=max(0,N-15);
	FOR(mask,1<<a) {
		ll tv=0,tw=0;
		FOR(i,a) if(mask&(1<<i)) tv+=V[i+15], tw+=W[i+15];
		if(tw<=MW) V2.push_back({tw,tv});
	}
	sort(ALL(V1));
	sort(ALL(V2));
	
	FOR(i,V1.size()-1) V1[i+1].second=max(V1[i].second,V1[i+1].second);
	FOR(i,V2.size()-1) V2[i+1].second=max(V2[i].second,V2[i+1].second);
	ll ma=0;
	y=V2.size()-1;
	FOR(x,V1.size()) {
		while(y>=0 && V1[x].first+V2[y].first>MW) y--;
		ma=max(ma,V1[x].second+V2[y].second);
	}
	cout<<ma<<endl;
}
void go2() {
	int i,x;
	FOR(i,N) {
		for(x=200001-W[i];x>=0;x--) {
			dp[x+W[i]]=max(dp[x+W[i]],dp[x]+V[i]);
		}
	}
	cout<<*max_element(dp,dp+MW+1)<<endl;
}

void go3() {
	int i,x;
	memset(dp,0x3f,sizeof(dp));
	dp[0]=0;
	FOR(i,N) {
		for(x=200001-V[i];x>=0;x--) if(dp[x]<=MW) {
			dp[x+V[i]]=min(dp[x+V[i]],dp[x]+W[i]);
		}
	}
	
	for(i=200000;i>=0;i--) if(dp[i]<=MW) return _P("%lld\n",i);
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	ll mv=0,mw=0;
	
	cin>>N>>MW;
	FOR(i,N) cin>>V[i]>>W[i], mw=max(mw,W[i]),mv=max(mv,V[i]);
	
	if(N<=30) go1();
	else if(mw<=1000) go2();
	else if(mv<=1000) go3();
}

まとめ

出てたら25分+1WAで４位？