くろたんく雑記帳

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

MENU

Python3で解く AtCoder Beginner Contest 185 D - Stamp

AtCoder 競プロ ABC-D 切り上げ

結構単純な、数え上げするだけ。 問題を把握するのに、少しだけ苦戦したがよく読んだらDにしては結構単純だった。

目次

概要

問題

問題概要は省略。

解くときに考えた内容

  • 最初と最後を同等に考えられる様に{\displaystyle 0}と{\displaystyle n+1}をリスト{\displaystyle a}に加える。
    （元のリスト{\displaystyle a}のうち、最初と最後の値を同等に扱える必要にするため結構キモ）
  • 更にソートする。
    • 具体的に言うと入力例１だと{\displaystyle [1, 3]} → {\displaystyle [0, 1, 3, 5]}
  • 0以上の差分のリストを作成する（間にいくつ数値があるかという意味で）
    • {\displaystyle [0, 1, 3, 5]} → {\displaystyle [1, 1]}
  • この時点で、0以上の差分のリストに値がなければ、白がないということ。
  • {\displaystyle k}は0以上の差分のリストの最小値になる。
    • そうでないと、どう取ってもかならず白を含んでしまうため
  • 差分のリストに含まれる値を{\displaystyle k}で割って、切り上げた値を足し上げていく。
    • 切り上げのイメージはX：白、O：青、△：赤として、XOOOOOXを例えばで{\displaystyle k=2}で△で埋めていくことを考えると割り切れる範囲はX△△△△OXのようなイメージで割り切れない部分は１度重なるようにしてX△△△△△Xとする必要があるから、切り上げするイメージ。

コード

n, m = map(int, input().split())
a = [int(x) for x in input().split()]
# 最初と最後を同等に考えられる様に
# 0とn+1をリストに加える
a.append(0)
a.append(n+1)
# print(a)
num = len(a)
a_s = sorted(a)
l = list()
for i in range(num-1):
    c = (a_s[i+1] - a_s[i] - 1)
    # print(c)
    if c > 0:
        l.append(c)
# print(l)
if len(l) == 0:
    print(0)
else:
    k = min(l)
    cnt = 0
    for i in l:
        # 切り上げ
        if i % k == 0:
            cnt += i // k
        else:
            cnt += i // k + 1
    print(cnt)

参考になる書籍

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

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

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

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

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

AtCoder Beginner Contest 185 参加ログ・感想

参加ログ AtCoder 競プロ

意味不明なやり方して頭大混乱で、絶対に落としちゃいけないCを落としてしまった・・・

内容

  • Python3でやっている。
  • 参加ログ。
  • 所感。
  • コンテスト中に何を考えたか。
  • コンテスト後に解説をみたり、少し整理したりしたくらいの内容。
  • 問題の詳細で細かく書こうと思うものは別記事とする。

結果

AB完。Cはただのコンビネーションでとにかく１１箇所を選ぶだけの計算だったのにわけわからんこと考えて終了なぜパニクるのかもよくわからんし、さらにPythonならオーバーフロー気にせずできる。Dは、マスのリストをソートして、差分を取って、一番小さい値で差分を割って切り上げを足すだけ。あとから考えると結構ラッキー回だったのにできなかったのは実力不足Orz

どう考えたか + α

問題

A - ABC Preparation

問題タイプ：最小値

文意から問題数が最も小さい値が答え。

a = [int(x) for x in input().split()]
ans = min(a)
print(ans)
B - Smartphone Addiction

問題タイプ：クエリ処理・条件分岐 初期に持っているバッテリー値{\displaystyle n}に対して、

  • 以降の変化するバッテリー値{\displaystyle bat} とする。
  • {\displaystyle a} - 前回の{\displaystyle b}の値({\displaystyle \_b})を引く。（状況：歩いている時間）
    • 初回は{\displaystyle a}を引く。
    • この時に{\displaystyle bat \leq 0} になったら'No'
  • {\displaystyle b - a}を足す。（状況：カフェで充電）
    • この時に{\displaystyle bat \gt n} になったら{\displaystyle bat = n}とする。（状況：満充電）
  • 次のクエリの{\displaystyle a}と引き算するために{\displaystyle b}を保持しておく。（状況：カフェ出た時間の保持）

なんか、結構条件をきちんと書き上げるだけなんだけど、条件分岐も多くて結構ハマった。

