今回は ABCDEF の 6 完 (51:48 + 15:00(3WA))。速解きセットだったけど、 G が惜しかった。 コンテスト後 AC できた。かなり悔しい。
制約が小さくても特に気にせず配列を使う。
すべて string にして結合してすべて値が同じかチェック。
つらい。差分というか辺？に対する累積和。 $r_i$ の位置によっては配列外がありえる。それをミスって 2WA した。
Abbreviate Fox という ARC の問題とほぼ同じ解答である。 空文字列 $T$ を用意して $S$ の先頭から入れていく。 $T$ の末尾が "ABC" になった時これを削除する。というのを繰り返すと解ける。
最大 $28$ 個ある辺のうち $7$ つ選んでグラフが連結になるものの重みを全探索すると解ける。 $ \displaystyle \binom{28}{7} \risingdotseq 10^6$ 程度なので全列挙できる。 今使った辺を bit で持っておいて作り終えたら Unionfind に辺を入れれば良い。
グラフの連結成分について考えるのがいい。 クエリが与えられた時、２つのノードを連結すると考える。このとき２つのノードがまだ連結されていない場合、 辻褄の合うように値を練り直す。相対的な値である。 このとき、必ず２つの連結成分についてサイズが小さい方の値を塗り替えるようにすると、 各ノードについて値の参照が $O(\log N)$ 回で済む。 そのため、そのように参照しながらやると速い。 また、$i$ は集合に入れられる。
また、すでに連結してある場合は、データの相対値が辻褄が合っているかを確かめる。 この時辻褄が合っていれば $i$ を入れてもいい。
これを最後までやると、高速に求めたい集合が求まる。
いろいろな DP を考えていったが、どうやら $N \leq 22$ の制約だと空間計算量 $O(2^N N)$ ができないようである。 そのため、どうにかして $O(2^N)$ の空間計算量にしたかった。時間計算量は割と大丈夫っぽい。
ここで、$dp[S]$ ... 数列 $B$ と対応させる物を左から決めていくと仮定した時、 現在 $A$ の値を $S$ だけ使ったときのコストの最小値というものを考える。まあそうだ。 この時、$A$ の連続した要素を一気に入れてしまうと、このように $1$ 次元で考えることができる。 そのため、$A$ についての現在入れられるあり得る区間を列挙してそれらを入れたときの遷移を作ればいい。
この区間を取る操作が $O(N^2)$ かかっているが、入れれば入れるほど可能な区間が少なくなるので 割と大丈夫っぽい。
自分は残り 5 ~ 10 分くらいでこれを思いついたが、区間をとる計算量を気にしてどうにか小さくできないかと 余計に考えてしまって間に合わなかった。かなりつらい思いをした。
Perf=1794 だった。ただ今回は G がもう少しで届きそうだったので、惜しかったなという気持ちもありつつ、 コンテスト後だったとしても解けてよかったとは思った。 まあ DP は得意な方ではあるが、うーん、いやでもこれはときたかったなぁ・・・ パフォはブレるのであまり気落ちしないように。
(2023/11/11 23:28)E の dfs なし解法として、 $(0, ..., 0, 1, ..., 1)$ という配列を next_permutation すると、 求めたい組合せの集合をすべて出してくれるようである。言語の仕様ではないようだが、重複した値の順列はすべて消してくれるみたいだ。
F については自分はマージテクで解いたが、想定解は重み付き Unionfind というもので解けるようだ。しかもけっこうまんまだった。 Unionfind の木について、自分の親との重みの差分を記録しておいて、経路圧縮によって根との重みの差分にするようにすると、 その連結成分についてのある場所とある場所の重みの差分が高速に求まるといったものであるようだ。
G については、計算量をしっかり見積もれなかったが、想定解を見ると、 実は区間を取る遷移をすべてやったとしても $O(2^N N)$ で済むようである。 これはある長さ $w$ の区間を取る物の数をすべて数え上げることでわかる。 $S$ の中のある位置に $0$ が $w$ 個連続に並んでいることを考える。このような位置の数は $N-w+1$ 個だけある。 そしてその指定された $w$ の区間以外は何でも値を取ることができるので、 $2^{N-w}$ 通りあることがわかる。 つまり、 $w$ の区間の長さのものの遷移の数は、$(N-w+1) \times 2^{N-w}$ 個であるので、これを $w$ について足し上げる。 これは答えが $2^N N - 2^N + 1$ である(Wolfram Alpha より) ので、 $O(2^N N)$ であることがわかる。 そのため、安心してこの問題を解くことができる。
こういう見積もりも考えられれば前述の計算量を気にして実装しようと思わなかったということをなくせるなと思う。 あと、ちゃんと計算してないけど実は小さそうみたいな発想もちょっと考えたい。
(2023/11/12 21:45)