ABC288の振り返り(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 - Many A+B Problems

B - Qualification Contest

略

自由欄

C - Don’t be cycle

やってみよう！

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

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

自由欄

try

出ました、閉路判定問題。
削除する辺の本数の最小値という表現が引っかかりますが、とりあえず「辺を追加しようとして、閉路になる場合は除く」でイケんじゃね？という考えで以下。

from collections import defaultdict class DSU(): def __init__(self, n=None): self.dsu = defaultdict(lambda: -1) if n: for i in range(n): self.dsu[i] def leader(self, i): if self.dsu[i] < 0: return i self.dsu[i] = self.leader(self.dsu[i]) return self.dsu[i] def merge(self, i, j): '''サイズの大きい方(x)に小さい方(y)をマージ''' if i == j: return x = self.leader(i) y = self.leader(j) if x == y: return if self.dsu[x] > self.dsu[y]: x, y = y, x self.dsu[x] += self.dsu[y] self.dsu[y] = x def members(self, i): l = self.leader(i) return [k for k, v in self.dsu.items() if self.leader(k) == l] def __len__(self): return len([1 for v in self.dsu.values() if v < 0]) def C(N, M, AB): dsu = DSU() cnt = 0 for a, b in AB: if dsu.leader(a) == dsu.leader(b): cnt += 1 else: dsu.merge(a, b) return cnt test_all(C)

結果：#38609158

自由欄

D - Range Add Query

やってみよう！

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

test_dataD = [ { "in":[7, 3, [3, -1, 1, -2, 2, 0, 5], 2, [[1, 6], [2, 7]]], "out": """Yes No""" },{ "in":[20, 4, [-19, -66, -99, 16, 18, 33, 32, 28, 26, 11, 12, 0, -16, 4, 21, 21, 37, 17, 55, -19], 5, [[13, 16], [4, 11], [3, 12], [13, 18], [4, 10]]], "out": """No Yes No Yes No""" }, ] def D(N, K, A, Q, lr): pass test_all(D)

自由欄

解説を見る

コンテスト中はても足も出なかったので、早速原案者の解説を見ます。
不変量を考えるとのこと。

…コードを追ってやってることは理解できました。
が、なぜそれで解が得られるのかというところが、証明や最初の解説を見てもしっくりこず…

同じような問題が出ても自力でACできる気がしない😇

from itertools import accumulate def D(N, K, A, Q, lr): cum = [] for i in range(K): cum.append([0] + list(accumulate(a if j % K == i else 0 for j, a in enumerate(A)))) for l, r in lr: ans = True for i in range(K - 1): ans = (cum[i][r] - cum[i][l - 1]) == (cum[i + 1][r] - cum[i + 1][l - 1]) if not ans: print("No") break else: print("Yes") test_all(D)

結果：#39005605

まとめ

Dで心折れた