たまたま TL に出てきたので参加。 意外と Twitter のおすすめは有能？
何問か気になったので記事にして書きます。
解法ものせるので、解きたい人は先に問題を見るか、慎重にスクロールしてください。
F: Three Keys Maze
問題概要
$N$ 種類の部屋と $M{}$ 個の通路で構成された迷宮がある。 また $K$ 種類の鍵が存在する。
部屋 $i$ には鍵 $a_{i,1},\dots a_{i,k_{i}}$ の $k_{i}$ 個の鍵がある。
鍵は持ち出せるが、同時に3個しか持てず、鍵を捨てた場合、その鍵は元の部屋に戻る。
通路 $i$ は部屋 $s_{i}$ と $t_{i}$ を結んでいて鍵 $b_{i}$ を持っているとき通過できる。
部屋 $1$ から $N$ までの最短距離はいくらか
$1\leq N\leq 100$
$1\leq M\leq 1000$
$1\leq K\leq 30$
考察
逆に、 $N$ から $1$ に行くことを考える。
このとき、鍵はいつでも拾えるが、部屋にあるゴミ箱にしか捨ててはいけないという感じになる。
鍵を拾うのは、通路を通る直前でよくて、鍵は捨てれるなら捨てちゃっていい。
これをすると、今いる部屋と持っている鍵を状態として見ることで、頂点数 $O(NK^{3})$ 辺の数 $O(K^{3}M)$ の$01$ BFS になる。
ある辺について、その辺を通れる状態数というのは $O(K^{2})$ 程度なので実際辺の数は $O(K^{2}M)$ になる。まあ多分通るやろと適当にやったけど通った
void solve(){ int N,M,K; cin>>N>>M>>K; vector<vector<bool>> key(N,vector<bool>(K+1)); rep(i,0,N){ int a; cin>>a; rep(j,0,a){ int b; cin>>b; key[i][b]=1; } } vector<vector<pair<int,int>>> G(N); rep(i,0,M){ int a,b,c; cin>>a>>b>>c; a--,b--; G[a].push_back({b,c}); G[b].push_back({a,c}); } int dp[N][K+1][K+1][K+1]; rep(i,0,N) rep(j,0,K+1) rep(k,0,K+1) rep(l,0,K+1) dp[i][j][k][l]=-1; //vector dp(N,vector(K+1,vector(K+1,vector<int>(K+1,-1)))); vector<tuple<int,int,int,int>> order; order.push_back({N-1,0,0,0}); dp[N-1][0][0][0]=0; vector<int> p,q; rep(rp,0,order.size()){ int a,b,c,d; tie(a,b,c,d)=order[rp]; int cost=dp[a][b][c][d]; p={b,c,d}; rep(i,0,3) if(key[a][p[i]]) p[i]=0; if(a==0&&vec_max(p)==0){ cout<<cost<<"\n"; return; } for(auto e:G[a]){ q=p; bool ok=0; rep(i,0,3){ if(q[i]==e.second) ok=1; } rep(i,0,3){ if(!ok&&q[i]==0) q[i]=e.second,ok=1; } if(ok){ sort(all(q)); if(dp[e.first][q[0]][q[1]][q[2]]==-1){ dp[e.first][q[0]][q[1]][q[2]]=cost+1; order.push_back({e.first,q[0],q[1],q[2]}); } } } } cout<<"-1\n"; }
I: Plus||Minus||Zero
長さ $N$ の正整数列 $X$ が与えられるので、$i=1,2,\dots , N$ について、独立に以下の問いに答える。
$X_{i}$ を $0$ に変更する。 要素が $-1,0,1$ のいずれかである長さ $N$ の整数列 $s$ を用いて、 $\sum s_{j}X_{j}$ と表せない正整数のうち、最も最小のものを求める。
$2\leq N\leq 60$
$1\leq X_{i}\leq 20000$
考察
この程度の制約なら bitset 高速化で全ての問題を独立に解くことができる。
$O(N^{3}X/w)$ とか？
void solve(){ const int M=3000000,C=M/2; int N; cin>>N; vector<int> X(N); rep(i,0,N) cin>>X[i]; rep(i,0,N){ bitset<M> dp; dp[C]=1; rep(j,0,N) if(i!=j) dp=((dp)|(dp<<X[j])|(dp>>X[j])); int ind=1; while(dp[ind+C]) ind++; cout<<ind<<"\n"; } }
J: Infinite Pokaiko Theorem
英小文字からなる文字列 $S$ と整数 $N$ が与えられます。
文字列 $T$ について、スコアを以下のようにします。
- $T$ の連続部分列で、 $S$ であるものをひとつ見つけ、その区間の $|S|$ 個の文字を全て
#に変えるという操作を $T$ に対して行うことができる回数の最大値
文字列 $T$ を長さ $N$ の英小文字からなる文字列から一様ランダムにとったとき、スコアの期待値を $\pmod{998244353}$
$1\leq |S|\leq 2000$
$1\leq N\leq 10^{18}$
考察
$T$ から $S$ を取る操作というのは前から貪欲でいい。
こういう問題は後ろの何文字が $S$ の prefix と一致しているかというのを状態として持って dp すれば良くて、 高々 $2$ 次の多項式を持って行列累乗すれば $O(|S|^{3}\log(N))$ で解ける。
これくらいシンプルな形の行列累乗の形は BMBM 法が適用できるらしいので $O(|S|^{2}\log(|S|)\log(N))$ で解ける。これが想定解らしい。
自分は $O(|S|\log(|S|)\log(N))$ で解いた。
まず、以下の条件を満たす多項式 $f(x)$ を求める。
- $[x^{a}](f(x))=$ 長さ $a$ の文字列をランダムにとったとき、 連続部分列で $S$ が含まれる箇所が一番最後のみである文字列が出現する期待値
$a\lt |S|$ については $[x^{a}](f(x))=0$ となる。
$|S\leq a$ については、$\frac{1}{26^{|S|}}$ から一番最初に $S$ が現れるのが長さ $k$ になったタイミングであるものの全ての $|S|\leq k\lt a$ に対する総和を引けば良い。
一番最後が $S$ である長さ $k$ の文字列 $U$ にランダムに $|T|-k$ 文字足すことで最後が $S$ になる確率を求めたい。
$|S|\leq |T|-k$ のときの確率は $\frac{1}{26^{|S|}}$。
$|T|-k\lt |S|$ のときは足す文字は $S$ の後ろ $|T|-k$ 文字になる。その文字を足して末尾を $S$ にできるなら確率は $\frac{1}{26^{|T|-k}}$ となる。
これを式で表すと以下のようになる。
$[x^{a}](f(x))=\frac{1}{26^{|S|}}-[x^{a}](\frac{x^{|S|}f(x))}{26^{|S|}(1-x)})-[x^{a}](g(x)f(x))$
$g(x)$ は定数項が $0$ で $x^{i}(1\leq i\lt N)$ の項は $S$ の $(N-i)$ 文字の接頭辞と接尾辞が同じなら $\frac{1}{26^{i}}$ そうでないなら $0$ の係数がつく。これは Zalgo を用いて $O(|S|)$ で求められる。
以上より、 $f(x)$ は以下を満たす。
$f(x)=\frac{x^{|S|}(1-f(x))}{26^{|S|}(1-x)}-g(x)f(x)$
$\frac{f(x)}{1-f(x)}=\frac{x^{|S|}}{26^{|S|}(1-x)(1+g(x))}$
実はこの問題の答えは $\frac{f(x)}{(1-f(x))(1-x)}$ なので、あとはボスタン森法を使えば良い。
この問題の答えは $\frac{f(x)}{(1-f(x))(1-x)}$になるのは、 $[x^{a}]\frac{f(x)}{1-f(x)}$ が $T$ から貪欲に $S$ をとったときに $a$ 文字目が末尾のものを取る確率になっているので、それの累積和を求めればスコアの期待値が求まるから。
hackerrank エアプすぎて、 c++ を選んで提出していたが、 c++20 を使うには c++20 を別で選ばなきゃいけなくて、それを知らなかったせいで ACL の畳み込みのライブラリがコンパイルできなくて通らなかった。
畳み込みを別のものを使って、コンテスト後にAC
この実装は Z_algo を使ってないため、追加で $O(|S|^{2})$ かかるが、そこを置き換えればより大きい制約でも解くことができる。
void solve(){ ll N; string S; cin>>N>>S; int L=S.size(); const ll M=26; ll rev=mod+1; while(rev%M) rev+=mod; rev/=M; vector<ll> p(L+1,1); rep(i,0,L) p[i+1]=(p[i]*rev)%mod; vector<ll> g(L); rep(i,1,L){ bool ok=1; rep(j,i,L) if(S[j]!=S[j-i]) ok=0; if(ok) g[i]=p[i]; } vector<ll> U={1,-1}; g[0]=1; auto tmp=convolution(g,U); vector<ll> A(L+1); A[L]=p[L]; auto B=tmp; B=convolution(B,U); auto ans=po167::boston_mori(A,B,N); cout<<ans<<"\n"; }
似たような問題が nowcoder の multiuni で出てた。
問題概要としては正整数 $N,K$ と01文字列 $T$ が与えられるので、長さ $N$ の01文字列で連続部分列として $T$ が現れる回数がちょうど $K$ 回なものの数を mod 998 で求める問題。今回は取る箇所が重なっていても良い
これも一番後ろに $T$ が出てくるものの数を表す多項式を組んで一工夫すれば解ける
