素人日記

競プロの精進記録その他。

筑駒入試コン2020 を解いた

2020/2/2に、有志コンである「筑駒入試コン2020」があったので参加しました。

筑駒中の中学2年生5人だけでwriter, testerをやっていたそうで、天才集団すぎて恐ろしいです...

問題は12問あり、どれも良問ばかりと評判でした(すごい)

有志コンなので流れてしまう可能性が高く、それは非常にもったいないと思ったのでメモを残すことにしました。 メモはあくまで自分用なのでかなり雑です...(解説は解説スライドの方が丁寧なので...)

問題・解説

問題: www.hackerrank.com 解説:

drive.google.com

解法メモ

4月 入学式

5月 班分け

UnionFind。

まず$i$と$A_i$を同じグループにして、その後$i$と$B_i$が同じグループに入っていないか調べる

struct UnionFind {
    vector<int> par;

    UnionFind(int n) : par(n, -1) {}
    void init(int n) { par.assign(n, -1); }

    int root(int x) {
        if(par[x] < 0)
            return x;
        else
            return par[x] = root(par[x]);
    }

    bool issame(int x, int y) { return root(x) == root(y); }

    bool merge(int x, int y) {
        x = root(x);
        y = root(y);
        if(x == y)
            return false;
        if(par[x] > par[y])
            swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }

    int size(int x) { return -par[root(x)]; }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    UnionFind uf(n);
    vector<int> a(n), b(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
        uf.merge(i, a[i]);
    }
    for(int i = 0; i < n; i++) {
        cin >> b[i];
        b[i]--;
        if(uf.issame(i, b[i])) {
            cout << "Impossible" << endl;
            return 0;
        }
    }

    map<int, vector<int>> res;
    for(int i = 0; i < n; i++) {
        res[uf.root(i)].emplace_back(i);
    }
    cout << res.size() << endl;
    for(auto p : res) {
        cout << p.second.size() << " ";
        for(auto b : p.second) {
            cout << b + 1 << " ";
        }
        cout << endl;
    }
}

6月 音楽祭

Kadane's Algorithm そのままです。

ark4rk.hatenablog.com

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int ans = -INF;
    int sum = 0;
    for(int i = 0; i < n; i++) {
        sum = max(sum + a[i], a[i]);
        chmax(ans, sum);
    }
    cout << ans << endl;
}

7月 夏休み

「乗り放題」をなんとかする問題。もちろんそのまま辺をバカスカ張るわけにはいかないので次のようにする

元のグラフに、 $$ 会社i\rightarrow{会社に属する駅x} $$ の向きにコスト$P_i$の辺を張り、2回料金を払わないように逆向きにコスト0の辺を張る。あとはダイクストラで解けます。 雰囲気がこれこれに似てる気がするなぁとずっと思っていたので本番で解きたかった〜...

using P = pair<ll, ll>;

struct edge {
    ll to;
    ll cost;
};

ll n, m, k;
vector<vector<edge>> g(300010);
vector<ll> p(200010);

ll dijkstra() {
    vector<ll> d(n + k, LLINF);
    priority_queue<P, vector<P>, greater<P>> que;
    que.push(P(0, 0));
    while(que.size()) {
        auto now = que.top();
        que.pop();
        ll nv = now.second;
        ll nd = now.first;
        if(d[nv] < nd) {
            continue;
        }
        for(auto next : g[nv]) {
            if(d[next.to] > nd + next.cost) {
                d[next.to] = nd + next.cost;
                que.push(P(d[next.to], next.to));
            }
        }
    }
    return d[n - 1];
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> m >> k;
    for(ll i = 0; i < k; i++) {
        cin >> p[i];
    }
    for(ll i = 0; i < m; i++) {
        ll a, b, d;
        ll c;
        cin >> a >> b >> c >> d;
        a--;
        b--;
        d--;
        g[a].emplace_back(edge{b, c});
        g[b].emplace_back(edge{a, c});
        g[a].emplace_back(edge{n + d, p[d]});
        g[b].emplace_back(edge{n + d, p[d]});
        g[n + d].emplace_back(edge{a, 0});
        g[n + d].emplace_back(edge{b, 0});
    }
    ll ans = dijkstra();
    cout << (ans == LLINF ? -1 : ans) << endl;
}

