TechFUL Coding Battle ～2024年5月回～ の問題解説です。
https://techful-programming.com/techful/event/5706
TCB にしては難し目の回で、自分も後ろ $4$ 問は理論値が達成できませんでした。
最近の TCB は公式解説を出してくれないので、誰かが書くしかないんですね。
かなり雑に書いてあるので、わからなかったら伝えてください。都度修正します。
簡単な解法あったらそれも教えてください。
$6,9,10,11,12$ 問目以外は省略します。
06
問題
長さ $N$ の英小文字からなる文字列 $S$ が与えられます。
以下の条件を満たす正整数 $K$ の最小値を求めてください。
- $S$ を左に $K$ 回サイクリックシフトした文字列 $T$ としたとき、英小文字から英小文字への全単射な置換 $f$ であって、任意の $i$ に対して $S_{i}=f(T_{i})$ であるようなものが存在する。
$1\leq N\leq 10^{5}$
解説
文字列の一致判定なのでハッシュを考えます。 長さ $N$ の $01$ 文字列 $S_{a}$ を $S$ の $i$ 文字目 が $a$ のときに限って、$S_{a}$ の $i$ 文字目が $1$ となるような文字列とします。
文字列の多重集合 ${S_{a},S_{b},\dots ,S_{z}}$ と ${T_{a},T_{b},\dots,T_{z}}$ が一致するような最小の整数 $K$ が求まればよくて、ローリングハッシュを用いれば十分高速です。
追記
$K$ としてあり得るものは $N$ の約数のみです。 ある $K$ が置換 $f$ を用いて、達成可能であると仮定します。$k=\mathrm{gcd}(K,N)$ とします。このとき、$aK - k$ が $N$ の倍数となるような正整数 $a$ が存在します。そのような $a$ を用いて、$f'=f^{a}$ とします。すると、$K=k$ のとき $f'$ を用いて、条件が達成可能になります。
よって、$N$ の約数の小さい順に $K$ を試して、達成可能ならそれを出力ということをすれば良いです。計算量は $O(d(N)N)$ です。
決定的な解法かつ、実装がこちらの方が短いです。この方法は、こたつがめさんに教えていただきました。
09
問題
長さ $N$ の非負整数列 $A,B$ が与えられます。 $A$ に対して以下の操作を好きな回数繰り返して、$A=B$ とすることが可能か否か判定してください。
- $2\leq i\leq N-1$ かつ $A_{i}=1$ であるようなものを選び、$A_{i-1},A_{i+1}$ を $A_{i-1}-1,A_{i+1}+1$ または $A_{i-1}+1,A_{i+1}-1$ で置き換える (どっちかを $+1$ 他方を $-1$ する) ただし、$A$ は常に非負整数列でなければならない。
例えば $(2,1,0,4) \to (1,1,1,4) \to (1,0,1,5)$ という操作が可能です。
$1\leq N\leq 10^{5}$
$0\leq A_{i}\leq 10^{5}$
$0\leq B_{i}\leq 10^{5}$
解説
このような逆操作が可能なものは極小である状態を考え、それが一致するかどうか判定すれば良いです。
結論から言うと、以下の操作を可能な限り繰り返して同じ配列になるならいいです。
- $2\leq i\leq |A|-1$ かつ $A_{i}=1$ であるようなものを選び、$A_{i-1},A_{i},A_{i+1}$ を取り除き、その部分に $A_{i-1}+A_{i+1}-1$ を挿入する。
これは stack を用いて $O(N)$ でできるので、高速に求まります。
どのようにしてこの考えが思いつくのでしょうか。
$A$ を $01$ 文字列に置き換えに置き換えます。 $A=(2,1,0,4)$ なら $1101001111$ のように、$A$ の要素と同じ数の $1$ を並べてその間に $0$ を挟んでいます。
このとき、問題の操作は $0101$ を $1010$ に置き換える操作、またはその逆に対応しています。
$(2,1,0,4) \to (1,1,1,4)$ は $1101001111$ から $1010101111$ への変化で、 $2$ 文字目から $5$ 文字目を反転させています。
$01$ 文字列を奇数番目だけ反転させると、問題の操作は $0000$ を $1111$ に変換させる操作、またはその逆になります。$0000$ と $1111$ の変換で同じ文字列にできるか否かは、文字列から $0000$ と $1111$ をできるかぎり消して、同じ文字列になるかを判定すればよいです。
この操作を $A$ に戻して考えると、解説の最初に書いた操作になります。
10
問題
整数 $X,Y,A,B,C,D,E,F,N$ が与えられます。
$2$ 次元座標上の点の列 $p_{n}$ を以下のように定義します。
$p_{0}=(x_{0},y_{0})=(X,Y)$
$p_{n}=(x_{n},y_{n})=(Ax_{n-1}+By_{n-1}+C,Dx_{n-1}+Ey_{n-1}+F)$
このとき以下の値を $998244353$ で割ったあまりを求めてください。
$$\sum_{n=1}^{N}||p_{n}-p_{n-1}||^{2}$$
ここで、$p=(x,y)$ に対して、$||p||=\sqrt{x^{2}+y^{2}}$ とします。
$-10^{18}\leq X,Y,A,B,C,D,E,F\leq 10^{18}$
$1\leq N\leq 10^{1000}$
解説
比較的シンプルな行列累乗の問題です。 何を管理すればいいかというと、$x^{2},xy,y^{2},x,y,ans, 1$ です。これがある整数 $N$ でわかっていれば、$N+1$ に対するこれらの値が線形で求まるため、行列に乗ります。
$N$ がとても大きいですが、$N$ の上の桁から見ていって、答えの行列を $10$ 乗した後、その行列にその桁の数だけ、ベースの行列をかけることをすれば良いです。
11
問題
長さ $N$ の非負整数列 $A$ が与えられます。ここで、$\mathrm{XOR}(A)=0$ が成り立ちます。
以下の操作を好きな回数繰り返してできる数列 $A$ の種類数を $998244353$ で割ったあまりを求めてください。
- 相異なる $1$ 以上 $N$ 以下の整数 $i,j$ と、非負整数 $x$ と $A_{j}$ 未満の非負整数 $y$ を選び、$A_{i}$ を $x$ に、$A_{j}$ を $y$ に置き換える。この操作後も $\mathrm{XOR}(A)=0$ である必要がある。
$1\leq N\leq 10^{5}$
$0\leq A_{i}< 2^{31}$
解説
$A$ の要素が全て $0$ のときの答えは $1$ になります。
$2^{a}\leq \max(A)<2^{a+1}$ を満たす整数 $a$ を求めます。
$A$ のなかで $a$ 桁目の bit が $1$ であるような整数の数を増やすことは不可能です。
$\min(A)<2^{a}$ であるなら、$a$ 桁目より下の桁は自由に決められます。 $a$ 桁目の $1$ の数は減らしたり同じ数を維持することは可能ですが、増やすことはできません。よって、$2^{a}\leq A_{i}$ となる $i$ の数を $b$ として、答えは以下のようになります。
$$2^{(N-1)a}\sum_{k=0,2,...,b}\mathrm{Bi}(N, k)$$
$2^{a}\leq \min(A)$ なら、$a$ 桁目は全て $1$ になります。$a$ 桁目を全て $1$ であるまま、下の桁を変更することは、$A$ の全ての要素から $2^{a}$ を引いた状態で操作することと同じです。そうでないときは、自由に決められるので、$A$ の全ての要素から $2^{a}$ を引いた数列を $A'$ とすると、答えは、$2^{(N-1)a}(2^{N-1}-1)$ に $A=A'$ のときの答えを足したものです。
よって、答えは $O(N\log(A))$ で求まります。
12
問題
整数 $N,K$ と 長さ $N$ の $01$ 文字列 $S$ が与えられます。
$S$ の連続する $K$ 文字で、すべて同じ数字であるものを反転させるという操作を何回でもできるとき、最終的にできる文字列の種類数を $998244353$ で割ったあまりを求めてください
解説
$9$ 問目と同様に連続する $01$ 文字列を消していきます。消した後の文字列に連続する $K$ 個の $0$ と $1$ を挿入して長さ $N$ の文字列にするときに、その場合の数が求まれば良いです。ただし、挿入の仕方が違くても、同じ文字列になることがあります。よって、一番最後の文字の後ろ以外は気を使って挿入するようにします。例えば、 $K = 1$ のときに、最初の文字の前にその文字と同じ文字を挿入するようなことはしません。
消した後の文字列の長さが $N-KA$ であるとき、 $i$ 文字目の前に $Ka$ 文字挿入する場合の数を $[x^{a}]f(x)$ としたとき、以下のようになります。
$$[x^{a}]f(x) = \frac{\mathrm{Bi}(Ka, a)}{(K - 1)\times a + 1}$$
一番最後に $Ka$ 文字挿入する場合の数を $[x^{a}]h(x)$ としたとき、以下のようになります。
$$h(x) = \dfrac{1}{1 - g(x)}$$
ただし、$g(x)$ は 以下が成り立つ多項式とします。
$$[x^{0}]g(x) = 0$$ $$[x^{a}]g(x) = \frac{2 \mathrm{Bi}(Ka - 1, a)}{Ka - 1}$$
$[x^{a}]f(x)$ は $a(K- 1)$ 個の $+1$ と $a$ 個の $-(K-{1})$ を並び替えて、累積和が負にならないようにする場合の数です。
$[x^{a}]g(x)$ は $a(K- 1)$ 個の $+1$ と $a$ 個の $-(K-{1})$ を並び替えて、累積和が最初と最後以外では正になるような場合の数の $2$ 倍です。
式の意味は以下の記事からわかります。
ここらへんもいいかも
ということで、答えは以下のようになります。
$$[x^{A}]\dfrac{f(x)^{N-KA}}{1-g(x)}$$
これはボスタン森とか累乗を高速に計算する方法を用いて $O(N(\log{N})^{2})$ とかで求まります。
多分定数倍も軽いです。
途中で登場した式は、 $K=1$ のときに壊れるかもしれませんが、$K=1$ のときの答えは自明に $2^{N}$ になるので、場合分けすれば問題ないです。
終わり
$12$ 問目に $5$ 時間弱かかっていますが、これは途中で一旦諦めて食事や入浴していたためです。個人的には $9$ 問目が一番難しかったです。
$12$ 問目は初手の方針が悪すぎて、時間切れになっちゃいました。少し時間をおいて考え直したらとんとん拍子で解けたので、調子が良かったらタイムボーナス取れたかなという感じです。
全完は $7$ 人でした。理論値は $1100$ 点です。
【次回予告】 かなり気が早いですが、次回開催も決定しました！！ 🏅7/24（水）10:00 ～ 7/30(火) 23:55🏅 7月回の参加もぜひぜひ事前エントリーお待ちしてます！✊
