pythonでAtCoder -ABC007-

対象

• AtCoder初心者（緑よりもランクが下の人）
• pythonがそれなりにかける人
• 数学やプログラミングに対する深い理解を持っていない人
  • Ex) DP, 深さ優先探索, メモ化再帰の実装ができない

動機

AtCoderは全ての問題に対して解説スライドが存在するが
解説をみて何となく理論を理解しても独力で実装ができない場合が多かった。

他の提出を見ても親切に解説コメントがついている回答はあまり存在せず、理解を実装に落とすことに苦労したため、簡単にでも解説がある回答はないものかと思い立ったことが動機である。

同様の苦労をしている人のためにも、稚拙なコードではあるが何らかの参考になればと思い
私の回答とそれに対する簡単なコメントを付与したコードをアップロードする。

実行環境

• python3

A

A.py

print(int(input())-1)

B

B.py

from string import ascii_lowercase
alphabet = ascii_lowercase
A = input()
if len(A) == 1:
    i = alphabet.index(A)
    print(-1 if i == 0 else alphabet[i-1])
else:
    print(A[:-1])

アルファベットを出す標準ライブラリがあるので使ってみました。

C

C.py

from queue import Queue
R, C = map(int, input().split(' '))
Sy, Sx = map(int, input().split(' '))
Gy, Gx = map(int, input().split(' '))
L = [[s for s in input()] for _ in range(R)]

move = [(0, -1), (0, 1), (1, 0), (-1, 0)]
q = Queue()
ans = 0

q.put([(Sy, Sx)])
L[Sy-1][Sx-1] = '#'

while not q.empty():
    pos = q.get()
    valid_pos = []
    for p in pos:
        for m in move:
            y, x = p[0]+m[0], p[1]+m[1]
            if y == Gy and x == Gx:
                ans += 1
                print(ans)
                exit()
            if L[y-1][x-1] == '.':
                L[y-1][x-1] = '#'
                valid_pos.append((y, x))
    if len(valid_pos) != 0:
        q.put(valid_pos)
    ans += 1
print(ans-1)

解説の通り、Queueを使って幅優先探索を実装しました。
もう少し効率よく書けそうな気はします。

D

D.py

def except_4_9(length):
    # 桁DPのテーブルを作る
    t = [[0] * 2 for _ in range(len(length)+1)]
    t[0][1] = 1
    for i in range(len(length)):
        for j in range(len(t[0])):
            n = int(length[i])
            # 制限を受けない桁
            if j == 0:
                t[i+1][j] += t[i][j] * 8
            # 制限を受ける桁
            else:
                for k in range(n+1):
                    if k in [4, 9]:
                        continue
                    # n==kの場合次の桁も制限を受ける
                    if n == k:
                        t[i+1][1] += t[i][j]
                    # n!=kの場合次の桁は制限を受けない
                    else:
                        t[i+1][0] += t[i][j]
    return sum(t[len(length)])

N, M = map(int, input().split(' '))
print(1 + M-except_4_9(str(M)) - (N-except_4_9(str(N-1))))

桁DPと呼ばれる解法を使っています。

終わりに

ABC→特に何も見ずに回答
D→解説、他の回答から実装

以上です。