以下の内容はhttps://potato167.hatenablog.com/entry/2024/10/02/203000より取得しました。

TCB 2024 年 9 月回の解説

TechFUL Coding Battle ～2024年9月回～ の解説です。

後ろ $6$ 問全部難しい気がするんですけど...

すごく解説を書くのが重くて、かなり雑に書いたので、不明点があればツイッターなどで都度教えてください。

07 - degree sequence of partition

問題

正 $N$ 角形に対角線を $N - 3$ 本交わらないように引きました。

$N$ 角形の頂点を時計回りに頂点 $1, 2, \dots N$ とします。

長さ $N$ の数列 $d$ が与えられます。頂点 $i$ の次数が $d_{i}$ であるような引き方が存在するか否か判定してください。

  • $3 \leq N \leq 1000$
  • $2 \leq d_{i} \leq N - 1$

解説

引き方が正しいとき、次数が $2$ になるような頂点が必ず存在します。また、このような頂点を $i$ としたとき、頂点 $i - 1$ と頂点 $i + 1$ は結ばれています。

よって、三角形 $i - 1, i, i + 1$ を取り除くことで、 $N - 1$ のケースに帰着できます。これを、 $N = 3, D = (2, 2, 2)$ になるまで繰り返すことができたら yes です。計算量は $O(N ^ {2})$ です。

$O(N)$ のやり方がある気がするんですが、自分はまだ思いついていません。

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
template<class T> T vec_min(vector<T> &a){assert(!a.empty());T ans=a[0];for(auto &x:a) ans=min(ans,x);return ans;}

int main() {
    int N;
    cin >> N;
    vector<int> D(N);
    rep(i, 0, N) cin >> D[i];
    bool ok = 1;
    while ((int)D.size() != 3){
        if (vec_min(D) != 2){
            ok = 0;
            break;
        }
        int ind = 0;
        // 2 を探す
        rep(j, 0, N){
            if (D[j] == 2){
                ind = j;
                break;
            }
        }
        vector<int> n_D(N);
        // D[ind] = 2 を一番後ろにローテートする
        rep(j, 0, N){
            n_D[(j + N - 1 - ind) % N] = D[j];
        }
        // 辺を消す
        n_D.pop_back();
        n_D.back()--;
        n_D.front()--;
        swap(n_D, D);
        N--;
    }
    // 三角形になっているか確認
    rep(i, 0, 3){
        if (D[i] != 2) ok = 0;
    }
    cout << (ok ? "Yes\n" : "No\n");
}

08 - farthest from two

問題

$N$ 頂点の木が与えられます。

$Q$ 個のクエリを処理してください。

  • 頂点 $u, v$ が与えられるので、 $\max_{1\leq x\leq N}(\mathrm{dist}(u, x) + \mathrm{dist}(v,x))$ を出力してください。

$1\leq N \leq 5 \times 10^{4}$ $1\leq Q \leq 5 \times 10^{4}$

解説

頑張ってダブリングすると $O(N\log(N)+Q\log(N))$ で解けます。

まず、適当な頂点を取って、根付き木とし、以下の値を全ての頂点に対して事前に計算しておきます。

  • $A[i] : $ 頂点 $i$ の部分木に属する頂点のうち、$i$ との距離の最大値
  • $B[i] : $ 頂点 $i$ の部分木に属さない頂点のうち、$i$ との距離の最大値
  • $C[i] : $ 頂点 $i$ の部分木に属さないかつ、$i$ の親の部分木に属する頂点のうち、頂点 $i$ の親との距離の最大値

$u, v$ の LCA を $w$ とします。このとき $u \neq w$ かつ $v\neq w$ ならば、答えは以下の値の最大値の $2$ 倍に、 $\mathrm{dist}(u, v)$ を足したものになります。

  • $A[u]$
  • $A[v]$
  • $B[w]$
  • $u, v$ 間の頂点のうち、 $w$ と、親が $w$ である頂点を除いた全ての頂点に対する、$C[i]$ の最大値
  • $w$ の子であって、 $u, v$ 間の頂点でない全ての頂点に対する、 $A[i]$ の最大値に $1$ を足したもの

上 $3$ つは簡単に求まります。 $C[i]$ の最大値はダブリングや HLD + sparse table で $O(\log(N))$ で求めることができます。一番最後は、各頂点に対して、子の頂点の $A[i]$ の大きい方から $2$ つを持っておくことによって、 $O(1)$ で求めることができます。

よって、クエリを高速に処理することができました。以下の実装例は本番提出のコードであることに注意してください。

雑な実装例 

