見出し画像

[ABC270Python]トヨタ自動車プログラミングコンテスト2022(AtCoder Beginner Contest 270))A～C問題Python解説

Kai

9月24日に行われました、ABC270の解説記事です。
質問等はコメントにてお願いいたします。

A問題

A, B = map(int, input().split())
question = [0 for i in range(3)]

for i in [A, B]:
    if i == 7:
        question[0] += 1
        question[1] += 1
        question[2] += 1
    elif i == 6:
        question[1] +=  1
        question[2] += 1
    elif i == 5:
        question[0] += 1
        question[2] += 1
    elif i == 4:
        question[2] += 1
    elif i == 3:
        question[0] += 1
        question[1] += 1
    elif i == 2:
        question[1] += 1
    elif i == 1:
        question[0] += 1
ans = 0
if question[0] >= 1:
    ans += 1
if question[1] >= 1:
    ans += 2
if question[2] >= 1:
    ans += 4
print(ans)

もうちょっと簡単にできたかもしれませんが、
A問題は特にTLEを気にする必要がない問題が多いので、
全部書き出すという方法をとる問題も頻出しますので、
書き間違えに注意しながら全部書き出すのも
一つの解法です。

大まかな流れとしては、
髙橋君、青木君それぞれに対して、
それぞれの問題が解けたか確認し、
それぞれの問題に対して、解けた人数(0人or1人or2人)
を計測します。
最後に1人以上解けた問題に関してはすぬけ君も解けたと判断し、
すぬけ君の合計点数を出力します。

「すぬけ君の点数は一意に定まることが証明できます。」
という記述から、
髙橋君、青木君についても合計点数から
3問の問題それぞれが解けたのかどうかを確認することができます。
例えば、A(高橋君)=5だとしたら、
1点の問題と4点の問題を解くことができて、
2点の問題を解くことができなかった
という組み合わせしか考えられません。

よって、上記の方法を順番にスクリプトに書くことで答えを導きだすことができます。

B問題

X, Y, Z = map(int, input().split())

if X < 0:
    X = -X
    Y = -Y
    Z = -Z

direct = [i for i in range(0, X)]

if Y not in direct:
    print(X)
elif 0 < Z < Y:
    print(X)
elif Z < 0:
    print(-2*Z + X)
else:
    print(-1)

イメージはしやすい問題ですので、
しっかり問題文を理解することができれば解くことができます。

髙橋君がゴールに到達できるのは以下の2とおりですね。
①ゴールまで壁がなく、そのままゴールできる。
②ゴールの前に壁があるが、壁の前にハンマーがあり、ハンマーで壁を壊すことによってゴールできる。

まずは高橋君は原点にいますので、
正の方向に進もうが、負の方向に進もうがX,Y,Zの全ての符号を変えれば問題ありません。
なので、Xが負の場合はYとZの符号も変えておきましょう。

次に原点からゴールまでの道のりをリストdirectに入れて確認します。
これがゴールまでに通る箇所になりますね。

最後に条件分岐です。
まずは、directにYが含まれていない、
つまり壁に出会わずゴールできるときは、
ゴールにそのままいけますので、
Xを出力します。
続いて、原点＜ハンマー＜壁＜ゴールとなっている場合は、
ハンマーを拾って壁をなくし、ゴールに進めるため、
最短距離はXとなり、
Xを出力します。

ここで、入力例2のように、
負のエリアにハンマーがある場合、
一度負の方向にハンマーを取りに行き、
再度ゴールの方向に向かうという場合があります。
つまり、ハンマー＜原点＜壁＜ゴールとなるときです。
この場合はハンマーを取りに行くZと
原点に戻るZ、
ゴールに行くＸがかかりますので、
答えは2Z+Xとなります。(この時Ｚは負の値になることに注意。)

これ以外でゴールに行く方法はありません。
-1を出力します。

C問題

import sys
 
sys.setrecursionlimit(10 ** 7)
n, x, y = map(int, input().split())
 
edge = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    edge[a].append(b)
    edge[b].append(a)
 
ans = [x]
 
 
def dfs(a, b):
    # print(a)
    if a == y:
        print(*ans)
        exit()
    for to in edge[a]:
        if to == b:
            continue
        ans.append(to)
        dfs(to, a)
        ans.pop()
 
# print(edge)
dfs(x, False)

C問題でDFSが出るとは思いませんでした。
全体のレベルが上がっているため、問題の難しさも
上がってきています。

DFSについてよく分かっていない場合は
以下等を参考にしてください。
レベルが上がってくると頻出テーマになってきます。

まずは、入力値から木をイメージする配列edgeに直します。
要素iからどこに繋がっているのかを表す配列edgeです。

そして関数dfsを作っていきます。
引数としてaとbを設定していますが、
aは今いる地点、bは1個前にいた地点だと考えてください。

DFSに追加する機能としては、訪れた場所を記録していく機能です。
配列ansに訪れたら記録していきます。
最初に頂点Xにいるので、ansにはXを入れておきます。

まず、a=yつまり、今頂点Yにいる場合は作業としては終了なので、ansを出力して終了します。

次にaからいける箇所について考えます。
先程作ったedgeを使うことで、次どこに行けるかが分かります。
まず、to == bの所ですが、これはループを避けるために行います。
どういうことかというと、例えば1と2が繋がっているとき、
1から2に移動したのに、2から1に戻ってしまったら意味がないですよね。
直前に来た場所には戻らないように設定します。
continueでそれ以下の工程をスキップできます。

続いて、移動することができたらその場所をまずansに記録します。
これで、DFSの大部分は終了したわけですが、
新しく今いる場所からさらに違う場所に繋がっている場合は
さらにこれまでと同様にDFSを続けていきます。
これが再帰関数と呼ばれるやつですね。
今度はaが今いる場所なので、a = to
bが1個前にいる場所なので、b = a
となりますね。

ans.pop()の箇所ですが、
最後までDFSをした結果、結局頂点Yにたどり着かなかった場合
(入力例1の場合は頂点4)は、
そこに行ったことが意味のない移動だったため、
訪れたリストansから削除します。

最後にDFSを実装して終了です。
実装はdfs(x, False)でできます。
最初にいる箇所は頂点X、一個前にいる箇所はないので、
Falseと設定します。

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