接着剤の精進日記

競プロでの精進や研究に関係したことを書いていきます。

トップ > AtCoderRegularContest105 > AtCoder Regular Contest 105（ARC105）

AtCoder Regular Contest 105（ARC105）

AtCoderRegularContest105 AtCoderRegularContest ARC105 ARC

atcoder.jp

A - Fourtune Cookies

どれを食べるか全探索すればいい
提出コード

void solve(){
    int A, B, C, D;
    cin >> A >> B >> C >> D;
    ll sum = A + B + C + D;
    bool ok = false;
    REP(i,2) REP(j,2) REP(k,2) REP(l,2){
        if(i == 0 and j == 0 and k == 0 and l == 0) continue;
        ll cnt = 0;
        if(i == 1) cnt += A;
        if(j == 1) cnt += B;
        if(k == 1) cnt += C;
        if(l == 1) cnt += D;
        if(sum - cnt == cnt) ok = true;
    }
    cout << (ok ? "Yes" : "No") << endl;
}

B - Product Max

操作を考えるとgcd(x, X) = gcd(x, X-x)が成り立つ
よって操作を行ってもgcd(a)が不変であることがわかるのでgcd(a)を求めればいい
提出コード

void solve(){
    int N;
    cin >> N;
    vector<ll> a(N);
    REP(i,N) cin >> a[i];
    int ans = 0;
    REP(i,N) ans = gcd(ans, a[i]);
    cout << ans << endl;
}

C - Camels and Bridge

ラクダの隊列はN!で全探索をすればいい
後はそれぞれの隊列の状態での長さの最小値を求めればいい
まず、max(w) > min(v)のときは必ず-1になる
max(w) \leq min(v)の時を考える
ラクダ(i, j) (1 \leq i \lt j \leq N)間に必要な距離がわかれば動的計画法によって全体に必要な長さを求めることがわかる
ラクダ(i, j) (i \leq k \leq j)間のラクダの重さの合計は累積和によって求めることが出来るので後は、その重さが耐えられる橋の長さがわかればいい
これは重さがvの時に耐えられる橋の長さの最大をlとし座圧を行いvectorなどに重さの昇順に並べておく
そうすると、ラクダ(i, j) (i \leq k \leq j)間のラクダの重さに耐えられる橋の長さが二分探索で求めることが出来るので、全体でO(N!N^2 logM)でこの問題に答えることが出来る
重さが10^8程度なので座圧しなくても良くて実装が少し楽になるらしい
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<int> w(N);
    REP(i,N) cin >> w[i];
    sort(w.begin(), w.end());
    map<int, int> mp;
    vector<int> l(M), v(M);
    REP(i,M){
        cin >> l[i] >> v[i];
        if(v[i] < w[N-1]){
            cout << -1 << endl;
            return;
        }
        if(mp.count(v[i])) chmax(mp[v[i]], l[i]);
        else mp[v[i]] = l[i];
    }
    vector<pair<int, int>> vp;
    vp.emplace_back(0, 0);
    for(auto [key, value] : mp) vp.emplace_back(key, value);
    vp.emplace_back(INF, 0);
    REP(i,(int)vp.size()-1) chmax(vp[i+1].second, vp[i].second);
    int ans = INF;
    do{
        vector<int> cum(N+1);
        REP(i,N) cum[i+1] = cum[i] + w[i];
        vector<int> dp(N+10);
        REP(i,N){
            for(int j=i+1;j<N;j++){
                int sum_w = cum[j+1] - cum[i];
                auto itr = lower_bound(vp.begin(), vp.end(), make_pair(sum_w, -INF));
                itr--;
                int len = itr -> second;
                chmax(dp[j], dp[i] + len);
                chmax(dp[j+1], dp[j]);
            }
        }
        chmin(ans, dp[N]);
    }while(next_permutation(w.begin(), w.end()));
    cout << ans << endl;
}

提出コード

onst int MAX = (int)1e8 + 10;
void solve(){
    int N, M;
    cin >> N >> M;
    vector<int> w(N);
    REP(i,N) cin >> w[i];
    sort(w.begin(), w.end());
    vector<int> v(MAX);

    REP(i,M){
        int l, vv;
        cin >> l >> vv;
        if(vv < w[N-1]){
            cout << -1 << endl;
            return;
        }
        chmax(v[vv], l);
    }
    REP(i,MAX-1) chmax(v[i+1], v[i]);
    int ans = INF;
    do{
        vector<int> cum(N+1);
        REP(i,N) cum[i+1] = cum[i] + w[i];
        vector<int> dp(N+10);
        REP(i,N){
            for(int j=i+1;j<N;j++){
                chmax(dp[j], dp[i] + v[min(MAX-1, cum[j+1]-cum[i]-1)]);
                chmax(dp[j+1], dp[j]);
            }
        }
        chmin(ans, dp[N]);
    }while(next_permutation(w.begin(), w.end()));
    cout << ans << endl;
}

D - Let's Play Nim

Nimなのでコインを皿に置き終わった時、各皿にあるコインの総xorが0なら後手必勝、それ以外は先手必勝となる
そのため、最後にコインを置く人はxorが0にそうじゃなければxorを0以外にしたい
まずNが奇数のとき、後手必勝となる
これは、後手が選べるもののうちコインの枚数が最大の袋と皿を選べば一つの皿に過半数のコインが乗った状態を作ることができ、総xorが0にならないようにすることが出来る
次にNが偶数の時を考える
これは奇数のときと同様に先手がコインの枚数が最大の袋と皿を選べば過半数のコインが乗った状態を作ることができるため先手必勝となる
ただし、任意の整数nについてn枚のコインが入った袋が偶数ある時、後手は先手と同じ手を打ち続けることでxorを0にすることが出来るため、この時のみ後手必勝となる
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> a(N);
    REP(i,N) cin >> a[i];
    if(N & 1){
        cout << "Second" << endl;
        return;
    }
    sort(a.begin(), a.end());
    bool ok = true;
    for(int i=0;i<N;i+=2){
        if(a[i] != a[i+1]) ok = false;
    }
    cout << (ok ? "Second" : "First") << endl;
}