LoginSignup
0
0

More than 1 year has passed since last update.

@sano192

トヨタシステムズプログラミングコンテスト2022(ABC279) A～D問題 ものすごく丁寧でわかりやすい解説 python 灰色～茶色コーダー向け #AtCoder

Last updated at Posted at 2022-12-12

トヨタシステムズプログラミングコンテスト2022(AtCoder Beginner Contest279) A～D問題の解説記事です。
灰色～茶色コーダーの方向けに解説しています。

その他のABC解説、動画などは以下です。

更新時はツイッターにて通知します。
https://twitter.com/AtCoder4

トヨタシステムズ様について

採用情報

A Dif:7

尖っている部分はvなら1個、wなら2個になります。
Sを1文字ずつ確認しながらvならば1、wならば2と数えていけばOKです。

Sのi文字目はS[i]と書きます。
注意が必要なのは最も左の文字を0文字目、次を1文字目、...と数えることです。すなわち先頭の文字はS[0]となります。

1文字ずつ文字を確認するにはforを使います。
for i in range(N)
とするとi=0,1,2,...,(N-1)と順に代入しながら処理ができます。
今回はNにあたる部分がSの文字数となります。len(S)と書くことでSの文字数を確認できます。

入力の受け取り、出力がわからない方は以下の記事を参考にしてください。

【提出】

# 入力の受け取り
S=input()

# 答え
ans=0

# i=0~(Sの文字数)-1
for i in range(len(S)):
    # Sのi文字目が「v」ならば
    if S[i]=="v":
        # 答えにプラス1
        ans+=1
    # そうでなければ(Sのi文字目がw)
    else:
        # 答えにプラス2
        ans+=2

# 答えの出力
print(ans)

B Dif:39

要するにTがSに含まれるか？を判定すればいいわけです。
if T in S:
と書けば判定ができます。

【提出】

# 入力の受け取り
S=input()
T=input()

# TがSに含まれていれば
if T in S:
    # 「Yes」を出力
    print("Yes")
# そうでなければ
else:
    # 「No」を出力
    print("No")

C Dif:64

列は入れ替えができるので好きな場所へもってくる事ができます。
よってSの各列についてどのようになっているかを確認し、それら全てが同じ数だけTにあるかを判定します。

まずSの各列の要素を記録します。
これは列ごとに0行目、1行目、2行目、...と文字を確認すればOKです。
Tも同様にして各列の要素を確認します。

同じものが同じだけあるかの確認にはソートを使えばいいです。
すなわちSの列ごとの要素、Tの列ごとの要素をソートして(辞書順に並べて)これらが完全に一致すれば「Yes」となります。

【提出】

# 入力の受け取り
H,W=map(int,input().split())

# Sの記録
S=[]
# i~0~(H-1)
for i in range(H):
    # 入力の受け取り
    Si=input()
    # Sへ追加
    S.append(Si)
    
# Tの記録
T=[]
# i~0~(H-1)
for i in range(H):
    # 入力の受け取り
    Ti=input()
    # Tへ追加
    T.append(Ti)

# Sの各列ごとの要素記録
Sc=[]
# Tの各列ごとの要素記録
Tc=[]

# w=0~(W-1)
for w in range(W):
    # w列の要素
    Mozi=""
    # h~0~(H-1)
    for h in range(H):
        # Moziへh行w列の文字を追加
        Mozi+=S[h][w]
    # 記録
    Sc.append(Mozi)

# w=0~(W-1)
for w in range(W):
    # w列の要素
    Mozi=""
    # h~0~(H-1)
    for h in range(H):
        # Moziへh行w列の文字を追加
        Mozi+=T[h][w]
    # 記録
    Tc.append(Mozi)

# 並び替え
Sc.sort()
Tc.sort()

# ScとTcが一致していれば
if Sc==Tc:
    # 「Yes」を出力
    print("Yes")
# そうでなければ
else:
    # 「No」を出力
    print("No")

D Dif:766

操作回数をxとしたとき、高橋くんが地面に到達できる時間をT(x)とすると以下のようになります。
T(x)=A/(1+√x)+Bx

まずどのような形のグラフになるかを確認しましょう。
以下のサイトで数式をそのまま打ち込むとグラフを作ることができます。
https://www.geogebra.org/graphing?lang=ja
A,Bの値をてきとうに変えながら観察すると、どうやら谷のような形になりそうだなとわかります。

ABC279D1.PNG

この最も低い場所の値を出したいです。
微分して0になる箇所を探してもいいですが、せっかくなので「三分探索」を使ってみましょう。

三分探索は本問のように谷、または山になっているグラフの最小、最大を探すのに便利な方法です。
まず探索範囲の端、L,Rを決めます。Lは0、Rはめちゃくちゃ大きい数にしておきます。
範囲を三等分した線の左側をLx,右側をRxとします。
すなわち
Lx=L+(R-L)*(1/3)
Rx=L+(R-L)*(2/3)
となります
T(Lx)とT(Rx)を比較して、
・T(Lx)の方が小さい→R=Rxとする
・T(Rx)の方が小さい→L=Lxとする
と更新します。
ABC279D2.PNG

