Atcoder Regular Contest 080 F. Prime Flip

Atcoder Regular Contest 080 F. Prime Flip

F: Prime Flip - AtCoder Regular Contest 080 | AtCoder

感想

解説を見た。簡単な方法に落とし込むまでの流れが好きな問題。

解法

まず区間をひっくり返すときのテクを使う。列においてある位置とその一つ前の位置を見て、それらの$\ xor\ $をとって、これを配列$\ x\ $などにいれる。imosの反転バージョンのような感じである。すると、$\ [l, r)\ $を反転する操作が、$\ x_l\ $と$\ x_r\ $のみを反転する操作になる。そして、問題はこの配列の数をすべて0にするための最小手数を求める問題に変わる。

ここで、ある位置の1を消す（位置をずらすのではなく個数を減らすという意味で）ためには、またある別の数と同時に消す他に方法はない。つまりこれらの1同士で同時に消えるペアを作って良い。以下、そのようなペアの作り方で最適なものを考える。

ある2数の位置が$\ a, b\ $だったとする。もし、$\ |a - b|\ $が3以上の素数なのだとしたら、これらは明らかに1回の操作で消せる。逆に、素数でなければ1回で消せることがないことも言える。

次に$\ |a - b|\ $が偶数であるとする。$\ |a - b| = 2\ $のときは、双子素数を使って2回の操作でこれらを消せる。$\ |a - b| \geq 4\ $のときは、ゴールドバッハの予想(ゴールドバッハの予想 - Wikipedia)によってその差を二つの素数の和で表せるのでやはり2回の操作で消せる。1回の操作で消すことは自明にできないので、これが最小回数である。

最後に$\ |a - b|\ $が奇数であり、かつ素数ではないとする。このとき、まず3回の操作で必ず消せることを示す。まず1回の操作で、$\ |a - b|\ $の値を3大きくする。すると、$\ |a - b|\ $は偶数になるので、上記よりあと2回の操作でこれを消せる。よって3回の操作で消せることがわかる。次に2回以下の操作では消せないことを示す。2回操作をするということは、3以上の素数は奇数なので、$\ |a - b|\ $の値の変化量は必ず偶数になるはずである。よってこれが0になることはない。1回の操作では当然消せないので、これで3回が最小の回数であることが示された。

あとはペアを作っていくだけである。まず位置が奇数であるグループと偶数であるグループにわけ、できるだけ1回で消せるペアをこのグループ間でつくればよい。この1回で消せるペアの数を最大化するとよいというのは割と自明だと思ったが、一応証明がeditorialには書いてあるので省略。

これは最大二部マッチングを求める問題に帰着されるので、あとはやるだけである。

実装

#include "bits/stdc++.h"
using namespace std;

bool is_prime(int x) {
        if (x == 1) return false;
        for (int i = 2; i * i <= x; i ++) {
                if (x % i == 0) return false;
        }
        return true;
}

struct edge {
        int to, cap, rev;
};
bool used[101010];
vector<edge> g[101010];
static const int INF = 0x3f3f3f3f;
void add_edge(int from, int to, int cap) {
        g[from].push_back((edge) { to, cap, (int)g[to].size() });
        g[to].push_back((edge) { from, 0, (int)g[from].size() - 1 });
}
int dfs(int v, int t, int f) {
        if (v == t) return f;
        used[v] = true;
        for (int i = 0; i < g[v].size(); i ++) {
                edge& e = g[v][i];
                if (!used[e.to] && e.cap > 0) {
                        int d = dfs(e.to, t, min(f, e.cap));
                        if (d > 0) {
                                e.cap -= d;
                                g[e.to][e.rev].cap += d;
                                return  d;
                        }
                }
        }
        return 0;
}
int MaxFlow(int s, int t) {
        int flow = 0;
        while (true) {
                memset(used, false, sizeof(used));
                int f = dfs(s, t, INF);
                if (f == 0) return flow;
                flow += f;
        }
}