#line 1 "a.cpp"
#include <bits/stdc++.h>
using namespace std;
using std::cout;
using std::cin;
using std::endl;
using ll=long long;
using ld=long double;
const ll ILL=2167167167167167167;
const int INF=2100000000;
#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
#define all(p) p.begin(),p.end()
template<class T> using _pq = priority_queue<T, vector<T>, greater<T>>;
template<class T> ll LB(vector<T> &v,T a){return lower_bound(v.begin(),v.end(),a)-v.begin();}
template<class T> ll UB(vector<T> &v,T a){return upper_bound(v.begin(),v.end(),a)-v.begin();}
template<class T> bool chmin(T &a,T b){if(a>b){a=b;return 1;}else return 0;}
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return 1;}else return 0;}
template<class T> void So(vector<T> &v) {sort(v.begin(),v.end());}
template<class T> void Sore(vector<T> &v) {sort(v.begin(),v.end(),[](T x,T y){return x>y;});}
bool yneos(bool a,bool upp=0){if(a){cout<<(upp?"YES\n":"Yes\n");}else{cout<<(upp?"NO\n":"No\n");}return a;}
template<class T> void vec_out(vector<T> &p,int ty=0){
    if(ty==2){cout<<'{';for(int i=0;i<(int)p.size();i++){if(i){cout<<",";}cout<<'"'<<p[i]<<'"';}cout<<"}\n";}
    else{if(ty==1){cout<<p.size()<<"\n";}for(int i=0;i<(int)(p.size());i++){if(i) cout<<" ";cout<<p[i];}cout<<"\n";}}
template<class T> T vec_min(vector<T> &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmin(ans,x);return ans;}
template<class T> T vec_max(vector<T> &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmax(ans,x);return ans;}
template<class T> T vec_sum(vector<T> &a){T ans=T(0);for(auto &x:a) ans+=x;return ans;}
int pop_count(long long a){int res=0;while(a){res+=(a&1),a>>=1;}return res;}
template<class T> bool inside(T l,T x,T r){return l<=x&&x<r;}


/*

#include<vector>
#include<cassert>
#include<math.h>

*/

namespace po167{
    struct LCA{
        std::vector<int> deep;
        std::vector<std::vector<int>> parent;
        int n;
        int m;
        LCA(int root_node,std::vector<std::vector<int>> &G):n((int)G.size()),m((int)(2+std::log(n)/std::log(2))){
            deep.resize(n),parent.assign(m,std::vector<int>(n));
            for(int i=0;i<n;i++){
                parent[0][i]=-1;
                deep[i]=-1;
            }
            deep[root_node]=0;
            parent[0][root_node]=-2;
            std::vector<int> order(n);
            order[0]=root_node;
            int look=1;
            for(int i=0;i<n;i++){
                for(auto x:G[order[i]]){
                    if(deep[x]==-1){
                        deep[x]=deep[order[i]]+1;
                        parent[0][x]=order[i];
                        order[look]=x;
                        look++;
                    }
                }
            }
            assert(look==n);//when G is not connected
            for(int i=0;i<n;i++) for(int j=1;j<m;j++){
                    int var=order[i];
                    if(parent[j-1][var]==-2) parent[j][var]=-2;
                    else{
                        parent[j][var]=parent[j-1][parent[j-1][var]];
                    }
                }
        }
        int lca(int var_1,int var_2){
            if(deep[var_1]>deep[var_2]){
                std::swap(var_1,var_2);
            }
            int dif=deep[var_2]-deep[var_1];
            int ind=0;
            while(dif){
                if(dif&1){
                    var_2=parent[ind][var_2];
                }
                ind++;
                dif>>=1;
            }
            if(var_1==var_2) return var_1;
            for(int i=m-1;i>=0;i--){
                if(parent[i][var_1]!=parent[i][var_2]){
                    var_1=parent[i][var_1];
                    var_2=parent[i][var_2];
                }
            }
            return parent[0][var_1];
        }
        int back(int var_1,int dif){
            for(int i=0;i<m;i++){
                if(dif==0) break;
                if(dif&1){
                    var_1=parent[i][var_1];
                }
                dif>>=1;
            }
            return var_1;
        }
        // https://atcoder.jp/contests/abc267/tasks/abc267_f
        // if dist(var_1,var_2) < d ... return -1
        // return x
        //    s.t dist(var_1, x) = d
        //        dist(var_2, x) = dist(var_1, var_2) - d
        int step(int var_1,int var_2,int d){
            int c=lca(var_1,var_2);
            int len=deep[var_1]+deep[var_2]-2*deep[c];
            if(len<d) return -1;
            if(deep[var_1]-deep[c]>=d) return back(var_1,d);
            return back(var_2,len-d);
        }
        int distance(int var_1,int var_2){
            int ascent=lca(var_1,var_2);
            return deep[var_1]+deep[var_2]-2*deep[ascent];
        }
    };
}
using po167::LCA;