n, m, t = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
_b = 0
bat = n 
for a, b in ab:
    _a = a - _b
    _b = b - a 
    bat -=  _a
    if bat <= 0:
        print('No')
        exit()
    bat += _b
    if bat > n:
        bat = n
    _b = b
if t - _b < bat:
    print('Yes')
else:
    print('No')
C - Duodecim Ferra

問題タイプ：組み合わせの数え上げ

文意から、とにかく{\displaystyle 11}箇所切るところを選ぶ選び方。つまり{\displaystyle _{L-1}C_{11}} Pythonの場合はオーバーフローは気にせず。分子と分母を別々に計算して割り算するだけ。

l = int(input())
# l-1から11を選ぶ選び方    
a, b = 1, 1
for i in range(1, 12):
    # 分子
    a *= l-i
    # 分母
    b *= i
print(a//b)

おわりに

今回は、絶対わからんっていう感じでもなかったのに、解ききれないといった感じ。またRatingは少し下がってしまった。沼はまだ深い・・・。

参考になる書籍

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

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

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

7章までPythonで章末問題をこなしていっている。

blacktanktop.hatenablog.com

Python3で解く AtCoder Regular Contest 110 B - Many 110

AtCoder 競プロ ARC 400点 条件分岐

きれいに条件分岐ができればいい。

最初'0'にアサインできたら、最後、左から数えて何番目の'0'にアサインできるかを考える問題

概要

問題

  • 文字列{\displaystyle s}は'110'が{\displaystyle 10^10}個連結したものである。
  • {\displaystyle n}文字の文字列{\displaystyle t}が与えられる。
  • {\displaystyle s}に{\displaystyle t}が連続する部分文字列としていくつ含まれる？

解くときに考えた内容

  • {\displaystyle t}の長さ別に考える。
  • {\displaystyle t}が1文字の場合
    • {\displaystyle t} = '1'の場合
      • {\displaystyle 2 \times 10^{10}} ('110'に2つ'1'があるから)
    • {\displaystyle t} = '0'の場合
      • {\displaystyle 10^{10}} ('110'に1つ'1'があるから)
  • {\displaystyle t}が2文字の場合
    • {\displaystyle t} = '11'と'10'の場合
      • {\displaystyle 10^{10}} ('110'に1つ'11'または'11'があるから)
    • {\displaystyle t} = '01'の場合
      • {\displaystyle 10^{10}-1} (最後の1つは取れないので-1)
    • {\displaystyle t} = '00'の場合
      • {\displaystyle 0}（このパターンはないので）
  • {\displaystyle t}が3文字以上の場合は0が {\displaystyle 10^{10}}があるので、{\displaystyle t}の0のどこまでアサインできるかということになる。
    • {\displaystyle t}の長さを3で割って切り上げる。
    • この値は{\displaystyle t}に含まれる0の個数であり、cntとする。
    • ここで、'110'をcnt分連結した文字列に含まれるかどうかで、カウント対象であるかと、その文字列が0で終わっているのか1で終わっているのかを同時に判定する（結構キモ）
    • '110'をcnt分連結した文字列にtが含まれるなら、tが0終わりでsに存在ということ。
      • 例えば、
        • 0110とすると、cnt = 2であり、{\displaystyle s}の0の最後……11'0110'、{\displaystyle 10^{10} - 1}個目まで取れる。
        • 0110110とすると、cnt = 3であり、{\displaystyle s}の0の最後……11'0110110'、{\displaystyle 10^{10} - 2}個目まで取れる。
      • 一般に、{\displaystyle 10^{10} - (cnt - 1)}となる。
    • '110'をcnt分連結した文字列にtが含まれず、'110'をcnt分+1連結した文字列にtが含まれるなら、tが1終わりでsに存在ということ。
      • 例えば、
        • 011とすると、cnt = 1であり、{\displaystyle s}の0の最後……11'011'0、{\displaystyle 10^{10} - 1}個目まで取れる。
        • 011011とすると、cnt = 2であり、{\displaystyle s}の0の最後……11'011011'0、{\displaystyle 10^{10} - 2}個目まで取れる。
      • 一般に、{\displaystyle 10^{10} - cnt}となる。
      • これらに当てはまらないものは {\displaystyle s}に{\displaystyle t}が含まれないので {\displaystyle 0}

f:id:black_tank_top:20201206095202j:plain
部分文字列のカウントイメージ

上図のように、 {\displaystyle t}が3文字以上で{\displaystyle s}に含まれるその他のパターンも同じ様に書いてみると、最初'0'にアサインできたあと、最後の左から数えて何番目の'0'にアサインできるかを考える問題であると言うことがわかる。

コードは全場合分けベースで書いたものと、 {\displaystyle t}が2文字のものも3文字のものと同様に考えて問題ないので、２種類にかき分けた。

コード

全部場合分け
n = int(input())
t = input()
m = 10**10
# 切り上げ
if len(t) % 3 == 0:
    cnt = len(t) // 3
else:
    cnt = len(t) // 3 + 1
# sにｔが存在する出力パターン
# tのサイズが1のとき
if t == '1':
    print(2*m)
elif t == '0':
    print(m)
# tのサイズが2のとき
elif t == '11' or t == '10':
    print(m)
elif t == '01':
    print(m-1)
elif t == '00':
    print(0)       
# tのサイズが3以上のとき
elif len(t) >= 3:
    # この書き方ならt = 0, 11などもここに含めても可能
    # 個数倍復元して含まれているなら、tが0終わりでsに存在
    if t in '110' * cnt:
        print(m-cnt+1)
        exit()
    # 上記でなくて個数倍+1で復元して含まれているなら、tが1終わりでsに存在
    elif t in '110' * (cnt+1):
        print(m-cnt)
        exit()
    # 上記以外はsにｔが存在しない出力パターン  
    else:
        print(0)
最低限
n = int(input())
t = input()
m = 10**10
if len(t) % 3 == 0:
    cnt = len(t) // 3
else:
    cnt = len(t) // 3 + 1
# tが1のとき
if t == '1':
    print(2*m)
    exit()
# それ以外の時（tが0や、2文字以上のときはこの記述で集約できる）
if t in '110' * cnt:
    print(m-cnt+1)
    # 上記でなくて個数倍+1で復元して含まれているなら、tが1終わりでsに存在
elif t in '110' * (cnt+1):
    print(m-cnt)
# 上記以外はsにｔが存在しない出力パターン  
else:
    print(0)

参考になる書籍

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

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

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

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

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

Python3で解く AtCoder Regular Contest 110 A - Redundant Redundancy

AtCoder 競プロ ARC 300点 最小公倍数

問題の制約がゆるすぎて、{\displaystyle n=30}のときの答えをprintするだけで終わる。

print(2329089562801)

なので、解説記事としては候補のうち最小という状態で考えるとした場合にする。

目次

概要

問題

  • 整数{\displaystyle n}が与えられる。
  • {\displaystyle 2} から{\displaystyle n}までのすべての整数で割って余りが{\displaystyle 1}になるような{\displaystyle n} 以上 {\displaystyle 10^{13}}以下の値は？

この制約が甘いので、{\displaystyle n}がどんな値でも{\displaystyle n=30}のときの答えを書けば良くなる。

解くときに考えた内容

上記のような事があるとしても、考え方としては、{\displaystyle n=30}でも一緒。

文意から、{\displaystyle 2} から{\displaystyle n}までのすべての整数で割り切れる数に{\displaystyle 1}を足せば、条件を満たす。

ちなみに記事冒頭の値は、30以内の素数を何回かかけた値のうち30以内のものをかけ合わせた値+1である

# 上記のコードでn=30としたときの値を入れてもACにはなる
print(2329089562801)
# ちなみにこれは、30以内の素数を何回かかけた値のうち30以内のものをかけ合わせた値+1である
# 30以内の素数：2, 3, 5, 7, 11, 13, 17, 19, 23, 29
print(2**4 * 3**3 * 5**2 * 7 * 11 * 13 * 17 * 19 * 23 * 29 + 1)
# 2329089562801

コード（候補のうち最小とするならば以下）

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)
def lcd(a, b):
    return int(a / gcd(a, b)) * b
