ABC 262 参加記

2022.08.02

競技プログラミング

42分5完で273位、パフォーマンスは2101でした。+57しましたが、前日に-68しているので実は負けです(？)

A World Cup

問題

$Y$以上で$4$で割ったあまりが$2$である最小の数を求めてね。

$2000 \leq Y \leq 3000$

提出コード

int main(){
 
    LL(Y);
 
    while(true){
        if(Y % 4 == 2){
            OUT(Y);
            break;
        }
        Y++;
    }
 
}

B Triangle (Easier)

問題

$N$頂点$M$辺の単純無向グラフが与えられます。次の条件をすべて満たす整数 $a, b, c$の組の総数を求めてね。

$1 \leq a < b < c \leq N$

頂点 $a$ と頂点 $b$ を結ぶ辺が存在する。

頂点 $b$ と頂点 $c$ を結ぶ辺が存在する。

頂点 $c$ と頂点 $a$ を結ぶ辺が存在する。

$3 \leq N \leq 100$

$1 \leq M \leq \frac{N(N-1)}{2}$

提出コード

int main(){
 
    LL(N, M);
 
    set<pll> S;
 
    rep(i, M){
        LL(u, v); u--; v--;
        S.insert({u, v});
        S.insert({v, u});
    }
 
    ll ans = 0;
 
    rep(a, N) rep(b, N) rep(c, N){
        if(!(a < b && b < c)) continue;
        bool add = true;
 
        if(S.find({a, b}) == S.end()) add = false;
        if(S.find({b, c}) == S.end()) add = false;
        if(S.find({c, a}) == S.end()) add = false;
 
        if(add) ans++;
    }
 
    OUT(ans);
}

適当に書いたので $O(N^3 \log N)$ ですが、ちゃんと書くと $O(N^3)$になります　set<pll>を書いてから気づいたのでそのまま書いてしまいましたが

C Min Max Pair

問題

$1$以上$N$以下の整数からなる長さ$N$の数列$a = (a_1, \ldots, a_N)$が与えられます。以下の条件をすべて満たす$i, j$の組の総数をもとめてね。

$1 \leq i < j \leq N$

$\min(a_i, a_j) = i$

$\max(a_i, a_j) = j$

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

$1 \leq a_i \leq N~(1 \leq i \leq N)$

考察

($a_i = j$かつ$a_j = i$)もしくは($a_i = i$かつ$a_j = j$)の時に条件を満たします。前者は見ていけばよいです。後者は$a_i = i$となるようなものを数えていけばよいです。

提出コード

int main(){
 
    LL(N);
    VECS(ll, A, N);
 
    ll F = 0, ans = 0;
 
    rrep(i, N){
 
        if(A[i] == i){
            ans += F;
            F++;
        }else{
            if(A[A[i]] == i && i < A[i]){
                ans++;
            }
        }
 
    }
 
    OUT(ans);
}

D I Hate Non-integer Number

問題

項数が$N$の整数列$A = (a_1, \ldots, a_N)$が与えられます。$A$の項を$1$個以上選ぶ方法は$2^N-1$通りありますが、そのうち選んだ項の平均値が整数であるものが何通りかを$998244353$で求めてね。

$1 \leq N \leq 100$

$1 \leq a_i \leq 10^9$

考察

$N \leq 100$ なので、選ぶ個数の最大は高々$100$個です。dp[i][M][m]を「$i$個選んで$M$で割ったあまりが$m$であるようなものの個数」とします。初期値を$dp[0][x][0] = 1~(1 \leq x \leq N)$、それ以外を$0$として$a_1,\ldots, a_N$を選ぶ/選ばない遷移をすればよいです。答えはdp[x][x][0]($1 \leq x \leq N$) の総和となります($x$個選んで$x$で割ったあまりが$0$になるものの総和が答えなので)。$\Theta(N^4)$かかりますが、C++を使っているんだぞ！と言いながら投げると間に合います。

提出コード

// https://github.com/Kyo-s-s/Kyo_s_s_Library/blob/main/md/Modint.md
 
int main(){
 
    LL(N);
    VEC(ll, A, N);
 
    vector dp(N+1, vector(N+1, vector(N+1, Mint(0))));
 
    for(int i = 1; i <= N; i++) dp[0][i][0] = 1;
 
    for(auto a: A){
        vector pd(N+1, vector(N+1, vector(N+1, Mint(0))));
        for(int i = 0; i < N; i++){
            for(int M = 1; M <= N; M++){
                for(int m = 0; m < M; m++){
                    pd[i][M][m] += dp[i][M][m];
                    pd[i+1][M][(m+a)%M] += dp[i][M][m];
                }
            }
        }
        swap(dp, pd);
    }
 
    Mint ans = 0;
    for(int i = 1; i <= N; i++){
        ans += dp[i][i][0];
    }
    OUT(ans);
}

通すのに9分くらいかかりました。でもバグらせずにかけたのでよかった！

E Red and Blue Graph

問題

$N$頂点$M$辺の単純無向グラフが与えられます。それぞれの頂点を赤または青で塗る方法は$2^N$通りあります。このうち、以下の条件をすべて満たすものの総数を$998244353$で割ったあまりを求めてね。

赤く塗られた頂点がちょうど$K$個

異なる色で塗られた頂点を結ぶ辺の本数が偶数となる

$2 \leq N, M \leq 2 \times 10^5$

$0 \leq K \leq N$

考察

$K = 1$の時、各頂点のうち出次数が偶数のものの個数です。$K=2$の時、次のようにすると答えが導けます。

// 頂点iの出次数をB[i]とする
for(x = 0; x < N; x++){
	for(y = 0; y < N; y++) if(x != y){
		// xとyを赤に塗ったものを考える
		cnt = B[x] + B[y] - 2 * (xとyをつなぐパスがあるか？あるなら1, ないなら0);
		if(cnt % 2 == 0) ans++;
	}
}

重複のない$R = \{ x_1,\ldots, x_K \} ~(0 \leq x_i < N)$に対して、$R$に属する頂点をすべて赤に塗ったとすると、前のコードのcntは、 $$ cnt = \sum_{i = 0}^K B_{x_i} - 2\times(Rに属する頂点のみからなるグラフの辺の本数) $$ と書くことができます。興味があるのはcntの偶奇のみなので、結局出次数の総和が偶数であればよいということがわかります。

これにより、この問題は次のように言い換えることができます。

数列$B=(B_1, \ldots, B_N)$があたえられます。ちょうど$K$個選んだ時の総和が偶数になるようなものは何通り存在しますか？

$B_i$も偶奇のみがわかればよいので、偶数と奇数をそれぞれ数えて、和が偶数になる(つまり、奇数の頂点を偶数個選ぶようなもの)かつちょうど$K$個選ぶものの数を数えればよいです。

提出コード

// https://github.com/Kyo-s-s/Kyo_s_s_Library/blob/main/md/Modint.md
// https://kyo-s-s.github.io/Library/Math/Enumeration.hpp

int main(){
 
    LL(N, M, K);
 
    vvll G(N);
    rep(i, M){
        LL(u, v); u--; v--;
        G[u].pb(v);
        G[v].pb(u);
    }
 
    ll Gu = 0, Ki = 0;
    rep(i, N){
        if(G[i].size() % 2 == 0) Gu++;
        else Ki++;
    }
 
    Enumeration<Mint> enu;
    Mint ans = 0;
    for(int ki = 0; ki <= K; ki += 2){
        ans += enu.nCk(Gu, K - ki) * enu.nCk(Ki, ki);
    }
 
    OUT(ans);
 
}

25分くらいで通せてよかったです。うれしい～～～