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;
}

Atcoder Typical DP Contest E. 数

Atcoder Typical DP Contest E. 数

E: 数 - Typical DP Contest | AtCoder

解法

自分の実際の思考の流れに従ってまとめておく。

まず自明に思いつくDPが、$\ dp[i][j] := \ $(上からi番目までを見て、各桁の和をDで割った余りがjであるような組み合わせの数)である。しかしこれだけでは上手く漸化式を立てることができない。

まず、$\ N = 10^k\ $のときを考えよう。このとき一番左の桁を0にすれば、各桁の数は0から9までの数を自由に取りうる（すべて0になる場合は除く）。よって、上に述べたdpの更新が容易になる。例えば、$\ i + 1\ $番目の数が7だとするとDPの定義より、dp[i + 1][j] += dp[i][[(j - 7) % D]のように更新できる。これを$\ k = 0, 1,2, ..., 9\ $ですべて計算する。

次に、もう少し一般に、$\ N = a * 10^k\ $のときを考える。このとき、まず、1番目の数を0に固定すると、上に述べたようにその総数が求められる。次に1番目の数を1から$\ a - 1\ $に固定したときを考える。このときも実はほとんど同じように考えることができる。例えばこれを3に固定したとすれば、上のDPにおいて、$\ j = -3 = d - 3\ $となっているものをとってこればよいからである。これで1番目を0から$\ a - 1\ $に固定したときの答えは求めらた。

さて、これ以降、一番左の数は、$\ a\ $に固定して考えて良い。次の桁からも同じようにその桁の数を固定して考えていくのだが、2番目の数を固定したときに使えるdp値は、dp[n - 2][j]である。これを今までと同じように利用して計算する。ただし、固定した数をどこかに保存して、常にその数を引いたmodをとらなければいけない。　

あとから気づいたが、同じ桁の値でも、それが上限値をとっているのか的な変数をもたせてやれば、もっとわかりやすく書けそう。とか思いながら他の人の解説などを見てみると、まさにそうだった。というかそれを桁DPとかなんとか言うらしい。前も桁DPの問題をそうとは知らずに解いたような...。まぁいいや。

実装

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

static const long long MOD = 1000000007;

signed main() {
        string s;
        int d;
        cin >> d >> s;
        int n = s.size();
        vector<vector<long long> > dp(n, vector<long long> (d, 0));
        dp[0][0] = 1;
        for (int i = 1; i < n; i ++) {
                for (int j = 0; j < d; j ++) {
                        for (int k = 0; k <= 9; k ++) {
                                dp[i][j] = dp[i][j] + dp[i - 1][(((j - k) % d) + d) % d] % MOD;
                        }
                }
        }
        long long ans = 0;
        long long ex = 0;
        for (int i = 0; i < n; i ++) {
                if (s[i] != '0') ans = ans + dp[n - 1 - i][((( - ex) % d) + d) % d] % MOD;
                for (int k = 1; k <= s[i] - '0' - 1; k ++) {
                        ans = ans + dp[n - 1 - i][(((- k - ex) % d) + d) % d] % MDO;
                }
                ex = (ex + s[i] - '0') % d;
        }
        cout << (ans - 1) % MOD << endl;
        return 0;
}

Atcoder ARC 030 D. グラフではない

Atcoder ARC 030 D. グラフではない

D: グラフではない - AtCoder Regular Contest 030 | AtCoder

解法

RBST(Randomized Binary Search Tree)として知られる永続データ構造を使う。ググって色々調べたり、他の人のコードから学んで実装した。

RBSTについて自分なりに少しまとめておく。

基本的にはTreapと同じで、配列を二分木によって表して、それぞれの根のポインタを上手く利用することで、区間クエリ（特にコピーや反転など）を高速に処理できるようにしたものである。Treapとの違いは、木のmergeの際に、Treapは優先度評価値によってどちらの根を新しい木の根にするかを決めるのに対し、RBSTはそれぞれの部分木のサイズの比率によって新しい根を決定する点である。

mergeとsplitは割と素直に（順番が崩れないように）実装する。また、部分木に関する情報は値の更新などがある度に更新する。

遅延評価をさせる場合は厄介だが、mergeの際に正しく子に伝播させるように実装すればよい。

コード中に整理のためにコメントで説明を書いておいた。

この実装さえできればあとはクエリ処理をてきとうに書くだけである。ちなみにshared_ptrを使わないと、$\ MLE\ $になった。

実装

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

#include <random>
mt19937 mt(0); //Mersenne Twisterによる乱数                                                                                        

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

using node = shared_ptr<node_t>;

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

node add(node v, long long a) { //根の遅延評価値にaを足す。valはこの時点では変更していない。
        if (!v) return NULL;
        int sz = v->sz;
        return node(new node_t(v->val, sz, v->add + a, v->sum + a * sz, v->lchild, v->rchild));
}

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

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

node merge(node left, node right) {
        if (!left || !right) return !left ? right : left;
        if (int(mt() % (size(left) + size(right)) < size(left))) { //ノード数に応じてどちらを根にするかを決める
                if (left->add == 0) { 
                        return make_node(left->val, left->lchild, merge(left->rchild, right), 0);
                }
                //遅延評価を子に伝播させ、自身のvalを更新して、add = 0としておく。
                node lv = add(left->lchild, left->add);
                node rv = merge(add(left->rchild, left->add), right);
                return make_node(left->val + left->add, lv, rv, 0); 
        } else {
                if (right->add == 0) {
                        return make_node(right->val, merge(left, right->lchild), right->rchild, 0);
                }
                node lv = merge(left, add(right->lchild, right->add));
                node rv = add(right->rchild, right->add);
                return make_node(right->val + right->add, lv, rv, 0);
        }
}

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, t->add);
                if (t->add == 0) return make_pair(left.first, rv);
                return make_pair(add(left.first, t->add), rv);
        } else {
                auto right = split(t->rchild, k - size(t->lchild) - 1);
                auto lv = make_node(t->val, t->lchild, right.first, t->add);
                if (t->add == 0) return make_pair(lv, right.second);
                return make_pair(lv, add(right.second, t->add));
        }
}

int main() {
        int n, q;
        cin >> n >> q;
        node tree = NULL;
        for (int i = 0; i < n; i ++) {
                int x;
                cin >> x;
                tree = merge(tree, new_node(x));
        }
        while (q --) {
                int type, a, b, c, d, v;
                cin >> type;
                if (type == 1) {
                        cin >> a >> b >> v;
                        auto y = split(tree, b);
                        auto x = split(y.first, a - 1);
                        tree = merge(x.first, merge(add(x.second, v), y.second));
                } else if (type == 2) {
                        cin >> a >> b >> c >> d;
                        auto mid = split(split(tree, d).first, c - 1).second;
                        auto x = split(tree, b);
                        auto left = split(x.first, a - 1).first;
                        auto right = x.second;
                        tree = merge(left, merge(mid, right));
                } else {
                        cin >> a >> b;
                        long long ans = sum(split(split(tree, b).first, a - 1).second);
                        cout << ans << endl;
                }
        }
        return 0;
}