ABC272の振り返り(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 - Integer Sum

略

B - Everyone is Friends

やってみよう！

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

test_dataB = [ { "in":[3, 3, [[ 1, 2], [ 2, 3], [ 1, 3]]], "out": "Yes" },{ "in":[4, 2, [[1, 2, 4], [2, 3, 4]]], "out": "No" }, ] def B(N, M, x): pass test_all(B)

自由欄

try

こんな感じ。
制約が小さいので特に実行時間は気にせず短いコードでACできます。
コンテスト中の提出では無駄にxを並べ替えてますが、入力の時点で昇順なので本問では不要でした。

from itertools import combinations as c def B(N, M, x): ans = set([]) for xx in x: ans |= set(c(xx, 2)) return "Yes" if ans == set(c(range(1, N + 1), 2)) else "No" test_all(B)

結果：#36084697

自由欄

C - Max Even

やってみよう！

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

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

自由欄

try

コンテスト中はループを早く抜けようと無駄な工夫を凝らしてWA×2となりました…
以下、振り返って素直に実装してみた版。

def C(N, A): e_top2 = [-1, -1] o_top2 = [-1, -1] def top2(n3): n3.remove(min(n3)) return n3 for a in A: if a % 2: o_top2 = top2(o_top2 + [a]) else: e_top2 = top2(e_top2 + [a]) if -1 in e_top2 and -1 in o_top2: return -1 elif -1 in e_top2: return sum(o_top2) elif -1 in o_top2: return sum(e_top2) else: return max(sum(o_top2), sum(e_top2)) test_all(C)

結果：#36085210

多少不格好でも、計算量があまり変わらなければシンプルな実装がベターですな。

自由欄

D - Root M Leaper

やってみよう！

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

test_dataD = [ { "in":[3, 1], "out": """0 1 2 1 2 3 2 3 4 """ },{ "in":[10, 5], "out": """0 3 2 3 2 3 4 5 4 5 3 4 1 2 3 4 3 4 5 6 2 1 4 3 2 3 4 5 4 5 3 2 3 2 3 4 3 4 5 6 2 3 2 3 4 3 4 5 4 5 3 4 3 4 3 4 5 4 5 6 4 3 4 3 4 5 4 5 6 5 5 4 5 4 5 4 5 6 5 6 4 5 4 5 4 5 6 5 6 7 5 6 5 6 5 6 5 6 7 6 """ }, ] def D(N, M): pass test_all(D)

自由欄

try

コンテスト終了後の提出がWAがその日は諦めました。
振り返ってみると、1つのMに対してあり得るx, yの組み合わせは1つ以上ありうることに気づきました。(以下例)

sq = [i ** 2 for i in range(21)] for i in range(1, 401): ab = set([]) for s in sq: if i - s in sq: a = s b = i - s if a > b: a, b = b, a ab.add((a, b)) if len(ab) > 1: print(i, ab)

という訳で、そこだけ修正したらACとなりました。

from io import StringIO from itertools import product from operator import add, sub from collections import deque def sqrt(x): return int(x ** (1/2)) def ret(grid): out = StringIO() for g in grid: print(*g, file=out) return out.getvalue() def D(N, M): sq = [i ** 2 for i in range(N + 1)] ab = set([]) for s in sq: if M - s in sq: a = s b = M - s if a > b: a, b = b, a ab.add((sqrt(a), sqrt(b))) def nxt(x, y): ret = [] for a, b in ab: for l, m in [[a, b], [b, a]]: for op1, op2 in product([add, sub], repeat=2): ret.append([op1(x, l), op2(y, m)]) return [[x, y] for x, y in ret if 0 <= 0 x <="N-1" and grid="[[-1]" * n for _ in range(n)] grid[0][0]="0" if m> 2 * N ** 2: return ret(grid) q = deque([(0, 0)]) while q: x0, y0 = q.popleft() for x, y in nxt(x0, y0): if grid[x][y] != -1: continue grid[x][y] = grid[x0][y0] + 1 q.append((x, y)) return ret(grid) test_all(D)

結果：#36087818

自由欄