8月 校内模死

$dp[i][j]:=\space{i}$番目まで見たときに、合計得点が$j$となるような問題の解き方の通り数

を先に求めて、後は各クエリに答えてあげれば良い

vector<vector<ll>> dp(510, vector<ll>(5050, 0));

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    dp[0][0] = 1;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < 5050; j++) {
            (dp[i + 1][j] += dp[i][j]) %= MOD;
            if(j + a[i] < 5050) {
                (dp[i + 1][j + a[i]] += dp[i][j]) %= MOD;
            }
        }
    }
    while(q--) {
        int x, y;
        cin >> x >> y;
        ll ans = 0;
        for(int i = x; i < y; i++) {
            (ans += dp[n][i]) %= MOD;
        }
        cout << ans << endl;
    }
}

9月 体育祭

制約が$N\leq{40}$で半分全列挙をして下さいと言っています

解法は合ってたが、setでイテレータを回したらメモリアクセスの関係で定数倍が重くてTLEして本番で通せなかった...(vectorにすると通ります)

setでイテレータを回すときは注意するべきだなぁと教訓を得ました...

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<ll> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    ll x, y;
    cin >> x >> y;
    vector<ll> v1, v2;
    for(int bit = 0; bit < (1 << (n / 2)); bit++) {
        ll sum = 0;
        for(int i = 0; i < (n / 2); i++) {
            if(bit & (1 << i)) {
                sum += a[i];
            }
        }
        v1.emplace_back(sum);
    }
    for(int bit = 0; bit < (1 << (n - n / 2)); bit++) {
        ll sum = 0;
        for(int i = 0; i < (n - n / 2); i++) {
            if(bit & (1 << i)) {
                sum += a[i + n / 2];
            }
        }
        v2.emplace_back(sum);
    }
    sort(ALL(v1));
    sort(ALL(v2));
    v1.erase(unique(ALL(v1)), v1.end());
    v2.erase(unique(ALL(v2)), v2.end());
    ll sum = accumulate(ALL(a), 0LL);
    if(sum <= x) {
        cout << sum << endl;
        return 0;
    }
    ll rec = 0;
    for(auto p : v1) {
        if(p > x) {
            continue;
        }
        auto it = lower_bound(ALL(v2), x - p);
        if(it == v2.end()) {
            it--;
        }
        if(*it > x - p && it != v2.begin()) {
            it--;
        }
        chmax(rec, p + *it);
    }
    cout << y + sum - rec << endl;
}

10月 稲の収穫

11月 文化祭

12月 クリスマス

1月 ロードレース

ラソンなので略。本当に気が向いたらやります(ごめんなさい)

2月 弁論大会

3月 卒業式

浪人生が$i$人選ばれるとすると、求める式は、

$$ \sum_{i=0}^{min(M,K)}{i}\cdot\binom{K}{i}\cdot\binom{N-K}{M-i} $$

です。今回は$N$の制約が大きいので、階乗の前計算をするのではなくnCkのkで前計算をします。