こうすることで最も低い部分が探索範囲に入ったまま、範囲を2/3に縮めることができます。
これをできるだけたくさん行います。具体的に何回行えばよいか？を求めるのはめちゃくちゃに難しい問題なので、TLEしない程度にできるだけ多い回数行うとしておきましょう。

適当な回数の計算を行ったらLに近い整数、すなわちx=int(L)としてT(x)とT(x+1)を計算し、小さい方を答えとして出力します。

【提出】

# 入力の受け取り
A,B=map(int,input().split())

# sqrtのインポート
from math import sqrt

# 関数Tを定義
def T(x):
    return A/(sqrt(1+x))+B*x

# 左端
L=0
# 右端
R=10**18
# 10^5回
for i in range(10**5):
    # 3等分した線の左側
    Lx=L+(R-L)*(1/3)
    # 3等分した線の右側
    Rx=L+(R-L)*(2/3)

    # T(Lx)≤T(RX)ならば
    if T(Lx)<=T(Rx):
        # 右端を更新
        R=Rx
    # そうでなければ
    else:
        # 左端を更新
        L=Lx
        
# Lを整数にする
x=int(L)

# 小さい方を出力
print(min(T(x),T(x+1)))

【広告】

『AtCoder 最速で緑になる 基礎・典型50問詳細解説』

ABC201～250から基礎・典型問題50問をとてつもなく丁寧かつ詳細に解説した本(kindle)、pdf(booth)です。
灰色、茶色コーダーにおすすめ！
値段：100円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0BBB7RKTP

【booth(pdf)】
https://booth.pm/ja/items/4102300

冒頭5問をサンプルとして無料公開しています
https://qiita.com/sano192/items/6361ed72106cb6dd5843

『AtCoder　凡人が『緑』になるための精選50問詳細解説』

AtCoderで緑になるための典型50問をひくほど丁寧に解説した本(kindle)、pdf(booth)を販売しています。
値段：100円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/gp/product/B09C3TPQYV/

【booth(pdf)】
https://sano192.booth.pm/items/3179185

1～24問目まではサンプルとして無料公開しています
https://qiita.com/sano192/items/eb2c9cbee6ec4dc79aaf

『AtCoder ABC201～225 ARC119～128 灰・茶・緑問題 超詳細解説 AtCoder 詳細解説』

ABC201~225、ARC119~128 の 灰・茶・緑DIfficulty問題(Dif：0～1199) を解説しています。
とにかく 細かく、丁寧に、具体例を豊富に、実装をわかりやすく、コードにコメントをたくさん入れて 解説しています。

サンプルを5問分公開しています
https://qiita.com/sano192/items/3258c39988187759f756

Qiitaにて無料公開している『ものすごく丁寧でわかりやすい解説』シリーズをベースにしていますが、 【キーワード】【どう考える？】【別解】を追加 し、 【解説】と【実装のコツ】を分ける ことでよりわかりやすく、 具体例や図もより豊富に 書き直しました。
Qiitaには公開していない ARC119~128の灰・茶・緑DIfficulty問題も書き下ろし ています。

値段：300円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B09TVK3SLV

【booth(pdf)】
https://booth.pm/ja/items/3698647

ARC119~128の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B09TVKGH17/

【booth(pdf)】
https://sano192.booth.pm/items/3698668

『AtCoder ABC226～250 ARC129～139 灰・茶・緑問題 超詳細解説 AtCoder 詳細解説』

ABC226~250、ARC129~139 の 灰・茶・緑DIfficulty問題(Dif：0～1199) を解説しています。
とにかく 細かく、丁寧に、具体例を豊富に、実装をわかりやすく、コードにコメントをたくさん入れて 解説しています。

サンプルを4問分公開しています
https://qiita.com/sano192/items/f8f09ea769f2414a5733

Qiitaにて無料公開している『ものすごく丁寧でわかりやすい解説』シリーズをベースにしていますが、 【キーワード】【どう考える？】【別解】を追加 し、 【解説】と【実装のコツ】を分ける ことでよりわかりやすく、 具体例や図もより豊富に 書き直しました。
Qiitaには公開していない ARC129~139の灰・茶・緑DIfficulty問題も書き下ろし ています。

値段：300円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0B7G13QMS

【booth(pdf)】
https://sano192.booth.pm/items/4025713

ARC129～139の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0B7G337YF

【booth(pdf)】
https://sano192.booth.pm/items/4025737

『Excelでリバーシを作ろう!!　マクロ、VBAを1から学ぶ』

Excelのマクロ(VBA)で「三目並べ」「マインスイーパー」「リバーシ」を作る解説本です！
マクロ、VBAが全くわからない人でも大丈夫！　丁寧な解説と図でしっかり理解しながら楽しくプログラミングを学ぶ事ができます！
値段：300円(Kindle Unlimited対象)

サンプルとして「準備」～「三目並べ」を無料公開しています。
https://qiita.com/sano192/items/9a47e6d73373d01e31fb

【kindle】
https://www.amazon.co.jp/dp/B09XLM42MW

【booth(pdf】
https://sano192.booth.pm/items/3785312

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0