ABC 247 参加記

2022.04.11

競技プログラミング

94分6完(3ペナ)でした。575位、パフォーマンスは1757です。

A Move Right

問題

0, 1からなる4文字の文字列$S$が渡されます。1つ右にシフトしてください。

提出コード

int main(){

    string S; cin >> S;
    
    string T = "0";
    rep(i, 3) T.pb(S[i]);
    cout << T << '\n';

}

ACコード

int main(){
    
	bitset<4> S; cin >> S;
	S >>= 1;
	cout << S << endl;

}

bitsetで入力を受け取るととても簡潔に書けますね、知りませんでした。

B Unique Nicknames

問題

$N$人の人がいて、人$i$の姓は$s_i$、名は$t_i$です。それぞれにあだ名をつけます。人$i$あだ名は、

$s_i$か$t_i$のいずれかである

自分以外の人の姓/名と一致しない

を満たす必要があります。全員にあだ名をつけることはできますか？

$2 \leq N \leq 100$、$N$は整数

$s_i, t_i$は英小文字からなる1文字以上10文字以下の文字列

考察

適当に書いてペナを食らいました。$s_i = t_i$の時にいやなきもちになるので、気を付けて書きます。

提出コード

int main(){

    ll N; cin >> N;

    vs S(N), T(N);
    rep(i, N){
        cin >> S[i] >> T[i];
    }

    rep(i, N){
		//人iにあだ名をつけれるか？
        bool pass = false;

        {
            //姓をあだ名にした場合
            bool ok = true;
            string nic = S[i];

            rep(j, N) if(i != j){
                if(S[j] == nic) ok = false;
                if(T[j] == nic) ok = false;
            }

            if(ok){
                pass = true;
            }
        }

        {
            //名をあだ名にした場合
            bool ok = true;
            string nic = T[i];

            rep(j, N) if(i != j){
                if(S[j] == nic) ok = false;
                if(T[j] == nic) ok = false;
            }

            if(ok){
                pass = true;
            }
        }

        if(!pass){
            YesNo(false); exit(0);
        }
    }

    YesNo(true);
}

C 1 2 1 3 1 2 1

問題

列$S_n$を次のように定義します。

$S_1$は1つの1からなる長さ1の列

$S_n(n \geq 2)$は$S_{n-1}, n, S_{n-1}$を順につなげた列

$N$が与えられるので、$S_N$を出力してください。

$N \leq 16$

考察

最初問題文を読んだ時には「再帰してください」と書いてあったのに、コンテスト終了後に再度読んだら「順にやってください」と書いてありました。再帰をするより順にやった方がコード記述量が少なくなります。

提出コード

int main(){

    
    ll N; cin >> N;
    
    map<int, vector<int>> memo;

    auto dfs = [&](auto&& self, ll x) -> vector<int> {
        if(memo.find(x) != memo.end()) return memo[x];

        if(x == 1){
            return {1};
        }

        auto B = self(self, x - 1);
        vector<int> ret = B;
        ret.pb(x);
        for(auto b: B) ret.pb(b);

        return memo[x] = ret;

    };

    auto ans = dfs(dfs, N);

    for(int i = 0; i < ans.size(); i++){
        cout << ans[i] << (i != ans.size() - 1 ? ' ' : '\n');
    }

}

ACコード

int main(){

    ll N; cin >> N;
    
    vi ans = {};
    rrep(i, N){
        vi nxt;

        for(auto a: ans) nxt.pb(a);
        nxt.pb(i);
        for(auto a: ans) nxt.pb(a);

        swap(ans, nxt);
    }

    for(int i = 0; i < ans.size(); i++){
        cout << ans[i] << (i != ans.size() - 1 ? ' ' : '\n');
    }

}

D Cylinder

問題

空の筒があります。クエリが$Q$個くるのでさばいてください。

1 x c : 数$x$が書かれたボールを右側から$c$個入れる

2 c : 筒の左側からボールを$c$個取り出し、取り出したボールに書かれている数の合計を出力

$1 \leq Q \leq 2 \times 10^5$

$0 \leq x \leq 10^9$

$1 \leq c \leq 10^9$

考察

そのままやります。ボールを$c$個実際に入れることはできないので、圧縮します。

提出コード

