ABC07CとD問題

問題はhttp://abc007.contest.atcoder.jp/

C問題

解答の方針

蟻本でみかけた幅優先探索
実装するだけだった

コード

python:abc07c.py

INF = 10**9+7

R,C = map(int,input().split())
sy,sx = map(int,input().split())
gy,gx = map(int,input().split())
c = [list(input())for i in range(R)]
distance = [[INF for i in range(C)]for i in range(R)]
queue = [[sy-1,sx-1]]
distance[sy-1][sx-1] = 0

def bfs():
    global distance
    global queue

    while len(queue):
        y,x = queue.pop(0)
        for ny,nx in [[1,0],[0,1],[-1,0],[0,-1]]:
            dy = y + ny
            dx = x + nx
            
            if 0 <= dx <= C and 0<= dy <= R and c[dy][dx] == '.' and distance[y][x]+1 < distance[dy][dx]:
                queue.append([dy,dx])
                distance[dy][dx] = distance[y][x] + 1

bfs()
print(distance[gy-1][gx-1])

D問題部分点

解答の方針

0<A,B<10000程度ならすべて0~A,0~Bのすべての値に対して、
4か9が含まれるかをカウントしてもO(2*10^5)程度なので間に合う

コード

abc07d.py

A,B = map(int,input().split())
res = 0
 
for i in range(B+1):
    if '4' in list(str(i))  or '9' in list(str(i)):
        res += 1
for i in range(A):
    if '4' in list(str(i))  or '9' in list(str(i)) :
        res -= 1
 
print(res)

D問題満点解答

解答の方針

0~9までの4,9が含まれる値は2つしかない。

また、100までの4，9が含まれる値は、
0~9,10~19,20~29,30~39,50~59,60~69,70~79,80~89　の8つの区間でそれぞれ2つずつ、
40~49,90~99の区間はすべてが対象なのでそれぞれ10つずつ
つまり、102 + 28である

1000までの場合も100を単位として考えると同じように計算できることから
10のn乗までの4,9が含まれる区間は漸化式として以下のように表せる。

a_{0} = 2\\
a_{n} = 2\times10^{n-1}+ a_{i-1}\times8

このことから以下の手順を踏むことで、解が求められると考えた。

1 与えられた値に4もしくは9が含まれる場合(例:14931),端数を取り去る(14000)。
取り去った分をresなどに足しておく

2 先ほどの漸化式の値を、配列として持って置き、各位ごとに、a[n]と掛け合わせ、順次resに加える。（例:14000の場合、1a[4] + 4a[3] + 0*a[2] + … + 0 *a[0])

3 入力A,Bごとに手順1,手順2を行い、resを返す。その後二つの値の差を出力する。

(補足）このように実装したが、微妙におかしなところが多く、いろいろな付け加えをしてしまい、とても見づらいコードになってしまった。いつか直したい

コード

abc07d.py

A,B = map(int,input().split())

A = list(str(A))
B = list(str(B))
list_A = list(map(int,A))
list_B = list(map(int,B))
a = [0 for i in range(19)]
a[1] = 2

def dfs(i,n): #漸化式aを求める
    global a
    if i == n:
        return 
    a[i] = 2*(10**(i-1)) + a[i-1]*8
    return dfs(i+1,n)

def cal(list):#4,9の含まれる値の計算
    l = len(list)
    n = l-1
    res = 0
    for k in range(l):
        if list[k] == 4 or list[k] == 9:#端数を取り去る
            for j in range(k+1,l):
                res += list[j] * (10**(l-1-j))
                list[j] = 0
                if j == l-1:
                    res += 1
    for i in range(l):
        count = 0
        if i == l-1 and list[i] == 4:#1の位が4の時(端数処理を行わないので特殊なパターン）
            count = 1
        elif 4 < list[i]:
            count = 1
        res += (list[i]-count)*a[n]+(10**n)*count
        #print(res,a[n],list[i],count,(list[i]-count)*a[n]+(10**n)*count)
        n -= 1
    if list[-1] == 9:
        res += 1
    return res

dfs(2,19)
m = cal(list_A)
n = cal(list_B)

if '4' in A or '9' in A:
    m -= 1

print(n-m)