ABC274の振り返り(A, B, C, D)

振り返りです。

def test_all(f): for i, data in enumerate(eval(f'test_data{f.__name__[0]}')): exp = data["out"] ans = f(*data["in"]) result = "AC" if exp == ans else "WA" print(f"{i+1} {result}: expected: {exp}, output: {ans}")

A - Batting Average

やってみよう！

A関数を完成させて「Run」ボタンをクリックしよう！

def A(A, B): pass A(7, 4) # 0.571 A(7, 3) # 0.429 A(2, 1) # 0.500 A(10, 10) # 1.000 A(1, 0) # 0.000

自由欄

try

既視感が半端ないですが、とりあえずこんな感じでAC。

def A(A, B): print(f'{B/A:.03f}') A(7, 4) # 0.571 A(7, 3) # 0.429 A(2, 1) # 0.500 A(10, 10) # 1.000 A(1, 0) # 0.000

結果：#35867401

自由欄

解説

2週続けて四捨五入することになるとは…
pythonのround関数が偶数丸めなのは前回振り返った通りですが、Fストリングで少数の精度を指定した場合も同様の挙動となります。

for i in range(10): x = i + 0.5 print(f'{x}=> round:{round(x)} f-string:{x:.0f}')

という訳で上の提出では本来ダメなのですが、解説によると本問の制約下では偶数丸めになるような数字は出ないことが証明できるらしいです。(どうやんだ…🤔)

それはそれとして、ユーザー解説で使っている四捨五入のテクニックをメモっておきます。
「5を足して10で割る」というは分かりやすくていいですね。

def A(A, B): print(f'{(B*10000/A + 5) // 10 / 1000:.3f}') A(7, 4) # 0.571 A(7, 3) # 0.429 A(2, 1) # 0.500 A(10, 10) # 1.000 A(1, 0) # 0.000

自由欄

B - Line Sensor

略

zip転置で一発の問題です。
結果：#35870973

自由欄

C - Ameba

やってみよう！

C関数を完成させて「Run」ボタンをクリックしよう！

test_dataC = [ { "in":[2, [1, 2]], "out": """0 1 1 2 2 """ },{ "in":[4, [1, 3, 5, 2]], "out": """0 1 1 2 2 3 3 2 2 """ }, ] def C(N, A): pass test_all(C)

自由欄

try

設問を理解するのに時間が掛かりました…

from io import StringIO def C(N, A): out = StringIO() ans = [0] * (2 * N + 2) for i, a in enumerate(A, 1): ans[i * 2] = ans[a] + 1 ans[i * 2 + 1] = ans[a] + 1 print(*ans[1:], sep="\n", file=out) return out.getvalue() test_all(C)

結果：#35882507

自由欄

D - Robot Arms 2

やってみよう！

D関数を完成させて「Run」ボタンをクリックしよう！

test_dataD = [ { "in":[3, -1, 1, [2, 1, 3]], "out": "Yes" },{ "in":[5, 2, 0, [2, 2, 2, 2, 2]], "out": "Yes" },{ "in":[4, 5, 5, [1, 2, 3, 4]], "out": "No" },{ "in":[3, 2, 7, [2, 7, 4]], "out": "No" },{ "in":[10, 8, -7, [6, 10, 4, 1, 5, 9, 8, 6, 5, 1]], "out": "Yes" }, ] def D(N, x, y, A): pass test_all(D)

自由欄

try(コンテスト中)

「x方向とy方向でそれぞれ数字を作れるか」って方向で実装したはいいもの、なぜかWA×2の結果に…

def D(N, x, y, A): SIZE = 10_000 x = x - A[0] xs = [] ys = [] for i, a in enumerate(A[1:]): if i % 2: xs.append(a) else: ys.append(a) def search(seed, target): # print(seed, target) dp = [False] * (2 * SIZE + 1) dp[seed[0] + SIZE] = True dp[-seed[0] + SIZE] = True for s in seed[1:]: new = dp.copy() for i, b in enumerate(dp): if b: new[i + s] = True new[i - s] = True # print("2:", *[i - SIZE for i, b in enumerate(new) if b]) dp = new # print(*[i - SIZE for i, b in enumerate(dp) if b]) return dp[target + SIZE] return "Yes" if search(xs, x) and search(ys, y) else "No" test_all(D)

結果：#36403154

自由欄

try(振り返り)

「数字を作る」といえばABC271のDで初めて経験しました。
ただし前回と異なる点は、いくつかを選んで数字を作るのではなく、全てを使って数字が作れるか判断することです。

上のコードでは前者での実装となっているため、例えば以下のようなインプットでYes判定となってしまいます。

# 正解はNo D(4, 8, -7, [7, 7, 1, 1])

という訳で、該当箇所(16行目)を修正したのが以下。

def D(N, x, y, A): SIZE = 10_000 x = x - A[0] xs = [] ys = [] for i, a in enumerate(A[1:]): if i % 2: xs.append(a) else: ys.append(a) def search(seed, target): # print(seed, target) dp = [False] * (2 * SIZE + 1) dp[seed[0] + SIZE] = True dp[-seed[0] + SIZE] = True for s in seed[1:]: new = [False] * (2 * SIZE + 1) for i, b in enumerate(dp): if b: new[i + s] = True new[i - s] = True # print("2:", *[i - SIZE for i, b in enumerate(new) if b]) dp = new # print(*[i - SIZE for i, b in enumerate(dp) if b]) return dp[target + SIZE] return "Yes" if search(xs, x) and search(ys, y) else "No" test_all(D)

結果：#36403178

自由欄