ll modinv(ll a, ll m = MOD) {
    ll b = m, u = 1, v = 0;
    while(b) {
        ll t = a / b;
        a -= t * b;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    u %= m;
    if(u < 0)
        u += m;
    return u;
}

// com1[i] = kCi
vector<ll> com1(200000);
// com2[i] = {n-k}C{i}
vector<ll> com2(200000);

ll n, m, k;

void init1() {
    com1[0] = 1;
    for(ll i = 1; i <= min(k, 100000LL); i++) {
        com1[i] = ((com1[i - 1] * (k - i + 1) % MOD) * modinv(i)) % MOD;
        com1[i] %= MOD;
    }
}

void init2() {
    com2[0] = 1;
    for(ll i = 1; i <= min((n - k), 100000LL); i++) {
        com2[i] = (com2[i - 1] * (n - k - i + 1) % MOD) * modinv(i) % MOD;
        com2[i] %= MOD;
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> m >> k;
    init1();
    init2();
    ll ans = 0;
    for(ll i = 1; i <= min(m, k); i++) {
        (ans += (i * com1[i] % MOD) * com2[m - i] % MOD) %= MOD;
    }
    cout << ans << endl;
}

EDR 38 D. Buy a Ticket

https://codeforces.com/contest/938/problem/D

問題

N頂点M辺の重み付き無向グラフがあり(連結とは限らない)、各辺は重みがw_iで、頂点v_iとu_iを相互に繋いでいる。

各頂点iにはコストa_iがある。

ここで、d(i,j) := 頂点iから頂点jへの最短距離(ただしiからjへの経路が存在しない場合はINFとする) とする。

各頂点iについて、2d(i,j) + a_j (j = 1~N) の最小値を求めよ。

制約

  • 2<=N<=2*105
  • 1<=M<=2*105
  • 1<=v_i, u_i<=N (v_i≠u_i)
  • 1<=w_i, a_i<=1012

解法1

元のグラフの辺のコストを2倍します。その後ダイクストラをするのですが、この時距離の最小値を保存する配列distの初期値をそれぞれa[i]にしておきます。

また、priority_queueには始めに頂点iにコストa[i]で移動してきたものとして突っ込んでおきます。

あとは普通にダイクストラをしてあげれば良いです。

実装1

https://codeforces.com/contest/938/submission/68132913

// first:コスト second:頂点番号
using P = pair<ll, ll>;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n, m;
    cin >> n >> m;
    vector<vector<P>> g(n);
    for(ll i = 0; i < m; i++) {
        ll v, u, w;
        cin >> v >> u >> w;
        v--;
        u--;
        g[v].push_back(P(2 * w, u));
        g[u].push_back(P(2 * w, v));
    }
    vector<ll> a(n), dist(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        dist[i] = a[i];
    }

    priority_queue<P, vector<P>, greater<P>> que;
    for(ll i = 0; i < n; i++) {
        que.push(P(a[i], i));
    }

    while(que.size()) {
        auto now = que.top();
        que.pop();
        ll nv = now.second;
        ll nd = now.first;
        if(dist[nv] < nd) {
            continue;
        }
        for(auto next : g[nv]) {
            if(dist[next.second] > dist[nv] + next.first) {
                dist[next.second] = dist[nv] + next.first;
                que.push(P(dist[next.second], next.second));
            }
        }
    }
    for(ll i = 0; i < n; i++) {
        cout << dist[i] << ' ';
    }
    cout << endl;
}

解法2

解法1とほとんど同じなのですが、若干異なります。

つまり新たに頂点n(0-index)を追加し、そこから頂点i(i=0〜n-1)に辺を張って、ダイクストラをすれば良いです。

実装2

https://codeforces.com/contest/938/submission/68232036

// first:コスト second:頂点番号
using P = pair<ll, ll>;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n, m;
    cin >> n >> m;
    vector<vector<P>> g(n + 1);
    for(ll i = 0; i < m; i++) {
        ll v, u, w;
        cin >> v >> u >> w;
        v--;
        u--;
        g[v].push_back(P(2 * w, u));
        g[u].push_back(P(2 * w, v));
    }
    vector<ll> a(n), dist(n + 1, LLINF);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        g[n].emplace_back(P(a[i], i));
    }

    priority_queue<P, vector<P>, greater<P>> que;
    dist[n] = 0;
    que.push(P(0, n));
    while(que.size()) {
        auto now = que.top();
        que.pop();
        ll nv = now.second;
        ll nd = now.first;
        if(dist[nv] < nd) {
            continue;
        }
        for(auto next : g[nv]) {
            if(dist[next.second] > dist[nv] + next.first) {
                dist[next.second] = dist[nv] + next.first;
                que.push(P(dist[next.second], next.second));
            }
        }
    }

    for(ll i = 0; i < n; i++) {
        cout << dist[i] << ' ';
    }
    cout << endl;
}