std::vector<std::vector<int>> tree_in(int N){
    std::vector<std::vector<int>> G(N);
    for(int i=0;i<N-1;i++){
        int a;int b;
        cin>>a>>b;
        a--,b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    return G;
}
std::tuple<std::vector<int>,std::vector<int>,std::vector<int>> tree_order_pare_depth(std::vector<std::vector<int>> &G,int root){
    int n=G.size();
    std::vector<int> order={root},pare(n,-1),depth(n);
    pare[root]=-2;
    for(int i=0;i<n;i++){
        int a=order[i];
        for(auto x:G[a]){
            if(pare[x]==-1){
                pare[x]=a;
                depth[x]=depth[a]+1;
                order.push_back(x);
            }
        }
    }
    return {order,pare,depth};
}
std::vector<int> tree_diameter_path(std::vector<std::vector<int>> &G){
    int n=G.size();
    auto r=(std::get<0>(tree_order_pare_depth(G,0))).at(n-1);
    std::vector<int> order,pare,depth,ans;
    tie(order,pare,depth)=tree_order_pare_depth(G,r);
    int ind=order[n-1];
    while(ind!=-2){
        ans.push_back(ind);
        ind=pare[ind];
    }
    return ans;
}

#line 4 "/Users/Shared/po167_library/ds/Doubling.hpp"
namespace po167{

template<class T, T(*op)(T, T)>
struct Doubling_op{
    int n;
    int depth;
    std::vector<std::vector<int>> index;
    std::vector<std::vector<T>> val;
    Doubling_op(std::vector<int> p, std::vector<T> v, long long lim = (1ll << 60) - 1){
        n = p.size();
        for (auto x : p) assert(0 <= x && x < n);
        assert(n == (int)v.size());
        depth = 1;
        while ((1ll << depth) <= lim) depth++;
        index.resize(depth);
        val.resize(depth);
        index[0] = p;
        val[0] = v;
        for (int i = 1; i < depth; i++){
            index[i].resize(n);
            val[i].resize(n);
            for (int j = 0; j < n; j++){
                int tmp = index[i - 1][j];
                index[i][j] = index[i - 1][tmp];
                val[i][j] = op(val[i - 1][j], val[i - 1][tmp]);
            }
        }
    }
    std::pair<int, T> query(int start_ind, T start_val, long long times){
        assert(0 <= start_ind && start_ind < n);
        assert(0 <= times && times < (1ll << depth));
        int i = 0;
        while (times){
            if (times & 1){
                start_val = op(start_val, val[i][start_ind]);
                start_ind = index[i][start_ind];
            }
            i++;
            times >>= 1;
        }
        return std::make_pair(start_ind, start_val);
    }
};

struct Doubling{
    int n;
    int depth;
    std::vector<std::vector<int>> index;
    Doubling(std::vector<int> p, long long lim = (1ll << 60) - 1){
        n = p.size();
        for (auto x : p) assert(0 <= x && x < n);
        depth = 1;
        while ((1ll << depth) <= lim) depth++;
        index.resize(depth);
        index[0] = p;
        for (int i = 1; i < depth; i++){
            index[i].resize(n);
            for (int j = 0; j < n; j++){
                index[i][j] = index[i - 1][index[i - 1][j]];
            }
        }
    }
    int query(int ind, long long times){
        assert(0 <= ind && ind < n);
        assert(0 <= times && times < (1ll << depth));
        int i = 0;
        while (times){
            if (times & 1) ind = index[i][ind];
            i++;
            times >>= 1;
        }
        return ind;
    }
};
}
#line 168 "a.cpp"
int f(int a, int b){
    return max(a, b);
}
int e(){
    return 0;
}

void solve();
// CYAN / FREDERIC
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    // cin >> t;
    rep(i, 0, t) solve();
}

