ABC307の振り返り(C, D, E)

振り返りです。

import sys from io import StringIO input = lambda: sys.stdin.readline()[:-1] def test(f, data): stdin = sys.stdin stdout = sys.stdout sys.stdin = StringIO(data["in"]) out = StringIO() sys.stdout = out err = None try: f() except BaseException as e: err = e else: ans = out.getvalue() exp = data["out"] sys.stdin = stdin sys.stdout = stdout if err: raise err result = "AC" if exp == ans else "WA" print(f"{result}: expected: {exp}, output: {ans}") def test_all(f): for i, data in enumerate(eval(f'test_data{f.__name__[0]}'), 1): print(f"case {i}") test(f, data)

C - Ideal Sheet

やってみよう！

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

test_dataC = [ { "in":"""3 5 #.#.. ..... .#... 2 2 #. .# 5 3 ... #.# .#. .#. ... """, "out": """Yes """ },{ "in":"""2 2 #. .# 2 2 #. .# 2 2 ## ## """, "out": """No """ },{ "in":"""1 1 # 1 2 ## 1 1 # """, "out": """No """ },{ "in": """3 3 ### ... ... 3 3 #.. #.. #.. 3 3 ..# ..# ### """, "out": """Yes """ }, ] def C(): pass test_all(C)

自由欄

コンテスト中

慣れないタイプの問題に困惑して実装の方針を立てるのに時間がかかる・・・
⇨結局以下のようなことを考えた(下図も参照)

シートCを想定して大きなマトリックスを作り、中央にシートAを配置する
シートBを、シートAから上下左右で最大8マス離れる範囲で動かす

一致判定として黒マスの相対座標を返すnormalize関数を作成しました。

def C(): from copy import deepcopy from itertools import product HA, WA = map(int, input().split()) A = [input() for _ in range(HA)] HB, WB = map(int, input().split()) B = [input() for _ in range(HB)] HX, WX = map(int, input().split()) X = [input() for _ in range(HX)] def normalize(m): ret = [] left_top = None for i in range(len(m)): for j in range(len(m[0])): if m[i][j] == "#": if left_top: ret.append(tuple(a - b for a, b in zip([i, j], left_top))) else: left_top = (i, j) ret.append((0, 0)) return ret x_pat = normalize(X) m_base = [list("." * (WB * 2 + WA + 16)) for _ in range(HB * 2 + HA + 16)] for i, j in product(range(HA), range(WA)): if A[i][j] == "#": m_base[HB + 8 + i][WB + 8 + j] = "#" for i in range(HB + HA + 16): for j in range(WB + WA + 16): m = deepcopy(m_base) for k in range(HB): for l in range(WB): if B[k][l] == "#": m[i + k][j + l] = "#" if x_pat == normalize(m): print("Yes") return print("No") test_all(C)

結果：#42922279

WA x 1 ...😩
結局デバッグできずに無念の試合終了

自由欄

振り返り

WA x 1の原因ですが、結論から言えば

「シートBを、シートAから上下左右で最大8マス離れる範囲で動かす」とすべきところを、
右と下に最大7マスまでしか動かしてなかった

からでした😇
なんというボーンヘッド💀

修正した該当箇所は31行目からのループ部分の17です。

...
    for i in range(HB + HA + 17):
        for j in range(WB + WA + 17):
            ...

def C(): from copy import deepcopy from itertools import product HA, WA = map(int, input().split()) A = [input() for _ in range(HA)] HB, WB = map(int, input().split()) B = [input() for _ in range(HB)] HX, WX = map(int, input().split()) X = [input() for _ in range(HX)] def normalize(m): ret = [] left_top = None for i in range(len(m)): for j in range(len(m[0])): if m[i][j] == "#": if left_top: ret.append(tuple(a - b for a, b in zip([i, j], left_top))) else: left_top = (i, j) ret.append((0, 0)) return ret x_pat = normalize(X) m_base = [list("." * (WB * 2 + WA + 16)) for _ in range(HB * 2 + HA + 16)] for i, j in product(range(HA), range(WA)): if A[i][j] == "#": m_base[HB + 8 + i][WB + 8 + j] = "#" for i in range(HB + HA + 17): for j in range(WB + WA + 17): m = deepcopy(m_base) for k in range(HB): for l in range(WB): if B[k][l] == "#": m[i + k][j + l] = "#" if x_pat == normalize(m): print("Yes") return print("No") test_all(C)

結果：#43336415　⇨　無事AC。はぁ

教訓

下手な方針を立てると実装が訳分からんくなってバグりやすくなる
- 16とか17とかの固定値なんやねん。。
やむを得ず上記で実装する場合には、しっかりコーナーケースまで検証する
- これはどんな問題でも基本的にやるべきだと思いますが、今回のような場合こそ特に、という意味で

