roiti46's blog

主に競プロ問題の解説を載せてます

Atcoder Beginner Contest #020 A,B,C,D(部分点)

C,Dがいつもよりも難しく感じた。

問題はこちら

A: クイズ

入力に応じてABCかchokudaiと出力する

解法

やるだけ

print ["ABC","chokudai"][input()-1]

B: 足し算

2つの正の整数を与えられるのでそれをつなげて2倍した数を答えよ

解法

これもやるだけ。しかし、入力が2行に分かれてると勘違いして無駄にREしてしまった。

a,b = raw_input().split()
print 2*int(a+b)

C:

HxWマスの地図が与えられる。地図には白と黒のマスがあり、スタートとゴールはそれぞれ白マスである。あるマスから白マスへは1秒、黒マスへはx秒、移動に時間がかかるとする。スタートからゴールまでT秒以内にたどりつけるようにxを設定するとき、正の整数xのとりうる最大値を答えよ。スタートからゴールまでに黒マスは必ず1度は通りx=1でT秒以内にたどり着けることが保障されている。

解法

xを二分探索で探していく。各xごとにBFSでゴールまでかかる時間の最小値を計算していく。100回ループを回しているが30回ちょっとで十分である。つい最近あったyukicoderのNo.168 ものさしによく似ている問題だった。

inf = 10**12
H,W,T = map(int,raw_input().split())
A = [list(raw_input()) for i in xrange(H)]
for y in xrange(H):
    for x in xrange(W):
        if A[y][x] == "S":
            sx,sy = x,y
        if A[y][x] == "G":
            gx,gy = x,y
            
ans = 0
l,d,r = 1,10**4,10**9+1
for loop in xrange(101):
    G = [[inf]*W for i in xrange(H)]
    G[sy][sx] = 0
    que = [[sx,sy,0]]
    while que:
        x,y,s = que.pop(0)
        for dx,dy in zip([1,0,-1,0],[0,1,0,-1]):
            nx,ny = x+dx,y+dy
            if 0 <= nx < W and 0 <= ny < H:
                if A[ny][nx] == "#":
                    if G[ny][nx] <= s+d:
                        continue
                    G[ny][nx] = s+d
                    que.append([nx,ny,s+d])
                else:
                    if G[ny][nx] <= s+1:
                        continue
                    G[ny][nx] = s+1
                    que.append([nx,ny,s+1])
    if G[gy][gx] <= T:
        ans = max(ans,d)
        l = d
    else:
        r = d
    d = (r+l)/2 if r != l else d+1
print ans

D: LCM Rush

LCM(a,b)をaとbの最小公倍数とする。NとKが与えられるので、1からNまでの整数についてLCM(i,K)の和を100,000,007で割った値を答えよ。部分点がいくつか設定されている。

解法

15点解法は単純にlcmのアルゴリズムを1からNまで適用していけばいい。 満点解法はまだです・・・。

mod = 10**9+7
def gcd(a,b):
    while b: a,b = b,a%b
    return a
 
def lcm(a,b):
    return a*b/gcd(a,b)
 
N,K = map(int,raw_input().split())
ans = 0
for i in xrange(1,N+1):
    ans = (ans+lcm(i,K))%mod
print ans