Codeforces Round #276 (Div. 2)

はい。 -o---(0/0) 1138(0)
http://codeforces.com/contest/485
ものすごくサーバが不調でテンポラリ時間が長かったりしてunratedになりました。もしレート有りだったら激落ちか、何も提出せず回避してたと思うのでアリナシはどっちでも良かった。

A. Factory

ざっくりと大意

・とある工場の生産計画を変更することを管理者が提案している。
・もし一日の始めに在庫がxあったら、x mod mだけ生産する？？？
・残念ながら製品を買う顧客は居ないので生産品は工場に貯まり続ける？？ ・取締役会では割り切れる日から生産が行われなくなることを心配している？？

方針のようなもの

・a%xで在庫を加算していって割り切れて生産が止まってしまう日が出てくるか探す。

a,m=map(int,raw_input().split())
#for i in range(m*2):
for i in range(21):
    a+=a%m
print 'No' if a%m else 'Yes'

初回の自分の提出ではmの2倍の日数をチェックすればいいんじゃね？古い問題でノミが座布団に止まる問題で割り切れるかどうかみたいな問題が円を2周分見てた気がするから2倍でいいんじゃね？？と思ったけどeditional読んだら20日分で良かったらしい。古い問題のノミの方も、今回の20日分のも数学上の証明や根拠は知らないです。

B. Valuable Resources

ざっくりと大意

・2個以上の複数のx,y座標が与えられるので、全ての座標を囲みかつ辺がx,y軸に水平垂直である最小の正方形の1辺の長さはいくつか？？

方針のようなもの

・x,yで最も離れている長さを探す。

n=int(raw_input())
xa=ya=-(10**9)
xi=yi=(10**9)
while n:
    n-=1
    x,y=map(int,raw_input().split())
    xa=max(xa,x)
    ya=max(ya,y)
    xi=min(xi,x)
    yi=min(yi,y)
print max(abs(xa-xi),abs(ya-yi))**2

正方形の辺や角の位置の座標は気にしないので、x,yでどちらかの最も離れている座標の長さを正方形の辺の長さにすれば全ての座標がその正方形の(辺の上を含む)中に入ることになる。

C. Bits

ざっくりと大意

・l<=x<=rの間の数をbit化して最も1を多く含む数は幾つか？？同じ個数のものが複数ある時はその内で最小のものはいくつか？？

方針のようなもの

・なんの工夫もなしに探したらTLEしたので後で考える。

#test 3でTLE
n=int(raw_input())
while n:
    n-=1
    l,r=map(int,raw_input().split())
    ans=chk=0
    while l<=r:
        a=bin(r)[2:]
        if a.count('1')>=chk:
            ans=r
            chk=a.count('1')
        elif len(a)<=chk:
            break
        r-=1
    print ans