🎲

[ABC263] AtCoder Beginner Contest 263（A-E 問題 Python）

2022/08/07に公開

Python

競技プログラミング

AtCoder

tech

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

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問題

考え方

Pのインデックスが $2〜N$ の $N-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問題

考え方

深さ優先探索（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問題

考え方

問題文を読み解くと $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問題

考え方

$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])

A問題

考え方

提出コード

B問題

考え方

提出コード

C問題

考え方

提出コード

D問題

考え方

提出コード

E問題

考え方

提出コード (TLE)

提出コード (AC)

Discussion