接着剤の精進日記

競プロでの精進や研究に関係したことを書いていきます。

キャディプログラミングコンテスト2021(AtCoder Beginner Contest 193)

atcoder.jp

A - Discount

$ 100 \times (1 - \frac{B}{A}) $ を出力する
提出コード

void solve(){
    double A, B;
    cin >> A >> B;
    printf("%.12lf\n", (1 - B / A) * 100);
}

B - Play Snuke

$ A_i \geq X_i $ のときは売り切れて買えない
それ以外の場合で、最小となる $ P_i $ を探す
提出コード

void solve(){
    int N;
    cin >> N;
    vector<ll> A(N), P(N), X(N);
    REP(i,N) cin >> A[i] >> P[i] >> X[i];
    ll ans = LINF;
    REP(i,N){
        if(A[i] >= X[i]) continue;
        chmin(ans, P[i]);
    }
    if(ans == LINF) ans = -1;
    cout << ans << endl;
}

C - Kaprekar Number

全探索をする
$ i \leq \sqrt{N} $ を満たす $ i $ について $ i^j \leq N ( j \geq 2 ) $ を満たすものをsetなどで管理すればいい
提出コード

void solve(){
    ll N;
    cin >> N;
    ll ans = N;
    set<ll> st;
    for(ll i=2;i*i<=N;i++){
        ll cur = i * i;
        while(cur <= N){
            st.insert(cur);
            cur *= i;
        }
    }
    cout << N - (ll)st.size() << endl;
}

D - Poker

二人の手札の場合の数は $ all = (9K - 8) (9K-9) $ となるので高橋くんが勝つときの場合の数を $ sum $ とすると $ \frac{sum}{all} $ が答え
$ sum $ については、高橋くんと青木くんの残りのカードについて全探索をして求めればいい
提出コード

void solve(){
    ll K;
    string S, T;
    cin >> K >> S >> T;
    vector<int> cntS(10), cntT(10);
    REP(i,4){
        cntS[S[i]-'0']++;
        cntT[T[i]-'0']++;
    }
    double sum = 0.0;
    double all = (9 * K - 8) * (9 * K - 9);
    for(int i=1;i<=9;i++){
        for(int j=1;j<=9;j++){
            if(i == j){
                if(cntS[i] + cntT[j] + 2 > K) continue;
            }
            else{
                if(cntS[i] + cntT[i] + 1 > K) continue;
                if(cntS[j] + cntT[j] + 1 > K) continue;
            }
            ll sumS = 0, sumT = 0;
            cntS[i]++;
            cntT[j]++;
            for(ll k=1;k<=9;k++){
                sumS += k * pow(10, cntS[k]);
                sumT += k * pow(10, cntT[k]);
            }
            cntS[i]--;
            cntT[j]--;
            if(sumS > sumT){
                if(i == j){
                    sum += (K - cntS[i] - cntT[i]) * (K - cntS[i] - cntT[i] - 1);
                }
                else sum += (K - cntS[i] - cntT[i]) * (K - cntS[j] - cntT[j]);
            }
        }
    }
    printf("%.12lf\n", sum / all);
}

E - Oversleeping

条件より $ (P + Q)a + P + q = (2X + 2Y)b + X + y (0 \leq q \lt Q, 0 \leq y \lt Y) $ を満たす $ a, b $ を見つけたい
左辺は $ P + Q $ の周期、右辺は $ 2X + 2Y $ の周期になっているので
\begin{align} t& \mod (P + Q) = P+q \\ t& \mod (2X + 2Y) = X+y \end{align}

を満たす最小の非負整数 $ t $ を求めることができればいい
これはACLのcrtを使えば求めることができる
提出コード

void solve(){
    ll X, Y, P, Q;
    cin >> X >> Y >> P >> Q;
    ll ans = 9 * LINF;
    for(int q = 0; q < Q; q++){
        for(int y = 0; y < Y; y++){
           auto [a, b] = crt({P+q, X+y}, {P+Q, 2*X+2*Y});
           if(a == 0 and b== 0) continue;
           chmin(ans, a);
        }
    }
    if(ans == 9 * LINF) cout << "infinity" << endl;
    else cout << ans << endl;
}

SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192)

atcoder.jp

A - Star

今の値から次の100の倍数までの差を求めたいので $ 100 - x \% 100 $ を出力
提出コード