int main(){

    ll Q; cin >> Q;

    deque<pll> que;

    rep(q, Q){
        int t; cin >> t;

        if(t == 1){
            ll x, c; cin >> x >> c;
            que.pb({x, c});
        }else{
            ll c; cin >> c;
            ll ret = 0;

            while(c != 0){

                auto [hx, hc] = que.front();

                ll po = min(c, hc);	//取り出した数
                ret += hx * po;
                que.front().se -= po;
                c -= po;

                if(que.front().se == 0){ //一番左にいるボールが0個になったとき
                    que.pop_front();
                }
                
            }

            cout << ret << '\n';
        }
    }    
}

E Max Min

問題

長さ$N$の数列$A$、$X, Y$があります。次の条件をすべて満たす整数の組$(L, R)$の個数を求めてください。

$1 \leq L \leq R \leq N$

$A_L, A_{L+1}, \cdots, A_{R}$の最大値は$X$であり最小値は$Y$である。

$1 \leq N \leq 2 \times 10 ^ 5$

$1 \leq A_i \leq 2 \times 10^5$

$1 \leq Y \leq X \leq 2 \times 10 ^ 5$

入力される値はすべて整数

考察

順に数列を見ていきます。見ていく中で$X, Y$が現れる最近のインデックスと範囲外($X$より大きいか$Y$より小さいか)が現れる最近のインデックスを覚えておきます。$X, Y$が現れる最近のインデックスを$xi$, $yi$、範囲外が現れる最近のインデックスを$oi$とします。$i$番目が右端になるときの条件を満たす区間を数えていきます。

$A_i = X$の場合

$xi$を$i$に更新します。

答えに$yi - oi$を足せばよいです。右端を$i$とすると左端の最小は$oi$に、最大は$yi$となり、その間はどこを左端にしてもよいからです。
$A_i = Y$の場合

$yi$を$i$に更新します。

答えに$xi - oi$を足せばよいです。
$Y \leq A_i \leq X$の場合

答えに$\min(xi, yi) - oi$を足せばよいです。右端を$i$とすると左端の最小は$oi$に、最大は$\min(xi, yi)$となり、その間はどこを左端にしてもよいからです。
それ以外の場合

$oi, xi, yi$を更新します。$oi$を$i$に、$x_i, y_i$はnullとなります。

$xi, yi$がnullの時に注意してください。提出コードではx,yという変数を用意し、nullかどうかを見ています。

提出コード

int main(){

    ll N, X, Y; cin >> N >> X >> Y;
    vector<ll> A(N); for(int i = 0; i < N; i++) cin >> A[i];
    
    ll ans = 0;

    ll x = 0, y = 0;	// 0 -> null
    ll xi, yi;
    ll idx = 0;
    ll oi = -1;
    for(auto a: A){
        
        if(a > X || Y > a){
            x = 0; y = 0;
            oi = idx;
        }

        if(a == X){
            xi = idx;
            x++;
        }
        
        if(a == Y){
            yi = idx;
            y++;
        }

        if(a == X){
            if(y != 0) ans += yi - oi;
        }elif(a == Y){
            if(x != 0) ans += xi - oi;
        }elif(!(a > X || Y > a)){
            if(x > 0 && y > 0) ans += min(xi, yi) - oi;
        }

        idx++;
    }

    cout << ans << '\n';

}

…ansに加算するところの条件分岐、$A_i$が$X$以下$Y$以上の時は$\min(xi, yi) - oi$を加算、でよくないですか？($A_i$が$X, Y$だった場合、$xi, yi$が今のインデックスに更新されるため) ということで書き直しました。

ACコード

int main(){

    ll N, X, Y; cin >> N >> X >> Y;
    vector<ll> A(N); for(int i = 0; i < N; i++) cin >> A[i];
    

    ll ans = 0;

    ll xi = INF, yi = INF;	//INF -> null
    ll idx = 0;
    ll oi = -1;
    for(auto a: A){
        
        if(a > X || Y > a){
            xi = INF;
            yi = INF;
            oi = idx;
        }

        if(a == X){
            xi = idx;
        }
        
        if(a == Y){
            yi = idx;
        }


        if(X >= a && a >= Y){
            if(xi != INF && yi != INF) ans += min(xi, yi) - oi;
        }

        idx++;
    }

    cout << ans << '\n';

}

F Cards

問題

$1, \cdots, N$の番号がついた$N$枚のカードがあり、カード$i$の表には$P_i$が、裏には$Q_i$が書かれています。ここで、$P, Q$は$1, \cdots, N$の並び替えです。$N$枚のカードから何枚かを選ぶ方法のうち、次の条件を満たすものは何通りありますか？998244353で割ったあまりをもとめてください。