感想

頂点にコストがある = 新しく頂点を追加して、そこから各頂点に辺を張る、という発想が新しいなと思いました。

ド典型だと思うので覚えておきたいです。

2020年元旦 AC数メモ

これは何

2020年が終わったときに自分がどれくらいACしたか等を知りたいので今のうちに進捗をメモする

つまりはこれの真似です kkt89.hatenablog.com

目標

これを忘れない!(素振り)

f:id:bakamono1357:20200101032717p:plain

特に復習をしていきたいですね

現在

f:id:bakamono1357:20200101033527p:plain f:id:bakamono1357:20200101033630p:plain f:id:bakamono1357:20200101032836p:plain f:id:bakamono1357:20200101032937p:plain f:id:bakamono1357:20200101032955p:plain f:id:bakamono1357:20200101033020p:plain f:id:bakamono1357:20200101033115p:plain

f:id:bakamono1357:20200101033308p:plain
AOJ-ICPC これひどいな...
f:id:bakamono1357:20200101033419p:plain
JOI難易度表

頑張るぞという気持ちになってきました。 良いお年を!

パ研合宿2019 第4日「Teamwork」オンライン参加記

これは何

弊学のB1であるばやしこ君と同級生のsuta君とチームを組んでパ研のコンテストにオンライン参加しました。

atcoder.jp

せっかく色々復習したのでどうせなら参加記とメモを残そうかなと思った次第です。

動き

新幹線の中で別の問題を考察しながら寝落ちしてて、起きると...

f:id:bakamono1357:20191227235611p:plain
出るに決まっています
slackを見るともうばやしこ君がAとBをサラッとACしてくれていた 神

チーム名もいつの間にかUHIUHI_bayashikoに決まっていた

f:id:bakamono1357:20191228000246p:plain
チームUHISHIROメンバーとチームを組むとウヒウヒにされます

ここからはsuta君がC、ばやしこ君がD、僕がEを見ることになりました

suta君が確率うげ~といいながらも爆速でAC

ばやしこ君が若干考察に詰まりながらもsuta君と相談しながら考察を詰め、実装がつらそうだったけどAC(強い...)

僕はその間Eを詰めていました

「そもそも最短経路の数え上げってどうやるんだ...」と思いながら、「でも最短経路の数え上げなんて絶対典型だろうし類題あるでしょ」と重いながら『競プロ 最短経路 数え上げ』と検索するとけんちょんさんのこの記事がヒットする。

drken1215.hatenablog.com

確かに最短経路を更新する時はその経路数も更新し、距離が同じ場合は足し込めばいい...結構簡単に求められるんだなあ!すごい!となる

しかし夏と冬で重複してる場合をどうするのか最後までわからず、部分点25点しか稼げなかった...

その後はばやしこ君が部分点を稼いでくれて、結果は

suta君とEの重複部分を詰めていたけど詰められなかったので反省。

問題

C,D,Eを復習したのでメモ。

C 罰ゲーム

解法

A君の出る目を固定すれば、B君とC君がA君より大きい目が出る場合の数をO(1)で計算できます。

実装

