AtCoder Regular Contest 106 に参加しました。

成績

f:id:gyouzasushi:20201025033527p:plain
f:id:gyouzasushi:20201025033941p:plain

A - 106

問題概要： $3^A+5^B=N$ を満たす正の整数の組 $(A,B)$ を一組求めよ（存在しなければ $-1$ を出力）。
制約： $N \leq 10^{18}$
こういうやつは変に数学せずに全探索した方がいいって歴史の教科書に書いてました。オーバーフローに気を使いたくないので雑に Python でやる。

f:id:gyouzasushi:20201025015743p:plain — ゼロは正の整数ではありません（一敗）

コードを表示

n = int(input())
for a in range(1,40):
    for b in range(1,30):
        if 3 ** a + 5 ** b == n:
            print(a, b)
            exit()
print(-1)

B - Values

問題概要： $N$ 頂点 $M$ 辺の単純無向グラフがあり、頂点 $i$ には値 $a_i$ が書かれている。次の操作を適切に行うことで、操作後の各頂点の値を $b_1, \cdots ,b_N$ にできるか？

（操作）辺を一つ選ぶ。選んだ辺が頂点 $x$ と頂点 $y$ を結んでいるとき、次のいずれかを行う。

・値 $a_x$ を $-1$ し、値 $a_y$ を $+1$ する。

・値 $a_x$ を $+1$ し、値 $a_y$ を $-1$ する。

制約： $N,M \leq 2 \times 10^5, -10^9 \leq a_i,b_i \leq 10^9$

どちらの操作を選んでも $\sum a$ は不変なので、「連結成分ごとに $\sum a = \sum b$ 」が必要。そしてこれは実は十分条件にもなってると思う。違ったらそのときにまた考えればいいかな……の気持ちで提出してもうた。Aでいきなりペナルティつけて焦ってたね。ACしたのでヨシ！

コードを表示

#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;
using ll = long long;
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;
    vector<ll> a(n), b(n);
    rep(i, n) cin >> a[i];
    rep(i, n) cin >> b[i];
    UnionFind uf(n);
    while (m--) {
        int c, d;
        cin >> c >> d;
        uf.unite(--c, --d);
    }
    vector<ll> aa(n), bb(n);
    rep(i, n) {
        aa[uf.root(i)] += a[i];
        bb[uf.root(i)] += b[i];
    }
    cout << (aa == bb ? "Yes\n" : "No\n");
}

C - Solutions

問題 & 制約：（リンク）

$M$ の符号で場合分けしたい気持ちになる。

( $M \lt 0$ のとき) 高橋くんのアルゴリズムは正解なので、青木くんの方が大きい値を出力することはないです。 $-1$ 。

( $M=0$ のとき) $[1,2], [3,4],\cdots, [2N-1,2N]$ みたいにすれば二人とも $N$ を出力して平和。

( $M \gt 0$ のとき) $[1,\infty]$ みたいな区間を作ることで、青木くんの値を $1$ に抑えることができる。あとは高橋くんが丁度 $M+1$ 個の区間を選ぶことになるように調節（できなければ $-1$ ）。

コードを表示

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e8;
int main() {
    int n, m;
    cin >> n >> m;
    if (m < 0) {
        cout << -1 << '\n';
        return 0;
    }
    if (m == 0) {
        for (int i = 1; i <= n; i++) {
            cout << 2 * i << ' ' << 2 * i + 1 << '\n';
        }
        return 0;
    }
    if (m > 0) {
        if (m >= n - 1) {
            cout << -1 << '\n';
            return 0;
        }
        for (int l = 1; l <= n - m - 1; l++) {
            cout << l << ' ' << l + INF << '\n';
        }
        for (int i = 1; i <= m + 1; i++) {
            int l = n - m - 1 + 2 * i;
            int r = l + 1;
            cout << l << ' ' << r << '\n';
        }
        return 0;
    }
}

D - Powers

問題概要：整数列 $A=(A_1,A_2,\cdots,A_N)$ と整数 $K$ が与えられる。 $1\leq X \leq K$ を満たす整数 $X$ それぞれについて、 $\displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} (A_L+A_R)^X$ の値を $\mod 998244353$ で求めよ。

制約： $2\leq N \leq 2\times 10^5, 1\leq K\leq 300, 1\leq A_i\leq 10^8$

$1\leq i \lt j \leq N$ の和をとるときには、まず $1\leq i , j\leq N$ について求めてから $i=j$ を引いて $2$ で割る、って歴史の教科書に書いてました。本問でいうと、求めるべきは $\displaystyle \sum_{i=1}^{N} \sum_{j=1}^{N} (A_i+A_j)^X$ と $\displaystyle \sum_{i}^{N} (A_i+A_i)^X$ 。後者はすぐ求まりそうなので前者を考えよう。ゴリゴリ展開していく。 \begin{eqnarray}　\displaystyle \sum_{i=1}^{N} \sum_{j=1}^{N} (A_i+A_j)^X &=& \sum_{i=1}^{N} (\sum_{j=1}^{N} \sum_{k=0}^{X} ({}_{N} C_{k} {A_j}^{X-k} \times {A_i}^k)) \\ &=& \sum_{i=1}^{N} (\sum_{k=0}^{X} ({}_{N} C_{k} \sum_{j=1}^{N} {A_j}^{X-k}) \times {A_i}^k) \\ &=&\sum_{k=0}^{X} ({}_{N} C_{k} \times (\sum_{j=1}^{N} {A_j}^{X-k}) \times(\sum_{i=1}^{N} {A_i}^k)) \\ \end{eqnarray} $\sum A^k=f(k)$ とすると \begin{eqnarray}　\displaystyle \sum_{i=1}^{N} \sum_{j=1}^{N} (A_i+A_j)^X &=&\sum_{k=0}^{X} ({}_{N} C_{k} \times f(X-k) \times f(k)) \\ \end{eqnarray} で、やっと計算できそうな見た目になってくれた😭 式変形で疲れ切ってもうて実装かなり時間かかった…… f:id:gyouzasushi:20201025032054p:plain

残り一分とちょっとのところでAC。めっちゃ気持ちいい、これだからやめられないんですよね。安心しすぎて変な呼吸はいった。

コードを表示

#include <bits/stdc++.h>
#include <atcoder/modint>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using mint = atcoder::modint998244353;
int main() {
    const int N = 200200;
    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, k;
    cin >> n >> k;
    vector<mint> a(n);
    vector<mint> f(k + 1);
    f[0] = mint(n);
    rep(i, n) {
        int x;
        cin >> x;
        a[i] = mint(x);
        f[1] += a[i];
    }

    auto b = a;
    for (int i = 2; i <= k; i++) {
        rep(j, n) {
            f[i] += b[j] * a[j];
            b[j] *= a[j];
        }
    }
    for (int x = 1; x <= k; x++) {
        mint ans = 0;
        for (int i = 0; i <= x; i++) {
            ans += comb(x, i) * f[i] * f[x - i];
        }
        ans -= mint(2).pow(x) * f[x];
        ans /= 2;
        cout << ans.val() << '\n';
    }
}

E - Medals, F - Figures

todo

ところで

今年も残すところあと二ヶ月！w GPAはなんか3ぐらいしかないです。オワオワリ

gyouzasushi’s diary

競プロとか

AtCoder Regular Contest 106 に参加しました。

成績

A - 106

B - Values

C - Solutions

D - Powers

E - Medals, F - Figures

ところで