📝

AtCoder備忘録(AGCにも手を出してみた)

2025/11/11に公開

最近大学が忙しくて競プロや記事作成に時間が取れていなかったので, その中で解いた問題などの考え方などを(自分の復習用とかにも)まとめておきます. ここ2回ABC参加できてないし今週も出れないのでその分頑張っていきたい、、、

読むためのヘッダー群

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i = (int)a; i < (int)b; i++)
#define vi vector<int > 
#define vvi vector<vi > 
#define vvvi vector<vvi >
#define pii pair <int, int>
#define MOD(a, b) (((a) % (b)) + (b)) % (b)
#define INF LLONG_MAX
#define Ans(i) cout << i << endl;

ABC269 D - Do use hexagon grid

蜂の巣みたいな形状のグラフの結合部分が何個あるか判定する問題.

マスの個数が有限なので左上のマスから順番に0, 1, 2...と数を振っていく. -1000〜1000の2001マスあるので2001進数の要領で数字とマスを一対一対応させる. それでUnionFindで結合判定する.
mapで持たせた方がだいぶ楽だった.

UnionFindはこちら

/// @brief Union-Find 木
/// @note 1.4 高速化 + 省メモリ化
/// @see https://zenn.dev/reputeless/books/standard-cpp-for-competitive-programming/viewer/union-find

class UnionFind{
public:
	UnionFind() = default;
	// n: 要素数. 
	explicit UnionFind(size_t n)
		: m_parentsOrSize(n, -1) {}
	int find(int i){
		if(m_parentsOrSize[i] < 0){
			return i;
		}
		return(m_parentsOrSize[i]=find(m_parentsOrSize[i]));
	}
	void merge(int a, int b){
		a = find(a);
		b = find(b);
		if (a != b){
			// union by size (小さいほうが子になる）
			if (-m_parentsOrSize[a] < -m_parentsOrSize[b]){
				std::swap(a, b);
			}
			m_parentsOrSize[a] += m_parentsOrSize[b];
			m_parentsOrSize[b] = a;
		}
	}
	bool connected(int a, int b){
		return (find(a)==find(b));
	}
	int size(int i){
		return -m_parentsOrSize[find(i)];
	}

private:
	// m_parentsOrSize[i] は i の 親,
	// ただし root の場合は (-1 * そのグループに属する要素数)
	std::vector<int> m_parentsOrSize;
};

signed main(){
    int n;cin>>n;
    UnionFind U(5e6+10);
    vi x(n),y(n);
    set<pii>S;
    vector<pii>move={{1,1},{1,0},{0,-1},{-1,-1},{-1,0},{0,1}};
    rep(i,n){
        cin>>x[i]>>y[i];
        x[i]+=1000,y[i]+=1000;
        S.insert({x[i],y[i]});
        for(auto itr:move){
            int R=x[i]+itr.first,C=y[i]+itr.second;
            if(S.count({R,C})){
                U.merge(x[i]*2002+y[i],2002*R+C);
            }
        }
    }
    set<int>heads;
    for(auto s:S){
        heads.insert(U.find(2002*s.first+s.second));
    }
    Ans(heads.size());
}

ABC281 D - Max Multiple

推移を扱っていくので見た感じdpかなと思いdpの配列を

dp[i][j][k]: j個使って,dで割る余りkのもののうちの最大値

のように設定してあとは"a[i]を使わないパターン"と"使うなら余りと個数が増えて"っていう場合分けをして実装した.

signed main(){
    int n,k,d;cin>>n>>k>>d;
    vin(a,n);
    vvvi dp(n+1,vvi(k+1,vi(d,-1)));
    // dp[i][j][k]: j個使って,dで割る余りkのもののうちの最大値
    dp[0][0][0]=0;
    rep(i,n){
        rep(j,k){
            rep(l,d){
                if(dp[i][j][l]==-1){
                    continue;
                }
                dp[i+1][j][l]=max(dp[i+1][j][l],dp[i][j][l]);
                dp[i+1][j+1][MOD(l+a[i],d)]=max(dp[i+1][j+1][MOD(l+a[i],d)],dp[i][j][l]+a[i]);
            }
        }
    }
    int ans=-1;
    rep(i,n){
        ans=max(ans,dp[i+1][k][0]);
    }
    Ans(ans);
}

