ABC256のC問題

Arakaki Tokyo -

相変わらずC問題に躓いているので振り返りです。

Tokio Marine & Nichido Fire Insurance Programming Contest 2022（AtCoder Beginner Contest 256) - AtCoder
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
AtCoderAtCoder Inc.

問題

C - Filling 3x3 array

try(1st.)

以下がコンテスト中に書いたコード。
テストケースでACにならず、うんうん唸ってる間に時間切れ…

from copy import deepcopy def main(h, w): global cnt cnt = 0 def rec(i, h, w): r, c = divmod(i, 3) if i == 8 and h[r] == w[c]: global cnt cnt += 1 else: if c == 2: v = h[r] if w[c] - v < (2-r): return available = [v] elif r == 2: v = w[c] if h[r] - v < (2-c): return available = [v] else: available = range(1, min(h[r] - (2-c), w[c] - (2-r)) + 1) for av in available: h = deepcopy(h) h[r] -= av w = deepcopy(w) w[c] -= av rec(i+1, h, w) rec(0, h, w) return cnt

テストデータ・テスト関数定義↓

# 縮小表示 test_data = [ { "in":[[3, 4, 6], [3, 3, 7]], "out": 1 },{ "in":[[3, 4, 5], [6, 7, 8]], "out": 0 },{ "in":[[5, 13, 10], [6, 13, 9]], "out": 120 },{ "in":[[20, 25, 30], [22, 29, 24]], "out": 30613 }, ] def test_all(f): for i, data in enumerate(test_data): exp = data["out"] ans = f(*data["in"]) result = "AC" if exp == ans else "WA" print(f"{i+1} {result}: expected: {exp}, output: {ans}") test_all(main)

try(2nd.)

コンテスト終了後に修正したのが以下。

24～28行でディープコピーしたのはいいものの、同じ変数名に代入したためforを回すたびに書き換えた内容が累積してた…

from copy import deepcopy def main2(h, w): global cnt cnt = 0 def rec(i, h, w): r, c = divmod(i, 3) if i == 8 and h[r] == w[c]: global cnt cnt += 1 else: if c == 2: v = h[r] if w[c] - v < (2-r): return available = [v] elif r == 2: v = w[c] if h[r] - v < (2-c): return available = [v] else: available = range(1, min(h[r] - (2-c), w[c] - (2-r)) + 1) for av in available: new_h = deepcopy(h) new_h[r] -= av new_w = deepcopy(w) new_w[c] -= av rec(i+1, new_h, new_w) rec(0, h, w) return cnt

diff ↓

# 縮小表示 from difflib import HtmlDiff as diff str_main1 = ''' from copy import deepcopy def main(h, w): global cnt cnt = 0 def rec(i, h, w): r, c = divmod(i, 3) if i == 8 and h[r] == w[c]: global cnt cnt += 1 else: if c == 2: v = h[r] if w[c] - v < (2-r): return available = [v] elif r == 2: v = w[c] if h[r] - v < (2-c): return available = [v] else: available = range(1, min(h[r] - (2-c), w[c] - (2-r)) + 1) for av in available: h = deepcopy(h) h[r] -= av w = deepcopy(w) w[c] -= av rec(i+1, h, w) rec(0, h, w) return cnt '''.splitlines() str_main2 = ''' from copy import deepcopy def main(h, w): global cnt cnt = 0 def rec(i, h, w): r, c = divmod(i, 3) if i == 8 and h[r] == w[c]: global cnt cnt += 1 else: if c == 2: v = h[r] if w[c] - v < (2-r): return available = [v] elif r == 2: v = w[c] if h[r] - v < (2-c): return available = [v] else: available = range(1, min(h[r] - (2-c), w[c] - (2-r)) + 1) for av in available: new_h = deepcopy(h) new_h[r] -= av new_w = deepcopy(w) new_w[c] -= av rec(i+1, new_h, new_w) rec(0, h, w) return cnt '''.splitlines() diff().make_file(str_main1, str_main2) test_all(main2)

よさそう。提出！

結果(2nd.)

なぜか一つだけREになってしまいました…🤔

提出 #32576286 - 東京海上日動プログラミングコンテスト2022（AtCoder Beginner Contest 256）

解説

スッキリしないまま解説を見てみます。

解説 - 東京海上日動プログラミングコンテスト2022（AtCoder Beginner Contest 256）

深さ優先探索(DFS)

どうやら私がやろうとしていたことはDFSだったようです。(解説の例2)

そもそも再帰関数内でディープコピーすること自体イケてないよなぁと考えていたところ、解説に倣って修正したのが以下。

たしかに、わざわざ引数をコピー／更新して引き回すより、グローバルで確定した値を持ってた方が分かりやすい。
でもこれってDFSだから成り立つ実装だよなぁ？
なんというか、グローバルの変数を参照／更新することへの漠然とした忌避感が拭いきれません。

def main3(h, w): global cnt cnt = 0 m = [[0]*3 for _ in range(3)] def rec(i): r, c = divmod(i, 3) if i == 9: if sum([r[2] for r in m]) == w[2]: global cnt cnt += 1 else: if c == 2: v = h[r] - (m[r][0] + m[r][1]) if v < 1: return available = [v] elif r == 2: v = w[c] - (m[0][c] + m[1][c]) if v < 1: return available = [v] else: available = range(1, min(h[r] - (2-c), w[c] - (2-r)) + 1) for av in available: m[r][c] = av rec(i+1) rec(0) return cnt test_all(main3)

無事ACとなりました。

提出 #32577098 - 東京海上日動プログラミングコンテスト2022（AtCoder Beginner Contest 256）

全探索

さて、解説の例1では全探索による実装が示されています。
あぁ、これ【競プロ典型 90 問】002でやったやつだ！

問題は異なるものの、要は『小さい制約なら全探索』です。
細かいことを気にせず力技で正答を得られるので、回答時間の短縮に繋がります。

という訳で実装してみたのが以下。

from itertools import product def main(h, w): cnt = 0 for m in product(range(1, 28+1), repeat=4): if (m02 := h[0] - (m[0] + m[1])) < 1: continue if (m12 := h[1] - (m[2] + m[3])) < 1: continue if (m20 := w[0] - (m[0] + m[2])) < 1: continue if (m21 := w[1] - (m[1] + m[3])) < 1: continue a = w[2] - (m02 + m12) b = h[2] - (m20 + m21) if a == b and a > 0: cnt += 1 return cnt test_all(main)

こちらも無事AC。

提出 #32575903 - 東京海上日動プログラミングコンテスト2022（AtCoder Beginner Contest 256）

実行時間的にもまだまだ余裕ありそうですね。
ちなみにアットコーダーのPyPy3(7.3.0)(≒Python3.6)ではセイウチ演算子に対応してないのでPython(3.8)で提出しています。
セイウチを使わずに実装してPyPyで提出すればより高速化できるでしょう。

まとめ

C問題までは、まず全探索で考えてみる。

自由欄