AtCoder-ARC112 B - -- - B【Python解答例】
AtCoder Regular Contest112でB問題までACの2完でした。
提出したB問題の解答を記事にしていきます。
atcoder.jp
AtCoder Regular Contest112 B - -- - B
問題文
すぬけくんは、整数 B を持って整数やさんを訪れました。 整数やさんでは、お金を払うことで、持っている整数を別の整数にしてもらうことができます。
具体的には、次の 2 種類のサービスを好きな順で好きなだけ購入することができます。
・1 円を払い、持っている整数を −1 倍する。
・2 円を払い、持っている整数から 1 を引く。
すぬけくんが C 円以内で作ることのできる整数は何通りありますか?
制約
・−10^18≤B≤10^18
・1≤C≤10^18
・入力はすべて整数
解答例
b, c = map(int,input().split()) if b < 0: b *= -1 c += 1 if b == 0: print(c) elif c <= 2: print(c + 1) elif c <= 2 * b: print(2 * c - 1) else: print(4 * b - 1 + (c - 2 * b) )
解説
整数Bをもっているすぬけが持っているお金Cをはらって何通りの整数をもつことができるか解答する問題です。
1円払えばBを- B に、2円払えばBをB - 1に変えることができます。
整数Bは負の値をとることもあります。
条件分けが複雑でしたがコンテストで解答したのは4通りの場合分けを行いました。
つぎの条件はすべてBが正の整数のときです。
ひとつめは最初にもっているBが0の場合です。
B = 0、C = 3 のとき、作ることのできる整数は(0, -1, 1)の3通り、つまりC通りになります。
C = 1 のばあい、0 × -1 = 0ですので1通り(= C通り)なのでB = 0の場合はCを出力すればOKです。
ふたつめはCが2以下(B は0でない)の場合です。
C = 1のとき、作ることができるのはBと- Bの2通りです。
C = 2のときはB, -B, B - 1 の3通りです。
なのでCが2以下の場合はC + 1通りとなります。
みっつめはCがBを2倍した値以下の場合です。
このときは2円しか払わずにBからできるだけ1を引いていっても0までにしかならない範囲になります。
B = 3, C = 4のとき作ることができる数は[3, -3, 2, -2, 1, -4, 4]です。
3 → -3 → -4 → 4 のようにBより大きい正の整数をとることがあるのに気づくのに時間がかかりました。
このときの組み合わせの数は2 × c - 1通りです。
よっつめはCがBを2倍した値より大きい場合です。
C = 2 × Bのとき2 × C - 1 = 4 × B - 1通りの組み合わせがあります。
それよりCが大きくなると、C - 2 × Bの値だけ上記に追加されます。
したがって4 × b - 1 + (c - 2 × b) 通りとなります。
さいごにBが負の値の場合は-Bと正の値に変換して、Cに1を足すことで置き換えることができました。
この場合分けをおこなうことでACでした。
解説を読むともっとスマートに考えることができるようです。
実際に作ることができる数字を書き出してがつがつ数式化することで解けましたが、スマートに解けたらいいですね。
どうしてもコンテスト中はあせってしまい冷静さを保つことが大変でした。
落ち着いて条件を考えていきたいです。
ARC112の関連記事はこちら
ebisuke33.hatenablog.com