君はまるで砂漠に咲く、一輪の花。

僕はその花に引き寄せられる蝶。

Codeforces Round #277.5 (Div. 2)

はい。
http://codeforces.com/contest/489

A. SwapSort

ざっくりと大意

・n個の数がそれぞれ\(a_0\)から\(a_{n-1}\)まで与えられるので、それをスワップで昇順にソートして最後にスワップした件数とその内容を出力。

方針のようなもの

スワップソートする。

n=int(raw_input())
a=map(int,raw_input().split())
ans=[]
for i in range(n-1):
    s=a[i]
    ad=i
    for j in range(i+1,n):
        if s>a[j]:
            s=a[j]
            ad=j
    if s!=a[i]:
        a[i],a[ad]=a[ad],a[i]
        ans.append((i,ad))
if len(ans):
    print len(ans)
    for x in ans:
        print x[0],x[1]
else:
    print 0

なんかコンテスト当時はバグらせまくってたけど書き直したら割りとあっさり何とかなった。単純に左端から自分より1つ先から右端の中で最小のものと入替えて終了。但し、これだと結構時間がかかっててもっと処理が早い人がいるので後で。

B. BerSU Ball

ざっくりと大意

・とある大学でn人の男とm人の女でダンスのペアを作る。
・ペア成立には男女でダンススキルの差が+-で1以内でなければならない。最大で作成できるペア数はいくつか??

方針のようなもの

・ソートして探せばよさそうっぽい。

n=int(raw_input())
a=map(int,raw_input().split())
m=int(raw_input())
b=map(int,raw_input().split())
ans=chk=0
a.sort()
b.sort()
for i in a:
    for j in b:
        if i-1<=j<=i+1:
            ans+=1
            b.remove(j)
            break
print ans

break忘れてて1WAしたけど修正して割りとあっさり通った。なんでコンテスト当時出来なかったんだ。。。

C. Given Length and Sum of Digits...

ざっくりと大意

・m桁の数でそれぞれの桁の総和がsになるものの最小のものと最大のものを出力。

方針のようなもの

・桁ごとに加算する。

m,s=map(int,raw_input().split())
chk=0
if (m>1 and s<1) or m*9<s:
    print -1,-1
elif m==1 and s==0:
    print 0,0 
else:
    x=[0]*m
    for i in range(m):
        if chk==s:
            break
        for j in range(1,10):
            chk+=1
            x[i]=j
            if chk==s:
                break
    x=''.join(map(str,x))
    y=[0]*(m-1)+[1]
    for i in range(m):
        if sum(y)==s:
            break
        for j in range(1,10):
            y[i]=j
            if sum(y)==s:
                break
    y=''.join(map(str,y[::-1]))
    print y,x

WAしながら無理に修正して通したので後で書き直す。出力する予定の数を1ずつ加算しながら探すのは加算していて繰り上がり時に1桁目が9から0に戻ってしまうのが各桁の総和では減ってしまうので端から桁を加算して9になっても足りなかったら更に隣の桁を加算しに行くと時間が節約できると思う。