void solve(){
    int N;
    cin >> N;
    auto G = tree_in(N);
    auto L = LCA(0, G);
    auto [order, pare, depth] = tree_order_pare_depth(G, 0);
    vector lower_dp(N, vector<int>(3));
    rep(i, 0, N){
        rep(j, 0, G[i].size()) if (G[i][j] == pare[i]){
            swap(G[i][j], G[i].back());
            G[i].pop_back();
                break;
        }
    }
    for (int i = N - 1; i >= 0; i--){
        int a = order[i];
        for (auto x : G[a]){
            if (chmax(lower_dp[a][2], lower_dp[x][0] + 1)){
                for (int j = 1; j >= 0; j--){
                    if (lower_dp[a][j] < lower_dp[a][j + 1]){
                        swap(lower_dp[a][j], lower_dp[a][j + 1]);
                    }
                }
            }
        }
    }
    vector<int> upper_dp(N);
    rep(i, 0, N){
        int a = order[i];
        int X = upper_dp[a], Y = 0;
        for (auto x : G[a]){
            if (chmax(Y, lower_dp[x][0] + 1)){
                if (X < Y) swap(X, Y);
            }
        }
        for (auto x : G[a]){
            if (X != lower_dp[x][0] + 1){
                upper_dp[x] = X + 1;
            }
            else{
                upper_dp[x] = Y + 1;
            }
        }
    }
    vector<int> base(N);
    pare[0] = 0;
    rep(i, 0, N){
        if (i == 0) continue;
        if (lower_dp[pare[i]][0] != lower_dp[i][0] + 1){
            base[i] = lower_dp[pare[i]][0];
        }
        else{
            base[i] = lower_dp[pare[i]][1];
        }
    }/*
    rep(i, 0, N) vec_out(lower_dp[i]);
    vec_out(upper_dp);
    vec_out(order);
    vec_out(base);*/

    po167::Doubling_op<int, f> D(pare, base, N);
    int Q;
    cin >> Q;
    while (Q--){
        int a, b;
        cin >> a >> b;
        a--, b--;
        int c = L.lca(a, b);
        int ans = upper_dp[c];
        if (b == c) swap(a, b);
        if (a == c){
            chmax(ans, lower_dp[b][0]);
            chmax(ans, D.query(b, 0, L.distance(a, b)).second);
        }
        else{
            chmax(ans, lower_dp[b][0]);
            chmax(ans, lower_dp[a][0]);
            // cout << ans << " ";
            auto tmp_a = D.query(a, 0, L.distance(c, a) - 1);
            auto tmp_b = D.query(b, 0, L.distance(c, b) - 1);
            chmax(ans, tmp_b.second);
            chmax(ans, tmp_a.second);
            // cout << ans << " ";
            vector<int> p = {-1, lower_dp[tmp_a.first][0] + 1, lower_dp[tmp_b.first][0] + 1};
            Sore(p);
            rep(j, 0, 3){
                if (p[j] != lower_dp[c][j]) chmax(ans, lower_dp[c][j]);
            }
        }
        cout << ans * 2 + L.distance(a, b) << "\n";
    }
}

09 - Segment Tree Break

問題

区間のセット $S$ があります。$S$ には初め、長さ $2^{N}$ のセグメントツリーの区間が全て入っています。つまり、$0\leq k \leq N$ に対する、 $[0, 2^{k}), [2^{k}, 2 \times 2^{k}), [2\times 2^{k}, 3 \times 2^{k}), \cdots [N - 2^{k}, N)$ が全て入っています。

$Q$ 個のクエリを処理してください。

  • $S$ から $[L, R)$ を削除する。その後、以下の問題について答える。

    • 任意の $0\leq l < r \leq 2^{N}$ に対して、$S$ からどの $2$ つも被らないような区間を選んで、その和が $[l, r)$ と同じようにすることができますか。できるのであれば、全ての $0\leq l < r \leq 2^{N}$ に対する、「選ぶ区間の数の最小値」の最大値を求めてください。

  • $1\leq N \leq 16$

解説

長さ $1$ の区間が $S$ から削除されたら、その後はもうできないので簡単です。

セグメントツリーのように更新します。 $S$ に最初から入っている $[L, R)$ 全てにおいて、以下の値を持っておきます。

  • $L<l<r=R$ を満たす区間 $[l, r)$ を作るのに必要な区間の最大値
  • $L=l<r<R$ を満たす区間 $[l, r)$ を作るのに必要な区間の最大値
  • $L\leq l<r\leq R$ を満たす区間 $[l, r)$ を作るのに必要な区間の最大値
  • $L=l<r=R$ を満たす区間 $[l, r)$ を作るのに必要な区間の最大値

この構造体をマージすることは簡単です。具体的には実装例を見てください。$[L, R)$ の最大の更新のみ、 $S$ に $[L, R)$ が含まれているか否かによって結果が変わります。

セグメントツリーと同じように更新すれば、各クエリを $O(\log(N))$ で処理することができます。

