CF270に参加。
ABCDだけさっさと解いて、後はHack…を狙ったがろくに稼げず。
とはいえABCD早解きのおかげでレートはHighest更新した。
http://codeforces.com/contest/472/problem/C
問題
N人の姓名および1~NのPermutationが与えられる。
N人をPermutationの順に並べ替えたとき、N人それぞれを苗字または名前のいずれかで呼んだら、それが昇順になるような可能性はあるかどうか答えよ。
解法
1人目を姓名のうち辞書順で小さい方からスタートする。
あとは(i-1)番目の人の呼び方が確定したら、かつi番目の人を姓と名のうち(i-1)番の呼び方より辞書順で後であり、かつ小さい方を選択していけばよい。
姓名どちらを選択しても(i-1)番目の呼び方より小さいなら、問題の条件を満たす可能性は無し。
int N; string F[100010],S[100010]; int P[100010]; string cur; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) { cin>>F[i]>>S[i]; if(F[i]>S[i]) swap(F[i],S[i]); } FOR(i,N) { cin>>x; x--; if(F[x]>cur) cur=F[x]; else if(S[x]>cur) cur=S[x]; else return _P("NO\n"); } return _P("YES\n"); }
まとめ
ここらへんはあっさり。