VK Cup 2012 Qualification Round 2
はい。
http://codeforces.com/contest/159
A. Friends or Not
ざっくりと大意
・なんかSNSでメッセージやりとり??
・A→BとB←Aのt2-t1がd以下ならOK??
方針のようなもの
・Aさん、Bさんはリストの[0]と[1]で一致を探して、tはテキトーに引き算して絶対値見ればいいかな?
n,d=map(int,raw_input().split()) l,ans=[],set() chk=0 for i in range(n): w=raw_input().split() l.append(w) for i in range(n): for j in range(i+1,n): if l[i][0]==l[j][1] and l[i][1]==l[j][0]: if d>=abs(int(l[j][2])-int(l[i][2]))>0: p=[l[i][0],l[i][1]] p.sort() p2=(p[0],p[1]) ans.add(p2) break ans=list(ans) print len(ans) for i in range(len(ans)): print ans[i][0],ans[i][1]
2,3回ほど微調整して提出しなおした。同じペアが1往復以上のやりとりがあったりとか、tが0とかの罠があった模様。
あとAC出してから記事を起こすまで気づかなかったけどやりとり成功したら探索は即中止で問題なかった。むしろ時間短縮のためには中止するべきだった。
まぁでも最大ケースの最後尾のラス2,1で成立する時に間に合ってなかったら他のケースで時間短縮しててもあんま意味無いですけどね。ただまあ時間を意識するしないは色々と後で影響するので気にする癖をつけましょう。