#include <bits/stdc++.h>
using namespace std;
const int INF=2100000000;
#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return 1;}else return 0;}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    struct F{
        int left = 0;
        int right = 0;
        int all = 1;
        int val = 1;
    };
    bool ok = true;
    auto merge = [&](F l, F r, int ex) -> F {
        F res;
        res.val = max(l.val, r.val);
        chmax(res.val, l.right + r.left);
        chmax(res.val, l.all + r.left);
        chmax(res.val, l.right + r.all);
        res.left = l.left;
        res.right = r.right;
        chmax(res.left, l.all + r.left);
        chmax(res.right, l.right + r.all);
        if (ex){
            res.all = 1;
        }
        else{
            res.all = l.all + r.all;
        }
        chmax(res.val, res.all);
        return res;
    };
    int N, Q;
    cin >> N >> Q;
    vector<F> dp(2 << N);
    vector<int> E(2 << N, 1);
    for (int i = (1 << N) - 1; i >= 1; i--){
        dp[i] = merge(dp[i * 2], dp[i * 2 + 1], 1);
    }
    while (Q--){
        int l, r;
        cin >> l >> r;
        int d = 0;
        while (r - l != (1 << (N - d))) d++;
        int ind = (l >> (N - d)) + (1 << d);
        if (d == N){
            ok = 0;
        }
        if (ok){
            E[ind] = 0;
            while (ind != 0){
                dp[ind] = merge(dp[ind * 2], dp[ind * 2 + 1], E[ind]);
                ind /= 2;
            }
            cout << dp[1].val << "\n";
        }
        else{
            cout << "-1\n";
        }
    }
}

10 - Slither Path

問題

$-1\leq A_{i}\leq 3$ を満たす長さ $N$ の数列 $A$ が与えられます。 任意の $i$ に対して、 $0\leq X_{i}\leq 3$ を満たす長さ $N$ の数列であって、以下の条件を全て満たすものの個数を $998244353$ で割ったあまりを求めてください。

  • $A_{i} \neq -1$ ならば、$X_{i} = A_{i}$

  • 同じ頂点を $2$ 度通らないように $1$ 行 $N$ 列のマス目の頂点を辺に沿って移動していく方法であって、$1\leq i \leq N$ を満たす整数 $i$ について次を満たすものが存在する

    • $X_{i} \neq 0$ ならば、左から $i$ 番目のマスの辺を通った回数が $X_{i}$ 回である。$X_{i} = 0$ のときは、マスの辺を通った回数の制約は存在しない。

解説

例えば、以下のようなケースが考えられます。

考察として、以下のような長い区間往復するケースは、別のケースに置き換えられれます。

よって、右から左に戻る辺は高々端に $1$ 箇所ずつしか存在しません。このことを踏まえて dp をします。

まずある $X$ について、それが達成可能かという問題を解くことにします。左からそのマスの情報を持って dp します。情報は以下の $6$ つのうちいずれかです。

  • まだ辺が張られていない
  • もう辺を張らない
  • 間に辺がなく、右側に $1$ 本辺を伸ばせる状態
  • 間に辺があり、右側に $0$ 本辺を伸ばせる状態
  • 間に辺があり、右側に $1$ 本辺を伸ばせる状態
  • 間に辺があり、右側に $2$ 本辺を伸ばせる状態

ある状態からある状態まで、そのマスの $X$ がいくらなら行けるかどうかを事前に求めておきます。自分は全て手打ちしましたが、もっと効率の良い方法があるかもしれません。

$dp[i][j]$ を $i$ 番目のマスまで見て、$j$ 番目の状態に到達可能かを持ちます。これで dp すれば、$X$ の存在可能の判定問題を解くことができます。$D = 6$ とすると、状態数が $DN$ で、遷移数が $D^{2}N$ です。

$dp[i]$ というのは $2^{D}$ 状態しかないので、これを持って dp することも可能です。このように持つ状態を変えると、元の問題を解くことができます。

具体的には $DP[i][j]$ を $i$ 番目まで見て、 $dp[i]$ の状態が $j$ であるような $X$ の数とします。$DP[i][j]$ から $DP[i + 1]$ の遷移先は、$A_{i}\neq -1$ なら $1$ 通り、$A_{i} = -1$ でも $4$ 通りしかありません。よって、状態数が $2^{D}N$ で、遷移数が $42^{D}N$ の dp で答えを求めることができます。

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++)

#include <atcoder/modint>
using mint = atcoder::modint998244353;

