keyence2021
A-Cの3問でした
https://gyazo.com/1cf13ccfd7b034a59134adbb8aa0b42a
https://gyazo.com/8886c1232049da6b710c42699eb6acb4
$ c_n = \max (c_{n-1}, \max a_ib_n [i\le n])
$ c_n = \max (c_{n-1}, b_n \max a_i [i\le n])
というわけで $ \max a_i [i\le n] を別途保存しておけばOK
code: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):
maxAS.append(x)
print(ret)
for i in range(1, N):
ret = max(ret, maxASi * BSi) print(ret)
https://gyazo.com/399ab72dbb56393a66ef66e1ef97034c
同じ箱に同じ値を入れてもメリットがない
数値が飛んでたら結果に影響しない
というわけで「0から順に連続して入れられるだけ入れる」が最適解になる貪欲法
箱の数の制限を忘れてて一度WAになった: (1)のK > 0
code: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 count0 > 0 and K > 0: # (1) i = 0
K -= 1
ret += 1
i += 1
print(ret)
https://gyazo.com/e60412189e8d57b2f1c1e23ba8897f9c
最初、図の間違った方のDPをしてサンプルが合わなくて悩んだ
https://gyazo.com/d77469b7257adfbca3f257a13f5e8b0e
例えば*を通らない経路は上の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マス広げとくのの組み合わせ
code: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()
table = 0 * ((H + 2) * (W + 2)) for h in range(1, H + 1):
for w in range(1, W + 1):
pos = h * (W + 2) + w
if c == 88: # "X":
elif c == 68: # "D":
elif c == 82: # "R":
else:
LEN = (H + W - 2)
NEGK = H * W - K
ret *= pow(3, (MOD - 1 - (LEN - NEGK)), MOD)
ret %= MOD
print(ret)
https://gyazo.com/b2e3f90a7532cacff62fc8ed74d62a72
考えたこと
8人を半分に分けて対戦させる時、1番の人と同じチームになる人が3人いて、それらの人の「同じだった回数」は1増えるので、1番以外の全員が同じ「1番と同じチームだった回数」になるのは3×7の21回目
間違いです
7箇所のうち3箇所が1であるようなベクトルを7つ足し合わせてすべて3にすることができればよい
終了後Twitter
D: N = 3だったら11110000 11001100 10101010 を作ってこれらを1以上選んでxor src なるほど
同じ値の連続が$ 2^i (0 \le i < N) であるようなものがN通り作れる
これらの値のXORは、それぞれを選択するかどうかの$ 2^N個あって、00000000以外はすべて1の個数が4個($ 2^{N-1})
この集合はXORについて閉じている(0が単位元)
「同じチームであった回数」は「XORした値の0である桁の数」なので、異なるものをXORした時に0である桁の数が変わらないこの性質が都合が良い
コンテスト後実装
同じ値の連続が$ 2^i (0 \le i < N) であるようなものをN通り作る
なおPythonは256ビットの整数も問題なくビット演算できる
このN個をXORして作られる値を列挙する
部分集合の列挙をビット演算でやる、よく使う方法
2進数の文字列化をして、0と1をAとBに置き換える
AC
code:python
def main():
N = int(input())
group = []
for i in range(N):
P = 2 ** (2 ** i)
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:
s = s.replace("0", "A").replace("1", "B")
print(s)
なるほど
$ {\displaystyle {\boldsymbol {H}}^{\intercal }{\boldsymbol {H}}=n{\boldsymbol {I}}_{n}} ということはつまり、$ i \neq j について $ \sum_k H_{ik}H_{kj} = 0ということ
なので、問題条件の「同じチームだった回数が任意のi<jについて等しい」を満たすわけだ
再帰的な構築 $ \begin{bmatrix} H & H\\ H & -H\end{bmatrix} は気づかなかった
僕がやったのは 群の準同型$ {\displaystyle \{1,-1,\times \}\mapsto \{0,1,\oplus \}} をして $ {\displaystyle {\boldsymbol {F}}_{n}={\begin{bmatrix}0_{1\times 2^{n-1}}&1_{1\times 2^{n-1}}\\{\boldsymbol {F}}_{n-1}&{\boldsymbol {F}}_{n-1}\end{bmatrix}}}することに相当する
$ 0_{1\times 2^{n-1}} 1_{1\times 2^{n-1}}が P - 1
$ {\boldsymbol {F}}_{n-1} {\boldsymbol {F}}_{n-1} が group = [x * (P + 1) for x in group]
僕はその後、部分集合ごとにXORしたけど、$ {\displaystyle {\boldsymbol {H}}_{2^{n}}={\boldsymbol {F}}_{n}^{\intercal }{\boldsymbol {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である場合だけ符号反転してるから
https://gyazo.com/5c9aa6ca4a24a6d8af633a07ebb33cf5
popcount(i & j)がij要素を符号反転した回数になる