2
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

pythonでAtCoder -ABC007-

Posted at

対象

  • 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→解説、他の回答から実装

以上です。

2
2
6

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?