AtCoder ABC #014 : Python練習編

Dでちょっと手間取ったけどまぁまぁの順位。
でもDはPythonはTLEした。
http://abc014.contest.atcoder.jp/assignments

A - けんしょう先生のお菓子配り

a個のお菓子をb人で分ける。
a個で公平に分けられない場合、お菓子をいくつか増やして公平に分けたい。
最小何個分ける必要があるか。

以下は１個ずつ足しながら判定。

import sys

i=a=input()
b=input()

while a%b>0:
	a+=1

print a-i

B - 価格の合計

N個の商品とその価格A[i]が与えられる。
ここで買う商品群Xがbitmaskの形で与えられるので、合計価格を求めよ。
bitwise-andを取りつつ計算。

import sys

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

for i in range(0,N):
	if (X & (1<<i)) > 0:
		ret+=A[i]

print ret

C - AtColor

N個の絵の具があり、それぞれの絵の具の濃度がA[i]～B[i]の範囲であれば、その絵の具は買われる。
買われる絵の具の数が最大となる単一の濃度において、その時の絵の具数を求めよ。

S[i]を濃度iの絵の具が買われる数とする。
A[i]～B[i]の範囲の絵の具が変われるなら、D[A[i]]をインクリメント、D[B[i]+1]をデクリメントする。
あとはimos法の要領でS[i]=S[i-1]+D[i]で計算し、S[i]の最大値を出力すればよい。

import sys

N = input()
D = [0]*1000005

for i in range(0,N):
	x,y=map(int,raw_input().strip().split())
	D[x] += 1
	D[y+1] -= 1

ma = cd = 0
for i in range(0,1000002):
	cd += D[i]
	ma = max(ma, cd)

print ma

D - 閉路

N頂点からなる、木構造を成すグラフが与えられる。
ここでQ個のクエリが与えられる。
クエリは２頂点A[i]、B[i]からなり、A[i]とB[i]の間に辺を追加したときに出来る閉路の長さを答えよ。

元の木でA[i]とB[i]の距離を求められれば、1を足したものが答えになる。
木における２点の距離は蟻本にもあるとおりLowest Common Ancestorで求めればよい。
ダブリングでO(N*logN)、クエリでO(Q*logN)かな。

Pythonでは間に合わないのでC++を使った。

int N,Q;
vector<int> E[1000005];
int P[20][100005],D[100005];

void dfs(int cur) {
	ITR(it,E[cur]) if(*it!=P[0][cur]) D[*it]=D[cur]+1, P[0][*it]=cur, dfs(*it);
}

int dist(int aa,int bb) {
	int ret=0,i;
	if(D[aa]>D[bb]) swap(aa,bb);
	for(i=19;i>=0;i--) if(D[bb]-D[aa]>=1<<i) ret+=1<<i,bb=P[i][bb];
	for(i=19;i>=0;i--) if(P[i][aa]!=P[i][bb]) ret+=2<<i, aa=P[i][aa], bb=P[i][bb];
	return ret+2*(aa!=bb);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	P[0][0]=0;
	dfs(0);
	FOR(i,19) FOR(x,N) P[i+1][x]=P[i][P[i][x]];
	
	cin>>Q;
	while(Q--) {
		cin>>x>>y;
		cout << dist(x-1,y-1)+1 << endl;
	}
}

まとめ

最近Pythonで間に合わない問題が多いな…。