AtCoder Regular Contest 108 に参加しました

黄パフォ出た回、饒舌がち　これあります
atcoder.jp

成績

300位ぴったりやん！飛び賞待ってます。

A - Sum and Product

問題概要：整数 が与えられる。 を満たすような正の整数の組 は存在するか？
制約：

うわ知ってるこれ！解と係数の関係やろ！で五分使ってもうた。たいへんもったいない……。 は の約数なので、適当に調べれば十分。

コードを表示

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ll s, p;
    cin >> s >> p;
    vector<ll> v;
    for (ll d = 1; d * d <= p; d++) {
        if (p % d) continue;
        v.push_back(d);
        v.push_back(p / d);
    }
    sort(v.begin(), v.end());
    for (ll n : v) {
        ll m = s - n;
        if (*lower_bound(v.begin(), v.end(), m) == m) {
            cout << "Yes\n";
            return 0;
        }
    }
    cout << "No\n";
}

B - Abbreviate Fox

問題概要：長さ の文字列 が与えられる。「 から " fox " という連続部分文字列をひとつ選んで取り除き、その前後の部分を連結する」という操作を何度でも行えるとき、操作後の の長さは最小でいくつか？
制約：

" fox " なのが難しい。" fox " を " (o) "に置き換えて括弧列っぽく考えると、stack でシミュレーションにしか見えなくなります。

コードを表示

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define sz(x) int(x.size())
using namespace std;
int main() {
    int n;
    string s;
    cin >> n >> s;
    string t;
    for (char c : s) {
        t += c;
        if (sz(t) >= 3 && t.substr(sz(t) - 3, 3) == "fox") {
            rep(_, 3) t.pop_back();
        }
    }
    cout << sz(t) << '\n';
}

C - Keep Graph Connected

問題概要： 頂点 辺からなる、自己ループのない連結グラフが与えられる。グラフのそれぞれの辺には、 以上 以下の整数で表されるラベルがついている。
グラフのそれぞれの頂点に 以上 以下の整数を書き込んだのち、以下の条件を満たさない辺をすべて取り除く。
（条件）辺の両端の頂点に書き込まれたふたつの整数のうち、いずれか一方のみが辺に付けられたラベルと等しい。
辺を取り除いたあとのグラフが連結のままであるような頂点への整数の書き込み方が存在するか判定せよ（あれば一例を出力）。
制約：

こういう問題は

• サンプルに No がないので必ず構築できるはず、という勘がはたらく（AtCoder あるある）。
• 適当な全域木で考えたら嬉しいがち、と歴史の教科書に書いてある。

以上を踏まえて、「どのような木に対しても問題文の条件を満たすように整数を書き込むアルゴリズムがあるはず、なのでそれを考えよう」みたいな方針で考察を進めた。木だったら話が早い。一回 WA になって泣きそうになったけど、すぐミスに気がついて AC できた。えらすぎぶっ壊れ

コードを表示

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
struct UnionFind {
    vector<int> data;
    UnionFind(int size) : data(size, -1) {
    }
    int root(int x) {
        return (data[x] < 0) ? x : data[x] = root(data[x]);
    }
    bool unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x != y) {
            if (data[y] < data[x]) swap(x, y);
            data[x] += data[y];
            data[y] = x;
        }
        return x != y;
    }
    bool find(int x, int y) {
        return root(x) == root(y);
    }
    int size(int x) {
        return -data[root(x)];
    }
};
int main() {
    int n, m;
    cin >> n >> m;
    using P = pair<int, int>;
    map<P, int> cs;
    vector<vector<int>> g(n);
    UnionFind uf(n);
    vector<bool> used(n);
    rep(i, m) {
        int u, v, c;
        cin >> u >> v >> c;
        u--, v--, c--;
        if (uf.unite(u, v)) {
            cs[P(u, v)] = c;
            cs[P(v, u)] = c;
            g[u].push_back(v);
            g[v].push_back(u);
            used[c] = 1;
        }
    }
    int x = -1;
    rep(i, n) if (!used[i]) x = i;
    vector<int> ans(n);
    ans[0] = x;
    auto dfs = [&](auto dfs, int pos, int pre) -> void {
        for (int nxt : g[pos]) {
            if (nxt == pre) continue;
            if (~pre && cs[P(pos, pre)] == cs[P(pos, nxt)] && ans[pos] != x)
                ans[nxt] = x;
            else
                ans[nxt] = cs[P(pos, nxt)];
            dfs(dfs, nxt, pos);
        }
        return;
    };
    dfs(dfs, 0, -1);
    rep(i, n) cout << ans[i] + 1 << '\n';
}

D - AB

問題概要：整数 と四つの文字 が与えられる（四つの文字はそれぞれ 'A' か 'B' のいずれか）。文字列 " AB " に対して、以下の操作を任意の順序で行う。

• 'A' , 'A' なる を選び、 の 文字目と 文字目の間に を挿入する。
• 'A' , 'B' なる を選び（中略） を挿入する。
• 'B' , 'A' なる（中略） を挿入する。
• 'B' , 'B' （中略） を挿入する。

の長さが になるまで操作を行ったあとの としてありうる文字列の個数を（mod で）求めよ。
制約：

何をどうしていいか全くみえないまま二十分ぐらい経っちゃってかなり苦しんだ。でも「数え上げる前に判定問題を解く」の典型を思い出してからはどんどん考察が進んだ！！！！！！えらい。
でも出てきた答えがどう考えても の制約に見合ってなくて、ここでもうひと苦しみした。まあもう時間もないし、とりあえず書いてとりあえず出してみるか！w の精神が功を奏したね。どうせ僕の提出なんて…… → あ〜れ〜れ〜〜？　を地で行ってもうた。 なんか場合分けすれば解けます。

コードを表示

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
using mint = atcoder::modint1000000007;
int main() {
    const int N = 400400;
    vector<mint> fact(N + 1), ifact(N + 1);
    fact[0] = 1;
    for (int i = 1; i <= N; i++) {
        fact[i] = fact[i - 1] * i;
    }
    ifact[N] = fact[N].inv();
    for (int i = N; i >= 1; i--) {
        ifact[i - 1] = ifact[i] * i;
    }
    auto comb = [&](int n, int r) {
        if (n < r || r < 0) return mint(0);
        return fact[n] * ifact[r] * ifact[n - r];
    };

    int n;
    cin >> n;
    char caa, cab, cba, cbb;
    cin >> caa >> cab >> cba >> cbb;
    if (n == 2) {
        cout << 1 << '\n';
        return 0;
    }
    if (cab == 'A') {
        if (caa == 'A') {
            cout << 1 << '\n';
            return 0;
        }
        if (cba == 'B') {
            cout << mint(2).pow(n - 3).val() << '\n';
            return 0;
        }
        mint ans = 0;
        for (int i = 2; i <= n - 1; i++) {
            ans += comb(i - 1, n - i - 1);
        }
        cout << ans.val() << '\n';
    } else {
        if (cbb == 'B') {
            cout << 1 << '\n';
            return 0;
        }
        if (cba == 'A') {
            cout << mint(2).pow(n - 3).val() << '\n';
            return 0;
        }
        mint ans = 0;
        for (int i = 2; i <= n - 1; i++) {
            ans += comb(i - 1, n - i - 1);
        }
        cout << ans.val() << '\n';
    }
}

E,F

todo

おしまい

次回 2064 perf で rating 1900 のるらしい。でもこういうこと考えてると絶対失敗するねんな。人生そういうとこあるわ。無欲でいこう。