🎲

[ABC263] AtCoder Beginner Contest 263(A-E 問題 Python)

2022/08/07に公開約3,700字

AtCoder Beginner Contest 263 の復習記録です。
A問題からE問題までやります。使用言語はPythonです。

A問題

https://atcoder.jp/contests/abc263/tasks/abc263_a

考え方

カードの番号ごとに、枚数をカウントしておき、降順に並び替えます。
1番目に多い枚数 =3 , 2番目に多い枚数 =2 を満たせば、フルハウスになります。

提出コード

num = list(map(int,input().split()))
card = [0]*13
for n in num:
    card[n-1] += 1
card.sort(reverse=True)
if card[0] == 3 and card[1] == 2:
    ans = "Yes"
else:
    ans = "No"
print(ans)

B問題

https://atcoder.jp/contests/abc263/tasks/abc263_b

考え方

Pのインデックスが 2〜NN-1 個になっています。
n 番目の親を調べるときには P_{n-2} を調べれば良いです。

提出コード

N = int(input())
P = list(map(int,input().split()))
ans = 0
while N > 1:
    N = P[N-2]
    ans += 1
print(ans)

C問題

https://atcoder.jp/contests/abc263/tasks/abc263_c

考え方

深さ優先探索(DFS)で調べました。リストに始めから 0 を入れておくことで、場合分けをしなくても良くなります。出力のときには 0 は出力しないようにします。

提出コード

import sys; sys.setrecursionlimit(10**6)
N,M = map(int,input().split())

def dfs(num,k):
    if k > N:
        print(*num[1:])
        return    
    for i in range(num[-1]+1,M+1):
        dfs(num+[i],k+1)
dfs([0],1)

D問題

https://atcoder.jp/contests/abc263/tasks/abc263_d

考え方

問題文を読み解くと A_n の左側 x 個を L に変換、右側 y 個を R に変換させたときの、数列の和の最小値を求める問題と考えられます。

下記のようにdpを考えてみます。

dp 定義
dpL[ i ] i 番目は L に変換する場合の i 番目以降の数列の和の最小値
dpA[ i ] i 番目は A_i を用いる場合の i 番目以降の数列の和の最小値
dpR[ i ] i 番目は R に変換する場合の i 番目以降の数列の和の最小値

dpL[ i ] への遷移は、dpL[ i+1 ], dpA[ i+1 ], dpR[ i+1 ]の最小値に L を加えたものになりますが、

L に変換される位置と R に変換される位置はそれぞれ両端から連続していることから、
dpA[ i ] への遷移は、dpA[ i+1 ], dpR[ i+1 ]の最小値に A_i を加えたもの。
dpR[ i ] への遷移は、dpR[ i+1 ]に R を加えたものになります。

提出コード

N,L,R = map(int,input().split())
A = list(map(int,input().split()))
dpR = [R*(N-i) for i in range(N)]
dpA = [0] * N
dpL = [0] * N
dpA[-1] = A[-1]
dpL[-1] = L

for i in range(N-1,0,-1):
    dpA[i-1] = A[i-1] + min(dpA[i], dpR[i])
    dpL[i-1] = L + min(dpL[i], dpA[i], dpR[i])

ans = min(dpL[0],dpA[0],dpR[0])
print(ans)

E問題

https://atcoder.jp/contests/abc263/tasks/abc263_e

考え方

i 番目のマスからゴールまでの、サイコロを振る回数の期待値を E_i とします。

E_i = \frac{1}{A_i+1}×\sum_{\mathclap{0\le k\le A_i}}(E_{i+k} + 1)

これを式変形していきます。

E_i = \frac{1}{A_i+1}×\sum_{\mathclap{0\le k\le A_i}}E_{i+k} + 1
\frac{A_i+1}{A_i+1}×E_i = \frac{1}{A_i+1}×(E_i+\sum_{\mathclap{1\le k\le A_i}}E_{i+k}) + 1
\frac{A_i}{A_i+1}×E_i = \frac{1}{A_i+1}×\sum_{\mathclap{1\le k\le A_i}}E_{i+k} + 1
E_i = \frac{1}{A_i}×\sum_{\mathclap{1\le k\le A_i}}E_{i+k} + \frac{A_i+1}{A_i}
E_i = \frac{\sum E_{i+k} +A_i+1}{A_i}

あとは、逆元を用いて実装すれば良いです。逆元はフェルマーの小定理を用います。

提出コード (TLE)

# TLEになるコード
MOD = 998244353
N = int(input())
A = list(map(int,input().split()))

E = [0]*N
for i in range(N-2,-1,-1):
    s = A[i]+1
    for k in range(1,A[i]+1):
        s += E[i+k]
        s %= MOD
    s *= pow(A[i], MOD-2, MOD)
    s %= MOD
    E[i] = s
 
print(E[0])

上記のコードがTLEになるのは、二重forループの部分で計算量が増えているからです。この部分について、累積和を用いて高速化します。マス i から先のマス k について、終わりのマス N まで E_k を合計した累積和 acc_i を準備します。

acc_i = \sum_{\mathclap{i\le k\le N}}E_k

提出コード (AC)

MOD = 998244353
N = int(input())
A = list(map(int,input().split()))

E = [0]*N
acc = [0]*(N+1)
for i in range(N-2,-1,-1):
    s = A[i]+1
    s += acc[i+1]-acc[i+A[i]+1]
    s %= MOD
    s *= pow(A[i], MOD-2, MOD)
    s %= MOD
    E[i] = s
    acc[i] = E[i] + acc[i+1]

print(E[0])

Discussion

ログインするとコメントできます