Croc Champ 2012 - Final
はい。
http://codeforces.com/contest/183
A. Headquarters
ざっくりと大意
・アウトローの車はGPSでn回の移動が検知されている
・だが記録は曖昧なので例えば'UL'と記録がるときはUかLのどちらかに移動
方針のようなもの
・全部シミュレートしたらもちろん時間は全然足りなかった\(^o^)/
#test 6でTLE n=int(raw_input()) l=[] for i in range(n): l.append(raw_input()) ima=[(0,0)] for i in range(-1,-n-1,-1): memo=set() for j in ima: if l[i]=='UL': memo.add((j[0]+1,j[1])) memo.add((j[0],j[1]-1)) elif l[i]=='UR': memo.add((j[0]-1,j[1])) memo.add((j[0],j[1]-1)) elif l[i]=='DL': memo.add((j[0]+1,j[1])) memo.add((j[0],j[1]+1)) elif l[i]=='DR': memo.add((j[0]-1,j[1])) memo.add((j[0],j[1]+1)) else: memo.add((j[0]-1,j[1])) memo.add((j[0]+1,j[1])) memo.add((j[0],j[1]-1)) memo.add((j[0],j[1]+1)) ima=memo ima=list(ima) print len(ima)
Finalの回だからテストケース厳しいけど通常の回の最易問とかだったらシミュっても間に合う程度じゃないかなぁと思う。とりあえず全部調べるのを書くのが大事らしいのでコレはコレで良いでしょう
ほかの人のblogとかググったら http://spinda2.blog48.fc2.com/blog-entry-521.html に行き着いたのでココの回答に合わせて書いてAC
n=int(raw_input()) a=c=1 for i in range(n): w=raw_input() if w=='UL' or w=='DR': a+=1 elif w=='UR' or w=='DL': c+=1 else: a+=1 c+=1 print a*c