keyence2021

キーエンスプログラミングコンテスト 2021 - AtCoder ARC相当の難易度 A-Cの3問でした

$c_{n} = max a_{i} b_{j} [i \leq j \leq n]$ を求める問題 (Iverson bracket記法)
$c_{n} = max (c_{n - 1}, max a_{i} b_{n} [i \leq n])$
$c_{n} = max (c_{n - 1}, b_{n} max a_{i} [i \leq n])$
というわけで $max a_{i} [i \leq n]$ を別途保存しておけばOK python

def main():
    N = int(input())
    AS = list(map(int, input().split()))
    BS = list(map(int, input().split()))
    maxAS = []
    x = 0
    for i in range(N):
        x = max(x, AS[i])
        maxAS.append(x)

    ret = AS[0] * BS[0]
    print(ret)
    for i in range(1, N):
        ret = max(ret, maxAS[i] * BS[i])
        print(ret)

B - Mex Boxes

同じ箱に同じ値を入れてもメリットがない
数値が飛んでたら結果に影響しない
というわけで「0から順に連続して入れられるだけ入れる」が最適解になる貪欲法
箱の数の制限を忘れてて一度WAになった: (1)のK > 0 python

def main():
    N, K = map(int, input().split())
    AS = list(map(int, input().split()))
    from collections import Counter
    count = Counter(AS)
    ret = 0
    while count[0] > 0 and K > 0:  # (1)
        i = 0
        K -= 1
        while count[i] > 0:
            ret += 1
            count[i] -= 1
            i += 1

    print(ret)

C - Robot on Grid

最初、図の間違った方のDPをしてサンプルが合わなくて悩んだ
- 例えば＊を通らない経路は上のDPだと最終的な答えに1として出されるわけなのだが、＊がM個あるなら3^Mになるのが正しい
- 最終的に何で割って辻褄を合わせればいいのかも一度間違えたがサンプルが親切なのでよく見ればよい
  - サンプル1の場合、ゴールまでの遷移が2回、＊が1つなので、1回余分だから3^1で割る
  - サンプル2の場合、遷移が4回、＊が4つなので3^0で割る
- REが出てるのはpowに負の値を入れられるのがPython3.8からなのを忘れてたせい see mod Pでの逆元
- タプルをキーにした辞書を使っててTLEしたので、配列に変えた。
  - W+2は、1オリジンなのと、端で条件分岐しないで良いように1マス広げとくのの組み合わせ python

def main():
    MOD = 998_244_353
    H, W, K = map(int, input().split())
    CS = [0] * ((H + 2) * (W + 2))
    for _k in range(K):
        h, w, c = input().strip().split()
        CS[(int(h) * (W + 2) + int(w))] = ord(c)

    table = [0] * ((H + 2) * (W + 2))
    v = table[1 + (W + 2)] = 1
    for h in range(1, H + 1):
        for w in range(1, W + 1):
            pos = h * (W + 2) + w
            v = table[pos] % MOD
            c = CS[pos]
            if c == 88:  # "X":
                table[pos + 1] += v * 3
                table[pos + (W + 2)] += v * 3
            elif c == 68:  # "D":
                table[pos + (W + 2)] += v * 3
            elif c == 82:  # "R":
                table[pos + 1] += v * 3
            else:
                table[pos + 1] += v * 2
                table[pos + (W + 2)] += v * 2

    ret = table[H * (W + 2) + W] % MOD
    LEN = (H + W - 2)
    NEGK = H * W - K
    ret *= pow(3, (MOD - 1 - (LEN - NEGK)), MOD)
    ret %= MOD
    print(ret)

D - Choosing Up Sides

考えたこと
- 8人を半分に分けて対戦させる時、1番の人と同じチームになる人が3人いて、それらの人の「同じだった回数」は1増えるので、1番以外の全員が同じ「1番と同じチームだった回数」になるのは3×7の21回目
  - 間違いです
    - 7箇所のうち3箇所が1であるようなベクトルを7つ足し合わせてすべて3にすることができればよい
終了後Twitter
- 双対ベクトル src
- E - Odd Sum RectanglesのN=Mのときと大体同じ問題 src
- 再帰 src
- アダマール行列 src src
- D: N = 3だったら11110000 11001100 10101010 を作ってこれらを1以上選んでxor src
  - なるほど
  - 同じ値の連続が $2^{i} (0 \leq i < N)$ であるようなものがN通り作れる
  - これらの値のXORは、それぞれを選択するかどうかの $2^{N}$ 個あって、00000000以外はすべて1の個数が4個( $2^{N - 1}$ )
  - この集合はXORについて閉じている(0が単位元)
  - 「同じチームであった回数」は「XORした値の0である桁の数」なので、異なるものをXORした時に0である桁の数が変わらないこの性質が都合が良い
コンテスト後実装
- 同じ値の連続が $2^{i} (0 \leq i < N)$ であるようなものをN通り作る
  - なおPythonは256ビットの整数も問題なくビット演算できる
- このN個をXORして作られる値を列挙する
  - 部分集合の列挙をビット演算でやる、よく使う方法
- 2進数の文字列化をして、0と1をAとBに置き換える
AC python

def main():
    N = int(input())
    group = []
    for i in range(N):
        P = 2 ** (2 ** i)
        group = [x * (P + 1) for x in group]
        group.append(P - 1)

    K = 2 ** N - 1
    print(K)
    for i in range(1, K + 1):
        x = 0
        for j in range(N):
            if (1 << j) & i:
                x = x ^ group[j]
        s = f"{x:0256b}"[-(2 ** N):]
        s = s.replace("0", "A").replace("1", "B")
        print(s)

アダマール行列 - Wikipedia
- なるほど
- $H^{⊺} H = n I_{n}$ ということはつまり、 $i \neq = j$ について $\sum_{k} H_{ik} H_{kj} = 0$ ということ
  - なので、問題条件の「同じチームだった回数が任意のi<jについて等しい」を満たすわけだ
- 再帰的な構築 $[H H H - H]$ は気づかなかった
- 僕がやったのは群の準同型 ${1, - 1, \times} \mapsto {0, 1, \oplus}$ をして $F_{n} = [0_{1 \times 2^{n - 1}} F_{n - 1} 1_{1 \times 2^{n - 1}} F_{n - 1}]$ することに相当する
  - $0_{1 \times 2^{n - 1}} 1_{1 \times 2^{n - 1}}$ が P - 1
  - $F_{n - 1} F_{n - 1}$ が group = [x * (P + 1) for x in group]
- 僕はその後、部分集合ごとにXORしたけど、 $H_{2^{n}} = F_{n}^{⊺} F_{n}$ でも良いらしい
  - Fはn行2^n列、各列は異なっているので、nビットの整数が全通り出てくる
    - 順序には意味はない
  - $H_{ij} = \sum_{k} F_{ki} F_{kj}$ なので、これは要するにpopcount(i & j) mod 2
    - 下記のpopcountを使った構築に帰着する
公式解説
- popcount(i & j)を使って構築してる
- これはアダマール行列の再帰的な構築において、i & jの最上位ビットが1である場合だけ符号反転してるから
- popcount(i & j)がij要素を符号反転した回数になる

🪴 Quartz 4.0

keyence2021

Graph View

Backlinks