void solve(){
    int X;
    cin >> X;
    X %= 100;
    cout << 100 - X << endl;
}

B - uNrEaDaBlE sTrInG

問題文の条件を満たしているかどうかを判定すればいい
提出コード

void solve(){
    string s;
    cin >> s;
    bool ok = true;
    REP(i,s.size()){
        if(i % 2 == 0){
            if('a' <= s[i] and s[i] <= 'z'){}
            else ok = false;
        }
        else{
            if('A' <= s[i] and s[i] <= 'Z'){}
            else ok = false;
        }
    }
    cout << (ok ? "Yes" : "No") << endl;
}

C - Kaprekar Number

毎回愚直に求めても十分間に合うのでシミュレートすればいい
提出コード

void solve(){
    string N;
    int K;
    cin >> N >> K;
    vector<int> ans;
    set<string> st;
    auto num = [&](string s) -> int{
        int res = 0;
        REP(i,s.size()){
            res = res * 10 + (s[i] - '0');
        }
        return res;
    };
    string pre = N;
    while(K--){
        string cur = pre;
        sort(cur.rbegin(), cur.rend());
        ll g1 = num(cur);
        sort(cur.begin(), cur.end());
        ll g2 = num(cur);
        ll nxt = g1 - g2;
        string ns = "";
        if(nxt == 0) ns = '0';
        while(nxt > 0){
            ns += char('0' + nxt % 10);
            nxt /= 10;
        }
        reverse(ns.begin(), ns.end());
        pre = ns;
    }
    cout << pre << endl;
}

D - Base n

難しい
$ X $ を $ n $ 進法表記で表した数には単調性があるのでオーバーフローに気をつけながら二分探索をすればいい
ただし $ | X | = 1 $ のときは答えが 01 になるので場合分けが必要
提出コード

void solve(){
    string X;
    ll M;
    cin >> X >> M;
    int d = 0;
    reverse(X.begin(), X.end());
    for(auto x : X) chmax(d, x - '0');
    if(X.size() == 1){
        if(d > M) cout << 0 << endl;
        else cout << 1 << endl;
        return;
    }
    ll l = d, r = M+1;
    auto check = [&](ll x) -> bool{
        ll cur = 0;
        ll base = 1;
        REP(i,X.size()){
            if((X[i] - '0') > LINF / base){
                return false;
            }
            ll tmp = base * (X[i] - '0');
            if(cur > LINF - tmp){
                return false;
            }
            cur += tmp;
            if(base > LINF / x){
                if(i + 1 < X.size()) return false;
            }
            base *= x;
        }
        if(cur > M) return false;
        else return true;
    };

    while(r - l > 1){
        ll m = (r + l) >> 1;
        if(check(m)) l = m;
        else r = m;
    }

    cout << l - d << endl;
}

E - Train

鉄道 $ i $ を使って 時刻 $ d $ に $ A_i $ から $ B_i $ に移動するとき、最短で $ \lceil \frac{d}{K_i} \rceil \times K_i + T_i $ で着くことができる
上記をコストとしたダイクストラで解くことができる
提出コード

void solve(){
    int N, M, X, Y;
    cin >> N >> M >> X >> Y;
    --X, --Y;
    vector<vector<tuple<int, ll, ll>>> g(N);
    REP(i,M){
        int A, B, T, K;
        cin >> A >> B >> T >> K;
        g[--A].emplace_back(--B, T, K);
        g[B].emplace_back(A, T, K);
    }
    vector<ll> dist(N, LINF);
    dist[X] = 0;
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
    pq.emplace(0, X);
    while(!pq.empty()){
        auto [d, cur] = pq.top(); pq.pop();
        if(d > dist[cur]) continue;
        for(auto [nxt, t, k] : g[cur]){
            ll nxt_d = (d + k - 1) / k * k + t;
            if(chmin(dist[nxt], nxt_d)){
                pq.emplace(dist[nxt], nxt);
            }
        }
    }
    ll ans = dist[Y];
    if(dist[Y] == LINF) ans = -1;
    cout << ans << endl;
}

F - Potion

選ぶ個数 $ k $ を固定して考えると
$ dp[i][j][l] := i $ 番目まで見たときに $ j $ 個選んで総和が $ l \pmod{k} $ のときの最大値としてDPをする
$ dp[N][k][X\%k] \neq -1 $ のとき $ \frac{X - dp[N][k][X\%k]}{k} $ となるのですべての $ k $ について上記のDPを行えば $ \mathcal{O}(N^4) $ で解ける
提出コード