def mod_lcd(n, mod):
    ans = 1
    for i in range(2, n+1):
        ans = lcd(ans, i)
    return ans + mod  
n = int(input())
ans = mod_lcd(n, 1)
print(ans)

参考になる書籍

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

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

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

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

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

Python3で解く AtCoder Beginner Contest 153 D - Caracal vs Monster

AtCoder 競プロ ABC ABC-D パターン発見

愚直に、1~hまでどんな風になるかをリストで残そうとすると、TLEになる様な制約なので、いい感じのパターンを見つける必要がある。
どんな人数になるかがちょっとよくわからないので、とりあえず書き出す。そうするとパターンが見えてくる。

目次

概要

問題

  1. モンスターが1体いて体力は{\displaystyle h}。
  2. モンスターを攻撃する。
  3. その時にモンスターの体力が {\displaystyle 1}なら倒せる。
  4. その時にモンスターの体力が {\displaystyle 1}より大きい時は、体力が半分（切り下げ）になって、２体になる。
  5. 攻撃回数の最小となるような攻撃回数は？

解くときに考えた内容

  • サンプルをみると、1, 3, 3, 7となっている。
  • DPっぽくやるのかなとおもったけどモンスターの体力の制約が {\displaystyle h \leqq 10^{12}}なので、無理そう。
  • モンスターの体力が {\displaystyle h}が1, 3, 7, 15の時は攻撃回数も1, 3, 7, 15。 モンスターの体力が {\displaystyle h}が1, 2, 4, 8の時は攻撃回数も1, 3, 7, 15。 つまり、hが{\displaystyle 2 ^ i \leq h \leq 2 ^{i+1}-1}の範囲であれば、必要な攻撃回数は{\displaystyle 2 ^{i+1}-1}ということになる。 (画像に番目って書いてあるけどhの値だったな。。。)
    f:id:black_tank_top:20200723082157j:plain
    hが2i~2i-1のモンスターを倒すのに必要な攻撃数のイメージ
  • なので、{\displaystyle 2 ^ i \leqq h}まで調べれば良いので{\displaystyle O(logN)}

