ABC269の振り返り(A, B, C, D, E)

Arakaki Tokyo -

振り返りです。

UNICORN Programming Contest 2022(AtCoder Beginner Contest 269) - AtCoder
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
AtCoderAtCoder Inc.
def test_all(f): for i, data in enumerate(eval(f'test_data{f.__name__}')): exp = data["out"] ans = f(*data["in"]) result = "AC" if exp == ans else "WA" print(f"{i+1} {result}: expected: {exp}, output: {ans}")

A - Anyway Takahashi

略

B - Rectangle Detection

やってみよう！

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

test_dataB = [ { "in":['..........', '..........', '..........', '..........', '...######.', '...######.', '...######.', '...######.', '..........', '..........'], "out": """5 8 4 9""" },{ "in":['..........', '..#.......', '..........', '..........', '..........', '..........', '..........', '..........', '..........', '..........'], "out": """2 2 3 3""" },{ "in":['##########', '##########', '##########', '##########', '##########', '##########', '##########', '##########', '##########', '##########'], "out": """1 10 1 10""" }, ] def B(*S): pass test_all(B) # 提出用 # print(B(*[input() for _ in range(10)]))

自由欄

try

コンテスト中の提出が微妙なので、振り返ってやり直すとこんな感じ。
何気にzip転置の使い所が多い気がする。

def B(*S): def get_range(S): row = ["#" in s for s in S] return row.index(True) + 1, 9 - row[::-1].index(True) + 1 A, B = get_range(S) C, D = get_range(zip(*S)) return f"{A} {B}\n{C} {D}" test_all(B) # 提出用 # print(B(*[input() for _ in range(10)]))

結果：#35652753

自由欄

C - Submask

やってみよう！

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

test_dataC = [ { "in":[11], "out": """0 1 2 3 8 9 10 11""" },{ "in":[0], "out": "0" },{ "in":[576461302059761664], "out": """0 524288 549755813888 549756338176 576460752303423488 576460752303947776 576461302059237376 576461302059761664""" }, ] def C(N): pass test_all(C) # 提出用 # print(C(int(input())))

自由欄

try(コンテスト中)

from itertools import product def C(N): ones = [i for i, f in enumerate(bin(N)[2:][::-1]) if f == "1"][::-1] for c in product([0, 1], repeat=len(ones)): n = sum([2**exp for exp, f in zip(ones, c) if f == 1]) print(n) return test_all(C)

結果：#34939876

try(振り返り)

上を見ずに振り返って再挑戦しました。
結果、やってることは大体一緒です。

from itertools import product def C(N): p2 = [2**i for i in range(61) if N & 2**i][::-1] ret = [sum(f for f, c in zip(p2, com) if c) for com in product([0, 1], repeat=len(p2))] return "\n".join(map(str, ret)) test_all(C) # 提出用 # print(C(int(input())))

結果：#35653766

自由欄

D - Do use hexagon grid

やってみよう！

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

test_dataD = [ { "in":[6, [[-1, -1], [0, 1], [0, 2], [1, 0], [1, 2], [2, 0]]], "out": 3 },{ "in":[4, [[5, 0], [4, 1], [-3, -4], [-2, -5]]], "out": 4 },{ "in":[5, [[2, 1], [2, -1], [1, 0], [3, 1], [1, -1]]], "out": 1 }, ] def D(N, XY): pass test_all(D) # 提出用 # N = int(input()) # XY = [list(map(int, input().split())) for _ in range(N)] # print(D(N, XY))

自由欄

try(コンテスト中)

愚直に幅優先探索です。

from collections import deque def is_neighbor(a, b): return ( (a[0] - 1 == b[0] and a[1] - 1 == b[1]) or (a[0] - 1 == b[0] and a[1] == b[1]) or (a[0] == b[0] and a[1] - 1 == b[1]) or (a[0] == b[0] and a[1] + 1 == b[1]) or (a[0] + 1 == b[0] and a[1] == b[1]) or (a[0] + 1 == b[0] and a[1] + 1 == b[1]) ) def D(N, XY): ret = 0 remaind = set(range(0, N)) while len(remaind): ret += 1 q = deque([remaind.pop()]) while len(q): now = q.popleft() for i in list(remaind): if is_neighbor(XY[now], XY[i]): remaind.remove(i) q.append(i) return ret test_all(D)

結果：#34946386

try(振り返り)

このコンテストに参加した時点ではまだABC264の振り返りをしてなかったので知る由もないのですが…
これ、ABC264：E問題で使ったUnion Findが使えそう…！！

というわけでDSU(まだ自分の中で呼び名が定着してないです😇)を使った提出が以下。

計算量的には上のBFSと同じ$O(N^2)$ですかね。
コーディング量が若干少なくなったので時間短縮に繋がりそうです🌝

