AtCoder ABC #029 : Python練習編

まーた雑な回答でWAしてしまった。
http://abc029.contest.atcoder.jp/assignments

A - 複数形

文字列が与えられるので、複数形にするため"s"を付けて出力せよ。

指示通り出力するだけ。語尾が"y"の場合も特に考慮する必要はないようだ。

S=raw_input()
print S+"s"

B - カキ

12個の英単語が与えられる。
"r"が含まれる単語の数を求めよ。

１個ずつ"r"の有無を判定するだけ。

ret = 0
for i in range(12):
	haver = 0
	S=raw_input()
	for c in S:
		if c == 'r':
			haver = 1
	ret += haver

print ret

C - Brute-force Attack

"a","b","c"だけで構成されるN文字の文字列を辞書順に列挙せよ。

"a","b","c"だけで構成されるi文字の文字列群をS[i]とする。
S[i]の各文字列の末尾に"a",",b","c"を付与したものをそれぞれS[i+1]に追加すればよい。

N=input()

S=[]
S.append([""])

for i in range(8):
	S.append([])
	for s in S[i]:
		S[i+1].append(s+"a")
		S[i+1].append(s+"b")
		S[i+1].append(s+"c")

for s in S[N]:
	print s

D - 1

1～Nまでの整数を10進数で順に並べるとき、1という数値は何回登場するか。

Nを10進数でXyyyyy=X*10^z + yyyyyという形で表現したとする。(最上位ケタがXで、残りがy)
X＜10の時は解が明らかなので、以後X≧10の場合を考える。

まず、leading zeroを含めると、10^k未満の整数を並べた際k*10^(k-1)個1が並ぶ。
よって、最上位桁が各i(0≦i＜X)の場合、後ろのz桁に1はz*10^(z-1)回ずつ登場する。
また、i=1の場合、その最上位桁の分10^z回1がならぶ。

これでX*10^z未満の整数で登場する1の数は列挙できたので、残りはX*10^z～X*10^z+yyyyyの範囲に現れる1の数を考える。
基本的には0～yyyyyの範囲に現れる1の数と一致するので、N=yyyyyとして再帰的に1の数を数えればよい。
ただしX==1の場合は最上位ケタの分(yyyyy+1)を加えること。

def num(n):
	d = 0
	while pow(10,d) < n:
		d += 1
	return d*n/10

def dfs(n):
	if n <= 0:
		return 0
	
	c = 1
	while c*10 <= n:
		c *= 10
	
	ret = 0
	for d in range(10):
		if (d+1)*c > n:
			if d == 1:
				ret += (n-c+1)
			return ret + dfs(n - c*d)
		
		ret += num(c)
		if d == 1:
			ret += c

print dfs(input())

まとめ

Dみたいな桁DP、どうもDPでうまく状態遷移が追えなくて、メモ化再帰を使ってしまう。