AtCoder Beginner Contest 103 (ABC103)
ABC103に参加しました。遅刻しなかった上に全完したのでレートが96上がりました。やったぜ。
A - Task Scheduling Problem
6通り全部試してもいいですが、A_i → A_j → A_k とタスクを行う場合、直感的に A_i ≦ A_j ≦ A_k がもっともコストが低そうですね。
なので、A_k = max(A), A_i = min(A), として答えはabs(A_k - A_j)+abs(A_j - A_i) = abs(A_k - A_i) = max(A)-min(A)となります。
B - String Rotation
(問題文で言われたとおりに)やるだけ。
str.substr(index)でstr[index]から末尾までの部分文字列を示します。
また、str.substr(index,length)でstr[index]からstr[index+length-1]までの部分文字列を示します。
最初に、s=s+sとしておくとより簡単な実装になるかも。
C - Modulo Summation
思考過程
aのそれぞれに対して m=(aの倍数-1)のとき嬉しいことは明らか。
つまりm=(全てのaの最小公倍数)-1とするとよい。
このときm%a=a-1となるので、∑(a-1)でよい。
D - Islands War
思考過程
(Aの最大値)<(Bの最小値)なら答え1だねってのは分かる。
じゃあそうじゃないときは1番大きいaを脇によけてans++して、もう1回判定するってのを繰り返すとよくって、
脇によけたやつどうしで、それと同様の操作をする((Aの最大値)<(Bの最小値)なら答え+1,そうじゃないときは1番大きいaを脇によけてans++して、もう1回判定するってのを繰り返す)と良さげ。
わきによけるときはaとセットのbも一緒によけて、Aの最大値、Bの最小値を更新する。
ただ、それすると実装が重い。つか毎回最大値判定にO(m)使うからともするとO(m^2)で通らない。
のでaの昇順にソートする。→たぶん解説と一緒でO(n logn)。
でもこれって、別に脇によけるのは一番大きなaでなくてもよくって、
つまりすべての(a,b)についてa<(Bの最小値) && b>(Aの最大値)なら答え+1,そうじゃないときは(a,b)を脇によけてans++して、もう1回判定するってのを繰り返すをやればよい。
このときソートがいらないのでO(n)。
僕のコードはこのときにソートつけてても通るので提出時間意識してつけっぱ。
