Codeforces Round #396 (Div.2)
はい。
http://codeforces.com/contest/766
A. Mahmoud and Longest Uncommon Subsequence
ざっくりと大意
・2つの文字列a,bで共通しない最長の文字列の長さ??問題文がよくわからず。
Python3
a=input() b=input() print(max(len(a),len(b)) if a!=b else -1)
わからないけども書くことは短い。
B. Mahmoud and a Triangle
ざっくりと大意
・n本の辺のうち3つを使って非縮退の、正の面積を有する三角形を作れるか?
Python3
n=int(input()) a=[int(i) for i in input().split()] a.sort() for i in range(n-2): for j in range(i+1,n-1): for k in range(j+1,n): if a[i]+a[j]<a[k]: break elif a[i]+a[j]>a[k] and a[i]+a[k]>a[j]: print('YES') exit() print('NO')
三角形の成立がa+b>c, a+c>b, c+b>aの3つが成立するか、らしい。ソート済ならばa[i]+a[j]<a[k]のときにはより小さいa[k]が現れることはないのでbreakで抜ける。ぎりぎりTLEではないがコンテスト当時と違う解法でしかも今回のが効率悪かった。
というか後から気づいたけどa[i]+a[k]>a[j]は常に成立するし、a[k]は順次大きくなっていくのでいらないし何もかも酷いのでやり直し。。
Python3
n=int(input()) a=[int(i) for i in input().split()] a.sort() for i in range(n-2): if a[i]+a[i+1]>a[i+2]: print('YES') exit() print('NO')
これでなんとかそれなりの回答。実はn>=45の場合には数が大きくなりすぎて109の制限に収まらないらしい。それなのでn>=45なら即時YES、未満なら調べる、というのも可能らしい。すごい。。