[ABC279 Python]トヨタシステムズプログラミングコンテスト2022(AtCoder Beginner Contest 279)A～C問題Python解説
いつもご覧いただきありがとうございます。
ABC279の解説記事です。
ミス等ありましたらコメントで教えていただけると幸いです。
おまけでD問題もあります。
A問題
S = input()
v = S.count("v")
w = S.count("w")
print(v+2*w)下に尖っている部分ですが、"v"には1か所、"w"には2か所ありますね。
"v"と"w"それぞれの個数を数えて、計算すれば答えが求められそうです。
文字列の中にある文字が何個存在するかを確認するには、
リスト.count(文字)とします。
B問題
S = input()
T = input()
if T in S:
print("Yes")
else:
print("No")問題文が長く書かれていますが、
部分文字列かどうかを判定するだけですので、
A問題と同様に文字列Tの中に文字列Sが存在するかどうかを確認するだけです。
C問題
H, W = map(int, input().split())
s = [input() for _ in range(H)]
t = [input() for _ in range(H)]
arr_s = list(zip(*s))
arr_t = list(zip(*t))
arr_s.sort()
arr_t.sort()
# print(arr_s, arr_t)
if arr_s == arr_t:
print("Yes")
else:
print("No")
Sの列を並べ替えてTと等しくできるかを判定するので、
SとTの列情報だけを確認することが必要です。
では、列情報だけを持ったうえで、どのように等しいかどうかを確認すればいいのでしょうか。
いろいろな方法が考えられますが、
SとTを「同じルールで」並べ替えて、
結果が等しいかどうかを比較することが有効です。
今回は辞書順を採用しました。
SとTそれぞれの列情報を図形ごとに辞書順に並べ替えます。
その結果が等しければ、Yes、違えばNoと出力することになります。
では具体的な方法について見ていきましょう。
まずは、S1～SH、T1～THというのは行情報になるので、
転置によって列情報に直します。
Pythonの転置は以下を確認してください。
今回はこの後辞書順に並べ替えることを考えて、
組み込み関数zip()による転置を採用しました。
後はそれぞれ辞書順に並べ替えるために、
リスト.sort()を使用します。
最後に並べ替えたリストが等しいかどうかを確認しましょう。
おまけ：D問題
import math
A, B = map(int, input().split())
# y = B*(g)+A/√(g+1)の最小値を求める
# y' = B-A/(2x^(3/2))
# よって、x = (A/2B)^(2/3)-1でyは最小値を取る
# 誤差もあるのでxの前後5ぐらいは候補としてもつ
x = int((A/(2*B))**(2/3)-1)
x_list = [x-5, x-4, x-3, x-2, x-1, x, x+1, x+2, x+3, x+4, x+5]
ans = A
# print(x, x_list)
for i in x_list:
if i+1!=0 and i+1>0:
# 平方根を取るときに正の整数のみを対象にする
ans = min(ans, B*i+A/(math.sqrt(i+1)))
print(ans)基本的に微分を使うので、高校数学を履修していない方は難しいかもしれません。
時間を表す関数は下に凸な関数になりますので、微分を用いて最小値を求める形になります。