ABC407の感想戦

at_coder, python
目次

AtCoder Beginners contes 407 に参加して、今回は A, B, C の 3 問のみ正解できた。どのように回答を導いたのか感想戦で復習する。

ソースコードはGitHubを参照

A - Approximation

２つの整数$A$と$B$（共に$\ge1$）が与えられ、$\dfrac{A}{B}$に最も近い整数を答える問題。

  • $B$は 0 にならないので、割り算の例外をかんがえる必要はない。
  • 最も近い整数ということなので、少数を四捨五入して整数にすれば良い。ちょうど$.5$の時は上下どちらも同じ差だけど、四捨五入ということで大きい数字に寄せる。

ここで Python で四捨五入する関数としてround()があるが、

round(1.5) == round(2.5)

となるので、大きい数字に寄せるという方針をどうするか。

そこで、$A$と$B$共に正の整数なので割った結果に$0.5$を加えて小数点以下を切り捨てることにしました。

import math

a, b = map(int, input().split())

print(math.floor(a / b + 0.5))

ただ考えてみれば、$.5$の時は上下どちらも同じ差なのでどちらに寄せても正解になる。それならば、round()を使ったほうがシンプルでmath.floor()を使うより良かったかも。

a, b = map(int, input().split())

print(round(a / b))

B - P(X or Y)

2 つのサイコロを振って次のいずれかの条件を満たす目が出る確率を求める問題。

  1. $(サイコロA + サイコロB) \ge X$
  2. $|サイコロA - サイコロB| \ge Y$
  • B 問題なので、難しく考えないで全ての組み合わせを作って条件を満たすか調べる。
  • $サイコロA$と$サイコロB$は区別がつかないが、$(1,2)$と$(2,1)$が区別できないとすると確率の計算が面倒なので区別することにする。
  • $サイコロA$と$サイコロB$を区別したときの各組み合わせの確率は、$(\dfrac{1}{6})^2 = 0.0277…$
ABC407_B.py
x, y = map(int, input().split())

comb = set()
for a in range(1, 7):
    for b in range(1, 7):
        if (a + b) >= x:
            comb.add(f"{a}, {b}")
        elif abs(a - b) >= y:
            comb.add(f"{a}, {b}")

if len(comb) == 0:
    # this is not required if 0.0 is acceptable.
    print(0)
else:
    print(len(comb) * ((1/6) ** 2))

条件 1 と条件 2 の両方を満たす組み合わせがあったらと思い、条件を満たす組み合わせを入れるためにset型を使用したがif ~ elif ~なのでList型で十分だった。

また、条件に一致する組み合わせがなかった時に掛け算をしてしまうと結果がfloat型になり0.0となる。サンプルの回答例に合わせるために0と比較しているが、これは不要だった。

C - Security 2

A と B のボタンがあり、このボタンを押す組み合わせで指定の数列を作るために必要な操作回数を答える問題。

  • A ボタンを押すと桁が増える。
  • B ボタンを押すと全ての数字に 1 が加算される。加算結果は繰り上がりしないで常に１桁。

ということで、数字の桁数は A ボタンを押した数となる。数字を変える B ボタンの操作回数をどのように計算するかが核心となる。

  1. A ボタンを押すと数列の最後に$0$が加えられるので、最後にある数が最後に加えられたということになる。よって最後が$7$ならば、A ボタンを押された後に B ボタンが 7 回押されたということが分かる。

  2. そして一桁上の数字は、その７回と、それ以前の B ボタンを何回か押された結果を示している。それならば、最後の桁数を作った’回分を引くと、最後の桁を作るための A ボタンを押す直前の値が分かる。入力例 2 の$407$なら、$0$から$7$を引いて$3$だったことが分かる。

  3. これを先頭の数字まで繰り返すと B ボタンを押した合計回数を計算できる。

ただし、これを素直に全ての桁を逆操作して A ボタンが押される前の状況を作っていると制限時間オーバーになってしまう。

そこで、個別に B ボタンが押された回数をかんがえるのではなく、桁を移動する時にこれまでの B ボタン操作回数の合計を持ってくることにした。例えば入力例 2 の$407$で、先頭の$4$を考える場合、$7+3$の合計 10 回操作されていたことがわかります。そこで現在の値$4$から$10$を引きます。ただし１桁だけを考えるので 10 で割った余りを引き算します。

ABC407_C.py
s = list(map(int, list(input())))

num_a = len(s)

num_b = 0
for i in range(num_a - 1, -1, -1):
    n = s[i]
    num_b += n

    s[i - 1] = (10 + s[i - 1] - num_b % 10) % 10
print(num_a + num_b)

なお、引き算する時に$10$を加算しておいて、最後に 10 で割った余りを求めると引き算結果が負になった時を考えなくて良くなります。

与えられた数列を数字が与えられたと考えてint(input())で受けてしまうと、先頭に$0$があった場合にその部分を無視して桁数を誤るしまうことになる。

D - Domino Covering XOR

マップ上の各セルには数字書かれたおり、ドミノで連続する２セル毎に消してゆき、残りの数字を$XOR$した結果の最大値を答える問題。

$XOR$なので、２進数で表してどうやって各桁の 1 が奇数個残るようにするかだと思うけど、分からなかった。全探索でということだけど、それをどう結びつけるのかが分からない。