def D(N, XY): dsu = [-1] * N def leader(i): if dsu[i] < 0: return i dsu[i] = leader(dsu[i]) return dsu[i] def merge(i, j): '''サイズの大きい方(x)に小さい方(y)をマージ''' if i == j: return x = leader(i) y = leader(j) if x == y: return if dsu[x] > dsu[y]: x, y = y, x dsu[x] += dsu[y] dsu[y] = x def is_neighbor(p1, p2): i1, j1 = p1 i2, j2 = p2 return ( i1 == i2 and j1 - 1 <= 1 j2 <="j1" + or j1="=" and i1 - i2 ) for s, now in enumerate(xy): t range(s): if is_neighbor(now, xy[t]): merge(s, t) return sum(1 n dsu 0) # 提出用 xy="[list(map(int," input().split())) _ range(n)] print(d(n, xy))< py-cell> test_all(D)

結果：#35655758

解説を見る

解説を見ると、やっぱりDSU使ってました。
が、着目しているマスに隣接するマスだけを探すことで$O(N)$の計算量に抑えられています。

こういうところの詰めが甘い…。反省です。

def D(N, XY): contain = [[-1] * 20010 for _ in range(2010)] for i, (x, y) in enumerate(XY): contain[x+1005][y+1005] = i dsu = [-1] * N def leader(i): if dsu[i] < 0: return i dsu[i] = leader(dsu[i]) return dsu[i] def merge(i, j): '''サイズの大きい方(x)に小さい方(y)をマージ''' if i == j: return x = leader(i) y = leader(j) if x == y: return if dsu[x] > dsu[y]: x, y = y, x dsu[x] += dsu[y] dsu[y] = x def get_neighbors(i, j): return ( [i-1,j-1], [i-1,j], [i,j-1], [i,j+1], [i+1,j], [i+1,j+1], ) for i, (x, y) in enumerate(XY): for s, t in get_neighbors(x, y): idx = contain[s+1005][t+1005] if idx > -1: merge(i, idx) return sum(1 for n in dsu if n < 0) # 提出用 # N = int(input()) # XY = [list(map(int, input().split())) for _ in range(N)] # print(D(N, XY)) test_all(D)

結果：#35656907

なぜか実行時間が3倍ほどに延びてしまいました…
Nがもっと大きかったら効果あるのかなぁ🤔

自由欄

E - Last Rook

初のインタラクティブ問題！
とりあえず、コンテスト終了後にACしたコードを貼っときます。

N = int(input())

def main(N):
    for i in range(2):
        s = 1
        e = N + 1
        while e - s > 0:
            # print(s, e)
            m = (s + e) // 2

            if i == 0:
                print(f"? {s} {m} {1} {N}")
            else:
                print(f"? {1} {N} {s} {m}")
            ans = int(input())
            if ans == -1: return
            elif ans == m - s + 1:
                s = m + 1
            else:
                e = m
        else:
            if i == 0:
                x = s
            else:
                y = s

    print(f"! {x} {y}")

main(N)

結果：#34956135

半開区間とか閉区間とか

二分探索に通ずる部分ですが、ここらへんの理解が怪しいので色々試してみました。

半開区間：[ok, ng)

N = int(input())

def main(N):
    def bs(f):
        def is_ok(m):
            f(ok, m)
            ans = int(input())
            return ans == m - ok

        ok = 1
        ng = N + 1
        while abs(ok - ng) > 1:
            m = (ok + ng) // 2 - 1

            if is_ok(m):
                ng = m + 1
            else:
                ok = m + 1
        return ok

    x = bs(lambda s, m: print(f"? {s} {m} {1} {N}"))
    y = bs(lambda s, m: print(f"? {1} {N} {s} {m}"))

    print(f"! {x} {y}")

main(N)

結果：#35729412

半開区間：(ng, ok]

N = int(input())

def main(N):
    def bs(f):
        def is_ok(m):
            f(m, ok)
            ans = int(input())
            return ans == ok - m

        ng = 0
        ok = N
        while abs(ok - ng) > 1:
            m = (ok + ng) // 2 + 1

            if is_ok(m):
                ng = m - 1
            else:
                ok = m - 1
        return ok

    x = bs(lambda s, m: print(f"? {s} {m} {1} {N}"))
    y = bs(lambda s, m: print(f"? {1} {N} {s} {m}"))

    print(f"! {x} {y}")

main(N)

結果：#35730449

閉区間：[ok, ng]

N = int(input())

def main(N):
    def bs(f):
        def is_ok(m):
            f(ok, m)
            ans = int(input())
            return ans == m - ok

        ok = 1
        ng = N
        while abs(ok - ng) > 0:
            m = (ok + ng) // 2

            if is_ok(m):
                ng = m
            else:
                ok = m + 1
        return ok

    x = bs(lambda s, m: print(f"? {s} {m} {1} {N}"))
    y = bs(lambda s, m: print(f"? {1} {N} {s} {m}"))

    print(f"! {x} {y}")

main(N)

結果：#35729641

う～ん、まだ身についてない気がする…

自由欄