解説を見る

こんな問題どうやって解くのんという訳で解説を見ます。

考え方の方向性は図 by kyopro_friendsと大差ないな…
判定にnormalizeを用いる発想は別解 by evimaと一緒だけど、その前にconvertして探索を容易にしたり、全体の実装が段違いに洗練されている…

結局私の実装力不足でした。本当にありがとうございました。

参考というか目標としてevimaさんの別解を以下に引用します。キレイだよなぁ～

def C_editorial(): ''' editorial by evima https://atcoder.jp/contests/abc307/editorial/6650 ''' def convert(H, W, S): s = set() for i in range(H): for j in range(W): if S[i][j] == '#': s.add((i, j)) return s def normalize(s): my = min(y for (y, x) in s) mx = min(x for (y, x) in s) return set((y - my, x - mx) for (y, x) in s) HA, WA = map(int, input().split()) A = normalize(convert(HA, WA, [input() for _ in range(HA)])) HB, WB = map(int, input().split()) B = normalize(convert(HB, WB, [input() for _ in range(HB)])) HX, WX = map(int, input().split()) X = normalize(convert(HX, WX, [input() for _ in range(HX)])) ans = False for dy in range(-HX, HX): for dx in range(-WX, WX): ans |= normalize(A.union((y + dy, x + dx) for (y, x) in B)) == X print('Yes' if ans else 'No') test_all(C_editorial)

D - Mismatched Parentheses

やってみよう！

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

test_dataD = [ { "in":"""8 a(b(d))c """, "out": """ac """ },{ "in":"""5 a(b)( """, "out": """a( """ },{ "in":"""2 () """, "out": """ """ },{ "in":"""6 )))((( """, "out": """)))((( """ },{# 追加 "in":"""7 a(b)()) """, "out": """a) """ }, ] def D(): pass test_all(D)

自由欄

振り返り

コンテスト中はC問題で心折れてボロボロでした。。
振り返るとこんな感じ。

Sを走査して対応する(と)を調べる
Sを走査して対応する(と)に挟まれる範囲を除いて出力する

という単純な実装です。

def D(): N = int(input()) S = input() A = [0] * N start = [] for i, c in enumerate(S): if c == "(": start.append(i) elif c == ")" and start: A[start.pop()] = 1 A[i] = -1 flag = 0 ans = [] for c, a in zip(S, A): flag += a if flag == 0 and a != -1: ans.append(c) print(*ans, sep="") test_all(D)

結果：#43426522

自由欄

E - Distinct Adjacent

test_dataE = [ { "in":"""3 3 """, "out": """6 """ },{ "in":"""4 2 """, "out": """2 """ },{ "in":"""987654 456789 """, "out": """778634319 """ }, ]

やってみよう！

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

def E(): out = "" return out test_all(E)

解説を理解する

はい、早速解説を見ます。
以下、自分なりの理解。

設問では円環ですが、一旦N人の人が一列に並んでいる場合を考えます。
その場合の回答は、$M \times (M - 1) \times (M - 1)... = M(M - 1)^{N - 1}$となります（多分）。

そこから円環の回答を導くためには、N人目が一人目と同じ番号である場合を除けばよいです。
困りました。そんな条件どうやって実装すんだ。という訳でここから解説の本題です。

N人目までの場合の数を数えた後に、その中から一人目と同じ番号かどうかを判断することはできません。
であれば、N人目までの場合の数を数えるプロセスの中で、i人目の番号が一人目と同じ番号かどうかを保持していけばよいです。

具体的には。
i人目までの場合の数を数えた時点で、i人目の番号が一人目と異なる番号の場合を$i_0$、同じ場合を$i_1$とすると、i+1人目は
$(i + 1)_0 = i_0 \times (M - 2) + i_1 \times (M - 1)$
$(i + 1)_1 = i_0$
となります。
よく見ると、結局i+1人目時点での場合の数は$(i_0 + i_1)\times (M - 1)$となり、総数としては一列に並んでいる場合で考えたときと同じになります。
このように、「一人目と同じ番号かどうか」の情報を引き回しながらN人目まで見たときに$N_0$が本問の回答となります。

考えた人頭いいー😇

包除原理については、余力があるときの宿題とします・・・

def E(): N, M = map(int, input().split()) MOD = 998244353 dp = [0, M] for i in range(N - 1): dp = [ (dp[0] * (M - 2) + dp[1] * (M - 1)) % MOD, dp[0] ] print(dp[0]) test_all(E)

結果：#43663626