見出し画像

[ABC279 Python]トヨタシステムズプログラミングコンテスト2022(AtCoder Beginner Contest 279)A~C問題Python解説

Kai

いつもご覧いただきありがとうございます。
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)

基本的に微分を使うので、高校数学を履修していない方は難しいかもしれません。
時間を表す関数は下に凸な関数になりますので、微分を用いて最小値を求める形になります。


この記事が気に入ったら、サポートをしてみませんか?
気軽にクリエイターの支援と、記事のオススメができます!