読者です 読者をやめる 読者になる 読者になる

AtCoder Beginner Contest #014

はい。ooox
A,B,C問題まで出来て1時間くらい残ってたがD問題はさすがにちょっと無理だった。
http://abc014.contest.atcoder.jp/

A - けんしょう先生のお菓子配り

方針のようなもの

・a個のお菓子とb人が同数なら追加必要なし、a>bなら1つ以上は配っているのでb人からa%bで端数の数を引けば追加の数になる。a<bなら単にb人からa個を引けば追加の数になる。

a=input()
b=input()
if a-b==0:
    print 0
elif a>b:
    print b-(a%b)
else:
    print b-a

B - 価格の合計

方針のようなもの

・Xをbin()でbitにして\(a_i\)の数列と突き合わせる。

n,X=map(int,raw_input().split())
l=[int(x) for x in raw_input().split()]
bx=str(bin(X))[2::]
bx='0'*(n-len(bx))+bx
bx=bx[::-1]
ans=0
for i in range(n):
    if bx[i]=='1':
        ans+=l[i]
print ans

C - AtColor

方針のようなもの

・いもす法というらしい http://imoz.jp/algorithms/imos_method.html
・素直に工夫せずに入力された数を0-1000000の数列に対して処理しようとすると、ある人が0-1000000が購入可であった時に0-1000000の端から端まで1を加算しているとそれだけでTLEになる。
・始点に+1と、終点の1つ先に-1という情報を置いておけば対象の区間全てに1を加算とかはしなくても大丈夫

n=int(raw_input())
l=[0 for i in xrange(1000002)]
for i in xrange(n):
    a,b=map(int,raw_input().split())
    l[a]+=1
    l[b+1]-=1
ans=chk=0
for i in l:
    chk+=i
    ans=max(ans,chk)
print ans

D - 閉路

方針のようなもの

・最小共通祖先(Lowest Common Ancestor)でa,b間の閉路になる前の最短経路を探して+1すれば閉路の辺の数というお話はわかったのですが実装方法がややこしい。
・そしてpython2は通してる人が居ないのでかなり無理ゲーくさい