コード

h = int(input())
ans = 1
if h >= 1:
    i = 0
    while 2**i <= h:
        ans = 2**(i+1) - 1
        i += 1
print(ans)

参考になる書籍

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

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

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

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

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

Python3で解く AtCoder Regular Contest 109 B - log

AtCoder 競プロ 400点 ARC

長さ{\displaystyle n+1}の丸太を買って、短い方から丸太を作れるだけ作って、残りは買う。{\displaystyle n } -（作れるだけ作った数）+ 1が答え。作れるだけ作った数をどうかんがえるかがポイント

目次

概要

問題

  • 長さ{\displaystyle 1}から{\displaystyle n}の{\displaystyle n}種類の丸太がほしい。
  • 長さ{\displaystyle 1}から{\displaystyle n+1}が各{\displaystyle 1}ずつ、各1円で売ってる。
  • 自由に切ってよい。例えば長さ{\displaystyle 5}の丸太を長さ{\displaystyle 2}と長さ{\displaystyle 3}としていい。
  • 余ったものは捨ててよい。
  • このとき、{\displaystyle n}が与えられたときに、長さ{\displaystyle 1}から{\displaystyle n}の{\displaystyle n}種類の丸太を用意する最小の金額は？

解くときに考えた内容

  • 長さ{\displaystyle n+1}の丸太を買って、短い方から丸太を作れるだけ作って、残りは買う方針でいく。これが最小なのは自明ではないが、証明はしない。

  • {\displaystyle n+1}から作れるだけ作るときに長さ{\displaystyle 1, 2, ... k}の{\displaystyle k}の最大値を求める必要がある。

  • {\displaystyle 1, 1+2, 1+2+3, ... 1+2+3+..+k}のような数列と{\displaystyle n+1}を比較して、最大の{\displaystyle k}を求めたい。

  • 等差数列の和の数列なので、{\displaystyle \frac{k(k+1)}{2}}のリストを制約分作ってもいいけど、作ると終わらない。

  • bisectはリストが無いとできないので、ここでは使えない。

  • ここでは、リストがない状態での二分探索を行う必要がある。（これまで、なぜわざわざこのような実装しているのかわからないときがあったが、このような状況のときに有効ということがわかった。）

普通の二分探索の実装で、{\displaystyle n+1}とmidの値と比較するべきところを{\displaystyle n+1}と等差数列の和として{\displaystyle \frac{mid(mid+1)}{2}}を比較するようにして、探索していくようにする。

コード

def log_cut(n):
    l = 0
    r = n
    while r - l > 1:
        mid = (l+r) // 2
        # ここの比較がポイント
        # リストも与える二分探索だとlist[mid]とn+1を比較するが
        # 今回はリストではなく、mid自体の値を使って、等差数列の和と比較する。
        if mid * (mid+1) // 2 <= (n+1):
            l = mid
        else:
            r = mid 
    return l
    n = int(input())
# これが作れる分のkの最大値
max_log = log_cut(n)
# n - max_log（買う分）+ （1, 2, ... , kは１本）
ans = n - max_log + 1
print(ans)

参考になる書籍

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

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

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

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

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

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