Yosupo Wettbewerb 解説

総評

お疲れ様でした。 問題タイトルが全部英語なのはデレマスの影響です

問題解説

C,D,Eの想定解は長いので後ろにまとめます

A問題 Trouble Busters

(面倒)100なA問題もいいかなって思った。

next_permutationを使うのが多分一番楽です。 一人ぐらい六重ループで通す人いると思ってました。

時間制限はかなり適当に設定したのですが、pythonだとTLEが厳しかったみたいで申し訳ないです…

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;

int main() {
    int p[9];
    for (int i = 0; i < 9; i++) {
        cin >> p[i];
    }
    sort(p, p+9);
    int res = -1;
    do {
        int r = 1000;
        for (int i = 0; i < 9; i+=3) {
            r = min(r, (p[i]+p[i+1]+p[i+2])/3);
        }
        res = max(res, r);
    } while (next_permutation(p, p+9));
    cout << res << endl;
}

B問題 Muscle Yosupo Returns

ユークリッドの互除法は最高。

部分点解法

PythonやJava等の、多倍長整数が使用できる言語を使うと普通に求められます。

from fractions import gcd
a, x, y = map(int, input().split())
print(gcd(a**x - 1, a**y - 1) % (10**9 + 7))
満点解法

多項式のままユークリッドの互除法をすると x>yとして (ax - 1) - ax-y(ay - 1) = ax-y - 1 から、 (ax - 1) % (ay - 1) = ax%y - 1 になります すると gcd(ax - 1, ay - 1) = agcd(x, y) - 1 が成立します

真面目な証明

自然数x, yと関数g(x)について

  • f(x, y) = f(y, x)
  • f(x, 0) = g(x)
  • f(x, y) = f(x, y-x) (x < y)

を満たす関数fは一意に定まり、f(x, y) = g(gcd(x, y))に他ならない

これを用いると

g(a, x, y) = gcd(ax - 1, ay - 1)

と置いたときに

  • g(a, x, y) = g(a, y, x)
  • g(a, x, 0) = ax - 1
  • g(a, x, y) = g(a, x, y-x) (x < y)

を示せば

g(a, x, y) = agcd(x, y) - 1

となる

1つ目と2つ目は自明、3つ目は上で示した

数学科の人はマサカリのほう宜しくお願いします

#include <iostream>

using namespace std;
typedef long long ll;

ll gcd(ll a, ll b) {
    if (b==0) return a;
    return gcd(b, a%b);
}

ll pow_mod(ll x, ll n, ll mod) {
    ll r = 1;
    while (n) {
        if (n & 1) r = (r * x) % mod;
        x = (x * x) % mod;
        n >>= 1;
    }
    return r;
}

const ll MD = 1e9+7;

int main() {
    ll a, x, y;
    cin >> a >> x >> y;
    cout << (pow_mod(a, gcd(x, y), MD) + MD - 1) % MD << endl;
}

C問題 Palindrome Relinquish

あんまり面白くない問題ですね…

まず、K=1,3,7,15,31,63の場合しか超回文は存在しないです。

そして長さ63の超回文ですら106個しか存在しません。

なので、超回文すべてについて文字列の中に存在するかを判定すればいいです。

あと、超回文は完全二分木を潰した感じの形になってます

D問題 Japanese Origami No.1

このセットの中では一番難しいと思います

平面走査を考えると、(x, y)平面に

  • 点を追加する
  • 点を削除する
  • 点を左上から右下への階段状にしたとき、幾つの点が含まれるか調べる

という3種類のクエリに答える問題になります

どっちかの軸(解説ではx軸)についてSegTreeを構築して、 それぞれの区間についてその区間に対応する点を階段状にしたものを持つSegTreeを考えます。

このSegTreeの区間のmergeは、左側の点を途中まで+右側の点全てとなります。 点をvectorやsetで持つと、mergeにO(区間の長さ)かかるので、追加削除クエリがO(N)かかります。 (実は永続平衡二分木を使用するとO(logN)でmergeが出来て、合計でクエリごとにO(log2N)で処理できるようになります。)

ここで階段状にしたものの点をすべて持たず、 階段状にした点の(最大のy座標, 点の個数, 左側の区間の点が何個使われてるか)だけを持ってもsegtreeは構築できます。

これでクエリごとにO(log2N)で処理できるようになって間に合います

E問題 Oh, Vertexes & Edges!

無向グラフでデータ構造をマージする一般的なテクって結構珍しいんじゃないでしょうか テストケースはできる限り早くなんとかします

部分点解法

適当に頑張ってください

満点解法

黒い頂点をどんどんmergeしていくことを考えます。 黒い頂点をどんどんmergeするときに一緒に辺もmergeして、同じ場所に向かって2本以上辺が生えたらその頂点も黒く塗るようにすればOKです データ構造をマージする一般的なテクにより計算量がO(MlogMlogN)になります

C問題想定解

#include <iostream>

using namespace std;
typedef long long ll;

const int MN = 1010;
int n, k;
int d[MN];
int nd[MN][10];
int buf[100];
bool solve() {
    int m = __builtin_ctz(k+1);
    if (1<<m != k+1) return false;
    int times = 1;
    for (int i = 0; i < m; i++) {
        times *= 10;
    }
    for (int i = 0; i < times; i++) {
        int t = i;
        for (int j = 0; j < m; j++) {
            buf[j] = t % 10;
            t /= 10;
        }
        int u = 0;
        for (int j = 1; j <= k; j++) {
            u = nd[u][buf[__builtin_ctz(j)]];
            if (n < u) break;
        }
        if (u <= n) {
            return true;
        }
    }
    return false;
}