mint solve(int N, vector<int> A){
    // 0 : まだない
    // 1 : もうない
    // 2 : マスの間に辺がない
    // 3 : マスの間に辺があり、横向きで手前に辺が 0 本ある
    // 4 : マスの間に辺があり、後向きで手前に辺が 1 本ある
    // 5 : マスの間に辺があり、横向きで手前に辺が 2 本ある

    vector p(4, vector<int>(6));
    const int L = 64;
    auto f = [&](int a, int b, int c) -> void {
        p[c][a] = (p[c][a] | (1 << b));
    };
    f(0, 0, 0);
    f(0, 1, 0);
    f(0, 2, 1);
    f(0, 3, 1);
    f(0, 4, 2);
    f(0, 5, 3);

    f(1, 1, 0);

    f(2, 1, 1);
    f(2, 2, 1);
    f(2, 4, 2);
    f(2, 5, 3);

    f(3, 1, 1);
    f(3, 2, 2), f(3, 2, 3);
    f(3, 4, 3);

    f(4, 1, 2), f(4, 1, 1);
    f(4, 2, 2);
    f(4, 4, 3);

    f(5, 1, 1);

    vector<array<int, L>> q(4);
    rep(i, 0, 4){
        rep(j, 0, L){
            q[i][j] = 0;
            rep(k, 0, 6) if (j & (1 << k)){
                q[i][j] = (q[i][j] | p[i][k]);
            }
        }
    }
    rep(i, 1, 4) rep(j, 0, L){
        q[0][j] = (q[0][j] | q[i][j]);
    }
    vector<mint> dp(L);
    dp[L - 1] = 1;
    rep(i, 0, N){
        vector<mint> n_dp(L);
        rep(k, 0, 4){
            if (k != A[i] && A[i] != -1) continue;
            rep(a, 0, L){
                n_dp[q[k][a]] += dp[a];
            }
        }
        swap(n_dp, dp);
    }
    mint ans = 0;
    rep(i, 1, L) ans += dp[i];
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin >> N;
    vector<int> A(N);
    rep(i, 0, N) cin >> A[i];
    cout << solve(N, A).val() << "\n";
}

11 - cycle partition

問題

$2$ 次元座標上の $N$ 個の格子点 $(x_{i}, y_{i})$ が与えられます。ただし、 $(x_{1}, y_{1}) = (0, 0)$ です。また、原点を含む $4$ 点を通る円が存在しないことが保証されます。

$K$ を $2K \leq N$ を満たす最大の整数とします。以下の条件を全て満たす円 $C$ の面積の最小値 $S$ を求め、その整数部分を出力してください。ただし、$S$ は一番近い整数と $0.01$ 以上離れています。

  • 原点は $C$ の周上に存在する。
  • $C$ の内部、周上に含まれる点の数はちょうど $K$ 個である。

$4\leq N\leq 1500$

$-10^{5} \leq x_{i}, y_{i} \leq 10^{5}$

解説

考察をすると、考えるべき円は以下のいずれかのみであることがわかります。

  • 原点と $(x_{i}, y_{i})$ を結ぶ線分を直径とする円
  • 原点とその他 $2$ 点を通る円
  • 原点とその他 $2$ 点を通る円を少し小さくして、周上に原点とその他 $1$ 点が存在するようにした円

これら全てについて調べると、円の種類数が $O(N^{2})$ で、 $1$ つの円について、その円の内部にある点の数を調べるのに $O(N)$ かかるため $O(N^{3})$ になって間に合わない(もしかしたら間に合うかも...)ので、計算量を落とします。

原点と $(x_{i}, y_{i})$ を結ぶ線分を直径とする円に関しては、愚直に調べても $O(N^{2})$ なので、問題ないです。

原点とその他 $2$ 点を通る円のうち、$1$ つ頂点を固定し、 $a$ とします。原点と $a$ を繋ぐ直線上にいない頂点を、$b_{1}, b_{2}, \dots b_{k}$ とし、以下の順番で並べます。

  • 原点、$a$、$b_{i}$ を通る円の中心を $(c, d)$ としたとき、$cy_{a} - dx_{a}$ の小さい順

そして、この順番に円の内部に含まれている頂点の数を数えると、増減は $1$ で、かつ簡単に求めることができます。計算量は $O(N^{2} \log(N))$ です。

ところで、この問題の答えの最大値ってなんでしょうね。よくわからず、半径の $2$ 乗のところまでは __int128_t を用いた有理数で求め、出力は long double で行いました。

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
const int INF=2100000000;
#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
#define all(p) p.begin(),p.end()
template<class T> bool chmin(T &a,T b){if(a>b){a=b;return 1;}else return 0;}
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return 1;}else return 0;}

// a / b
struct frac{
    __int128_t a, b;
};

struct point_int{
    ll x;
    ll y;
};

struct point_frac{
    frac x;
    frac y;
};

