Japan Alumni Group Summer Camp 2015 Day 3

Japan Alumni Group Summer Camp 2015 Day 3のバチャをやった。6完57011ペナ

B:

シフトの仕方は以下の4通り

・右シフトのみ

・左シフトのみ

・右シフトした後左シフト

・左シフトした後右シフト

各位置について自分より右にある1の中で一番左にある1の位置を持っておくと良い。

D:

和が10^nより大きくなる場合と、小さくなる場合に分けて考える。

大きくなる時

和が9より大きいペアを1個選ぶ。->和が9となるペアを先頭に置けるだけ置く。->残りを昇順にペアにして後ろに置くことで。最初に決めたペアに対して最小な和が作れる。

小さくなる時

和が9より小さいペアを1個選ぶ。->和が9となるペアを先頭に置けるだけ置く。->残りを降順にペアにして後ろに置くことで。最初に決めたペアに対して最大な和が作れる。

ペアの数は高々100個なので十分全探索できる。

E:

gcd(a,b)でcが割り切れなかったら-1

cがaかbと等しいなら1

a,b,cをgcd(a,b)で割っておく。

aからbに注いでいくことを考える。

操作を(a+b)*2+1回行うと1周し、aもbも空になる。

逆の操作をしても同じ。

拡張ユークリッドの互除法などでどのタイミングでcが登場するか調べる。

F:

角度の制約を考えると、N角形のときに直角にできる角の数kは

k<(2n+4)/3

となる。また、実際に上限が達成できる。

J:

自分の約数kについて、(N-k)/kの約数の数が分かれば良い。