void solve(){
    int N;
    ll X;
    cin >> N >> X;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    ll ans = LINF;
    for(int k=1;k<=N;k++){
        vector dp(N+1, vector(N+1, vector(N+1, -1LL)));
        dp[0][0][0] = 0;
        REP(i,N){
            REP(j,N){
                REP(l,N){
                    if(dp[i][j][l] == -1) continue;
                    chmax(dp[i+1][j][l], dp[i][j][l]);
                    chmax(dp[i+1][j+1][(l+A[i])%k], dp[i][j][l] + A[i]);
                }
            }
        }
        if(dp[N][k][X%k] != -1) chmin(ans, (X - dp[N][k][X%k]) / k);
    }
    cout << ans << endl;
}

Codeforces Round #702 (Div. 3)

codeforces.com

A. Dense Array

$ 2 \times \min(a_i, a_{i+1}) \gt \max(a_i, a_{i+1}) $のとき、小さいほうから大きい方へ2倍ずつしていけばいいので2倍する必要のある回数の総和を求める
提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    REP(i,n) cin >> a[i];
    int ans = 0;
    REP(i,n-1){
        if(max(a[i], a[i+1]) <= 2 * min(a[i], a[i+1])) continue;
        int cur = min(a[i], a[i+1]);
        while(2 * cur < max(a[i], a[i+1])){
            ans++;
            cur *= 2;
        }
    }
    cout << ans << endl;
}

B. Balanced Remainders

余ってるものから操作回数が少ない方に変えていく
提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> cnt(3);
    REP(i,n){
        cin >> a[i];
        a[i] %= 3;
        cnt[a[i]]++;
    }
    int ans = 0;
    REP(i,n){
        if(cnt[a[i]] <= n / 3) continue;
        if(a[i] == 0){
            if(cnt[1] < n / 3){
                cnt[1]++;
                cnt[0]--;
                ans++;
            }
            else if(cnt[2] < n / 3){
                cnt[2]++;
                cnt[0]--;
                ans += 2;
            }
        }
        else if(a[i] == 1){
            if(cnt[2] < n / 3){
                cnt[2]++;
                cnt[1]--;
                ans++;
            }
            else if(cnt[0] < n / 3){
                cnt[0]++;
                cnt[1]--;
                ans += 2;
            }
        }
        else{
            if(cnt[0] < n / 3){
                cnt[0]++;
                cnt[2]--;
                ans++;
            }
            else if(cnt[1] < n / 3){
                cnt[1]++;
                cnt[2]--;
                ans += 2;
            }
        }
    }
    cout << ans << endl;
}

C. Sum of Cubes

片方を固定するともう片方も一意に決まるのでそれが正の整数になる3乗根を持つかどうかわかればいい
これは二分探索で求めることができるので片方を全探索してもう片方は二分探索で求めればいい
事前に列挙しておけば二分探索いらなかった
提出コード

void solve(){
    ll x;
    cin >> x;
    for(ll a=1;a*a*a<=x;a++){
        ll b = x - a*a*a;
        if(b <= 0) continue;
        ll l = 1, r = 1e4;
        while(r - l > 1){
            ll m = (l + r) >> 1;
            if(m * m * m > b) r = m;
            else l = m;
        }
        if(l * l * l == b){
            cout << "YES" << endl;
            return;
        }
    }
    cout << "NO" << endl;
}

D. Permutation Transformation

再帰関数で操作を実際に行えばいい
提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    REP(i,n) cin >> a[i];
    vector<int> dep(n, -1);
    auto dfs = [&](auto && self, int l, int r, int d) -> void{
        // dumps(l, r);
        if(l == r){
            dep[l] = d;
            return;
        }
        int ma = 0;
        int idx = 0;
        for(int i=l;i<=r;i++) if(chmax(ma, a[i])) idx = i;
        dep[idx] = d;
        if(l <= idx-1) self(self, l, idx-1, d+1);
        if(idx+1 <= r) self(self, idx+1, r, d+1);
    };
    dfs(dfs, 0, n-1, 0);
    REP(i,n) cout << dep[i] << " ";
    cout << endl;
}

E. Accidental Victory

昇順にソートをして考える
$ [0, i) $ が $ i $ に勝てるかどうかは $ \sum_{j=0} ^{i-1} a_j \geq a_i $ を満たしていればいい
よって上記を満たす区間 $ [l, n] $ を求めればいい
提出コード