実装も軽い。こういう問題好きです

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    vector<ll> l(3), r(3);
    for(ll i = 0; i < 3; i++) {
        cin >> l[i] >> r[i];
    }
    ll ans = 0;
    for(ll i = l[0]; i <= r[0]; i++) {
        ll one = max(r[1] - max(i + 1, l[1]) + 1, 0LL);
        ll two = max(r[2] - max(i + 1, l[2]) + 1, 0LL);
        ans += one * two;
    }
    ll mul = 1;
    for(ll i = 0; i < 3; i++) {
        mul *= (r[i] - l[i] + 1);
    }
    cout << fixed << setprecision(15);
    cout << (double)ans / mul << endl;
}

D リミックスジュース

解法

K=Nとします。まず、1~iの和でXを超える最も最小のiを探します。まず、i個の1を横に並べます。するとX以下の和の連続する部分列はi*(i+1)/2個できます。

後は、残りX-(i(i+1)/2)個作りたいです。これは、i個1を並べた数列の前にn-i+1-{X-(i(i+1)/2)}を置いてあげて、余った分は適当に109以下の巨大な数を並べてあげるだけで良いです。

実装

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n, x;
    cin >> n >> x;
    vector<ll> ans(n);
    for(ll i = 1; i <= n; i++) {
        if(i * (i + 1) / 2 >= x) {
            x -= i * (i + 1) / 2;
            ans[0] = n - i + 1;
            for(ll j = 1; j <= i - 1; j++) {
                ans[j] = 1;
            }
            for(ll j = i; j < n; j++) {
                ans[j] = (ll)(1e9) - 1;
            }
            break;
        }
    }
    cout << n << endl;
    ans[0] -= x;
    for(ll i = 0; i < n; i++) {
        cout << ans[i] << ' ';
    }
    cout << endl;
}

E IOIのために

解法

夏と冬それぞれについてダイクストラをして、頂点1を始点とする最短距離とその最短経路の個数を数え上げます。

その後、夏と冬で重複してる部分を除きます。これは、もう1度夏についてダイクストラをしてあげて、「夏の現在の仮の最短距離 == 本当の最短距離」&&「冬の場合の、行き先の最短距離 == 今の頂点への最短距離 + 次の頂点へのコスト」の場合のみ、最短経路の数を更新すると、夏と冬で重複している最短経路の数が数え上げられます。

後は、「夏の最短経路の数」+「冬の最短経路の数」-「重複している最短経路の数」を出力してあげればよいです。

実装

using P = pair<ll, ll>;
using data = pair<vector<ll>, vector<ll>>;
struct edge {
    ll to, cost, s, w;
};
 
ll n, m;
 
data dijkstra(ll s, ll n, vector<vector<edge>> &g) {
    vector<ll> d(n, LLINF), num(n, 0);
    d[s] = 0;
    num[s] = 1;
    // first:最短距離, second:頂点番号
    priority_queue<P, vector<P>, greater<P>> que;
    que.push(P(0, s));
    while(que.size()) {
        auto now = que.top();
        que.pop();
        ll nv = now.second;
        ll nd = now.first;
        if(d[nv] < nd) {
            continue;
        }
 
        for(auto next : g[nv]) {
            if(d[next.to] > d[nv] + next.cost) {
                d[next.to] = d[nv] + next.cost;
                num[next.to] = num[nv];
                que.push(P(d[next.to], next.to));
            } else if(d[next.to] == d[nv] + next.cost) {
                (num[next.to] += num[nv]) %= MOD;
            }
        }
    }
    return data(d, num);
}
 
