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になったので後で。