【AtCoder】ARC109の問題を初心者的書き方で解説する with Python
ここではAtCoderの問題を解説していきます。
AtCoderの解説は基本的にC++が多く、私のような初心者には難しく書かれていたりするため、
A~Cの問題を基本的な書き方で書いていきます。
分かりやすさ重視のため、コードの書き方も長く書いています。
そもそも自分がBeginnerなので、初心者の自分でもわかる必要最低限のスキルを使ってまとめていきたいと思います。
A問題 Hands
100階建ての建物 A , B があります。
について、建物Aの階とBの階は廊下で繋がれています。 また、について、建物Aの階とBの階は廊下で繋がれています。
どの廊下も双方向に通行可能で、移動には分かかります。 また、A,Bどちらの建物にも階段があり、について、同じ建物の階と階は階段で繋がれています。どの階段も双方向に通行可能で、移動には分かかります。建物Aの階から建物Bの階に移動するのにかかる最短時間を求めてください。入力は以下の形式で標準入力から与えられる。
解説にあるようにひとまとめに計算してもいいですが、分かりやすく場合分けをして考えてみました。
こういう問題は図を書いてイメージするのが大事ですね。
1.の場合
この場合は普通に廊下を分かけて渡るだけです。
仮に一つ別の解を利用した場合、階段を降りる(or上る)時間 + 廊下を渡る時間 + 階段を上る(or降りる)時間を計算しなければならず、
必ず分より大きくなります。
2.の場合
この場合はからに降りる場合となります。
この時、とりあえず先に建物Bまで移動して、そのあとどのように降りれば早いかを考えるとわかりやすいです。
AからBに移動する際には、斜めの廊下を使うのが一番早いです。この時点でとの階数差はになります。
そのあとどのように降りればよいかというと、以下の図のように2パターン考えられます。
すなわち、1階分降りる時間であるとを比較し、小さい方の値を選択すればいいことが分かります。
3.の場合
この場合はからに上る場合となります。
この場合は先にと同じ高さまで上り、(階数差は)そのあとBに普通の廊下を使って移動することを考えればよいです。
この際、2と同様にとのどちらが早いかを考えて選択すればよいです。
解答は以下の通り。
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)