【解説もどき】ABC264Cの考え方

問題

atcoder.jp

思考

まず、をいじってに近づけるのとをいじってに近づけるのとどちらが良いかを検討。普通に前者の方がよさそうなので前者で。

…考えても解法が思いつかない。とりあえずゴリ押ししてみよう。

削除する行と列が決まっているならば、どの順番で削除しても結果は同じである。削除する行の選び方は通りであり、ゆえ、選び方の最大値は。列についても同様で、計算量は最大でとなる…たぶん。総当たりでも十分に間に合いそうである。*1

さて、どうやって行/列を削除しようか。色々悩んだ末、

1. 削除する行/列の値を別の値(今回は-1を採用)で置き換える
2. 2次元配列を1次元に変換
3. 変換した配列から-1を取り除く
4. 配列を再び2次元に戻す(これがと一致すればOK)

という方式を採用することに。しかし配列の形状を変える関数が果たして実装されているかどうか…。幸いにもNimには存在したので、このままいくことに。

残るは行と列の選び方である。bit全探索にして1か0の個数が合わないときはスキップするのが良さそうだ。

実装

まずはbit全探索の部分から。

for h in 0..<(1 shl H1):
    if h.countSetBits != H2: continue # 1 -> 残す
    for w in 0..<(1 shl W1):
        if w.countSetBits != W2: continue # 1 -> 残す

1のbitの個数がの行/列の数と一致しないときは飛ばす、つまり0のbitの行/列を削除することにした*2。

続いて-1で置き換える部分。を直接変更するのはまずいので新しく変数をつくる。

var C = A
for i in 0..<H1:
    for j in 0..<W1:
        if not (h.testBit(i)) or not (w.testBit(j)):
            C[i][j] = -1

行/列のどちらかが0のbitになっているところを削除する、ということに注意。

そして配列の形状を変換する部分。

var D = C.concat.filterIt(it != -1).distribute(H2)

concatは「配列の配列をただの配列にしたものを返す関数」、filterItは「条件を満たす値だけを残した配列を返す関数」、そしてdistributeは「配列を指定した数に分割してできる配列の配列を返す関数」である*3。の行数、つまり個の配列に分割したいのでdistributeにはを入れる。(この辺、Haskellをやっておいて良かったな…)

あとはD == Bをするだけである。

解答

出来上がったものがこちらになります。

import strformat, macros, sequtils, strutils
import  math, algorithm, bitops, sets, deques, tables
# Nim standard imput macro
# example & original sourse => ttps://foo-x.com/blog/nim-contest-macro/
let readNext = iterator(getsChar: bool = false): string {.closure.} =
    for s in stdin.readAll.split.filterIt(it != ""):
        if getsChar:
            for i in 0..<s.len():
                yield s[i..i]
        else:
            yield s

proc read(t: typedesc[string]): string = readNext()
proc read(t: typedesc[char]): char = readNext(true)[0]
proc read(t: typedesc[int]): int = readNext().parseInt
proc read(t: typedesc[float]): float = readNext().parseFloat

macro read(t: typedesc, n: varargs[int]): untyped =
    var repStr = "" 
    for arg in n:
        repStr &= &"({arg.repr}).newSeqWith " 
    parseExpr(&"{repStr}read({t})") 

macro read(ts: varargs[auto]): untyped =
    var tupStr = "" 
    for t in ts:
        tupStr &= &"read({t.repr})," 
    parseExpr(&"({tupStr})") 

macro read(n: int, ts: varargs[auto]): untyped =
    for typ in ts:
        if typ.typeKind != ntyAnything:
            error("Expected typedesc, got " & typ.repr, typ) 
    parseExpr(&"({n.repr}).newSeqWith read({ts.repr})") 

let
    H1, W1 = read(int)
    A = read(int, H1, W1)
    H2, W2 = read(int)
    B = read(int, H2, W2)

var ans = false

block solve:
    for h in 0..<(1 shl H1):
        if h.countSetBits != H2: continue 
        for w in 0..<(1 shl W1):
            if w.countSetBits != W2: continue 
            var C = A
            for i in 0..<H1:
                for j in 0..<W1:
                    if not (h.testBit(i)) or not (w.testBit(j)):
                        C[i][j] = -1
            var D = C.concat.filterIt(it != -1).distribute(H2)
            if D == B:
                ans = true
                break solve

if ans:
    echo "Yes"
else:
    echo "No"

*1:かなり雑にで見積もってもギリギリ間に合う。

*2:「import bitops」を書いておくこと

*3:「import sequtils」を書いておくこと