見出し画像

[ABC286 Python]ウルシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 286) A～D問題Python解説

Kai

A問題

N, P, Q, R, S = map(int, input().split())
A = list(map(int, input().split()))
A[R-1:S], A[P-1:Q] = A[P-1:Q], A[R-1:S]
print(*A)

少し問題文が分かりづらいですが、
要は、
「数列AのP番目からQ番目の項」と「数列AのR番目からS番目の項」を入れ替えて数列Aを出力しなさい。
ということになります。

Pythonで入れ替えは次を参考にしてください。

後はインデックス値に注意して数列を作成させましょう。

B問題

N = int(input())
S = list(input())

for i in range(N-1):
    if S[i] == "n" and S[i+1] == "a":
        S[i] = "n"
        S[i+1] = "ya"
print("".join(S))

文字列SをリストSとして扱うと簡単に解くことができます。
Sに"na"が含まれるということは、
S[i]="n",S[i+1]="a"となる連続した部分があるということになります。
ここのS[i+1]を"a"から"ya"に変えることで正解の文字列を作ることができます。

最後にリストから文字列に戻す場合は、
"".join(リスト)を使いましょう。

C問題

N, A, B = map(int, input().split())
S = list(input())
S += S
ans = 10**19
for i in range(N):
    c = A*i
    for j in range(N//2):
        if S[i+j] != S[i+N-1-j]:
            c += B
    ans = min(ans, c)
print(ans)

Nの値が小さいので、全探索で考えましょう。
後は、回文を答えとして出力する必要はないので、
実際に文字を移動したり、置き換えたりする必要はありません。

プログラムの概要について見ていきましょう。
まずは、A円払う…という移動(操作1とします。)を全部試してみます。
その上で、操作1をi回(0~N回)した時に、
B円払う…という置き換え(操作2とします。)をして合計金額を比較するといった流れです。

先程お伝えした通り、実際に操作をする必要はありません。
まず、操作1をi回した段階でA*i円かかります。
次に、回文になるように回文になってない箇所をB円使って変更します。
これの合計を変数cに入れることによって、
最終的にansとcを比較して、答えを導くことができます。


D問題

N, X = map(int, input().split())
a = []
b = []
for i in range(N):
    A, B = map(int, input().split())
    a.append(A)
    b.append(B)

dp = [[False for _ in range(X+1)] for __ in range(N+1)]
dp[0][0] = True

for i in range(N):
    for j in range(X+1):
        for k in range(b[i]+1):
            if dp[i][j] and j+a[i]*k<=X:
                dp[i+1][j+a[i]*k] = True
if dp[N][X]:
    print("Yes")
else:
    print("No")

2023/01/22追記しました。

DPで解きます。
DPについてよく分かっていない方は以下の記事をご覧ください。

今回はdp[i][j]でDPを用意します。
iは硬貨の種類(0~N)を表します。
jは商品の値段(0~X)を表します。
dp[i][j]はTrueまたはFalseで表します。

つまりdp[i][j]は
「i種類の硬貨でj円を払うことができるのか」を表し、
True or Falseで表現するということになります。

では実際のプログラムを見ていきましょう。
1種類ずつ効果を見ていき、
今dp[i][j]=Trueつまりj円を払うことができている
かつ
その硬貨の残りの枚数で払うことができる値段はTrueになるので、
そのように条件分岐で設定することでDPが完成します。

最後にN種類の硬貨でX円を払うことができればYesです。

この記事が気に入ったらサポートをしてみませんか？