kmjp's blog

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

AtCoder ABC #018 : Python練習編

ARC

ABC018に参加。
Dで無駄に2WAしてタイムロス。
http://abc018.contest.atcoder.jp/assignments

A - 豆まき

３人の得点が与えられるので、３人の順位を答えよ。

６通りif文列挙で十分。

import sys
import math

A=input()
B=input()
C=input()

if C<A and C<B and B<A:
	print "1\n2\n3"
if C<A and C<B and B>A:
	print "2\n1\n3"
if A<B and A<C and B<C:
	print "3\n2\n1"
if A<B and A<C and B>C:
	print "3\n1\n2"
if B<A and B<C and A<C:
	print "2\n3\n1"
if B<A and B<C and A>C:
	print "1\n3\n2"

B - 文字列の反転

文字列Sが与えられる。
この文字列に対しN個のクエリが与えられる。
各クエリはl,rで与えられるので、Sの部分文字列S[l,r]を反転させる。
最終的なSを答えよ。

題意の通り実装するだけ。
Pythonだと部分文字列や反転も扱いやすいね。

import sys
import math

S=raw_input()
N=input()

while N>0:
	N-=1
	x,y=map(int,raw_input().strip().split(" "))
	s1=S[0:x-1]
	s2=S[x-1:y]
	s3=S[y:]
	S=s1+s2[::-1]+s3

print S

C - 菱型カウント

R*Cのサイズの二次元グリッドがあり、各セルは白か黒に塗られている。
一辺Kの菱形に塗られている白セル群は何個あるか。

菱形の中心を総当たりし、そのつど菱形判定を行うとO(R*C*K^2)で部分点どまり。
C++なら１方向分累積和を取っておいてO(R*C*K)で満点が取れる。
PythonだとO(R*C*K)では間に合わない。

斜め方向の累積和を事前に取っておくと、菱形の中心を１マスずらしたときの白セル差分がO(1)で求められるので、O(R*C)で解くことができる。
また、黒点からマンハッタン距離K未満の点は中心として不可、と見なしてBFSで求める手もある。

import sys
import math

R,C,K=map(int,raw_input().strip().split(" "))
S=[]
sum=[[0 for i in range(505)] for j in range(505)]
RR=[[0 for i in range(505)] for j in range(505)]
LL=[[0 for i in range(505)] for j in range(505)]

def getL(y,x,s):
	return LL[y+1+(s-1)][x+1-(s-1)]-LL[y+1-1][x+1+1]

def getR(y,x,s):
	return RR[y+1+(s-1)][x+1+(s-1)]-RR[y+1-1][x+1-1]
	

for y in range(R):
	S.append(raw_input().strip())
	for x in range(C):
		sum[y+1][x+1]=sum[y+1][x]+(S[y][x]=='o')
		RR[y+1][x+1]=RR[y][x+1-1]+(S[y][x]=='o')
		LL[y+1][x+1]=LL[y][x+1+1]+(S[y][x]=='o')

ret=0
ss=1+4*(K-1)*K/2

for y in range(R):
	if y < K-1 or y+K-1 >= R:
		continue
	
	st = 0
	for x in range(K-1,C-(K-1)):
		if x == K-1:
			for i in range(-(K-1),K):
				st += sum[y+i+1][x+(K-1-abs(i))+1]-sum[y+i+1][x-(K-1-abs(i))]
		else:
			st += getR(y-(K-1),x,K-1)
			st += getL(y,x+(K-1),K)
			
		if st==ss:
			ret += 1
		st -= getL(y-(K-1),x,K-1)
		st -= getR(y,x-(K-1),K)

print ret

D - バレンタインデー

N人の女性とM人の男性がおり、うちP人の女性とQ人の男性でグループを作る。
各女性と男性がグループになったときのグループの幸福度が与えられる。
最適なグループを作ったとき、グループの幸福度の総和の最大値を答えよ。

N,Mは小さいので、女性の選び方を2^N総当たりし、うちP人選ぶ場合について幸福度を求める。
選んだP人が各男性に与える幸福度を求め、男性を幸福度降順にソートして上位Q人を取ればよい。
O(2^N*N*M)程度かかるのでPythonではちょっと工夫しないと間に合わない。
以下では最初の9人と残り(N-9)人の幸福度の和を前処理で求めている。
C++ならそんな小細工は不要。

import sys
import math

N,M,P,Q,R = map(int,raw_input().strip().split(" "))
mat=[[0 for i in range(25)] for j in range(25)]

for i in range(R):
	x,y,z = map(int,raw_input().strip().split(" "))
	mat[x-1][y-1]=z

bits=[0]*512
low=[[0 for i in range(512)] for j in range(18)]
hi=[[0 for i in range(512)] for j in range(18)]

for mask in range(1<<min(N,9)):
	for i in range(min(N,9)):
		if mask & (1<<i):
			bits[mask]+=1
			for j in range(M):
				low[j][mask] += mat[i][j]

if N>9:
	for mask in range(1<<(N-9)):
		for i in range(N-9):
			if mask & (1<<i):
				for j in range(M):
					hi[j][mask] += mat[i+9][j]

ma = 0

for mask in range(1<<N):
	if bits[mask&511] + bits[mask>>9] != P:
		continue
	
	V=[]
	for i in range(M):
		V.append(low[i][mask&511] + hi[i][mask>>9])
	
	V.sort()
	ma=max(ma,sum(V[M-Q:]))

print ma

int N,M,P,Q,R;
int X[500],Y[500],Z[500];
int mat[20][20];
ll ma;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>P>>Q>>R;
	FOR(i,R) {
		cin>>X[i]>>Y[i]>>Z[i];
		mat[X[i]-1][Y[i]-1]=Z[i];
	}
	
	int mask;
	FOR(mask,1<<N) {
		if(__builtin_popcount(mask)!=P) continue;
		vector<int> V;
		
		FOR(i,M) {
			int t=0;
			FOR(j,N) if(mask&(1<<j)) t+=mat[j][i];
			V.push_back(t);
		}
		ll tot=0;
		sort(V.begin(),V.end());
		reverse(V.begin(),V.end());
		FOR(i,Q) tot+=V[i];
		ma=max(ma,tot);
		
	}
	cout<<ma<<endl;
}

まとめ

Dで変数名を２回も間違えた…。