読者です 読者をやめる 読者になる 読者になる

Codeforces Round #277.5 (Div. 2)

はい。 ox----(0/0) 1089(-49)
http://codeforces.com/contest/489
問題文とサンプルは分かりやすかったけどショボいミスしてACはA問題だけでした。

A. SwapSort

ざっくりと大意

・swapでソートしてそのswap手順を出力する。

方針のようなもの

・過去にAOJで使ったのからコピペしよう。

n=int(raw_input())
l=map(int,raw_input().split())
chk=cnt=0
ans=[]
if n==1:
    print 0
    exit()
while 1:
    if l[cnt]>min(l[cnt+1:]):
        p=l[cnt+1:].index(min(l[cnt+1:]))
        l[cnt],l[p+cnt+1]=l[p+cnt+1],l[cnt]
        ans.append((cnt,p+cnt+1))
        chk+=1
    cnt+=1
    if cnt+1>n-1:
        break
print chk
if chk>0:
    for i in ans:
        print i[0],i[1]

コンテスト時間中はpythonだけでAOJの問題の使い回しでもっとぐちゃぐちゃしてたけど復習で書いたら、自力で行数減らして処理時間も短く出来た。比較は左端から交換候補を自身より一つ右以降から右端までにより小さい数がないかを探す。同じ場合はswapする必要なし。一つ右にずれた時に必要であれば交換する。

B. BerSU Ball

ざっくりと大意

・n人の少年とm人の少女がいる。
・\(a_i\)と\(b_i\)の差が1以下ならペア成立、1より大きいと不成立。ペアは何組作れるか。

方針のようなもの

・2重ループで探す。

n=int(raw_input())
a=map(int,raw_input().split())
a.sort()
m=int(raw_input())
b=map(int,raw_input().split())
b.sort()
ans=0
for i in range(n):
    for j in range(m):
        if abs(a[i]-b[j])<=1:
            ans+=1
            m-=1
            b.pop(j)
            break
        elif b[j]>a[i]:
            break
print ans

なんか工夫っぽいことしたつもりで無駄にWAになった。入力は大きくなかったのでコンテスト中は工夫しようとかはするべきではなかった。

C. Given Length and Sum of Digits...

ざっくりと大意

・m桁の数で各桁の総和でsになる0始まりではない最小と最大のものを出力、なければ-1。

方針のようなもの

・100..と999..から探そうとするとTLEになったので後で。