ABC254 E - Small d and k

ある頂点 $x$ から距離が $k(k\le 3)$ の点のindexの総和を求める問題.

グラフ作る.
全ての頂点からマックス3回幅優先探索をする.
a. dist[j]:今探索の根本になってる頂点iからの最短距離.
b. used: ある頂点iからの探索で通ってdistをINF以外にした点の集合.
c. ans[i][j]: 頂点iから距離jのところにあるindexの総和.
d. 探索終了後にusedにある全ての距離をansに適切に加算して全部INFに戻す.
クエリを処理する.

Eも解けるようになってきて嬉しい.

signed main(){
    int n,m;cin>>n>>m;
    vvi G(n+1);
    rep(i,m){
        int a,b;cin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    int lim=3;
    vi dist(n+1,INF);
    queue<int>Q;
    vvi ans(n+1,vi(4));
    repi(i,1,n+1){
        set<int>used;
        Q.push(i);
        used.insert(i);
        dist[i]=0;
        while(Q.size()){
            int pos=Q.front();
            Q.pop();used.insert(pos);
            for(auto next:G[pos]){
                if(dist[next]>dist[pos]+1){
                    dist[next]=dist[pos]+1;
                    if(dist[next]<=lim){
                        Q.push(next);
                    }
                }
            }
        }
        // Ans(i)
        for(auto s:used){
            // Ans(s<<" "<<dist[s]);
            for(int j=3;j>=dist[s];j--){
                ans[i][j]+=s;
            }
            dist[s]=INF;
        }

    }
    int q;cin>>q;
    for(;q--;){
        int x,k;cin>>x>>k;
        Ans(ans[x][k]);
    }
}

AGC005 A - STring

与えられる文字列の中から連続する"ST"という部分列を削除することを繰り返していくことでえられる文字列をの長さを返す問題.

STの並びは(左から)一文字ずつ見ていく中で'S'の次に'T'がくる時だけなので着目している一番右の文字が'S'かつ次の文字が'T'の時だけ削除が発生する. これはstackで扱える.
// (Aとはいえ)AGCも解けるようになってきて嬉しい.

signed main(){
    string s;cin>>s;
    stack<char>S;
    for(auto c:s){
        if(S.empty()){
            S.push(c);
        }else if(!(S.top()=='S'&&c=='T')){
            S.push(c);
        }else{
            S.pop();
        }
    }
    Ans(S.size());
}

AGC017 A - Biscuits

長さ $N$ の配列 $A$ からいくつか要素を選ぶ時(0個でも), その総和を2で割った余りがpになる選び方を求める問題.
思考と試行の流れ↓↓
Aの要素のうち2で割った余りが0のものの個数を $even$ , 1のものの個数を $odd$ と置く.

$p=0$

$even$ から何個かと $odd$ から偶数個選ぶ.
$odd$ からのみ偶数個選ぶ.
$even$ からのみ何個か選ぶ.

$p=1$

$even$ から何個かと $odd$ から奇数個選ぶ.
$odd$ からのみ奇数個選ぶ.

$even$ や $odd$ の中から個数を決めずに何個か選ぶ方法ならばある部分集合に対してそれぞれの要素が入るか/入らないかで2通りあるので $2^{even}, 2^{odd}$ で求めることができる.
そうすると必要になってくるのは
$\Large oddから偶数個/奇数個選ぶ場合の数$
である.
これを $odd=4$ で試すと
偶数個選ぶのは

{}_4 C_0+{}_4 C_2+{}_4 C_4=1+6+1=8

奇数個選ぶのは

{}_4 C_1+{}_4 C_3=4+4=8

おお等しいんや.
次に $odd=5$ で試すと
偶数個選ぶのは

{}_5 C_0+{}_5 C_2+{}_5 C_4=1+10+5=16

奇数個選ぶのは

{}_5 C_1+{}_5 C_3+{}_5 C_5=5+10+1=16

こっちは同じ要素しか出てこないから等しいのは自明そう.
一応2の累乗で偶然っていう可能性があるので

odd=6

で試しても32で一致.
つまり

\underline{ある個数から偶数個選ぶ場合の数と奇数個選ぶ場合の数は等しい}

// 数学がちょっと好きとか言っておきながら性質としてのこれを知りませんでした。
そしてこれは

$\frac{2^{odd}}{2}=2^{odd-1}$

と表すことができる. ( $odd=0$ で場合分けが必要.)

一応証明

自然数 $k$ について

{}_{2k} C_0+{}_{2k} C_2+...+{}_{2k} C_{2k}=2^{2k-1}

を示す.

補題(ほどでもないけど)

{}_n C_k = {}_{n-1} C_{k-1}+{}_n C_k

が成立する. パスカルの三角形とか普通に等式変形とかで示せる." $n$ 個から $k$ 個選ぶ時にある1要素を区別して, それを選ぶ時は $n-1$ 個から $k-1$ 個, 選ばない時は $n$ 個から $k$ 個選ぶ"みたいな解釈ができる.

でこれを $\textcolor{red}{両端以外}$ に適用すると,

{}_{2k} C_0+\textcolor{red}{{}_{2k-1} C_1+{}_{2k-1} C_2+...++{}_{2k-1} C_{2k-3}+{}_{2k-1} C_{2k-2}}+{}_{2k} C_{2k}

となり, 当然

{}_{2k} C_0=1={}_{2k-1} C_0

{}_{2k} C_{2k}=1={}_{2k-1} C_{2k-1}

が成り立つので, さらに

{}_{2k-1} C_0+{}_{2k-1} C_1+{}_{2k-1} C_2+...++{}_{2k-1} C_{2k-3}+{}_{2k-1} C_{2k-2}+{}_{2k-1} C_{2k-1}

と変形することができて, これは二項定理から

{}_{2k-1} C_0+{}_{2k-1} C_1+{}_{2k-1} C_2+...++{}_{2k-1} C_{2k-3}+{}_{2k-1} C_{2k-2}+{}_{2k-1} C_{2k-1}=2^{2k-1}

となるので

{}_{2k} C_0+{}_{2k} C_2+...+{}_{2k} C_{2k}=2^{2k-1}

が示された.

すると嬉しいことがあってさっきの場合分け

$p=0$

$even$ から何個かと $odd$ から偶数個選ぶ.
$odd$ からのみ偶数個選ぶ.
$even$ からのみ何個か選ぶ.

$p=1$

$even$ から何個かと $odd$ から奇数個選ぶ.
$odd$ からのみ奇数個選ぶ.

のうち, 1, 2は同じ値になることがわかる.
さらに $p=0$ の時の3についても $\large {2でoddを0個選ぶパターン}$ に包含されていると考えると,
( $2^{odd}$ の中には0個選ぶものも含まれている)求めるものは一気にスッキリして

\large{\lbrace evenから選ぶ組み合わせ\rbrace *\lbrace oddから偶数(=奇数)個選ぶ組み合わせ\rbrace }

で求めることができて,

ans=2^{even}+2^{odd-1}=2^{even+odd-1}

で求めることが出来る.
さらに当然

even+odd=n

なのでこれは

ans=2^{n-1}

とまで変形できる. あとは

odd=0

の時だけ場合分けして解けば終わり.
この時全て偶数なので

$p=0$ なら $2^n$ 通り
$p=1$ なら実現不能なので0通り.

となる.

// $2^{50}$ は $\lparen 2^{10} \rparen ^{5}$ なので15桁くらいなのでlong longならオーバーフローしないでしょう.

signed main(){
    int n,p;cin>>n>>p;
    int odd=0;
    rep(i,n){
        int a;cin>>a;
        odd+=a%2;
    }
    int ans;
    if(odd==0){
        ans=(p==0?(1LL<<n):0);
    }else{
        ans=(1LL<<(n-1));
    }
    Ans(ans);
}

最後に

ここまで読んでくれてありがとうございました✨✨
わかりにくかったり、間違っている部分があったらぜひ教えてください！
完全に私事なのですがモニターやらキーボードをついに導入して作業がとっても楽しくなりました！