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