// a < b ?
bool frac_min(frac a, frac b) {
    if ((a.a < 0) ^ (b.a < 0)){
        return a.a < 0;
    }
    if (a.a < 0 && b.a < 0){
        a.a *= -1;
        b.a *= -1;
        return frac_min(b, a);
    }
    if (a.b == 0 || b.b == 0) return a.b != 0;
    auto l = a.a / a.b, r = b.a / b.b;
    if (l != r) return l < r;
    a.a -= a.b * l;
    b.a -= b.b * r;
    swap(a.a, a.b);
    swap(b.a, b.b);
    return frac_min(b, a);
}

/*
 *
 * (a, b) と原点の二等分線
 * ax + by - (a * a + b * b) / 2 = 0
 * cx + dy - (c * c + d * d) / 2 = 0
 * bcy - c * (a * a + b * b) / 2 =
 * ady - a * (c * c + d * d) / 2
 * y = (c * (a * a + b * b) - a * (c * c + d * d)) / 2(bc - ad)
 */
bool online(point_int p1, point_int p2){
    return p1.x * p2.y == p1.y * p2.x;
}
frac cross_point_y(point_int p1, point_int p2){
    frac res;
    __int128_t a, b, c, d;
    a = p1.x;
    b = p1.y;
    c = p2.x;
    d = p2.y;
    res.a = c * (a * a + b * b) - a * (c * c + d * d);
    res.b = 2 * (b * c - a * d);
    if (res.b < 0) res.a *= -1, res.b *= -1;
    return res;
}
point_frac circle_center(point_int p1, point_int p2){
    assert(!online(p1, p2));
    point_frac res;
    res.y = cross_point_y(p1, p2);
    swap(p1.x, p1.y);
    swap(p2.x, p2.y);
    res.x = cross_point_y(p1, p2);
    return res;
}

frac dist(point_frac a){
    return {a.x.a * a.x.a + a.y.a * a.y.a, a.x.b * a.x.b};
}

bool inside(point_frac c, point_int a){
    __int128_t R = 0, D = 0, tmpx = 0, tmpy = 0;
    R = c.x.a * c.x.a + c.y.a * c.y.a;
    tmpx = ((__int128_t)a.x) * c.x.b - c.x.a;
    tmpy = ((__int128_t)a.y) * c.y.b - c.y.a;
    D = tmpx * tmpx + tmpy * tmpy;
    return D <= R;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<point_int> p(N);
    rep(i, 0, N){
        cin >> p[i].x >> p[i].y;
    }
    frac ans;
    ans.a = 1, ans.b = 0;
    int K = N / 2;
    // 直径パターン
    rep(i, 1, N){
        point_frac C;
        C.x.a = p[i].x;
        C.x.b = 2;
        C.y.a = p[i].y;
        C.y.b = 2;
        int cou = 0;
        rep(j, 0, N){
            if (inside(C, p[j])) cou++;
        }
        auto D = dist(C);
        if (cou == K && frac_min(D, ans)) ans = D;
    }
    // 1 点固定
    rep(i, 1, N){
        int base = 1;
        vector<int> order;
        vector<int> Y(N);
        vector<point_frac> Cs(N);
        vector<frac> dist_line(N);
        // line : p[i].y * x - p[i].x * y = 0
        rep(j, 1, N){
            if (online(p[i], p[j])){
                if (abs(p[j].x) + abs(p[i].x - p[j].x) == abs(p[i].x)
                    &&  abs(p[j].y) + abs(p[i].y - p[j].y) == abs(p[i].y)){
                    base++;
                }
            }
            else{
                order.push_back(j);
                if (p[i].y * p[j].x - p[i].x * p[j].y < 0){
                    Y[j] = 1;
                    base++;
                }
                Cs[j] = circle_center(p[i], p[j]);
                dist_line[j].b = Cs[j].x.b;
                dist_line[j].a = Cs[j].x.a * (__int128_t)p[i].y;
                dist_line[j].a -= Cs[j].y.a * (__int128_t)p[i].x;
            }
        }
        if (order.empty()) continue;
        sort(all(order), [&](int l, int r){
            return frac_min(dist_line[l], dist_line[r]);
        });
        for (auto x : order){
            if (base == K){
                auto D = dist(Cs[x]);
                if (frac_min(D, ans)) ans = D;
            }
            if (Y[x] == 1) base--;
            else base++;
            if (base == K){
                auto D = dist(Cs[x]);
                if (frac_min(D, ans)) ans = D;
            }
        }
    }
    // 答えの出力
    ld S = ans.a / ans.b;
    S += (ld)(ans.a % ans.b) / (ld)(ans.b);
    S *= acosl(-1);
    ll out = floorl(S);
    cout << out << "\n";
}

12 - almost alternating permutation

問題