void solve(){
    int n;
    cin >> n;
    vector<ll> a(n);
    REP(i,n) cin >> a[i];
    vector<int> ans, idx(n);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int x, int y){
        return a[x] < a[y];
    });
    ll sum = 0;
    int l = 0;
    REP(i,n){
        // dumps(i, a[idx[i]], sum);
        if(sum < a[idx[i]]) l = i;
        sum += a[idx[i]];
    }
    for(int i=l;i<n;i++) ans.emplace_back(idx[i]);
    sort(ans.begin(), ans.end());
    cout << ans.size() << endl;
    for(auto x : ans) cout << x+1 << " ";
    cout << endl;
}

F. Equalize the Array

$ C $ を全探索する
各要素が何回出現するかをカウントし、各要素ごとに何個存在するかをカウントする
$ C $ を固定したときに必要になる操作回数は累積和を使うと $ \mathcal{O}(1) $ で求められる
提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    map<int, int> mp;
    REP(i,n){
        cin >> a[i];
        mp[a[i]]++;
    }
    vector<int> cnt(n+2);
    for(auto [k, v] : mp) cnt[v]++;
    vector<ll> cum(n+2);
    REP(i,n+1) cum[i+1] = cum[i] + cnt[i];
    int ans = n;
    ll pre = 0;
    REP(i,n+1){
        int tmp = pre;
        if(cnt[i] == 0) continue;
        if(i+1 <= n) tmp += (n - pre - i * cnt[i]) - i * (cum[n+1] - cum[i+1]);
        pre += i * cnt[i];
        chmin(ans, tmp);
    }
    cout << ans << endl;
}

G. Old Floppy Drive

頭壊れた
一周するたびにどれだけ値が増減するかと一周するときに左からの累積maxを求めておく
$ x $ を超えないように何周するかは割り算で求めることができるので、残り1周を実際にシミュレートをすればいい
愚直にシミュレートすると $ \mathcal{O}(nm) $ かかるので累積maxを使って二分探索で求めればいい
1周だと境界でバグらせそうな気がしたので2周させた
提出コード

void solve(){
    int n, m;
    cin >> n >> m;
    vector<ll> a(n), x(m);
    REP(i,n) cin >> a[i];
    REP(i,m) cin >> x[i];
    ll cycle = 0;
    ll ma = -LINF;
    REP(i,n){
        cycle += a[i];
        chmax(ma, cycle);
    }
    vector<ll> cum(n, -LINF);
    cum[0] = a[0];
    ll sum = a[0];
    for(int i=1;i<n;i++){
        sum += a[i];
        chmax(cum[i], max(cum[i-1], sum));
    }
    REP(i,m){
        if(x[i] <= a[0]) cout << "0 ";
        else if(ma <= 0 or (ma < x[i] and cycle <= 0)) cout << "-1 ";
        else{
            ll cnt = 0;
            if(cycle > 0) cnt += floor_div(x[i] - ma - 1, cycle);
            if(cnt < 0) cnt = 0;
            ll cur = cnt * cycle;
            ll ans = -1;
            if(cnt == 1) ans += n;
            else if(cnt > 1) ans += n + (cnt - 1) * n;
            bool ok = false;
            {
                auto itr = lower_bound(cum.begin(), cum.end(), x[i] - cur);
                if(itr == cum.end()){
                    ok = true;
                    cur += cycle;
                    ans += n;
                }
                else{
                    cur += *itr;
                    ans += itr - cum.begin() + 1;
                }
            }
            if(ok){
                auto itr = lower_bound(cum.begin(), cum.end(), x[i] - cur);
                ans += itr - cum.begin() + 1;
            }
            cout << ans << " ";
        }
    }
    cout << endl;
}

AtCoder Beginner Contest 191(ABC191)

atcoder.jp

A - Vanishing Pitch

$ VT \leq D \leq VS $を満たす場合No、そうでない場合Yes
提出コード

void solve(){
    int V, T, S, D;
    cin >> V >> T >> S >> D;
    if(V * T <= D and D <= V * S) cout << "No" << endl;
    else cout << "Yes" << endl;
}

B - Remove It

$ A_i = X $となる要素は出力しなければいい
提出コード

