LoginSignup
2
0

More than 1 year has passed since last update.

@sano192

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

Last updated at Posted at 2022-09-27

トヨタ自動車プログラミングコンテスト2022(AtCoder Beginner Contest 270)　A～C問題の解説記事です。
灰色～茶色コーダーの方向けに解説しています。

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

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

A - 1-2-4 Test　Dif:45

公式解説の通りAorBを計算すれば答えが出ます。
そんなん思いつくか！という人のための解法を紹介します。

まず高橋君の点数から高橋君はどの問題を解けたのかを考えましょう。
1点問題をX、2点問題をY、4点問題をZとします。
0点→解けた問題はない
1点→Xのみ解けた
2点→Yのみ解けた
3点→X,Yが解けた
4点→Zのみ解けた
5点→X,Zが解けた
6点→Y,Zが解けた
7点→X,Y,Zが解けた

同様にして青木君が解けた問題も確認します。

X,Y,Zを変数として、どちらかが解けた場合は=1、どちらも解けなかった場合は=0にしましょう。
例えば高橋君が2点、青木君が6点なら高橋君はY,青木君はY,Zが解けているので
X=0
Y=1
Z=1
となります。よってすぬけ君の点数は2+4=6点とわかります。

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

【提出】

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

# 1点問題が解けたら=1
X=0
# 2点問題が解けたら=1
Y=0
# 4点問題が解けたら=1
Z=0

# A=1ならば
if A==1:
    # X=1にする
    X=1
elif A==2:
    Y=1
elif A==3:
    X=1
    Y=1
elif A==4:
    Z=1
elif A==5:
    X=1
    Z=1
elif A==6:
    Y=1
    Z=1
elif A==7:
    X=1
    Y=1
    Z=1

# Bも同様
if B==1:
    X=1
elif B==2:
    Y=1
elif B==3:
    X=1
    Y=1
elif B==4:
    Z=1
elif B==5:
    X=1
    Z=1
elif B==6:
    Y=1
    Z=1
elif B==7:
    X=1
    Y=1
    Z=1

# 答え
ans=0

# 1点問題が解けていたら
if X==1:
    # 答えにプラス1
    ans+=1
# 2点問題が解けていたら
if Y==1:
    # 答えにプラス2
    ans+=2
# 4点問題が解けていたら
if Z==1:
    # 答えにプラス4
    ans+=4

# 答えの出力
print(ans)

B - Hammer　Dif:106

0,X,Y,Zの位置関係は24通りしかありません。
それぞれの答えを考えましょう。

0<X<Y<Z → |X|
0<X<Z<Y → |X|
0<Y<X<Z → -1
0<Y<Z<X → -1
0<Z<X<Y → |X|
0<Z<Y<X → |X|
X<0<Y<Z → |X|
X<0<Z<Y → |X|
X<Y<0<Z → 2|Z|+|X|
X<Y<Z<0 → |X|
X<Z<0<Y → |X|
X<Z<Y<0 → -1
Y<0<X<Z → |X|
Y<0<Z<X → |X|
Y<X<0<Z → |X|
Y<X<Z<0 → |X|
Y<Z<0<X → |X|
Y<Z<X<0 → |X|
Z<0<X<Y → |X|
Z<0<Y<X → 2|Z|+|X|
Z<X<0<Y → |X|
Z<X<Y<0 → -1
Z<Y<0<X → |X|
Z<Y<X<0 → |X|

-1になるパターンは4通り、2|Z|+|X|になるパターンは2通り、それ以外は全て|X|になることがわかります。
これらを条件分岐で確認します。

【提出】

# 入力の受け取り
X,Y,Z=map(int,input().split())

# -1になるパターン
if 0<Y<X<Z or 0<Y<Z<X or X<Z<Y<0 or Z<X<Y<0:
    # -1を出力
    print(-1)
# 2|Z|+|X|になるパターン
elif X<Y<0<Z or Z<0<Y<X:
    # 2|Z|+|X|を出力
    print(2*abs(Z)+abs(X))
# それ以外
else:
    # |X|を出力
    print(abs(X))

C - Simple path 　Dif:625

各頂点のXからの距離を書き込んでみましょう。
X=5，Y=6とします。

