[白俊]1782775-Python 3

2775.私は女性会長になります。

https://www.acmicpc.net/problem/2775

私の答え-成功

from sys import stdin

T = int(stdin.readline())

dp = []

for i in range(T):
    k = int(stdin.readline())
    n = int(stdin.readline())

    nums = [i for i in range(n+1)]
    ans = 0
    for _ in range(k):
        for j in range(1, n+1):
            nums[j] += nums[j-1]
    
    print(nums[-1])

0階に1~n番、i番にi名があります.
nums=[1,2,3,...,n]初期化
自分の下(a-1)階の1番からb番まで、人々の数の和を満たす.
0層からk層まで累積和を繰り返し求めればよい.

迷宮を探る

https://www.acmicpc.net/problem/2178

マイプール-タイムアウト(再帰)

import sys
sys.setrecursionlimit(10**9)

N, M = map(int, sys.stdin.readline().split())

mat = []
for i in range(N):
    mat.append([0]*M)

for i in range(N):
    s = sys.stdin.readline().strip()
    for j in range(M):
        mat[i][j] = int(s[j])

ans = N*M

def func(m, i, j, cnt):
    global ans
    if i == N-1 and j == M-1:
        ans = min(ans, cnt)
        return
    if cnt > ans:
        return

    tmp = m[i][j]
    m[i][j] = 0

    if i-1 >= 0 and mat[i-1][j]:
        func(m, i-1, j, cnt+1)
    if i+1 < N and mat[i+1][j]:
        func(m, i+1, j, cnt+1)
    if j-1 >= 0 and mat[i][j-1]:
        func(m, i, j-1, cnt+1)
    if j+1 < M and mat[i][j+1]:
        func(m, i, j+1, cnt+1)
    
    m[i][j] = tmp

func(mat, 0, 0, 1)
print(ans)

ダンジョンをマットに保存
(0,0)から現在の位置に関連付けられたパスに戻る
この場合、経過した値はすべてゼロになります.
(N-1,M-1)ansを最高値に更新
でも….タイムアウト...予想していた...

マイプールタイムアウト(queue)

from sys import stdin
import collections

N, M = map(int, stdin.readline().split())

dp = []
mat = []
for i in range(N):
    dp.append([N*M]*M)
    mat.append([0]*M)

for i in range(N):
    s = stdin.readline().strip()
    for j in range(M):
        mat[i][j] = int(s[j])

dp[-1][-1] = 1

queue = collections.deque([(N-1, M-1)])

while queue:
    i, j = queue.popleft()

    mat[i][j] = 0

    if i == 0 and j == 0:
        break

    if i-1 >= 0 and mat[i-1][j]:
        dp[i-1][j] = dp[i][j]+1
        queue.append((i-1, j))
    if i+1 < N and mat[i+1][j]:
        dp[i+1][j] = dp[i][j]+1
        queue.append((i+1, j))
    if j-1 >= 0 and mat[i][j-1]:
        dp[i][j-1] = dp[i][j]+1
        queue.append((i, j-1))
    if j+1 < M and mat[i][j+1]:
        dp[i][j+1] = dp[i][j]+1
        queue.append((i, j+1))

print(dp[0][0])

終了値から表示を開始し、(0,0)を返します.
宛先値(N-1,M-1)を格納するためにdeque形式のqueueを作成する
queue値がポップアップされ、接続の場所が検索され、queueに追加されます.
過去の場所はこれ以上見る必要がないので、mat[i][j]=0
このとき、dp値は現在値+1に更新される
break一番早く到着(0,0)
でも….これも.タイムアウト...
=>matの値は変わらず、別途アクセスを作成し、使用後にパスしました

エクスポート-成功(queue)

from sys import stdin
import collections

N, M = map(int, stdin.readline().split())

visited = []
dp = []
mat = []
for i in range(N):
    dp.append([0]*M)
    mat.append([0]*M)
    visited.append([0]*M)

for i in range(N):
    s = stdin.readline().strip()
    for j in range(M):
        mat[i][j] = int(s[j])

dp[0][0] = 1
visited[0][0] = 1

queue = collections.deque([(0, 0)])

while queue:
    i, j = queue.popleft()

    if i-1 >= 0 and visited[i-1][j] == 0 and mat[i-1][j] == 1:
        dp[i-1][j] = dp[i][j]+1
        visited[i-1][j] = 1
        queue.append((i-1, j))
    if i+1 < N and visited[i+1][j] == 0 and mat[i+1][j] == 1:
        dp[i+1][j] = dp[i][j]+1
        visited[i+1][j] = 1
        queue.append((i+1, j))
    if j-1 >= 0 and visited[i][j-1] == 0 and mat[i][j-1] == 1:
        dp[i][j-1] = dp[i][j]+1
        visited[i][j-1] = 1
        queue.append((i, j-1))
    if j+1 < M and visited[i][j+1] == 0 and mat[i][j+1] == 1:
        dp[i][j+1] = dp[i][j]+1
        visited[i][j+1] = 1
        queue.append((i, j+1))

print(dp[N-1][M-1])

アクセスが0でmatが1の場合にのみappendをキューに追加

他人の解答

from sys import stdin
import collections

# dx[0], dy[0] => 오른쪽
# dx[1], dy[1] => 왼쪽
# dx[2], dy[2] => 아래
# dx[3], dy[3] => 위

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

N, M = map(int, stdin.readline().split())

visited = []
dp = []
mat = []
for i in range(N):
    dp.append([0]*M)
    mat.append([0]*M)
    visited.append([0]*M)

for i in range(N):
    s = stdin.readline().strip()
    for j in range(M):
        mat[i][j] = int(s[j])

dp[0][0] = 1
visited[0][0] = 1
queue = collections.deque([(0, 0)])

while queue:
    i, j = queue.popleft()

    for k in range(4):
        nx, ny = i+dx[k], j+dy[k]
        if 0 <= nx < N and 0 <= ny < M:
            if visited[nx][ny] == 0 and mat[nx][ny] == 1:
                dp[nx][ny] = dp[i][j] + 1
                visited[nx][ny] = 1
                queue.append((nx, ny))

print(dp[N-1][M-1])

4方向に関する情報をdx,dyに入れてfor文として扱う
(注-ifゲート4個はforゲートより速い)
nx、nyが範囲内の場合、dp値の更新&アクセス=1&appendをキューに追加
注意)2 D配列がある場合は、1行として処理できます.

mat = [list(map(int, list(input()))) for _ in range(N)]