void solve(){
    int N;
    ll X;
    cin >> N >> X;
    vector<ll> A(N);
    REP(i,N) cin >> A[i];
    REP(i,N) if(A[i] != X) cout << A[i] << " ";
    cout << endl;
}

C - Digital Graffiti

問題がよくわからなくて本番中は飛ばした
$ (x, y) , (x+1, y), (x, y+1), (x+1, y+1) $の$ 2 \times 2 $長方形領域を考える
この時、この長方形領域に#が1個または3個含まれる時$ (x, y) $は頂点となる
よって上記を満たす個数を数えればいい
提出コード

void solve(){
    int H, W;
    cin >> H >> W;
    vector<string> fi(H);
    REP(i,H) cin >> fi[i];
    int ans = 0;
    REP(i,H-1) REP(j,W-1){
        int cnt = (fi[i][j] == '#') + (fi[i][j+1] == '#') + (fi[i+1][j] == '#') + (fi[i+1][j+1] == '#');
        if(cnt == 1 or cnt == 3) ans++;
    }
    cout << ans << endl;
}

D - Circle Lattice Points

整数$ x $を固定したときに、$ y $の取りうる範囲は三平方の定理から求めることができる
よってyの上限が$ u $、下限が$ b $とすると$ u - b + 1 $個格子点が存在する
浮動小数点数のままでやると誤差があるので整数に直すのが無難そう
本番はXとYを平行移動させてlong doubleで通してしまった
提出コード

void solve(){
    long double X, Y, R;
    cin >> X >> Y >> R;
    X += 2e5;
    Y += 2e5;
    ll st = ceil(X - R);
    ll en = floor(X + R);
    ll num = 0;
    for(int i=st;i<=en;i++){
        long double p = sqrt(pow(R, 2) - pow((X - (long double)i), 2));
        ll b = ceil(Y - p);
        ll u = floor(Y + p);
        num += u - b + 1;
    }
    cout << num << endl;
}

E - Come Back Quickly

ある頂点$ i $を始点とした最短経路とある頂点$ j ( \neq i ) $からiへの最短経路がわかればいい
$ j $ から$ i $への経路は、与えられたグラフの辺をすべて逆辺にして考えるとこのグラフ上での$ i $から$ j $への最短経路となる
そのため、与えられたグラフと逆辺のグラフに対しダイクストラで全始点について求めればいい
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    Dijkstra<ll> d1(N, LINF), d2(N, LINF);
    vector<ll> ans(N, LINF);
    REP(i,M){
        ll a, b, c;
        cin >> a >> b >> c;
        --a, --b;
        if(a == b) chmin(ans[a], c);
        else{
            d1.make_edge(a, b, c);
            d2.make_edge(b, a, c);
        }
    }
    REP(i,N){
        d1.solve(i);
        d2.solve(i);
        REP(j,N) if(j != i){
            chmin(ans[i], d1.cost[j] + d2.cost[j]);
        }
        if(ans[i] == LINF) ans[i] = -1;
        cout << ans[i] << endl;
    }
}

AtCoder Beginner Contest 190(ABC190)

atcoder.jp

A - Very Very Primitive Game

実際にシミュレートをし、先に操作を行えなくなった方の負け
提出コード

void solve(){
    int A, B, C;
    cin >> A >> B >> C;
    int x = C;
    while(A >= 0 and B >= 0){
        if(x) B--;
        else A--;
        x = 1 - x;
    }
    if(B == -1) cout << "Takahashi" << endl;
    else cout << "Aoki" << endl;
}

B - Magic 3

$ X_i \lt S $ and $ Y_i \gt D $を満たす$ i $が存在すればYesそうでなければNo
提出コード

void solve(){
    ll N, S, D;
    cin >> N >> S >> D;
    vector<int> X(N), Y(N);
    REP(i,N) cin >> X[i] >> Y[i];
    bool ok = false;
    REP(i,N){
        if(X[i] < S and Y[i] > D) ok = true;
    }
    cout << (ok ? "Yes" : "No") << endl;
}

C - Bowls and Dishes

