【AtCoder】ARC109の問題を初心者的書き方で解説する with Python

ここではAtCoderの問題を解説していきます。
AtCoderの解説は基本的にC++が多く、私のような初心者には難しく書かれていたりするため、
A~Cの問題を基本的な書き方で書いていきます。
分かりやすさ重視のため、コードの書き方も長く書いています。
そもそも自分がBeginnerなので、初心者の自分でもわかる必要最低限のスキルを使ってまとめていきたいと思います。

A問題 Hands

100階建ての建物 A , B があります。
i=1,\cdots,100について、建物Aの\,i\,階とBの\,i\,階は廊下で繋がれています。 また、i=1,\cdots,99について、建物Aの\,i+1階とBの\,i階は廊下で繋がれています。
どの廊下も双方向に通行可能で、移動には\,x分かかります。 また、A,Bどちらの建物にも階段があり、i=1,\cdots,99について、同じ建物の\,i階と\,i+1階は階段で繋がれています。どの階段も双方向に通行可能で、移動にはy分かかります。建物Aのa階から建物Bのb階に移動するのにかかる最短時間を求めてください。

入力は以下の形式で標準入力から与えられる。
a \hspace{1cm}b \hspace{1cm}x\hspace{1cm}y

解説にあるようにひとまとめに計算してもいいですが、分かりやすく場合分けをして考えてみました。
こういう問題は図を書いてイメージするのが大事ですね。

f:id:amadeus_salieri:20201201174729j:plain

1.a=bの場合
この場合は普通に廊下をx分かけて渡るだけです。
仮に一つ別の解を利用した場合、階段を降りる(or上る)時間y + 廊下を渡る時間x + 階段を上る(or降りる)時間yを計算しなければならず、
必ずx分より大きくなります。


2.a>bの場合
この場合はaからbに降りる場合となります。
この時、とりあえず先に建物Bまで移動して、そのあとどのように降りれば早いかを考えるとわかりやすいです。

AからBに移動する際には、斜めの廊下を使うのが一番早いです。この時点でabの階数差はa-1-bになります。

そのあとどのように降りればよいかというと、以下の図のように2パターン考えられます。

f:id:amadeus_salieri:20201201175528j:plain

すなわち、1階分降りる時間である2xyを比較し、小さい方の値を選択すればいいことが分かります。


3. a < bの場合
この場合はaからbに上る場合となります。
この場合は先にbと同じ高さまで上り、(階数差はb-a)そのあとBに普通の廊下を使って移動することを考えればよいです。
この際、2と同様に2xyのどちらが早いかを考えて選択すればよいです。


解答は以下の通り。

a,b,x,y = list(map(int, input().split()))
 
#同じ階の場合
if a == b:
    print(x)
 
#降りる場合
elif a>b:
    if 2*x<=y:
        print(x + (a-1-b)*2*x)
    else:
        print(x + (a-b-1)*y)
 
#上る場合
else:
    if 2*x<=y:
        print((b-a)*2*x + x)
    else:
        print((b-a)*y + x)