vector<int> even, odd;

void push(int x) {
        if (x & 1) odd.push_back(x);
        else even.push_back(x);
}

int main() {
        int n;
        cin >> n;
        vector<int> x(n);
        for (int i = 0; i < n; i ++) cin >> x[i];
        for (int i = 0; i < n; i ++) {
                if (i == 0 || x[i] - 1 != x[i - 1]) push(x[i]);
                if (i == n - 1 || x[i] + 1 != x[i + 1]) push(x[i] + 1);
        }
        int o = odd.size(), e = even.size();
        int s = 0, t = o + e + 1;
        for (int i = 0; i < o; i ++) add_edge(s, i + 1, 1);
        for (int i = 0; i < e; i ++) add_edge(i + o + 1, t, 1);
        for (int i = 0; i < o; i ++) {
                for (int j = 0; j < e; j ++) {
                        int d = abs(odd[i] - even[j]);
                        if ((d & 1) && is_prime(d)) add_edge(i + 1, j + o + 1, 1);
                }
        }
        int k = MaxFlow(s, t);
        int ans = k + ((e - k) / 2 + (o - k) / 2) * 2 + ((o - k) % 2) * 3;
        cout << ans << endl;
        return 0;
}

Atcoder AGC 005 E. Sugigma: The Showdown

Atcoder AGC 005 E. Sugigma: The Showdown

E: Sugigma: The Showdown - AtCoder Grand Contest 005 | AtCoder

感想

後半の考察に1時間以上かかったが、自力で一発ACしたので嬉しかった。木とゲームに関する問題はやっぱり得意だ。

解法

以下、先手を$\ N\ $、後手を$\ P\ $と呼ぶことにする。

まずゲームが終了しない場合というのはどういう場合なのかを考察する。無限にループが起こる部分というのは、$\ N\ $にとっては距離$\ 1\ $であってかつ、$\ P\ $にとっては距離$\ 3\ $以上であるような2頂点間である。これは図を書けば簡単に証明できる。このようなループに$\ N\ $が$\ P\ $に追いつかれないように到達できるならばゲームは終了しないことがわかる。

このようなループを含む点を列挙するには、まず$\ N\ $に関する木の隣り合う頂点をペアにして保管しておき、そのそれぞれに対して$\ P\ $に関する木の上での距離が求められれば良い。これは$\ P\ $に関する根付き木のLCAを考えて、はい。

