88分3完599位、パフォーマンスは1791でした。

A

問題

長さ$N$の数列$A$が与えられます。$A$の先頭$K$項の和をスコアと呼ぶことにします。与えられた$A$のスコアを$s$と置きます。

$A$の隣接する2要素を入れ替える操作を好きな回数行うことができます。スコアを$s + 1$以上にすることが達成可能か判定し、また可能であるなら必要な最小の操作回数を求めてください。

• $2 \leq N \leq 4 \times 10 ^ 5$
• $1 \leq K \leq N - 1$
• $1 \leq A_i \leq 10 ^ 9$

考察

$K+1$番目以降の要素のいずれかを先頭$K$個に持ってくることを考えます。$j > K$番目の要素を$i \leq K$番目まで持ってくるとき、$j - i$手かかります。

$j$番目の要素を$K+1$番目の位置に持ってくるのに$j - (K + 1)$手、$i$番目の要素を$K$番目の位置まで持ってくるのに$K - i$手、$K$番目と$K + 1$番目を交換するのに$1$手で合計$j - i$手となります。

$i = 1, 2, \cdots, K$について、どの要素を持ってくるのが最適かを考えると、$K+1$番目以降で$A_i$より大きいいちばん左側(インデックスが小さい)ものを持ってくるのが最適です。これは二分探索をすることで求めることができます。

提出コード

template<class T> 
T bisect_right(vector<T> &array, T key){
    return upper_bound(all(array),key) - array.begin();
}

ll N, K; cin >> N >> K ;
    vector<ll> A(N); for(int i = 0; i < N; i++) cin >> A[i];
    
    if(K == N){
        cout << -1 << endl; exit(0);
    }

    vll R;
    for(int i = K; i < N; i++){
        R.pb(A[i]);
    }

    rep(i, R.size() - 1) chmax(R[i+1], R[i]);

    ll ans = INF;

    for(int i = 0; i < K; i++){

        ll r = bisect_right(R, A[i]);
        r++; 

        if(r != R.size() + 1){
            chmin(ans, K + r - i - 1);
        }

    }

    if(ans == INF) ans = -1;
    cout << ans << '\n';

}

upper_boundなどをきちんと理解していないかつPythonで競プロを始めたということでbisect_rightを自作しています。本当にごめんなさい。イテレーターとかなにもわかりません…

B

問題

空の数列$x$を持っています。次の2種類の操作を好きな順番で$N$回行います。

• 操作A : $x$の要素をすべてflipする(0は1に、1は0になります)。 その後、$x$の先頭に0を追加する。

• 操作B : $x$の末尾に0を追加する

0と1からなる長さ$N$の数列$A$が与えられます。$x$を$A$に一致させることが可能か判定してください。

• $1 \leq N \leq 2 \times 10 ^ 5$
• $0 \leq A_i \leq 1$

考察

わからなかったので小さい$N$に対して作れる数列を列挙してエスパーしようとしたりしましたが、ダメでした。結局2WAしたのちぐちゃぐちゃなコードで一応ACはしました。

正しい考察

逆から操作を行うことを考えます。末尾が0の状態で操作Aを行うと末尾が1となってしまい、再度操作Aを行わなければ操作Bが行えなくなってしまいます。ゆえに末尾が0であるならば操作Bを行うべきです。末尾が1の状態の時は操作Aを行うしかないので行います。この時先頭が0でなければ不可能となります。

逆から操作を行うことは考えたのですが末尾が0の状態で操作Aを行うべきでないことに気づけず、時間を溶かしていました…

ACコード

int main(){

    ll N; cin >> N;
    deque<int> A;
    rep(i, N){
        int a; cin >> a;
        A.pb(a);
    }

    int flip = 0;
    bool ans = true;
    while(!A.empty()){
        if(A.back() == flip) {
            A.pop_back();
        }elif(A.front() == flip) {
            A.pop_front();
            flip ^= 1;
        }else{
            ans = false; 
            break;
        }
    }

    YesNo(ans);

}

C

問題

$N$枚のカードがあり、$1$から$N$までの番号がついています。カード$i$には整数$A_i$が書かれています。また、$N$は偶数です。

すぬけくんと最小太郎くんがゲームをします。$N$ターンからなり、すぬけくんから交互にターンをプレイします。各ターンでは、

• すぬけくんのターン : まだ誰にもとられていないカードのうち、好きなものを1枚とる

• 最小太郎くんのターン : まだ誰にもとられていないカードのうち、番号が最小のものを1枚とる

あなたは、このゲームで次の不正を1度だけすることができます。

• 整数$k(0 \leq k \leq N - 1)$を選び、カードに書かれている整数を左に$k$個ずらす。つまり、カード$1, 2, \cdots, N$に書かれている数を、$A_{k+1}, A_{k + 2}, \cdots, A_N, A_1, A_2, \cdots, A_{k}$に書き換える。

あなたがすぬけくんのスコアを最大化するように不正をしたとき、選ぶべき$k$の値と$k$を選んだ場合のスコアを求めてください。

• $2 \leq N \leq 2 \times 10 ^ 5$
• $1 \leq A_i \leq 10^9$

考察

すぬけくんがとることのできる最大スコアは$A$のうち整数の大きいもの上位$N / 2$個の総和です。実際これが可能です。

$A$のうち整数の大きいもの上位$N / 2$個をとればよいので、各カードについてとる/とらないが確定します。取らないカードでは1を、取るカードでは-1とする数列$R$を考えます(公式解説と逆です！注意！)。数列$R$について累積和をとります。正の値をとる箇所ではすぬけくんがとるべきカードが最小太郎くんに取られてしまっていることになります。ここで、数列$R$の累積和の最小となるインデックスが1となるように$k$を定めると、正の値をとらなくなります。よって解くことができます。

提出コード

int main(){

    ll N; cin >> N;
    vector<ll> A(N); for(int i = 0; i < N; i++) cin >> A[i];
    
    vector<tuple<int, ll, bool>> Card;
    rep(i, N){
        Card.pb({i, A[i], false});
    }

    sort(all(Card),[](auto a,auto b){ return get<1>(a) > get<1>(b); });
    rep(i, N / 2){
        Card[i] = {get<0>(Card[i]), get<1>(Card[i]), true};
    }

    sort(all(Card),[](auto a,auto b){ return get<0>(a) < get<0>(b); });
    
    vector<int> R;
    ll su = 0;
    for(auto [idx, val, use]: Card){

        if(use) R.pb(-1);
        else R.pb(1);

        if(use) su += val;
    }

    rep(i, R.size() - 1){
        R[i+1] += R[i];
    }

    int ans = 0;
    rep(i, N){
        if(R[ans] > R[i]) ans = i;
    }

    cout << ans << " " << su << '\n';
    
}

インデックス/値/使うか否か　の3つの値を持ちたかったのでtupleを使いましたが、書いていてだいぶ嫌な気持ちになりました。よい書き方を知りたいです。

AtCoderのハンドルネーム: Kyo_s_s
目標レーティング: 1600
必要パフォーマンス: 1846.19
https://t.co/VQD8mPP73q

明日のABCで1847をだしたら、入青......！！！

— きょ (@Kyo_s_s) April 9, 2022

青になりたいです。　よろしくおねがいします。