ABC270_C_1.png

例えば頂点5から頂点4へは頂点5→頂点2→頂点4というルートになるため距離は2です。

これがわかれば頂点Yから距離が小さくなる方へ進んで行くことで単純パスを確認できることがわかります。
具体的には
頂点6(距離4)→頂点3(距離3)→頂点1(距離2)→頂点2(距離1)→頂点5(距離0)
となります。

距離を記録するためにBFSを使います。
BFSは幅優先探索(breadth first search)の略称で、グラフを探索するアルゴリズムです。

BFSの解説動画を作りましたので、本問が難しいと感じた方は是非御覧ください。

(1)Xをキューへ追加
(2)キューの左端(先頭)から頂点を取り出す(今いる頂点)
(3)今いる頂点から行ける頂点について
　・距離が更新されていないならば(まだ到達していない頂点ならば)
　　距離を記録(今いる頂点の距離+1)
　　キューへ追加
(4)キューが空になるまで(2)~(3)を繰り返す

キューについて詳しくは「dequeについて」を御覧ください。

距離が確認できたら頂点Yから距離が減る方へ進みながら頂点番号を記録していきます。

dequeについて
dequeはリストのようなものですが、先頭から要素を取り出す操作をO(1)で行うことができます。
(リストだとO(N)かかります)
インポート：from collections import deque
作成：変数名=deque()
先頭(左端)に要素追加【O(1)】：変数名.appendleft(要素)
末尾(右端)に要素追加【O(1)】：変数名.append(要素)
先頭(左端)から要素を取り出して削除【O(1)】：変数名.popleft()
末尾(右端)から要素を取り出して削除【O(1)】：変数名.pop()

【使用例】

# インポート：from collections import deque
from collections import deque

# 作成：変数名=deque()
que=deque()

# 先頭(左端)に要素追加【O(1)】：変数名.appendleft(要素)
que.appendleft(1)

# 末尾(右端)に要素追加【O(1)】：変数名.append(要素)
que.append(3)

# 先頭(左端)から要素を取り出して削除【O(1)】：変数名.popleft()
x=que.popleft()

# 末尾(右端)から要素を取り出して削除【O(1)】：変数名.pop()
y=que.pop

詳しく知りたい人は以下のページを見てください。

【提出】

# 入力の受け取り
N,X,Y=map(int,input().split())

# 繋がっている頂点の記録
# connect[1]=[2,3,4]なら頂点1から頂点2,3,4へ行ける
connect=[[] for i in range(N+1)]

# (N-1)回
for i in range(N-1):
    # 入力の受け取り
    U,V=map(int,input().split())
    # 繋がっている頂点の記録
    connect[U].append(V)
    connect[V].append(U)

# 頂点Xからの距離
Dist=[-1]*(N+1)
# 頂点Xの距離は0
Dist[X]=0

# キューを用意
# インポート
from collections import deque
que=deque()

# (1)Xをキューへ追加
que.append(X)

# (4)キューが空になるまで(2)~(3)を繰り返す
while 0<len(que):
    # (2)キューの左端(先頭)から頂点を取り出す(今いる頂点)
    Now=que.popleft()

    # (3)今いる頂点から行ける頂点について
    # to：今いる頂点から行ける頂点
    for to in connect[Now]:
        # ・距離が更新されていないならば(まだ到達していない頂点ならば)
        if Dist[to]==-1:
            # 距離を記録(今いる頂点の距離+1)
            Dist[to]=Dist[Now]+1
            # キューへ追加
            que.append(to)

# 答え
ans=deque()

# 頂点Yの距離
Count=Dist[Y]

# 今いる頂点
Now=Y

# Countが1以上の間
while 0<Count:
    # 答えの左端(先頭)に今いる頂点を追加
    ans.appendleft(Now)

    # 今いる頂点から行ける頂点
    for to in connect[Now]:
        # 距離が(Count-1)である頂点を見つけたら
        if Dist[to]==Count-1:
            # Countをマイナス1
            Count-=1
            # その頂点へ移動
            Now=to

# 答えの先頭にXを追加
ans.appendleft(X)

# 答えの出力(*をつけるとカッコなしで出力できる)
print(*ans)

【広告】

『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

2
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
2
0