data dijkstra2(ll s, ll n, vector<vector<edge>> &g, vector<ll> &summer,
               vector<ll> &winter) {
    vector<ll> d(n, LLINF), num(n, 0);
    d[s] = 0;
    num[s] = 1;
    // first:最短距離, second:頂点番号
    priority_queue<P, vector<P>, greater<P>> que;
    que.push(P(0, s));
    while(que.size()) {
        auto now = que.top();
        que.pop();
        ll nv = now.second;
        ll nd = now.first;
        if(d[nv] < nd) {
            continue;
        }
 
        for(auto next : g[nv]) {
            if(d[next.to] > d[nv] + next.cost) {
                d[next.to] = d[nv] + next.cost;
                if(summer[next.to] == d[next.to] &&
                   winter[next.to] == winter[nv] + next.w) {
                    num[next.to] = num[nv];
                }
                que.push(P(d[next.to], next.to));
            } else if(d[next.to] == d[nv] + next.cost) {
                if(summer[next.to] == d[next.to] &&
                   winter[next.to] == winter[nv] + next.w) {
                    (num[next.to] += num[nv]) %= MOD;
                }
            }
        }
    }
    return data(d, num);
}
 
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    vector<vector<edge>> gs(n), gw(n);
    for(ll i = 0; i < m; i++) {
        ll a, b, s, w;
        cin >> a >> b >> s >> w;
        a--;
        b--;
        gs[a].emplace_back(edge{b, s, s, w});
        gs[b].emplace_back(edge{a, s, s, w});
        gw[a].emplace_back(edge{b, w, s, w});
        gw[b].emplace_back(edge{a, w, s, w});
    }
    auto summer = dijkstra(0, n, gs);
    auto winter = dijkstra(0, n, gw);
    auto both = dijkstra2(0, n, gs, summer.first, winter.first);
    ll ans = (summer.second[n - 1] + winter.second[n - 1]) % MOD;
    ans = (ans - both.second[n - 1] + MOD) % MOD;
    cout << ans << endl;
}

感想

新幹線の中で出たのもあって物理的に実装できない時間があり、チームに迷惑をかけてしまった。ごめんなさい。

ただ、普段チームを組まない人とチーム戦をするのはとても楽しかったです、suta君とばやしこ君、組んでくれてありがとうございました!

そしてパ研運営の皆様に感謝です!

冬休みにやりたいことリスト

これは何

  • 長期休暇中にやりたいことをいつも長期休暇前に色々考えて、結局何も実現できなくて無為に過ごしてしまうのをいつもやってしまう
  • これを防ぐために、せめてやろうと思っていることをメモとして残しておきたいね
  • 残すか~~~

勉学

  • 複素関数論、代数学フーリエ変換、信号処理、情報数学は現状理解が追いついてないので、追いつく(授業を聞きなさ~い!)
  • アルゴリBのグループワークの進捗を出す(これが最優先)

競プロ

  • 今まで逃げてたABC-Dをいっぱい埋めたい 具体的にはここらへん

  • 緑・水diff埋まってなさすぎでは 埋めなさい f:id:bakamono1357:20191219024555p:plain

  • JOIバチャをやる 難易度5、6あたりから選ぶ

  • こどふぉバチャ これは1日1回やりたい(とは言ってもじゅぴろさん達が毎日一緒に走ってくれそう)

  • ライブラリの理解、実装(特にグラフ... SCC、LCAとか)

  • 1000AC突破したいなあ(↓ 2019/12/19時点)

なんかやりたいこと思いついたら冬休みまでにここに随時追加していく!(素振り) これ全部できるの...?わからん...

Codeforces Round #494 (Div. 3) E - Tree Constructing

問題

直径がd、頂点の最大入次数がkとなるようなn頂点の木を構築しなさい。 構築できるならば"YES"を出力した後全ての辺を出力し、できないならば"NO"とだけ出力する。

制約

  • 1 <= n,d,k <= 4 * 105

解法

  • まず、d+1個の頂点を使って頂点をまっすぐに繋ぎ、直径dの木を構築する。この時点でdeg[i] (頂点iの入次数)がkより大きい場合は"NO"。

  • 残りのn-d-1個の頂点をこの木につないでいく。既に木につないでいる頂点をqueueにすべて入れる。(queueには新たにつなげることのできる頂点の候補が入っている)

  • queueから取り出した頂点vが、dist[v](頂点vから他の頂点へのパスのうち、最大の距離)< d かつdeg[v] < kであるならばそれを新しい頂点とつなぎ、それぞれのdistとdegを更新する。

  • 最後に、残りのn-d-1個の頂点全てを木につなげたかどうかをチェックしてあげればよい。