さて、あとは$\ N\ $が$\ P\ $と出会わない範囲でどのような移動ができるのかを考えればよい。よく考えると、$\ P\ $は$\ P\ $に関する木の上を（ループを考慮しなければ）どんどん下に向かって($\ N\ $に向かって）下りていくという戦法しか取る必要がない。すると、$\ P\ $に関する木においてそのdepthがそのまま$\ P\ $が到達するのに必要なステップ数に一致する。

よって、移動しようとしている点について、$\ P\ $が到達するステップ数より自身のステップ数が小さいような移動のみを行なっていけば良い。これは典型的な$\ BFS\ $を記述すればよい。

$\ BFS\ $の途中で、ループを含むような点に到達できたなら、ゲームは終了しないので-1を出力する。そうでないなら通ることができたすべての点についてdepthの最大値をとれば、$\ P\ $がゲームを終わらせるためのステップ数の最大値が求められるので、ターン数としてその2倍を出力する。

実装

#include "bits/stdc++.h"
using namespace std;

#define pii pair<int, int>

struct state { int v, step; };

vector<int> gx[202020];
vector<int> gy[202020];
int depth[202020];
int parent[30][202020];

void dfs(int v, int p, int d) {
        parent[0][v] = p;
        depth[v] = d;
        for (auto i : gy[v]) if (i != p) dfs(i, v, d + 1);
}
void init(int s, int V) {
        dfs(s, -1, 0);
        for (int k = 0; k < 30 - 1; k ++) {
                for (int i = 0; i < V; i ++) {
                        if (parent[k][i] < 0) parent[k + 1][i] = -1;
                        else parent[k + 1][i] = parent[k][parent[k][i]];
                }
        }
}
int lca(int u, int v) { 
        if (depth[u] > depth[v]) swap(u, v);
        for (int k = 0; k < 30; k ++) {
                if ((depth[v] - depth[u]) >> k & 1) { 
                        v = parent[k][v];
                }
        }
        if (u == v) return u;
        for (int k = 30 - 1; k >= 0; k --) {
                if (parent[k][u] != parent[k][v]) {
                        u = parent[k][u];
                        v = parent[k][v];
                }
        }
        return parent[0][u];
}
int dist(int u, int v) {
        return depth[u] + depth[v] - depth[lca(u, v)] * 2;
}

int main() {
        int n, x, y;
        cin >> n >> x >> y;
        x --, y --;
        vector<pii> edge(n);
        for (int i = 0; i < n - 1; i ++) {
                int a, b;
                cin >> a >> b;
                a --, b --;
                edge[i] = mp(a, b);
                gx[a].push_back(b);
                gx[b].push_back(a);
        }
        for (int i = 0; i < n - 1; i ++) {
                int a, b;
                cin >> a >> b;
                a --, b --;
                gy[a].push_back(b);
                gy[b].push_back(a);
        }
        init(y, n);
        vector<pii> loop;
        for (int i = 0; i < n - 1; i ++) {
                if (dist(edge[i].first, edge[i].second) >= 3) loop.push_back(edge[i]);
        }
        set<int> loop_set;
        for (int i = 0; i < loop.size(); i ++) {
                loop_set.insert(loop[i].first);
                loop_set.insert(loop[i].second);
        }
        queue<state> q;
        q.push((state){ x, 0 });
        int ans = -1;
        vector<bool> used(n, false);
        used[x] = true;
        while (!q.empty()) {
                state now = q.front(); q.pop();
                ans = max(ans, depth[now.v] * 2);
                if (loop_set.count(now.v)) {
                        cout << -1 << endl;
                        return 0;
                }
                for (auto next : gx[now.v]) if (!used[next]) {
                        used[next] = true;
                        if (depth[next] <= now.step + 1) continue;
                        q.push((state){ next, now.step + 1 });
                }
        }
        cout << ans << endl;
        return 0;
}

Atcoder AGC 003 D. Anticube

Atcoder AGC 003 D. Anticube

D: Anticube - AtCoder Grand Contest 003 | AtCoder

感想

素因数分解したときに出てくる3乗は消しても良いことには割とすぐに気づき、共存できない数同士のペアが一意に定まるところまでは落とし込めた。が、実装方法と計算量の落とし方はなんだかさっぱりだったので、結局nuipさんのコードをジロジロ見ながら実装した。恥ずかしながら、unordered_mapを初めて使った。

解法

まずいかなる3乗も1と等価と見なしてよい。すると、どの数も素因数をそれぞれ高々2個までしかもたないような数に書き換えることができる（調べて見るとこれを正規化というらしい？）。

次に、この操作によって定まる数には、（1を除いて）それと共存できないそれとは異なる数が一意に定まる。これは割と自明で、例えば上の操作によって、$\ x = a^1 * b^2 * c ^ 1\ $のような感じになったとすると、これと共存できない数は、（上の操作を行なった結果）$\ y = a ^ 2 * b ^ 1 * c ^ 2\ $となるような数しかない。実装も基本的にはこのように片方の指数$\ x\ $に対してもう一方の指数は$\ 3 - x\ $とする。

これらの2数のうち出現した回数が多い方を採用していけば良いことになる。ただし、上の操作によって1になるような数が1つでも存在すれば、そのような数のうち1個だけは追加できるので、1を足す。

素数の列挙は、$\ \sqrt[3]{10^{10}}\ $以下の数までで抑えないと$\ TLE\ $する。ペアの数がどのような数であるかを理解していればそんなに難しくなかった。

ちなみに下から5行目の不等式の評価は、そのままパクったのだが、個数が同じときにでもどちらかの個数を1回だけ足さなければいけないため、ペアの値が常に相異なることを利用して、pairで比較して大きい方のものを取る、という風にうまく実装されている。

実装

#include "bits/stdc++.h"
using namespace std;

#define pll     pair<long long, long long>
#define ll      long long

//N以下の素数列挙。O(N log log N)
int N = 2180; //N * N * N >= 10^10
vector<int> prime;
void init() {
        vector<bool> is_prime(N + 1, true);
        is_prime[0] = is_prime[1] = false;
        for (int i = 2; i <= N; i ++) {
                if (is_prime[i]) {
                        prime.push_back(i);
                        for (int j = i + i; j <= N; j += i) is_prime[j] = false;
                }
        }
}

int main() {
        init();
        int n;
        cin >> n;
        vector<ll> a(n);
        for (int i = 0; i < n; i ++) cin >> a[i];
        unordered_map<ll, pll> cnts; //その値, 個数, その値のペアの値
        for (auto v : a) {
                ll val = 1, another = 1;
                for (auto p : prime) {
                        if (v % p != 0) continue;
                        int cnt = 0;
                        while (v % p == 0) {
                                cnt ++;
                                v /= p;
                        }
                        if (cnt % 3 == 1) {
                                val *= p;
                                another *= p * p;
                        } else if (cnt % 3 == 2) {
                                val *= p * p;
                                another *= p;
                        }
                }
                if (v > 1) {
                        ll tmp = sqrt(v);
                        ll root = 0;
                        for (int i = -1; i < 2; i ++) if ((tmp + i) * (tmp + i) == v) root = tmp + i;
                        val *= v;
                        if (root) another *= root;
                        else another *= v * v;
                }
                cnts[val].second = another;
                cnts[val].first ++;
        }
        auto tmp = cnts;
        ll ans = 0;
        for (auto u : tmp) if (u.first != 1 && cnts[u.second.second] < u.second) ans += u.second.first;
        if (cnts[1].first != 0) ans ++;
        cout << ans << endl;
        return 0;
}

Atcoder ARC 061 D. すぬけ君の塗り絵 / Snuke's Coloring

Atcoder ARC 061 D. すぬけ君の塗り絵 / Snuke's Coloring

D: すぬけ君の塗り絵 / Snuke's Coloring - AtCoder Regular Contest 061 | AtCoder

解法

最も愚直な方法は、$\ H * W\ $の配列を用意し、そこにクエリに従って色をつけていき、最後に$\ 3 * 3\ $の範囲を動かして全探索する方法である。 当然これは時間計算量も空間計算量も厳しい。

あるグリッドが塗られたときに、各カウントがどのように変化するかを考える。すると、その塗られたグリッドを中心とする$\ 5 * 5\ $の範囲のみのカウントが変わることに気づく。よってそこのカウントの変化だけを見れば良い。

普通にグリッドを用意すると同様にMLEとなる。ある座標が塗られているかどうかだけ判定できればよいので、塗られた座標をsetに入れておくとよい。計算量は$\ O(n\log n)\ $の大きめの定数倍？

実装

#include "bits/stdc++.h"
using namespace std;

#define mp      make_pair
#define pii     pair<int, int>

int main() {
        long long h, w, n;
        cin >> h >> w >> n;
        set<pii> s;
        vector<long long> ans(10, 0);
        ans[0] = (h - 2) * (w - 2);
        for (int k = 0; k < n; k ++) {
                long long a, b;
                cin >> a >> b;
                a --, b --;
                for (long long i = max(0LL, a - 2); i < min(a + 1, h - 2); i ++) {
                        for (long long j = max(0LL, b - 2); j < min(b + 1, w - 2); j ++) {
                                int cnt = 0;
                                for (long long y = i; y < i + 3; y ++) {
                                        for (long long x = j; x < j + 3; x ++) {
                                                if (s.count(mp(y, x))) cnt ++;
                                        }
                                }
                                ans[cnt] --;
                                ans[cnt + 1] ++;
                        }                 
                }
                s.insert(mp(a, b));
        }
        for (int i = 0; i < 10; i ++) {
                cout << ans[i] << endl;
        }
        return 0;
}

Atcoder AGC 017 B. Moderate Differences

Atcoder AGC 017 B. Moderate Differences

B: Moderate Differences - AtCoder Grand Contest 017 | AtCoder

解法

数列において減少する回数を固定して、差分($\ B - A\ $)のとりうる最小最大を決めて条件を満たすものがあるかを判定する。

例えば下限を考えているときは、増加させる際に最低$\ C\ $だけ増加させる必要があり、減少させる際に$\ D\ $だけ減少させることができるので、これで下限が求められる。

こうして求めた下限、上限の間の任意の数をとれることは言うまでもない。

このように回数を固定して考える発想は常に持っておきたい。

実装

#include "bits/stdc++.h"
using namespace std;

int main() {
        long long n, a, b, c, d; cin >> n >> a >> b >> c >> d;
        bool ans = false;
        for (int i = 0; i < n - 1; i ++) if (i * c - (n - 1 - i) * d <= b - a && b - a <= i * d - (n - 1 - i) * c) ans = true;
        cout << (ans ? "YES" : "NO") << endl;
        return 0;
}

Atcoder AGC 006 C. Rabbit Exercise

Atcoder AGC 006 C. Rabbit Exercise

C: Rabbit Exercise - AtCoder Grand Contest 006 | AtCoder

解法

まず、各ステップにおいて、期待値を決定していけることに注目する。うさぎ$\ a\ $について、そのジャンプ後の位置の期待値は、左右のジャンプが両方確率$\ \frac {1}{2}\ $であることから、$\ (x_{a - 1} - x_a) + (x_{a + 1} - x_a) + x_a = x_{a - 1} + x_{a + 1} - x_a\ $となる。

ここから先の考察は解説をみた。この式をよく見ると、$\ x_a - x_{a - 1}\ $と$\ x_{a + 1} - x_a\ $の値の交換になっていると気づくらしい。確かにそうだなという感じだった。よってあとは階差数列をswapしまくればいい。

実装

#include "bits/stdc++.h"
using namespace std;

signed main() {
        int n;
        cin >> n;
        vector<long long> x(n);
        for (int i = 0; i < n; i ++) cin >> x[i];
        vector<long long> d(n - 1);
        for (int i = 0; i < n - 1; i ++) d[i] = x[i + 1] - x[i];
        long long m, k;
        cin >> m >> k;
        vector<long long> a(m);
        for (int i = 0; i < m; i ++) { 
                cin >> a[i];
                a[i] --;
        }
        vector<long long> move(n - 1);
        for (int i = 0; i < n - 1; i ++) move[i] = i;
        for (int i = 0; i < m; i ++) swap(move[a[i]], move[a[i] - 1]);
        vector<vector<long long> > swp(n - 1, vector<long long> (61));
        for (int i = 0; i < n - 1; i ++) swp[move[i]][0] = i;
        for (int i = 1; i < 61; i ++) { 
                for (int j = 0; j < n - 1; j ++) { 
                        swp[j][i] = swp[swp[j][i - 1]][i - 1];
                }
        }
        for (int b = 0; b < 61; b ++) {
                if ((k >> b) & 1) {
                        vector<long long> next(n - 1);
                        for (int i = 0; i < n - 1; i ++) next[swp[i][b]] = d[i];
                        for (int i = 0; i < n - 1; i ++) d[i] = next[i];
                }
        }
        long long prev = x[0];
        cout << prev << endl;
        for (int i = 0; i < n - 1; i ++) { 
                prev = d[i] + prev;
                cout << prev << endl;
        }
        return 0;
}                                         

CF Croc Champ 2013 - Round 1 E. Copying Data（別解）

CF Croc Champ 2013 - Round 1 E. Copying Data（別解）

Problem - E - Codeforces

解法

RBSTの実装法を学んだので、過去に解いた問題をRBSTで書いてみた。遅延セグ木でぐちゃぐちゃする問題が、思考停止ではい、の問題に変わった。

解としては自明に正しいけれど、$\ TLE\ $した。shared_ptrを使わずにやると、$\ MLE\ $した。mersenne twisterをxorshiftに変えてみたけどそれでもまぁだめ（思ったよりは速くなった）。メモリプールを作ってやれば上手くいくかもしれないらしいけど実装法がよくわからなくてもういいやってなった。

$\ O(n\log n)\ $で十分高速なのかと思っていた...

実装

#include "bits/stdc++.h"
#include <cassert>
using namespace std;

unsigned long xor128() {
        static unsigned long x = 123456789, y = 362436069, z = 521288629, w = 88675123;
        unsigned long t = (x ^ (x << 11));
        x = y; y = z; z = w;
        return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}

struct node_t {
        int sz;
        long long val;
        shared_ptr<node_t> lchild, rchild;
        node_t(long long val, int sz, shared_ptr<node_t> lchild, shared_ptr<node_t> rchild)
                     : val(val), sz(sz), lchild(lchild), rchild(rchild) {}
};

using node = shared_ptr<node_t>;

int size(node t) { return !t ? 0 : t->sz; }

node new_node(long long val) {
        return node(new node_t(val, 1, NULL, NULL));
}

node make_node(long long val, node left, node right) {
        int sz = size(left) + size(right) + 1;
        return node(new node_t(val, sz, left, right));
}

node merge(node left, node right) {
        if (!left || !right) return !left ? right : left;
        if (int(xor128() % (size(left) + size(right)) < size(left))) {
                return make_node(left->val, left->lchild, merge(left->rchild, right));
        } else {
                return make_node(right->val, merge(left, right->lchild), right->rchild);
        }
}

pair<node, node> split(node t, int k) { //[0, k), [k, n)
        if (k == 0) return pair<node, node>(NULL, t);
        if (k >= size(t)) return pair<node, node>(t, NULL);
        if (size(t->lchild) >= k) {
                auto left = split(t->lchild, k);
                auto rv = make_node(t->val, left.second, t->rchild);
                return make_pair(left.first, rv);
        } else {
                auto right = split(t->rchild, k - size(t->lchild) - 1);
                auto lv = make_node(t->val, t->lchild, right.first);
                return make_pair(lv, right.second);
        }
}

node find(node tree, int k) {
        while (tree != NULL) {
                int sz = size(tree->lchild);
                if (sz > k) tree = tree->lchild;
                else if (sz == k) return tree;
                else {
                        tree = tree->rchild;
                        k -= sz + 1;
                }
        }
        return tree;
}

int main() {
        int n, q;
        scanf("%d%d", &n, &q);
        node tree_a = NULL;
        vector<int> a(n), b(n);
        for (int i = 0; i < n; i ++) {
                int a;
                scanf("%d", &a);
                tree_a = merge(tree_a, new_node(a));
        }
        node tree_b = NULL;
        for (int i = 0; i < n; i ++) {
                int b;
                scanf("%d", &b);
                tree_b = merge(tree_b, new_node(b));
        }
        while (q --) {
                int type;
                scanf("%d", &type);
                if (type == 1) {
                        int x, y, k;
                        scanf("%d%d%d", &x, &y, &k);
                        x --, y --;
                        node mid = split(split(tree_a, x + k).first, x).second;
                        node left = split(tree_b, y).first;
                        node right = split(tree_b, y + k).second;
                        tree_b = merge(merge(left, mid), right);
                } else {
                        int x;
                        scanf("%d", &x);
                        x --;
                        long long ans = find(tree_b, x)->val;
                        cout << ans << endl;
                }
        }
        return 0;
}