SRM 657 Div1 Medium PolynomialGCD
各素数ごとに独立になっているので、それぞれ解いて解を掛け合わせればよい。
素数 p の出現回数が一番多くなる場所を決めると、全体で何回 p が出現するかを O(NlogN/p) 程度で計算でき、場所の個数は、Nなので、各素数ごとに、O(N^2logN/p) で計算できる。
全体では、O(Nlog^2N) 程度で計算できる。
コーナーケースとして、s = "19592" のようなケースに注意する必要がある (1WA)
この例では、2 で 12 回割り切ることができる。 (一番左の 1 に 8 を割り当てるのが最適となるが、考察を間違えると、左右の 1 と 2 に 4 を割り当ててしまう。)
bool isPrime(ll x){ if(x<=1) return false; for(ll i = 2; i*i <= x; i++) if(x%i==0) return false; return true; } ll pow_mod(ll a, ll r, ll m){ ll x = 1; while(r){ if(r&1) (x*=a)%=m; (a*=a)%=m; r>>=1; } return x; } class PolynomialGCD { public: int gcd(string s) { int n = s.size(); vector<int> v(n); rep(i, n) v[i] = s[i]-'0'; ll res = 1; for(ll i = 2; i <= n; i++){ if(!isPrime(i)) continue; ll cnt = INF; for(ll j = 0; j < n; j++){ ll c = 0, c2 = INF; ll x = i; while(c2>=i){ c2 = 0; for(ll k = j%x; k < n; k += x) c += v[k], c2++; x *= i; } chmin(cnt, c); } (res*=pow_mod(i, cnt, mod))%=mod; } return res; } };
SRM 654 Div1 Medium SuccessiveSubtraction2
区間を 2 つ選んで符号を反転させることができるので、区間和の最小値が計算できれば、あとは簡単に計算できる。
これは、O(N) でやってよいので、配列が更新される度に最初から計算し直せば良い。(解いているときは何も考えずに、StarrySky Tree を貼ってしまい、計算量が余計に log 倍されてしまった。)
どちらの解法でも TLE しているが、不具合が無ければ通るはず。
配列版 O(QN)
#define N 2010 int dp[N], dp2[N]; int s[N], s2[N]; class SuccessiveSubtraction2 { public: vector <int> calc(vector <int> a, vector <int> p, vector <int> v) { int n = a.size(), m = p.size(); vector<int> res; mset(dp, 0); mset(dp2, 0); mset(s, 0); mset(s2, 0); rep(i, m){ a[p[i]] = v[i]; ll sum = a[0]; for(int j = 1; j < n; j++) sum -= a[j]; if(n<=2){ res.pb(sum); continue; } for(int j = 2; j < n; j++) s[j+1] = s[j]+a[j]; for(int j = n-1; j >= 2; j--) s2[j] = s2[j+1]+a[j]; for(int j = 2, mn = 0; j <= n; j++){ chmin(mn, s[j]); dp[j] = max(dp[j-1], s[j]-mn); } for(int j = n-1, mn = 0; j >= 1; j--){ chmin(mn, s2[j]); dp2[j] = max(dp2[j+1], s2[j]-mn); } int r = -INF; for(int j = 2; j < n; j++) chmax(r, dp[j]+dp2[j]); res.pb(sum+2*r); } return res; } };
StarrySky Tree 版 O(QNlogN)
struct starrysky { int seg_n; vector<ll> data, datb; void init(int n, ll initial_value = 0){ seg_n = 1; while(seg_n<n) seg_n<<=1; data = vector<ll>(seg_n*2-1, 0); datb = vector<ll>(seg_n*2-1, 0); } // min(v[a], v[a+1],..., v[b-1]) // to use: query(a, b); ll rmin(int a, int b, int k, int l, int r){ if(r <= a || b <= l) return INF; if(a <= l && r <= b) return data[k]+datb[k]; return min(rmin(a, b, k*2+1, l, (l+r)/2), rmin(a, b, k*2+2, (l+r)/2, r))+data[k]; } ll rmin(int a, int b){ return rmin(a, b, 0, 0, seg_n); } void radd(int a, int b, ll x, int k, int l, int r){ if(r <= a || b <= l) return;//return INF; if(a <= l && r <= b){ data[k] += x; return; } else { radd(a, b, x, k*2+1, l, (l+r)/2); radd(a, b, x, k*2+2, (l+r)/2, r); datb[k] = min(datb[k*2+1]+data[k*2+1], datb[k*2+2]+data[k*2+2]); } } void radd(int a, int b, ll x){ radd(a, b, x, 0, 0, seg_n); } }; #define N 2010 int dp[N], dp2[N]; class SuccessiveSubtraction2 { public: vector <int> calc(vector <int> a, vector <int> p, vector <int> v) { int n = a.size(), m = p.size(); vector<int> res; starrysky x, y; x.init(n+2); y.init(n+2); ll sum = a[0]; for(int i = 1; i < n; i++) sum -= a[i]; for(int i = 2; i < n; i++){ x.radd(i, n+2, a[i]); y.radd(0, i, a[i]); } rep(i, m){ if(p[i]==0) sum += v[i]-a[0]; else sum -= v[i]-a[p[i]]; if(p[i]<2) a[p[i]] = v[i]; else { int d = v[i]-a[p[i]]; x.radd(p[i], n+2, d); y.radd(0, p[i], d); a[p[i]] = v[i]; } int r = -INF; mset(dp, 0); mset(dp2, 0); for(int j = 2; j < n; j++){ int mn = x.rmin(j, j+1)-x.rmin(0, j+1); dp[j] = max(dp[j-1], mn); } for(int j = n-1; j >= 2; j--){ int mn = y.rmin(j, j+1)-y.rmin(j, n); dp2[j] = max(dp2[j+1], mn); } for(int j = 2; j < n; j++) chmax(r, dp[j]+dp2[j+1]); if(n<=2) r = 0; res.pb(sum+r*2); } return res; } };
SRM 652 Div1 Medium MaliciousPath
K = 0 のときは、 dijkstra で解ける。
頂点を *1 と拡張すると、K>0 の場合も dijkstra を多少書き換えるだけで解くことができる。
辺の長さが少し特殊なので、k=0..K として順番に dijkstra を行うことで効率よく最短路が求まる。
計算量は、O(K(N+M)logN)となる。
下記コードは editorial や他人の解説記事を読んだ感じではおそらく正しいが、practice ルームでは TLE となるので注意。(同じような現象が最近 (2018/02/07) よく起こるので、サーバ側の問題だと思う)
#define NN 1010 vector<P> g[NN], g2[NN]; ll d[NN][NN], d2[NN][NN]; class MaliciousPath { public: long long minPath(int n, int K, vector <int> f, vector <int> t, vector <int> c) { rep(i, n) g[i].clear(); rep(i, n) g2[i].clear(); int m = f.size(); rep(i, m){ g[f[i]].pb(P(c[i], t[i])); g2[t[i]].pb(P(c[i], f[i])); } rep(i, n){ sort(all(g[i])); sort(all(g2[i])); } rep(i, n) fill(d[i], d[i]+NN, INF); mset(d2, 0); rep(k, K+1) d[n-1][k] = 0; rep(k, K+1){ priority_queue<P, vector<P>, greater<P>> q; q.push(P(0, n-1)); while(!q.empty()){ P p = q.top(); q.pop(); ll l = p.fst, u = p.snd; if(d[u][k]<l) continue; for(auto x: g2[u]){ ll l2 = max(d2[x.snd][k], l+x.fst), v = x.snd; if(d[v][k]>l2){ d[v][k] = l2; q.push(P(l2, v)); } } } rep(i, m) chmax(d2[f[i]][k+1], d[t[i]][k]+c[i]); } return d[0][K]==INF?-1:d[0][K]; } };
*1:頂点), (token数
SRM 651 Div1 Medium FoxConnection3
2次元グリッド上にきつねがN匹いる (N <= 6)
すべてのきつねが辺で連結になるように動かすとき、最小で何ステップでできるか？(きつねは重なることは出来ない)
まず、1次元の場合には、中央値に寄せるのが一番効率がよい。 (N が偶数のときは、真ん中の2つの値の平均を中央値とする。)
2次元の場合にもできるだけ中央に寄せるのがよい。
中央に近づけたあとは、高々 5*5 マスのグリッド上にすべてのきつねがいることになるので、BFS で調べれば良い。(状態数は、高々25C6 (=177,100)で、遷移も高々24なので、map を使っても十分間に合う。)
vector<int> x, y, x2, y2; int n; map<vector<int>, int> dp; int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; int h, w; struct UF { vector<int> par, rank, sz; void init(int n){ par = rank = vector<int>(n, 0); sz = vector<int>(n, 1); for(int i = 0; i < n; i++){ par[i] = i; } } int find(int x){ if(par[x] == x){ return x; }else{ return par[x] = find(par[x]); } } int size(int x){ return sz[find(x)]; } void unite(int x, int y){ x = find(x); y = find(y); if(x == y) return; if(rank[x] < rank[y]){ par[x] = y; sz[y] += sz[x]; }else{ par[y] = par[x]; if(rank[x] == rank[y]) rank[y]++; sz[x] += sz[y]; } } bool same(int x, int y){ return find(x) == find(y); } }; class FoxConnection3 { public: bool check(vector<int> &v){ UF uf; uf.init(n); rep(i, n) rep(j, n){ int a = v[i]/w, b = v[i]%w, c = v[j]/w, d = v[j]%w; if(abs(a-c)+abs(b-d)==1) uf.unite(i, j); } return uf.size(0)==n; } void comp(vector<int> &x, ll &res){ for(int i = 4; i >= 0; i--){ int cnt = 0, cnt2 = 0; rep(j, n){ if(x[j]==i) cnt++; else if(x[j]>i) cnt2++; } if(cnt==0){ rep(j, n) if(x[j]>i) x[j]--; res += min(cnt2, n-cnt2); } } } long long minimalSteps(vector <int> x_, vector <int> y_) { x=x_;y=y_; n = x.size(); x2=x; y2=y; sort(all(x2)); sort(all(y2)); ll xx = ((ll)x2[n/2]+x2[(n-1)/2])/2, yy = ((ll)y2[n/2]+y2[(n-1)/2])/2; cerr<<xx<<endl; ll res = 0; rep(i, n){ if(x[i]<xx-2){ res += xx-2-x[i]; x[i] = xx-2; rep(_, 2) rep(j, n) if(i!=j&&x[i]==x[j]&&y[i]==y[j]) x[i]++,res++; } if(y[i]<yy-2){ res += yy-2-y[i]; y[i] = yy-2; rep(_, 2) rep(j, n) if(i!=j&&x[i]==x[j]&&y[i]==y[j]) y[i]++,res++; } if(x[i]>xx+3){ res += x[i]-xx-3; x[i] = xx+3; rep(_, 2) rep(j, n) if(i!=j&&x[i]==x[j]&&y[i]==y[j]) x[i]--,res++; } if(y[i]>yy+3){ res += y[i]-yy-3; y[i] = yy+3; rep(_, 2) rep(j, n) if(i!=j&&x[i]==x[j]&&y[i]==y[j]) y[i]--,res++; } } rep(i, n) x[n-i-1] -= xx-2; rep(i, n) y[n-i-1] -= yy-2; comp(x, res); comp(y, res); h = w = 1; rep(i, n) chmax(h, x[i]+1); rep(i, n) chmax(w, y[i]+1); vector<int> v(n); rep(i, n) v[i] = x[i]*w+y[i]; sort(all(v)); dp[v] = 0; queue<vector<int>> q; q.push(v); while(true){ vector<int> vv = q.front(); q.pop(); int t = dp[vv]; if(check(vv)) return res+t; for(auto &a: vv){ int aa = a; rep(i, 4){ int ax = aa/w+dx[i], ay = aa%w+dy[i]; if(ax<0||ax>=h||ay<0||ay>=w) continue; a = ax*w+ay; vector<int> vv2(vv); int cnt = 0; rep(j, n) if(vv2[j]==a) cnt++; if(cnt>1) continue; sort(all(vv2)); if(!dp.count(vv2)){ dp[vv2] = t+1; q.push(vv2); } } a = aa; } } } };
SRM 650 Div1 Medium TheKingsRoadsDiv1
グラフ G が与えられる。G が深さ9以下の完全二分木に3本の余計な辺を追加したグラフであるかを判定する問題である。
色々な解法が考えられるが、根の候補を小さくしてから、それが正しいか判定するという方針で解いた。
根の候補を小さくする部分は、
全点間距離を O(N^2) で前計算し、u からの距離が h 以上の頂点の頂点が無く、 距離が h-1 である頂点が floor(2^(h-3)) 個以上存在する頂点 u を候補とすると、だいたい 1 個くらいに絞ることができる。(未証明)
根を固定したあとは、取り除く辺を全部試せば良い。
完全二分木は、葉以外の頂点は子が2つあるという性質を用いて効率よく全探索できる。深さt と、深さ t の頂点集合と、使用済み頂点集合 (used配列) を状態として持つような dfs を行った。(下記コード参照)
下記コードでは、next_permutation を用いて無駄な計算を行っているが、高々、O(N) * (5!)*(4!)*(3!) 程度で計算できる。
#define N 1030 int d[N][N]; vector<int> g[N]; int n, h; bool used[N]; class TheKingsRoadsDiv1 { public: void bfs(int u0){ int *du = &d[u0][0]; fill(du, du+N, INF); du[u0] = 0; queue<int> q; q.push(u0); while(!q.empty()){ int u = q.front(); q.pop(); for(auto v: g[u]){ if(du[v]>du[u]+1){ du[v] = du[u]+1; q.push(v); } } } } bool dfs(vector<int> us, int t){ if(t==h-1) return true; for(auto u: us) used[u] = true; vector<vector<int>> xs; vector<int> vs; for(auto u: us){ vector<int> x; for(auto v: g[u]){ if(used[v]) continue; x.pb(v); } if(x.size()>=6||(x.size()<2)){ for(auto u: us) used[u] = false; return false; } if(x.size()==2){ vs.pb(x[0]); vs.pb(x[1]); continue; } sort(all(x)); xs.pb(x); } int l = xs.size(); if(l<=0){ if(vs.size()==(1<<(t+1)) && dfs(vs, t+1)) return true; for(auto u: us) used[u] = false; return false; } while(true){ do{ vector<int> vs2(vs); for(auto x: xs){ rep(i, 2) vs2.pb(x[i]); } sort(all(vs2)); UNIQUE(vs2); if(vs2.size()!=(1<<(t+1))) continue; if(dfs(vs2, t+1)) return true; }while(next_permutation(all(xs[l-1]))); for(int i = l-2; ; i--){ if(i<0){ for(auto u: us) used[u] = false; return false; } if(next_permutation(all(xs[i]))){ for(int j = i+1; j <= l-1; j++) sort(all(xs[j])); break; } } } } string getAnswer(int h_, vector <int> a, vector <int> b) { h=h_; mset(used, 0); n = (1<<h)-1; rep(i, n) g[i].clear(); rep(i, a.size()){ a[i]--; b[i]--; g[a[i]].pb(b[i]); g[b[i]].pb(a[i]); } rep(i, n) bfs(i); int lb = 1<<(max(h-3, 0)); rep(i, n){ int cnt = 0; rep(j, n){ if(d[i][j]==h-1) cnt++; if(d[i][j]>=h) cnt = -INF; } if(cnt >= lb){ vector<int> x; x.pb(i); if(dfs(x, 0)) return "Correct"; } } return "Incorrect"; } };
SRM 646 Div1 Medium TheGridDivOne
制約を見ると明らかに座標圧縮なので、座標圧縮して dijkstra 等のアルゴリズムで最短経路を求めると解ける。
出題された当時は地力 (実装力) が足りず解けなかったが、今見ると、特に難しいところのない素直な問題に見える。
#define N 150 ll d[N][N]; vector<int> x, y, x2, y2; int n; map<int, int> xd, yd; int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; class TheGridDivOne { public: int find(vector <int> x_, vector <int> y_, ll k) { x=x_; y=y_; n = x.size(); x2.clear(); y2.clear(); x2.pb(0); y2.pb(0); rep(i, n) rep(j, 3){ x2.pb(x[i]+j-1); y2.pb(y[i]+j-1);} sort(all(x2)); UNIQUE(x2); sort(all(y2)); UNIQUE(y2); int h = x2.size(), w = y2.size(); rep(i, h) xd[x2[i]] = i; rep(i, w) yd[y2[i]] = i; rep(i, N) fill(d[i], d[i]+N, INF); rep(i, n) d[xd[x[i]]][yd[y[i]]] = -1; d[xd[0]][yd[0]] = 0; priority_queue<P, vector<P>, greater<P>> q; q.push(P(0, xd[0]*N+yd[0])); ll res = 0; while(!q.empty()){ P p = q.top(); q.pop(); int a = p.snd/N, b = p.snd%N; ll l = p.fst; if(l>d[a][b]) continue; rep(i, 4){ int a2 = a+dx[i], b2 = b+dy[i]; if(a2==h) chmax(res, k-l+x2[a]); if(a2<0||a2>h||b2<0||b2>w||d[a2][b2]<0) continue; ll l2 = l+abs(x2[a]-x2[a2])+abs(y2[b]-y2[b2]); if(dx[i]==1) chmax(res, x2[a]+min(l2, k)-l); if(l2<d[a2][b2]){ d[a2][b2] = l2; if(l2<=k) q.push(P(l2, a2*N+b2)); } } } return res; } };
SRM 644 Div1 Medium MakingTournament
実験すると、K=1 のときは、フィボナッチ数列になる。
K>1 のときは、2^K +1 項間漸化式になりそうなので、最初の 2^K +1 項あたりまでを愚直に計算すると、行列を復元することができる。
というのを実装したら通った。直感的には正しいことが分かるが、ちゃんと証明して解きたい。
#define M 300 ll f[7][M], g[7][M]; ll pow_mod(ll a, ll r, ll m){ ll x = 1; while(r){ if(r&1) (x*=a)%=m; (a*=a)%=m; r>>=1; } return x; } vector<ll> mul(vector<vector<ll>> &A, vector<ll> &x){ int n = x.size(); vector<ll> y(n, 0); rep(i, n) rep(j, n) (y[i]+=A[i][j]*x[j])%=mod; return y; } void mul(vector<vector<ll>> &A){ vector<vector<ll>> B(A); int n = A.size(); A = vector<vector<ll>>(n, vector<ll>(n, 0)); rep(k, n) rep(i, n) rep(j, n) (A[i][j]+=B[i][k]*B[k][j])%=mod; } class MakingTournament { public: int howManyWays(long long N, int K) { mset(f, 0); mset(g, 0); rep(i, M) g[0][i] = 1; g[0][1] = 0; f[0][0] = 1; for(ll i = 2; i < M; i++) f[0][i] = (f[0][i-1]+f[0][i-2])%mod; for(ll k = 1; k < 6; k++){ rep(i, M) g[k][i] = (f[k-1][i]-g[k-1][i]+mod)%mod; f[k][0] = 1; rep(i, M) rep(j, i) (f[k][i]+=f[k][j]*g[k][i-j])%=mod; } ll m = 1<<K; vector<vector<ll>> A(m, vector<ll>(m, 0)); rep(i, m-1) A[i+1][i] = 1; rep(i, m){ ll sum = 0; rep(j, m) (sum+=f[K-1][i+j+1]*A[0][m-j-1])%=mod; A[0][i] = (f[K-1][i+m+1]-sum+mod)%mod; } vector<ll> x(m, 0); x[0] = 1; N--; while(N){ if(N%2) x = mul(A, x); mul(A); N>>=1; } return (x[m-1]+mod)%mod; } };