bit全探索をする
$ i $番目のbitが0のとき$ C_i $の皿にボールを乗せ、1のとき$ D_i $の皿にボールを乗せることにして全探索すればいい
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<int> A(M), B(M);
    REP(i,M){
        cin >> A[i] >> B[i];
        --A[i], --B[i];
    }
    int K;
    cin >> K;
    vector<int> C(K), D(K);
    REP(i,K){
        cin >> C[i] >> D[i];
        --C[i], --D[i];
    }
    int ans = 0;
    REP(i,1<<K){
        vector<int> ball(N);
        REP(j,K){
            // dumps(C[i], D[i]);
            if(i >> j & 1) ball[C[j]] = 1;
            else ball[D[j]] = 1;
        }
        int tmp = 0;
        REP(j,M){
            if(ball[A[j]] and ball[B[j]]) tmp++;
        }
        chmax(ans, tmp);
    }
    cout << ans << endl;
}

D - Staircase Sequences

難しい
等差数列の和を考える
$ n $を項数、$ a $を初項とすると$ N = \frac{n}{2} \left( 2a + n - 1 \right) $が成り立つ
$ 2N = n \left( 2a + n - 1 \right) $とすると、$ n $と$ 2a + n - 1 $は$ 2N $の約数となる
また、$ n $は$ 2N $の約数なので
$ \frac{2N}{n} = 2a + n - 1 $が成り立ち、$ \frac{2N}{n} - n + 1 = 2a $となる
よって、$ 2N $の約数を全列挙し、$ \frac{2N}{n} - n + 1 $が偶数になるかどうかを調べればいい
提出コード

void solve(){
    ll N;
    cin >> N;
    int ans = 0;
    for(auto d : divisor(2*N)){
        ll x = 2 * N / d;
        if((x - d + 1) % 2 == 0) ans++;
    }
    cout << ans << endl;
}

E - Magical Ornament

任意のペア$ \left( i, j \right) \left( 1 \leq i, j \leq K \right) $についての$ \left( C_i, C_j \right) $間の最短経路がわかっていれば、bitDPで解くことができる
これは予め各$ C_i $を始点とした最短経路を求めておけばいい
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<ll> A(M), B(M);
    Dijkstra<ll> d(N, LINF);
    REP(i,M){
        cin >> A[i] >> B[i];
        --A[i], --B[i];
        d.make_edge(A[i], B[i], 1);
        d.make_edge(B[i], A[i], 1);
    }

    int K;
    cin >> K;
    vector<int> C(K);
    REP(i,K){
        cin >> C[i];
        --C[i];
    }

    vector dist(K, vector<ll>(K, LINF));
    REP(i,K){
        d.solve(C[i]);
        REP(j,K) if(i != j){
            chmin(dist[i][j], d.cost[C[j]]);
            chmin(dist[j][i], d.cost[C[j]]);
        }
    }

    vector dp(K, vector(1<<K, LINF));
    REP(i,K) dp[i][0] = 0;
    for(int bit=1;bit<(1<<K);bit++){
        REP(j,K) if(bit >> j & 1){
            REP(k,K){
                ll cost = dp[j][bit-(1<<j)] + dist[j][k];
                if(bit == ((1<<K) - 1)) chmin(dp[k][bit], dp[j][bit-(1<<j)]);
                chmin(dp[k][bit], cost);
            }
        }
    }

    ll ans = LINF;
    REP(i,K) chmin(ans, dp[i][(1<<K)-1]);

    if(ans == LINF) ans = -2;
    cout << ans + 1 << endl;
}

F - Shift and Inversions

$ k = 0 $の場合については、BITを使って転倒数を求めればいい
それ以外の場合を考える
今ある数列を$ [a_0, a_1, \dots, a_{N-1} ] $とすると操作後の数列は
$ [a_1, a_2, \dots, a_{N-1}, a_0] $となる
数列から$ a_0 $を取り除いたときの転倒数の変化を考えると$ [a_1, \dots, a_{N-1} ] $の中で$ a_0 $未満のものの個数分転倒数が減少する
また、数列の末尾に$ a_0 $を追加したときの転倒数の変化は、$ [a_1, \dots, a_{N-1} ] $の中で$ a_0 $より大きいものの個数分増加する
よって、一番はじめに転倒数を求めた後は上記のように各操作での転倒数の差分を計算すればいい
提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> a(2*n);
    REP(i,n){
        cin >> a[i];
        ++a[i];
        a[i+n] = a[i];
    }
    ll ans = 0;
    BIT<int> b(n);
    REP(i,n){
        ans += i - b.sum1(a[i]);
        b.add1(a[i], 1);
    }
    for(int i=n;i<2*n;i++){
        cout << ans << endl;
        ans -= a[i-n] - 1;
        ans += n - a[i-n];
    }
}