ABC018に参加。
Dで無駄に2WAしてタイムロス。
http://abc018.contest.atcoder.jp/assignments
A - 豆まき
3人の得点が与えられるので、3人の順位を答えよ。
6通り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++なら1方向分累積和を取っておいてO(R*C*K)で満点が取れる。
PythonだとO(R*C*K)では間に合わない。
斜め方向の累積和を事前に取っておくと、菱形の中心を1マスずらしたときの白セル差分が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で変数名を2回も間違えた…。