実装

#include <bits/stdc++.h>
using namespace std;
template <class T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return 1;
    }
    return 0;
}
typedef long long int ll;
 
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define endl "\n"
const double EPS = 1e-7;
const int INF = 1 << 30;
const ll LLINF = 1LL << 60;
const double PI = acos(-1);
const int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
 
//-------------------------------------
 
using P = pair<int, int>;
 
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, d, k;
    cin >> n >> d >> k;
    if(d >= n || n == 1 || (k == 1 && n > 2)) {
        cout << "NO" << endl;
        return 0;
    }
    vector<P> ans;
    int now = d + 1;
    for(int i = 0; i < now - 1; i++) {
        ans.emplace_back(P(i, i + 1));
    }
    queue<int> que;
    vector<int> deg(n, 0);
    vector<int> dist(n, 0);
    for(int i = 0; i < d + 1; i++) {
        if(i == 0 || i == d) {
            deg[i] = 1;
        } else {
            deg[i] = 2;
        }
        dist[i] = max(i, d - i);
        que.push(i);
    }
    while(que.size() && now < n) {
        int v = que.front();
        que.pop();
        if(dist[v] >= d || deg[v] >= k) {
            continue;
        }
        int next = now++;
        ans.emplace_back(P(v, next));
        deg[v]++;
        deg[next] = 1;
        dist[next] = dist[v] + 1;
        que.push(v);
        que.push(next);
    }
    if(now < n) {
        cout << "NO" << endl;
    } else {
        cout << "YES" << endl;
        for(auto e : ans) {
            cout << e.first + 1 << ' ' << e.second + 1 << endl;
        }
    }
}

感想

  • かなりできる気がしたけど時間がなくてバチャ中に実装できなかった 他の問題で余計な時間を食いすぎました

CODE THANKS FESTIVAL 2017(Parallel) F - Limited Xor Subset

別解が面白かったのでメモを残します。

問題

N要素の正の整数列aがあり、i番目の要素はa_{i}である。 N個の整数のうち0個以上を選んでそれらのbitごとの総XORを計算したとき、それがKとなるような整数の選び方の総数を10^{9}+7で割った余りを求めなさい。 ただし、0個選んだときのbitごとのXORは0とする。

制約

  • 1<=N<=100000
  • 0<=K<=100000
  • 1<=a_{i} (1<=i<=N)
  • \sum_{1}^{N} {a_i} <= 100000
  • 入力はすべて整数

解法

  • 想定解(https://img.atcoder.jp/code-thanks-festival-2017-open/editorial.pdf)はdpですが、ここでは別解のみを書きます。
  • まず、問題文を読むと、この問題の性質より、①数列の要素をswapしても答えは変わらない。②数列の2つの要素a_ia_jに対してXORを取り、それを新たな数列の要素(つまり、a_i\oplus{a_j}a_jに新たに変更する)としても答えは変わらない。ことがわかります。まず、①について、XORは可換であるためこれは成立します。②については、以下の説明により成り立ちます。 f:id:bakamono1357:20191118145958p:plain
  • ここで、数列aKをそれぞれmod2上の行列、行ベクトルで表すことを考えます。
  • まず、数列をbitごとに分解します。各桁を行、数列の個数を列とし、行列にして表します。例えば、N=4a={1,2,5,7}の時、以下のように表します。この場合、i行が下からi桁目のbit、j列がj番目の数列の要素に対応していることがわかります。 f:id:bakamono1357:20191118143759p:plain
  • 次に、Kを各bitに分解し、行ベクトルに分解します。例えばK=3の場合、以下のように表します。 f:id:bakamono1357:20191118144201p:plain
  • ここで、実は、先程説明した①は行の入れ替え、②はある行に別の行を加えるに対応していることがわかります。つまり、これは行基本変形と同じであることがわかります。
  • ここから考えると、求める選び方の総数は連立1次方程式Ax=bの解の個数に等しいです。よって答えは、行基本変形により掃き出し法でrankを求め、解が存在するならば2^{N-rank}(なぜなら、パラメータの個数はN-rank個あり、各パラメータの値はmod2なので2通りしかないため)存在しないならば0通りであることがわかりました。計算量は行数をR、列数をCとすると、bitset高速化により、O(R^{2}C/64)となります。
  • 参考文献:けんちょんさんの記事(http://drken1215.hatenablog.com/entry/2019/03/20/202800)、trapのブログ(https://trap.jp/post/435/

実装

#include <bits/stdc++.h>
using namespace std;
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return 1;
    }
    return 0;
}
typedef long long int ll;

