Soxy Log

競技プログラミングに関すること

AtCoder ABC136 E - Max GCD

問題


AtCoder ABC136 E - Max GCD

解法


Aの要素を全て割り切る整数の候補は、A[i]の総和Sの約数である。
これらをd[i]とすると、全てを試してもたかだかO(sqrt(N * max(A)))個であるので時間内に計算を終えることができる。
d[i]でA[j]を割った余りをa[j]とすると、aの要素同士で題意の操作を行い、K回以内に全てのa[i]をd[i]の倍数にできるかを判定すればよい。
a[i]を昇順にソートした配列と、1つの仕切りを考える。
仕切りより左のj個のa[i]の和をsum_left、右のN-j個のd[i]-a[j]の和をsum_rightとすると、abs(sum_left - sum_right)がd[i]の倍数となるときのsum_rightが、全てのAをd[i]の倍数にするための操作回数である。
仕切りの位置をずらしていくことで、全てのAをd[i]の倍数にする為の最小操作回数が求まる。
これを全てのd[i]に対して行うことでdの最大値を求めればよい。

ソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    int N;
    ll K;
    cin >> N >> K;
    vector<ll> A(N);
    ll S(0);
    for(int i(0);i<N;++i){
        cin >> A[i];
        S += A[i];
    }
    vector<ll> d;
    for(int i(1);i*i<=S;++i){
        if(S % i == 0){
            d.push_back(i);
            d.push_back(S/i);
        }
    }
    int M = d.size();
    vector<ll> a(N);
    ll a_sum,sum_left,sum_right,target_d,d_max(0);
    for(int i(0);i<M;++i){
        target_d = d[i];
        a_sum = 0;
        for(int j(0);j<N;++j){
            a[j] = A[j] % target_d;
            a_sum += a[j];
        }
        sort(a.begin(),a.end());
        sum_left = a_sum;
        sum_right = 0;
        ll swap_num = 1e18;
        for(int j(N-1);j>=0;--j){
            sum_left -= a[j];
            sum_right += target_d-a[j];
            if(abs(sum_left - sum_right) % target_d == 0) swap_num = min(swap_num, max(sum_left, sum_right));
        }
        if(swap_num <= K) d_max = max(d_max, target_d);
    }
    cout << d_max << endl;
    return 0;
}

AtCoder ABC135 D - Digits Parade

問題


AtCoder ABC135 D - Digits Parade

解法


dp[i][j]を先頭i文字として考えられるもののうち,13で割ったあまりがjであるものの数と定義し、 動的計画法でdp[N][5]を求める。(解答)

ソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = pow(10,9) + 7;
 
string S;
int dp[100005][13];
 
ll solve(int pos, int rem) {
    if(pos == S.length()) return rem == 5;
    if(dp[pos][rem] != -1) return dp[pos][rem];
    ll ans(0);
    if(S[pos] == '?') {
        for(int i(0); i < 10; ++i) {
            ans += solve(pos + 1, (rem * 10 + i) % 13) % mod;
        }
    }
    else ans += solve(pos + 1, (rem * 10 + S[pos] - '0') % 13) % mod;
    return dp[pos][rem] = ans % mod;
}
 
int main() {
    memset(dp, -1, sizeof dp);
    cin >> S;
    cout << solve(0, 0) << endl;
}

AtCoder ABC134 E - Sequence Decomposing

問題


AtCoder ABC134 E - Sequence Decomposing

解法


数列Aの広義単調減少列の長さの最大値が答えである。(解答)
A[N]からA[1]の順に走査し、最長の広義単調減少列dec_lenを求める。
A[i]>=dec_len[top]の場合、dec_lenにA[i]を追加し、topをインクリメントする。
そうでない場合、dec_len中のA[i]より大きい要素の最小値をA[i]で置き換える。
これを繰り返すことで、広義単調減少列の長さtopが求まる。

ソースコード

#include <bits/stdc++.h>
using namespace std;
int N, top, A[200001], dec_len[200001];
int main(){
    cin >> N;
    for(int i=N; i>=1; --i) cin >> A[i];
    for(int i=1; i<=N; ++i) {
        if(A[i]>=dec_len[top]){
            dec_len[++top]=A[i];
        }else {
            dec_len[upper_bound(dec_len+1,dec_len+top+1,A[i])-dec_len]=A[i];
        }
    }
    cout << top << endl;
    return 0;
}

AtCoder ABC134 D - Preparing Boxes

問題


AtCoder ABC134 D - Preparing Boxes

解法


b[N]からb[1]の順にボールを入れていくか決定していく。
b[i]は、b[i以上N以下のiの倍数]の総和を2で割った余りがa[i]と等しく無い場合1、等しい場合0とすることで求まる。

ソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    int N;
    cin >> N;
    vector<int> a(N+1);
    for(int i(1);i<N+1;++i) cin >> a[i];
    int b_sum;
    vector<int> b(N+1,0);
    for(int i(N);i>=1;--i){
        b_sum = 0;
        for(int j(i);j<=N;j+=i){
            b_sum += b[j];
        }
        if(b_sum%2 != a[i]){
            b[i] = 1;
        }
    }
    int M(0);
    for(int i(1);i<N+1;++i){
        if(b[i] == 1) M++;
    }
    cout << M << endl;
    if(M > 0){
        for(int i(1);i<N+1;++i){
            if(b[i]) cout << i << ' ';
        }
    }
    return 0;
}

AtCoder AGC035 B - Even Degrees

問題


AtCoder AGC035 B - Even Degrees

解法


Mが偶数であれば、全ノードにおいてエッジの起点の数が偶数となるような有向グラフを構成できる。
その一例の求め方を以下に示す。
まず、深さ優先で隣接するノードを探索していき、passed_order[node番号]に訪れた順を記録していく。 訪れたノードが直前に訪れたノード(親)でなく、かつ、以前に訪れたノードであれば、 現在のノードを起点とするエッジでその再訪ノードと結び、edge_origin[node]をインクリメントする。 これを繰り返して全てのノードを訪れたときには、与えられたグラフは有向エッジと無向全域木で構成される。 全域木について、葉から順に起点の数が偶数なるようにエッジの向きを決めていくことで題意のグラフの一例が得られる。

ソースコード

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> G;
vector<int> edge_origin, passed_order;
int order(0);

void solve(int node, int parent){
    if(passed_order[node]) return ;
    passed_order[node] = ++order;
    for(int neighbor : G[node]){
        if(neighbor == parent) continue;
        if(passed_order[neighbor]){
            if(passed_order[node] > passed_order[neighbor]){
                edge_origin[node]++;
                cout<<node<<" "<<neighbor<<endl;
            }
        } else {
            solve(neighbor , node);
        }
    }
    if(parent == -1) return;
    if(edge_origin[node]%2){
        cout << node << " " << parent << endl;
        edge_origin[node]++;
    } else {
        cout<<parent<<" "<<node<<endl;
        edge_origin[parent]++;
    }
}
int main(){    
    int N, M;
    cin >> N >> M;
    if(M%2 != 0){
        cout<< -1 <<endl;
        return 0;
    }
    G.resize(N+1);
    edge_origin.resize(N+1);
    passed_order.resize(N+1);
    int a, b;
    for(int i(0); i < M; ++i){
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    solve(1,-1);
    return 0;
}

AtCoder AGC 035 A - XOR Circle

問題


AtCoder AGC035 A - XOR Circle

解法


例えば、N=4の場合
a_1 \oplus a_3=a_2
a_2 \oplus a_4=a_3
a_3 \oplus a_1=a_4
a_4 \oplus a_2=a_1
が成立するとき、条件を満たす。
4つの式を掛け合わせて整理すると
(a_1 \oplus a_2 \oplus a_3 \oplus a_4) \oplus (a_1 \oplus a_2 \oplus a_3 \oplus a_4) = a_1 \oplus a_2 \oplus a_3 \oplus a_4
これを満たすのは、a_1 \oplus a_2 \oplus a_3 \oplus a_4=0の場合のみである。
このように、条件を満たすのはN個のa[i]のxorを掛け合わせた値が0の場合であることを利用する。

ソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    int N;
    cin >> N;
    vector<ll> a(N);
    for(int i(0);i<N;++i) cin >> a[i];
    ll xor_product(a[0]);
    for(int i(1);i<N;++i) xor_product = xor_product ^ a[i];
    if(xor_product == 0) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

AtCoder ABC133 E - Virus Tree 2

問題


AtCoder ABC133 E - Virus Tree 2

解法


頂点0からDFSの要領で色を塗っていくことで塗り分け方の総数が得られる。

ソースコード


解答を参考に実装。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll MOD = pow(10,9) + 7;

ll dfs(int K, const vector<vector<int>>&G, int now, int from){
    int available_colors_num;
    if(from == -1){
        available_colors_num = K-1;
    }else{
        available_colors_num = K-2;
    }
    if(K<G[now].size()){
        return 0;
    }else{
        ll case_num = 1;
        for( auto e : G[now]){
            if(e == from) continue;
            case_num *= available_colors_num;
            available_colors_num--;
            case_num %= MOD;
        }
        for(auto e : G[now]){
            if(e==from)continue;
            case_num *= dfs(K,G,e,now);
            case_num %= MOD;
        }
        return case_num;
    }

}

int main(){
    int N,K;
    cin >> N >> K;
    vector<vector<int>> G(N);
    for(int i(0);i<N-1;++i){
        int a,b;
        cin >> a >> b;
        a--;b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    ll ans = K*dfs(K,G,0,-1);
    ans %= MOD;
    cout << ans << endl;
    return 0;
}