くろたんく雑記帳

日常とか、わんちゃんとか、機械学習とか、競プロとか、

MENU
トップ > AtCoder > Python3で解く AtCoder Regular Contest 109 A - Hands

Python3で解く AtCoder Regular Contest 109 A - Hands

AtCoder 競プロ 300点 ARC 条件分岐

状態を把握するのに、ちょっと時間はかかったが、イメージはできた。しかし場合分けが多く、そこにハマったのでまとめる

目次

概要

問題

  • 100階建ての建物 {\displaystyle A, B}がある。
  • {\displaystyle A_i}と{\displaystyle B_i}は廊下でつながっていて、{\displaystyle x}分かかる。
  • {\displaystyle A_{i+1}}と{\displaystyle B_i}は廊下でつながっていて、{\displaystyle x}分かかる。
  • {\displaystyle A_i}と{\displaystyle A_{i+1}}および{\displaystyle B_i}と{\displaystyle B_{i+1}}は階段でつながっていて、{\displaystyle y}分かかる。
  • 与えられた、{\displaystyle A}階から{\displaystyle B}階へ最短時間で移動したときの時間は？

解くときに考えた内容

まずイメージ図

f:id:black_tank_top:20201129095551j:plain
全体のイメージ

  • 文意から、１００階建ての建物 {\displaystyle A, B}は上の一番左のようになっている。
  • {\displaystyle y, 2x}の大小で降りる手段として、廊下か階段かを選択すべきかがわかり、最後は{\displaystyle B}へ移動するのに{\displaystyle x}という構図。降りるときと登るときとでことなるのは降りるときしか{\displaystyle B}へ移動できないので、そこで場合分けが必要。
  • まずは、{\displaystyle A, B}が同じフロアの場合、もしくは{\displaystyle A}から{\displaystyle B}が１階降りる場合。
    • {\displaystyle x}が最短。
      （なぜなら、{\displaystyle 1 \leq x, y \leq 100}なので、{\displaystyle x \lt x + y}は自明）
  • 次に２階以上降りる場合。
    • {\displaystyle B - A} を {\displaystyle step}とすると
    • {\displaystyle step \leq -2}ということ。
      • １階おりるのに{\displaystyle y \geq 2x}のとき、廊下を選んで{\displaystyle 2x}で {\displaystyle step-1}階降りて、最後に {\displaystyle x}で {\displaystyle B}へ行く
      • １階おりるのに{\displaystyle y \lt 2x}のとき、階段を選んで{\displaystyle y}で {\displaystyle step-1}階降りて、最後に {\displaystyle x}で {\displaystyle B}へ行く
  • 次に１階以上登る場合。
    • これ上記の{\displaystyle step-1}を{\displaystyle step}と考えればいい。

コード

a, b, x, y = map(int, input().split())
step = b - a
if step == 0 or step == -1:
    ans = x
# 下に-1を含めても良い。結果xになるから
elif step <= -2:
    if y >= 2 * x:
        ans = (abs(step)-1) * 2 * x + x
    else:
        ans = (abs(step)-1) * y + x
elif step >= 1:
    if y >= 2 * x:
        ans = step * 2 * x + x
    else:
        ans = step * y + x
print(ans)

終わりに

結構きれいに場合分けしないと、うまく行かない。絵に書けばだいたい分かるが、時間かかりすぎた。

参考になる書籍

けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」 ご本人の記事の中で難易度は、螺旋本ということで初学者でも非常に結構読みやすい!!!（実際に、けんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているし、この書籍も非常に読みやすい）どのようなステータスの人にもおすすめの一冊になっている。

とうとう発売され自分の手元にも来た（2020-10-03）。現在読み中なのである程度読み込んだら感想を書く予定。めっちゃ図が多いし、章末問題もあるしかなりイケてる。答えはC++で書かれているがそのうちPythonでも書かれるとのことなので、自分で前もってやってしまおうと思う（答え合わせできるのはありがたい）。

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

７章までは別記事に残してある。 blacktanktop.hatenablog.com