AtCoder ABC #007 : Python練習編

ABC#007に参加。
Aの解答は17sで２位とそこそこの滑り出しだったけど、Dで手間取って順位を落とした。
http://abc007.contest.atcoder.jp/assignments

A - 植木算

N本の木が一列に並んでいる。木の間の隙間は何個あるか。
N-1を返すだけ。

import sys

N=input()
print N-1

B - 辞書式順序

アルファベットで構成された文字列が与えられる。それより辞書順で小さい文字列を返せ。
入力が"a"なら解なし、それ以外は"a"を返せばよい。

import sys

S=raw_input()
if S=="a":
	print "-1"
else:
	print "a"

C - 幅優先探索

２次元グリッドがあり、一部マスは移動不可である。
開始位置からゴールまでの最短到達移動マス数を答えよ。
問題文の説明通りQueueを使ってBFSするだけ。

import sys
from collections import deque

H,W=map(int,raw_input().strip().split(" "))
sy,sx=map(int,raw_input().strip().split(" "))
gy,gx=map(int,raw_input().strip().split(" "))

M=[]
for y in range(0,H):
	M.append(raw_input().strip())

dist=[10000] * 10000
dist[sy*100+sx-101]=0

dx=[1,-1,0,0]
dy=[0,0,1,-1]

q=deque([sy*100+sx-101])

while len(q)>0:
	k=q.popleft()
	cy = k/100
	cx = k%100
	for i in range(0,4):
		ty=cy+dy[i]
		tx=cx+dx[i]
		if M[ty][tx]=="#":
			continue
		if dist[ty*100+tx]<=dist[cy*100+cx]+1:
			continue;
		dist[ty*100+tx]=dist[cy*100+cx]+1
		q.append(ty*100+tx)

print dist[gy*100+gx-101]

D - 禁止された数字

２つの数値A,Bが与えられる。
A～Bの間で、いずれかの桁に4か9を含む整数の数を求めよ。
0～Pの間で題意を満たす整数の数をfunc(P)とするとfunc(B)-func(A-1)が答え。

func(P)は桁DPで高々桁数分の再帰で解くことができる。
Pの最上位桁をX、残りをYYYYYYとして、P = XYYYYYYY = X*10^Z + YYYYYYY と表せるとする。
0 ≤ V < XであるVについて、V*10^Z + WWWWWWW (WWWWWW < 10^Z) の形の整数は明らかにPより小さい。
そのような数値のうち題意を満たすのは以下の通りなので、その分解に加える。

• V=4またはV=9なら、下位の桁はなんでも題意を満たすので10^Z通り
• それ以外なら、下位の桁に１個以上4,9を含めば題意を満たすので、逆に１個も4,9を含まないものを除くと(10^Z - 8^Z)通り

最後にV=X、すなわち最上位桁がPの時の処理だが

• V=4またはV=9なら、下位の桁はなんでも題意を満たすので(YYYYYYY+1)通り
• それ以外なら、func(YYYYYY)を再帰的に解く。１回再帰するごとに桁数が１個減るので最大再帰回数はPの桁数分。

import sys

A,B=map(int,raw_input().strip().split(" "))

def dodo(v):
	if v<=0:
		return 0
	if v>=1000000000000000000:
		v -= 1
	
	vv = 1
	ld = 1
	ret = 0
	
	while vv*10 <= v:
		vv *= 10
		ld *= 8
	
	for i in range(0,int(v/vv)):
		ret += vv
		if i!=4 and i!=9:
			ret -= ld
	
	if int(v/vv)==4 or int(v/vv)==9:
		return ret + (v - int(v/vv)*vv + 1)
	else:
		return ret + dodo(v - int(v/vv)*vv)

print dodo(B)-dodo(A-1)

まとめ

桁DP、いっつも不等号の書き方で１個ずれたりしてもどかしい。