$1, \cdots, N$のどの数も選んだカードのいずれかに書かれている

$1 \leq N \leq 2 \times 10 ^ 5$

考察

サンプル1を考えます。

3

1 2 3

2 1 3

3枚目のカードは、表裏ともに3が書かれています。このカードを選ばないと条件を満たさなくなるため、選ぶことが確定します。

1, 2枚目のカードは、両方選ぶ/どちらか一方を選ばないことが可能です。よってこのサンプルの解は3通りとなります。

$P, Q$は$1, \cdots, N$の並び替えなので、

a b c d e

b c d e a

のような組に分けることができます。この組に対して、何通りの取り方ができるかを求めることができればよいです。これを求めます。

組の枚数が1枚のとき

具体的には、

a

a

のような場合です。この場合はこのカードを選ばなくてはならないため、1通りです。
組の枚数が2枚のとき

具体的には、

a b

b a

のような場合です。この場合は両方選ぶ/どちらか一方を選ばないの3通りが可能です。
組の枚数が3枚のとき

具体的には、

a b c

b c a

のような場合です。この場合について考えてみます。
- 1枚目を選ぶ場合
  - 2枚目を選び、3枚目を選ぶ
  - 2枚目を選び、3枚目を選ばない
  - 2枚目を選ばず、3枚目を選ぶ
- 1枚目を選ばない場合
  - 2枚目を選び、3枚目を選ぶ
の4通りです。

ここから、
$i$番目のカードを選んだ場合、$i+1$番目ではカードを選ぶ/選ばないの2通りが可能
$i$番目のカードを選ばなかった場合、$i+1$番目のカードは必ず選ばなくてはならない

ということがわかります。このような選び方を考えていけばよいです。これはDPをすればよいです。

$N$番目の次のカードは1番目であることに注意してください。1番目を選んだ場合と選ばなかった場合で場合分けします。

$1$枚目を選んだ場合 : $N$枚目のカードを選ぶ/選ばないが可能

1枚目 2枚目 3枚目 4枚目 5枚目 6枚目

選ぶ 1 1 2 3 5 8

選ばない 0 1 1 2 3 5
1枚目を選ばなかった場合 : $N$枚目のカードを選ぶのみ可能

1枚目 2枚目 3枚目 4枚目 5枚目 6枚目

選ぶ 0 1 1 2 3 5

選ばない 1 0 1 1 2 3

	1枚目	2枚目	3枚目	4枚目	5枚目	6枚目
選ぶ	1	1	2	3	5	8
選ばない	0	1	1	2	3	5

	1枚目	2枚目	3枚目	4枚目	5枚目	6枚目
選ぶ	0	1	1	2	3	5
選ばない	1	0	1	1	2	3

これらをかけていけばよいです。

提出コード

using mint =  modint998244353;

int main(){

    ll N; cin >> N;
    vector<ll> P(N); for(int i = 0; i < N; i++) cin >> P[i];
    vector<ll> Q(N); for(int i = 0; i < N; i++) cin >> Q[i];
    
    dsu uf(N);

    rep(i, N) uf.marge(P[i] - 1, Q[i] - 1);

    vvi ret = uf.groups();

    mint ans = 1;

    for(auto r: ret) if(r.size() != 1){
        
        mint k = 0;
        //1枚目を選ぶ場合
        {
            pair<mint, mint> dp = {1, 0};
            rep(i, r.size() - 1){
                dp = {dp.fi + dp.se, dp.fi};
            }
            k += dp.fi + dp.se;
        }

        //1枚目を選ばない場合
        {
            pair<mint, mint> dp = {0, 1};
            rep(i, r.size() - 1){
                dp = {dp.fi + dp.se, dp.fi};
            }
            k += dp.fi;
        }

        ans *= k;

    }
    
    cout << ans.val() << '\n';

}

1枚目を選ぶDPと選ばないDPですが、選んだ場合の2枚目以降と選ばなかった場合の3枚目以降は同じです。よってこれらはまとめることができます。これらをまとめると公式解説の式が導けます。きれいですね(DPをしても十分通る制約なのでDPをしてもよいです)。

できませんでした。敗因はこの秋刀魚が半額だったからだと思われます。 https://t.co/at5VD2TnGM
— きょ (@Kyo_s_s) April 10, 2022

次のABCで入青したいです。