AtCoder Regular Contest 106 ARC 106 参加記

A - 106

問題へのリンク

解説

オーバーフローしそうなのでpythonで。

実装

N = int(input())

for a in range(60):
    if a == 0:
        continue
    rem = N - pow(3, a)
    if rem < 0:
        break
    for b in range(60):
        if b == 0:
            continue
        if rem == pow(5, b):
            print(a, b)
            exit()
print(-1)

B - Values

問題へのリンク

解説

連結成分の和が同じなら達成できます。dfsとかunion findでも実装できます。ac-libraryのdsuはgroupsというのがあるらしいのでそれが一番楽そうです。

実装

vvec<int> G;
vector<ll> a, b;
vector<ll> used;
void dfs(int cur, int pre, vector<int>&v){
    used[cur] = true;
    v.push_back(cur);
    for(auto nxt: G[cur]){
        if(used[nxt])continue;
        dfs(nxt, cur, v);
    }
}
int main() {
    int N, M;
    cin >> N >> M;
    G.resize(N);
    a.resize(N);
    b.resize(N);
    used.resize(N, false);
    cin >> a >> b;
    rep(i,M){
        int c, d;
        cin >> c >> d;
        c--, d--;
        G[c].push_back(d);
        G[d].push_back(c);
    }
    rep(i,N){
        if(used[i])continue;
        vector<int> v;
        dfs(i, -1, v);
        dump(v);
        ll suma = 0;
        ll sumb = 0;
        for(auto x: v)suma += a[x];
        for(auto x: v)sumb += b[x];
        dump(suma, sumb);
        if(suma != sumb){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}

C - Solutions

問題へのリンク

解説

まず、高橋君の方は区間スケジューリング問題の最適解なので、青木君が追い越すことはできません。よってはできません。また、 or の場合もできません。は、の場合ですが、はあり得ないです。一個は取れます。また、は、かの場合ですが、前者は高橋君が全て取れるときは青木君も全て取れますし、後者は同様にはあり得ないことから、無理です。

以上の考察により、の場合のみを考えればよいです。この場合、達成可能です。 まず、クソでか区間を置くことで、青木君の結果をに固定します。このとき、高橋君の結果がになればいいので、個の区間を取れるように置きます。ここで残った個の区間は、高橋君にも青木君にも取れないように置きます。具体的には以下のようにです。

構築が完了しました。

実装

int main() {
    int N, M;
    cin >> N >> M;
    if(N == 1 && M == 0){
        cout << 1 << " " << 2 << endl;
        return 0;
    }
    if(M == N || M == N-1 || M < 0){
        cout << -1 << endl;
        return 0;
    }
    int rem = N - M - 1;
    for(int i = 1; i <= M+1; i++){
        cout << 2 * i+rem << " " << 2 * i+rem + 1 << endl;
    }
    for(int i = 1; i <= N-M-1; i++){
        cout << i << " " << INF - i << endl;
    }
}