Codeforces Round #276 (Div. 2) - 君はまるで砂漠に咲く、一輪の花。

A. Factory

ざっくりと大意

・最初にaの在庫を持っている工場がxを現在の在庫として、x mod mの数の分だけ生産しようと計画している。
・生産をしていて x mod m が0で生産出来なくなってしまうならYes、停まること無く生産できるならNoを出力。

方針のようなもの

・x mod m の計算を回す。

a,m=map(int,raw_input().split())
p,x=a,2*m

while x:
    x-=1
    a+=a%m
    if p==a:
        print 'Yes'
        exit()
    p=a
print 'No'

初回の時もだけどm*2回せばと思って回して解説で20回で良いと書いてあっても何故なのかよくわからないまま。。

B. Valuable Resources

ざっくりと大意

・ストラテジーゲームでn個の鉱山を含んで都市を座標軸と平行な境界で最小の正方形で作りたい。

方針のようなもの

・マンハッタン距離で最も離れているものを探す。

n=int(raw_input())
x=[1000000000,-1000000000]
y=[1000000000,-1000000000]
while n:
    n-=1
    a,b=map(int,raw_input().split())
    if a>x[1]:
        x[1]=a
    if a<x[0]:
        x[0]=a
    if b>y[1]:
        y[1]=b
    if b<y[0]:
        y[0]=b
print max(abs(x[1]-x[0])**2,abs(y[1]-y[0])**2)

コンテスト当時の方のようなmaxで値を保存のが簡略な気がするような。。縦か横で最も離れている、マンハッタン距離で最も離れている鉱山を見つければそれが全ての鉱山を正方形で囲むために最低限必要な長さである。

C. Bits

ざっくりと大意

・l,rの数が与えられ、l,rの範囲の数で２進数表記にした時にもっとも1が多いものを10進数表記で出力、解が複数ある時は10進数で最小のものを出力。

方針のようなもの

・ l,rが等しい、rの2進数表記がすべて1で埋まる、l,rそれぞれを2進数表記にした時に桁の長さが違う時は楽であるが、桁が同じ長さの時は端から調べる。

n=int(raw_input())
while n:
    n-=1
    l,r=map(int,raw_input().split())
    chk=bin(l)[2:]
    chk2=bin(r)[2:]
    if l==r or '0' not in chk2:
        print r
    elif len(chk)<len(chk2):
        print int('1'*(len(chk2)-1),2)
    else:
        x=len(chk2)
        chk3=list(chk)
        for i in range(-1,-x-1,-1):
            chk3[i]='1'
            p=''.join(chk3)
            if int(str(p),2)>r:
                chk3[i]='0'
                break
        p=''.join(chk3)
        print int(str(p),2)

l,rが等しいか、rの2進数表記が1で埋まるならrを出力。l,rの2進数表記で桁の長さが異なればrを1桁減らして全て1で埋めたものを出力。
e,g, l=4, r=8 -> 2進数表記で \(4{10}\)=\(100_2\) と \(8{10}\)=\(1000_2\) の時に1000から1桁減らして3桁を全て1で埋めた \(7_{10}\)=\(111_2\) が最も多く1を含み最小の数である。
桁の長さが同じであるならばlを小さい方の桁から1に置き換えてrより大きくなったら直前に置き換えた1を0に戻して10進数に変換して出力する。