Codeforces Round #307 (Div. 2) 参加記

はい。 ox--- (0/0) 1328(+136) http://codeforces.com/contest/551
B問題の難易度がアレだったので通ったのがA問題だけでもレートがやや上がった。そして参加記を書く前に解き直したらAC出たという悲しみ。

A. GukiZ and Contest

ざっくりと大意

・n人のレーティングのそれぞれの値が上から何番目であるかを出力する？？

方針のようなもの

・レーティングの数列をコピーして調べる。

python

n=int(raw_input())
l=map(int,raw_input().split())
chk=sorted(l)
chk=chk[::-1]
for i in l:
    print chk.index(i)+1,

毎回indexで見るのとか入力の大きさによっては時間がかかるが、今回は大きい入力ではなかったので特に工夫しなくても大丈夫だった。

B. ZgukistringZ

ざっくりと大意

・文字列aを並び替えて文字列b,cを最も多く含んでいるように文字列kを作る？？

方針のようなもの

・a,b,cいずれも各文字の出現個数を個数をメモしてb,cで使う分量をaから引いて最大になる使い方を探す。

python

a=raw_input()
b=raw_input()
c=raw_input()

def cnter(x):
    l=[0]*26
    for i in x:
        l[ord(i)-97]+=1
    return l

def chker(p,q):
    z1=[]
    for i in range(26):
        if q[i]:
            z1.append(p[i]/q[i])
    return min(z1)

def runner(p,q,r):
    for i in range(26):
        p[i]-=q[i]*r
    return p

def rev():
    for i in range(26):
        cnta[i]+=cntb[i]
        

cnta=cnter(a)
cntb=cnter(b)
cntc=cnter(c)
cnta2=cnta[:]
chk=[0]*2

ab=chker(cnta,cntb)
if ab:
    cnta=runner(cnta,cntb,ab)
    chk[0]=ab
ac=chker(cnta,cntc)
if ac:
    cnta=runner(cnta,cntc,ac)
    chk[1]=ac

ans=chk[:]
memo=cnta[:]

while chk[0]:
    chk[0]-=1
    rev()
    ac=chker(cnta,cntc)
    if ac:
        cnta=runner(cnta,cntc,ac)
        chk[1]+=ac
    if sum(chk)>sum(ans):
        ans=chk[:]
        memo=cnta[:]

w=b*ans[0]+c*ans[1]
for i in range(26):
    if memo[i]>0:
        w+=(chr(i+97))*memo[i]

print w

変数名とか色々な処理の書き方もすごい適当なままです。。
最初の解法は毎回1文字ずつゴニョゴニョしててTLEでコンテスト時間中は諦めてしまって終わり。翌日に文字の出現個数でみればいいことに気づいて書きなおすがb,cどちらかを先に最大限使って、余りをもう片方にで行けると思ったけどそんなに簡単ではなくてWA。。もう一日経ってからbを最大限と余りをcに充ててから、bを1つずつ減らしつつcを増やしていくと全探索で最大になるパターンを見つけられることに気づいてやっとAC。
でもまぁこれくらいならコンテスト時間中に出来るべきだったなと思う。