Cまでは良かった。
http://arc045.contest.atcoder.jp/tasks/arc045_a
http://arc045.contest.atcoder.jp/tasks/arc045_b
A - スペース高橋君
Left,Right,AtCoderの3つの文字列がスペース区切りで与えられるので、'<','>','A'に置換せよ。
色んなやり方があるが、自分はcinで文字列を1個読み込んで対応する文字列を出力した。
void solve() { int i,j,k,l,r,x,y; string s; int first=0; while(cin>>s) { if(first++) _P(" "); if(s=="Left") _P("<"); if(s=="Right") _P(">"); if(s=="AtCoder") _P("A"); } _P("\n"); }
B - ドキドキデート大作戦高橋君
N個の教室があり、M人で掃除を行う。
i番目の人の担当箇所は、S[i]~T[i]番の連続した教室である。
1人が掃除を行わなくても全部屋最低1人が掃除を行ってくれるような担当の番号を列挙せよ。
まずimos法の要領で各部屋を何人が掃除対象としているかを求める。
2人以上が掃除対象としている部屋は、1人が掃除を行わなくても誰かが掃除をしてくれる。
各担当について、担当範囲の部屋が上記条件を満たしているなら、その担当は掃除を行わなくても良い。
これはSegTreeで解いても良いし、各部屋「2人以上が掃除対象としている」なら1、そうでないなら0として、その累積和を求めておくと、ある区間内がすべて条件を満たしているかO(1)で求められるのでそれで求めても良い。
int N,M; int S[303030],T[303030]; int ok[303030]; int ok2[303030]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; FOR(i,M) { cin>>S[i]>>T[i]; ok[S[i]]++; ok[T[i]+1]--; } for(i=1;i<=N;i++) { ok[i]+=ok[i-1]; ok2[i]=ok2[i-1]+(ok[i]>1); } vector<int> R; FOR(i,M) { if(ok2[T[i]]-ok2[S[i]-1]==T[i]-(S[i]-1)) R.push_back(i+1); } _P("%d\n",R.size()); FORR(r,R) _P("%d\n",r); }
まとめ
Bがいつもより若干複雑か。