VK Cup 2012 Round 1
はい。
http://codeforces.com/contest/161
A. Dress'em in Vests!
ざっくりと大意
・二次元と三次元の国王が争っていた
・二次元国にはn人の兵士がいてa1からanのサイズの防弾衣を希望した
・サイズの違いはa-xからa+yまでは許容される
・最もより多くの兵士に防弾衣を配ろう
・マッチ件数\n兵士の番目 防弾衣の番目を出力かな
方針のようなもの
・兵士の方で複数の防弾衣が選べるのと、防弾衣が複数の兵士の希望に合うのと両方を見なくても大丈夫かな??
・とりあえず小さい方からだけ見よう
#!/usr/bin/env python # -*- coding: UTF-8 -*- n,m,x,y=map(int,raw_input().split()) a=map(int,raw_input().split()) b=map(int,raw_input().split()) chk=0 ans=[] for i in range(n): if chk==m: break if b[-1]<a[i]-x: break if b[chk]>a[-1]+y: break for j in range(chk,m): if b[j]>=a[i]-x and b[j]<=a[i]+y: chk=j+1 ans.append([i+1,j+1]) break elif b[j]>a[i]+y: chk=j break print len(ans) for i in range(len(ans)): print ans[i][0],ans[i][1]
test 10でTLEになるのをどうしても解決できず。小さい方から見れば一応は最も多く防弾衣が使えるようにはなるっぽい。思いつく限りbreakなど噛ませて少しでも早く全部チェックさせようとしてるけど解決できず。。後日持ち越し。