Atcoder 復習 備忘録

ABC294 D問題

順序付き集合型 std::set を使う。

D.cpp

set<int> called;
cout << *begin(called)<< "\n";    //begin(called)で先頭をさすイテレータを取得。
                                  //*でイテレータの指す値を取得。

O(log N)で集合の最小値を取得できる。

ABC296 C問題

C.cpp

map<int,int> color;
for(auto x: color){
	ans+=x.second/2; //mapの二つ目の要素にアクセス
}

for (auto [_, cnt]: mp) ans += cnt / 2; //解答の例
	

ABC297 E問題

順序付き集合setを使う

E.cpp

    set<ll> st;
    auto push=[&](ll x){
        rep(i,n){
            ll nx=x+a[i];
            st.insert(nx);
            push(x);
        }
    };
    push(0);
    rep(i,K-1){
        ll x=*st.begin();
        st.erase(x);
        push(x);
    }
    ll ans =*st.begin();

ABC298 C問題

順序付き多重集合std::multiset を使う。実装はstd:setと同じ。

ABC298 D問題

998244353で割った余りを扱う問題ではmodintと呼ばれる構造体を用いる。ACLのmodintのpowでは繰り返し二乗法によって累乗を求める仕様になっている。

D.cpp

using mint = modint998244353;

int main(){
    mint ans=1;

    ans=mint(10)*pow(1000);
}