#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define endl "\n"
const double EPS = 1e-7;
const int INF = 1 << 30;
const ll LLINF = 1LL << 60;
const double PI = acos(-1);
const int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

//-------------------------------------

const int MAX_ROW = 20;     // 行
const int MAX_COL = 110000; // 列

struct BitMatrix
{
    int h, w;
    bitset<MAX_COL> val[MAX_ROW];
    BitMatrix(int m = 1, int n = 1) : h(m), w(n) {}
    bitset<MAX_COL> &operator[](int i) { return val[i]; }
};

// 掃き出し法によりrankを求める
int GaussJordan(BitMatrix &A, bool isExtended = false)
{
    int rank = 0;
    for (int c = 0; c < A.w; c++)
    {
        if (isExtended && c == A.w - 1)
        {
            break;
        }
        int p = -1;
        for (int r = rank; r < A.h; r++)
        {
            if (A[r][c])
            {
                p = r;
                break;
            }
        }
        if (p == -1)
        {
            continue;
        }
        swap(A[p], A[rank]);
        for (int r = 0; r < A.h; r++)
        {
            if (r != rank && A[r][c])
            {
                A[r] ^= A[rank];
            }
        }
        rank++;
    }
    return rank;
}

int linearEquation(BitMatrix A, vector<int> b, vector<int> &res)
{
    int m = A.h;
    int n = A.w;
    BitMatrix mat(m, n + 1);
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            mat[i][j] = A[i][j];
        }
        mat[i][n] = b[i];
    }
    int rank = GaussJordan(mat, true);
    // 解なしの場合
    for (int r = rank; r < m; r++)
    {
        if (mat[r][n])
        {
            return -1;
        }
    }
    // 解がある場合、resに解を代入し、rankを返す
    res.assign(n, 0);
    for (int i = 0; i < rank; i++)
    {
        res[i] = mat[i][n];
    }
    return rank;
}

ll pow_mod(ll n, ll k, ll mod)
{
    if (k == 0)
    {
        return 1;
    }
    else if (k % 2 == 1)
    {
        return pow_mod(n, k - 1, mod) * n % mod;
    }
    else
    {
        ll t = pow_mod(n, k / 2, mod);
        return t * t % mod;
    }
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    BitMatrix A(20, n);
    vector<int> b(20);
    for (int d = 0; d < 20; d++)
    {
        for (int i = 0; i < n; i++)
        {
            if (a[i] & (1 << d))
            {
                A[d][i] = 1;
            }
        }
        if (k & (1 << d))
        {
            b[d] = 1;
        }
    }
    vector<int> ans;
    int rank = linearEquation(A, b, ans);
    cout << (rank == -1 ? 0 : pow_mod(2LL, n - rank, MOD)) << endl;
}

感想

  • 俗に言う「F2上で線形代数」ってやつだそうです。実装はけんちょんさんの記事を大いに参考(というか写経)にしました。
  • この解法ならばa_iの制約がもっと大きくても解けるので、すごい...