Educational Codeforces Round 1
はい。
http://codeforces.com/contest/598
A. Tricky Sum
ざっくりと大意
・1からnまでを2の累乗の数なら減算、そうでなければ加算する??
方針のようなもの
・わからんのでパクろう。
t=int(raw_input()) for i in range(t): n=int(raw_input()) a=(n*(n+1))/2 x=2**0 while x<=n: a-=x*2 x*=2 print a
1からnまでの和を求めた後に2の0乗の1から始めて減算をしていく。一度は正の数を加算で計算してしまっているので2の累乗の数は2倍にして減算する必要がある。2の0乗から始めて2を掛け続けて、2の累乗の数を対象にしてn以下の時に減算を繰り返して解を求める。計算内容自体は凄い単純なのだが気づけなかったというか、考えることを放棄してたというか…
B. Queries on a String
ざっくりと大意
・文字列sとm件のクエリが与えられる。
・各クエリはr文字目をl文字目へ入れ替えするような処理をk回行う。
方針のようなもの
・計算する。
s=raw_input() n=int(raw_input()) for i in range(n): t=s l=map(int,raw_input().split()) tmp=s[l[0]-1:l[1]] x=((l[2]%len(tmp)))*-1 tmp=tmp[x:]+tmp[:x] s=t[:l[0]-1]+tmp+t[l[1]:] print s
各クエリで文字列の変動が発生するのは(繰返し回数によってはクエリ前と同じになることあり)、l文字目からr文字目の間。変動内容は末尾から入れ替え回数文字目から末尾までを前にして、それ以前のを後ろに付け足す。
例えば、文字列'12345'の2文字目から4文字目までを2回入れ替えするなら(クエリではl=2, r=4, k=2)、2文字目から4文字目が'234'。それの入れ替え処理が2回なので末尾から2文字目のと、それ以前のを後ろに付け足して'34'と'2'で'342'が変動内容となる。全文字列では'13425'となる。