AtCoder ABC #020 : Python練習編

Aで1WAしたが、結局D問題が100pt最上位なので関係なかった。
時間半分の時点で離脱したのだけど、包除原理で混乱していたのであと１時間で101pt取れたかは微妙。
http://abc020.contest.atcoder.jp/assignments

A - クイズ

問題番号1か2が与えられるので、それぞれ回答を返せ。

問題内容は原文を見てもらうとして、"ABC"か"chokudai"を返せばよい。

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

B - 足し算

２つの整数A,Bが与えられる。
２つの整数を連結したものを２倍した値を返せ。

文字列で連結した後、数値化して２倍すればよい。

A,B=raw_input().strip().split(" ")
A+=B
print int(A)*2

C - 壁抜け

２次元グリッド上でSのセルからGのセルに移動したい。
壁の無いセルに進入するには時間1、壁のあるセルに進入するには時間xがかかる。
セルの状態が与えられるとき、最短移動時間がT以下となる最大のxを答えよ。

xを二分探索する。
あとはWarshall-FloyedなりDijkstraなりで最短移動時間を求めればよい。
Warshall-FloyedだとPythonでは実行時間が厳しいため、以下のコードはDijkstraを使った。

import Queue as queue

H,W,T=map(int,raw_input().strip().split(" "))
S=[]
sy=sx=gy=gx=0

def ok(v):
	dist = [[(1<<60) for i in range(W)] for j in range(H)]
	q = queue.PriorityQueue()
	
	dist[sy][sx] = 0
	q.put((0,sy*100+sx))
	
	dd=[1,0,-1,0]
	while not q.empty():
		e = q.get()
		y = e[1] / 100
		x = e[1] % 100
		if e[0] != dist[y][x]:
			continue
		
		for i in range(4):
			ty = y + dd[i]
			tx = x + dd[i^1]
			
			if tx >= 0 and tx < W and ty >= 0 and ty < H:
				co = dist[y][x]
				if S[ty][tx] == '#':
					co += v
				else:
					co += 1
				
				if co < dist[ty][tx]:
					dist[ty][tx] = co
					q.put((co,ty*100+tx))
	
	if dist[gy][gx] <= T:
		return 1
	return 0


for y in range(H):
	S.append(raw_input().strip())
	for x in range(W):
		if S[y][x]=='S':
			S[y]=S[y][0:x]+'.'+S[y][x+1:]
			sy = y
			sx = x
		
		if S[y][x]=='G':
			S[y]=S[y][0:x]+'.'+S[y][x+1:]
			gy = y
			gx = x

ret = 0
for i in range(40,-1,-1):
	if ok(ret + (1<<i)):
		ret += 1<<i

print ret

D - LCM Rush

N,Kが与えられる。1～Nの各整数にiに対し、LCM(i,K)の総和を1000000007で割った剰余を答えよ。

LCM(i,K)=i*K/GCD(i,K)であるため、GCD(i,K)が同じものをまとめて処理する。

まず、F(n,k)を、1≦i≦nのうちGCD(i,k)==1となるiの和とする。
すると、各dに対して、K*F(N/d,K/d)を足し合わせたものが解になる。

あとはF(n,k)を求めるわけだが、これはkの素因数に対して包除原理を用いて1～nの和からkと互いに素でない数の和を引いていけば良い。

import math

mo = 1000000007

def enumdiv(n):
	S=[]
	i = 1
	while i*i <= n:
		if i*i > n:
			break
		if n % i == 0:
			S.append(i)
			if i*i != n:
				S.append(n/i)
		i += 1
	
	S.sort()
	return S

def enumpfactor(n):
	S=[]
	i = 2
	while i*i <= n:
		if n % i == 0:
			S.append(i)
			while n % i == 0:
				n /= i
		i += 1
	
	if n > 1:
		S.append(n)
	return S

def dodo(n,k):
	v=0
	F = enumpfactor(k)
	for mask in range(0,1<<len(F)):
		sgn = 1
		mul = 1
		for i in range(0,len(F)):
			if mask & (1<<i):
				sgn = -sgn
				mul *= F[i]
		
		v += sgn * mul * ((n/mul)*(n/mul+1)/2) % mo
	
	return v % mo


N,K=map(int,raw_input().strip().split(" "))

P = enumdiv(K)
ret = 0
for r in P:
	ret += K * dodo(N/r, K/r) % mo

print ret % mo

まとめ

これ系の包除原理、いつも約数でbitmaskを取るか素因数でbitmaskを取るか迷う。