int main() {
    cin >> n >> k;
    string s;
    cin >> s;
    for (int i = 0; i < n; i++) {
        d[i] = s[i] - '0';
    }
    for (int i = 0; i < MN; i++) {
        fill_n(nd[i], 10, MN);
    }
    for (int i = n-1; i >= 0; i--) {
        for (int j = 0; j < 10; j++) {
            nd[i][j] = nd[i+1][j];
        }
        nd[i][d[i]] = i+1;
    }
    if (solve()) {
        cout << "Found" << endl;
    } else {
        cout << "Not Found" << endl;
    }
}

D問題想定解

#include <iostream>
#include <cassert>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;
typedef long long ll;

template<int S>
struct SegTree {
    static const int N = 1<<S;
    struct Node {
        int ma, num, lnum;
    } seg[2*N];
    SegTree() {
        for (int i = 1; i < 2*N; i++) {
            seg[i] = {-1, 0, 0};
        }
    }
    void set(int k, int x) {
        k += N;
        if (x == -1) {
            seg[k] = {-1, 0, 0};
        } else {
            seg[k] = {x, 1, 0};
        }
        while (k > 1) {
            k /= 2;
            update(k);
        }
    }
    //lower_bound(seg[k], x)のイメージ
    int find(int k, int x) {
        if (k >= N) {
            if (x >= seg[k].ma) return 0;
            return 1;
        }
        if (x > seg[k*2+1].ma) {
            return find(k*2, x);
        } else {
            return seg[k].lnum + find(k*2+1, x);
        }
    }
    void update(int k) {
        assert(1 <= k && k < N);
        seg[k].ma = max(seg[k*2].ma, seg[k*2+1].ma);
        seg[k].lnum = find(k*2, seg[k*2+1].ma);
        seg[k].num = seg[k].lnum + seg[k*2+1].num;
    }
};

typedef pair<int, int> P;
const int MN = 100100;
const int MM = 200100;

SegTree<17> st;
int h[MN], res[MM];
vector<P> e;
void calc() {
    sort(e.begin(), e.end());
    for (int i = 0; i < (int)e.size(); i++) {
        int t = e[i].second;
        if (t < MN) {
            //insert
            st.set(h[t], t);
        } else if (t < 2*MN) {
            //erase
            st.set(h[t-MN], -1);
        } else {
            //count
            res[t-2*MN] = st.seg[1].num;
        }
    }
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int l, r;
        scanf("%d %d %d", &l, &r, h+i);
        e.push_back(P(l, i));
        e.push_back(P(r, i+MN));
    }
    int m;
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        int p;
        scanf("%d", &p);
        e.push_back(P(p, i+2*MN));
    }
    calc();
    for (int i = 0; i < m; i++) {
        printf("%d\n", res[i]);
    }
    return 0;
}

E問題想定解

#include <iostream>
#include <queue>
#include <cassert>
#include <set>
#include <unordered_set>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;

queue<int> q;

template <int N>
struct UnionFind {
    int ig[N];
    vector<int> gi[N];

    set<int> g[N];
    void init(int n = N) {
        for (int i = 0; i < n; ++i) {
            ig[i] = i;
            gi[i] = {i};
        }
    }
 
    void merge(int a, int b) {
        if (same(a, b)) return;
        int x = ig[a], y = ig[b];
        if (gi[x].size() < gi[y].size()) swap(x, y);
        for (int j: gi[y]) {
            ig[j] = x;
        }
        gi[x].insert(gi[x].end(), gi[y].begin(), gi[y].end());
        gi[y].clear();
        
        if (g[x].size() < g[y].size()) swap(g[x], g[y]);
        for (int d: g[y]) {
            if (g[x].count(d)) {
                q.push(d);
            }
        }
        g[x].insert(g[y].begin(), g[y].end());
    }
 
    bool same(int a, int b) {
        return ig[a] == ig[b];
    }
};

const int MN = 100100;
UnionFind<MN> uf;
bool c[MN]; //color

vector<int> g[MN];
int main() {
    int n;
    scanf("%d\n", &n);
    uf.init();

    char cs[MN];
    scanf("%s", cs);

    for (int i = 0; i < n; i++) {
        if (cs[i] == 'B') {
            q.push(i);
        }
    }
    int m;
    scanf("%d\n", &m);
    for (int i = 0; i < m; i++) {
        int x, y;
        scanf("%d %d\n", &x, &y); x--; y--;
        g[x].push_back(y);
        g[y].push_back(x);
        uf.g[x].insert(y);
        uf.g[y].insert(x);
    }

    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (c[u]) continue;
        c[u] = true;
        for (int d: g[u]) {
            if (!c[d]) continue;
            uf.merge(u, d);
        }
    }
    string res;
    for (int i = 0; i < n; i++) {
        res += (c[i] ? 'B' : 'W');
    }
    printf("%s\n", res.c_str());
    return 0;
}

元ネタ

Trouble Busters(BiBi) 筋肉よすぽ(KIC #003) Pluto Relinquish(DDR) Japanese Ninja No.1(デッドボールP) Oh, Love & Peace!(µ's)