AtCoder Regular Contest 112 B – — – B をPython3で解く

Share

AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。

出典:
AtCoder Regular Contest 112 B – — – B

すぬけ君が整数やさんに行く話。謎の店である。問題のタイトルも少し面白い。
整数がどこからどこの範囲を取れるのかを考える必要があるが、一旦簡単な例で書き出してみると分かりやすいと思う。

じっくりと最後まで考察できれば、割とシンプルなコードで解ける。まぁ、コンテストの時はそうも行かなかったんだけど……そこは、通れば正義ということで。

# AtCoder Regular Contest 112 B - -- - B
# https://atcoder.jp/contests/arc112/tasks/arc112_b
# tag: 範囲 考察 交差判定 すぬけ君 整数屋

# ここでは、僕がどんな感じで考えたのかを書いておく。
# 公式解説とは少し違う流れだが、最終的には同じような
# ところに着地する。

# 以下、-1 倍するのを -B、1 引くのを --B と書く。
# まあ、Pythonには ++ や -- の演算子はないんだけど……。

# まず、元の数 B が正の場合と限定すると考えやすい。

# B が元の数以上になるためには、まず -B にしたあと
# 適当な回数(以下 x) --B し、最後にもう一度 -B してやる必要がある。
# 2 回 -B する必要があることを考慮すると、
# 0 <= x <= max(0, (C-2)//2) となる(C=1 の場合に注意)
# これで、B ~ B + x まで好きな数になれる。
# また、普通に --B の操作を繰り返すことで、B 以下の数字に
# なることもできる。
# ここまでをまとめると、-B を 0 回、もしくは 2 回行う場合、
# B - C//2 ~ B + max(0, (C-2)//2) の範囲で好きな数になれる。
# これを仮に p_min ~ p_max とする。

# 次に、可能な限り小さくすることを考えると、
# まず -B したあと、--B を行うことになる。
# この操作により、
# -(B + (C-1)//2) ~ -B の範囲を取れる
# また、まず --B をしたあと -B を行うことも可能で、
# その操作により
# -B ~ -(B - (C-1)//2) の範囲も取れる
# すなわち、-B を 1 回行う場合、
# -(B + (C-1)//2) ~ -(B - (C-1)//2) の範囲で好きな数になれる。
# これを仮に s_min ~ s_max とする。

# このように、反転 (-B) したところで終わる範囲と、そうでない範囲の
# 二つの範囲のみが問題となる。

# 元の数 B が負の場合は、単純に上記の p と s が反転したものとなる。
# 元の数 B が 0 の場合も、範囲の重なりが多少変になるが、
# 同様に考えて構わない。

# あとは、その二つの範囲 p_min ~ p_max, s_min ~ s_max が
# いくつの数を含むのかという問題になる。

# この二つの範囲が重なっている場合、その範囲は
# max(p_min, s_min) ~ min(p_max, s_max) となるので、

def main():
    B, C = map(int, input().split())

    p_min = B - C//2
    p_max = B + max(0, (C-2)//2)
    s_min = -(B + (C-1)//2)
    s_max = -(B - (C-1)//2)

    # それぞれの範囲を足し、あれば交差判定分を引く
    result = p_max - p_min + s_max - s_min + 2 \
            - max(0, min(p_max, s_max) - max(p_min, s_min) + 1)

    print(result)

main()
Share

コメントを残す

メールアドレスが公開されることはありません。