$(1, 2, \dots N)$ の順列 $A$ のうち、以下の条件をいずれも満たすような $A$ の総数を $998244353$ で割ったあまりを求めてください。

  • $A_{i} < A_{i + 1} < A_{i + 2} < A_{i + 3}$ を満たす $1\leq i \leq N - 3$ が存在しない
  • $A_{i} > A_{i + 1} > A_{i + 2}$ を満たす $1\leq i \leq N - 2$ が存在しない

$N \leq 30000$

解説

www.mathenachia.blog

EDPC T - Permutation は > < 列が与えられるので、それを満たす順列の数の数え上げでした。

それを $O(N\log^{2}(N))$ で解くことができて、それを紹介したのが上の記事です。

これは < を包除原理で消しています。その包除原理と同じ考えで > を包除原理で消すことで、この問題を解くことができます。

まず、いい文字列を以下のように定義します。

  • 長さ $N - 1$ の > < 列であって、> が $2$ 連続しないかつ、< が $3$ 連続しない

次に、以下の問題 X を考えます。

長さ $N - 1$ の < ? 列が与えられます。いい文字列であって、> を < ? のいずれかに置き換えることによって与えられた文字列になるもののコストの総和を求めてください。ただし、コストは > を < に置き換えた個数を $x$ としたとき、 $(-1)^{x}$ であるとします。

本題の答えは、以下のようにして表されます。

全ての長さ $N - 1$ の < ? 列に対して、以下の値の総和を求めてください。

  • 問題 X の答えと、「全ての連続する < の区間に対する、[区間の長さ + 1] の階乗の逆数の総積」と、$N$ の階乗の積

本題の答えが $[T^{N}]N!f(T)$ となるような多項式 $f(x)$ を定義します。

また、多項式 $a(T), b(T), c(T)$ を以下を満たすように定義します。

  • 長さ $M - 1$ の < のみからなる文字列を与えたときの問題 X の答えが $[T^{M}]M!a(T)$
  • 長さ $M$ の <<<...<<? の形をした文字列を与えたときの問題 X の答えが $[T^{M}]M!b(T)$
  • 長さ $M+1$ の ?<<...<<? の形をした文字列を与えたときの問題 X の答えが $[T^{M}]M!c(T)$

このとき、以下の式が成り立ちます。

$$f(T) = a(T) + \frac{b(T)^{2}}{1 - c(T)}$$

よって、 $a(T), b(T), c(T)$ が求められれば良いです。これらは簡単な $O(N)$ の DP で求めることができます。

以上で問題が解けました。これは $O(N \log(N))$ で求めることができます。

以下のコードは自分のライブラリを一部使っています。

GitHub - potato167/po167_library

po167::FPS_inv が逆数を求めるライブラリで、po167::Binomial が二項係数に関わる様々な値を求めるライブラリです。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#include <atcoder/convolution>
using mint = atcoder::modint998244353;
#include "po167_library/math/Binomial.hpp"
#include "po167_library/fps/FPS_inv.hpp"

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    po167::Binomial<mint> table;
    vector dp(N + 1, vector<mint>(3));
    vector<mint> sum(N + 1);
    dp[0][0] = 1;
    sum[0] = 1;
    rep(i, 0, N){
        dp[i + 1][1] += dp[i][0];
        dp[i + 1][2] += dp[i][1];
        dp[i + 1][0] -= dp[i][1] + dp[i][2];
        rep(k, 0, 3) sum[i + 1] += dp[i + 1][k];
    }
    vector<mint> a(N + 1), b(N + 1), c(N + 1);
    rep(i, 0, N){
        a[i + 1] = sum[i] - (i ? sum[i - 1] : 0);
    }
    rep(i, 0, N){
        b[i + 1] = sum[i];
    }
    rep(i, 0, N){
        c[i + 1] = dp[i + 1][0];
    }
    rep(i, 1, N + 1){
        a[i] *= table.invfact(i);
        b[i] *= table.invfact(i);
        c[i] *= table.invfact(i);
    }
    c[0] = 1;
    auto f = atcoder::convolution(po167::FPS_inv(c), atcoder::convolution(b, b));
    mint ans = f[N] + a[N];
    ans *= table.fact(N);
    cout << ans.val() << "\n";
}

終わり

$3$ 位でした。

8、10、11 問目に関しては、サンプルのみで突破するのは不可能だと考えたため、愚直を描いて、ランダムテストをしました。 10、11 問目は考察も出遅れたため、完全にタイムボーナスを無視してやりました。



以上の内容はhttps://potato167.hatenablog.com/entry/2024/10/02/203000より取得しました。
このページはhttp://font.textar.tv/のウェブフォントを使用してます
不具合報告/要望等はこちらへお願いします。
モバイルやる夫Viewer Ver0.14