Learning Algorithms

アルゴリズムの勉強メモ

Atcoder Grand Contest 007 F. Shik and Copying String

Atcoder Grand Contest 007 F. Shik and Copying String

F: Shik and Copying String - AtCoder Grand Contest 007 | AtCoder

感想

考えることはシンプルなんだけど条件が難しい

解法

$\ T\ $の連続する文字の先頭文字と、それに対応する$\ S\ $の文字を決定できる。これがうまく対応させられないときは構成不可能で、逆に対応させることができれば構成可能である。

これらを$\ s + 1\ $回以下の操作で構成できるための条件は、$\ S\ $と$\ T\ $の対応する位置を$\ a\ $と$\ b\ $で表すと、任意の$\ i\ $について、$\ a_{i + s} - s \geq b_i\ $が成り立つことである。よってこれは二分探索で求めることができる。この条件は、絵を書いて$\ 1\ $時間くらいにらめば思いつく(ほんまか?)。

実装
#include "bits/stdc++.h"
using namespace std;
 
int main() {
        int n;
        scanf("%d", &n);
        string s, t;
        cin >> s >> t;
        if (s == t) return !puts("0");
        if (s[0] != t[0]) return !puts("-1");
        vector<int> a, b;
        b.push_back(0);
        for (int i = 1; i < n; i ++) if (t[i] != t[i - 1]) b.push_back(i);
        int k = b.size();
        int p = n - 1;
        int bp = k - 1;
        while (p > 0) {
                while (t[b[bp]] != s[p]) p --;
                if (p == 0) break;
                a.push_back(p);
                bp --;
                p = min(p, b[bp]);
        }
        a.push_back(0);
        reverse(a.begin(), a.end());
        if (a.size() != k) return !puts("-1");
        int lb = -1, ub = k;
        while (ub - lb > 1) {
                int s = (lb + ub) / 2;
                bool ok = true;
                for (int i = 0; i < k; i ++) {
                        if (i + s < k) ok &= a[i + s] - s >= b[i];
                }
                if (ok) ub = s;
                else lb = s;
        }
        printf("%d\n", ub + 1);
        return 0;
}

Atcoder Grand Contest 010 E. Rearranging

Atcoder Grand Contest 010 E. Rearranging

E: Rearranging - AtCoder Grand Contest 010 | AtCoder

感想

とにかく自力でACできて喜んでいたが、うさぎさんのコードを見ると圧倒的に簡潔でわかりやすかったので、大幅に真似て改良した。
AtCoder Grand Contest 010: E - Rearranging · うさぎ小屋

ちなみにこの問題は、以下の問題に近いものを感じた。こちらをACしていたから解けたのだと思う。
F: Wide Swap - AtCoder Grand Contest 001 | AtCoder

解法

まず先手がどのようにすれば最適な数列を構成できるかを考える。各数に関して、自分と互いに素ではない数に対して辺を張ることを考える。このとき連結にならないもの同士は、どう配置してもスワップできるので、独立に考えて最後に適当に(てきとーに)並べればよい。

ある連結成分について、最適な数列を構成する。まず、その成分の中で最小の値を一番左に置くのが最適である。なぜなら、その数を置いたときに任意の$\ DFS\ $順でそれ以降の数を並べていけば、その最初の数がスワップによって後ろの移動することはないからである。

さて、ある値を置いたあとに、その右に置く数はどんな数であるかを考える。その数と互いに素ではない数がまだ存在するなら、その数の中で最小のものを置けば良い。その数はその左の数とスワップされることはないし、もし仮に互いに素であるが、それよりも小さい数が存在したとしても、それを置いてしまうとスワップによってより大きくされてしまうはずであるからだ。

もし存在しないならば、まだ使っていない数の中で最小のものを置けば良い。ここで、より小さい数を選ぶことになる場合は明らかに問題がないのだが、より大き数数を選ぶ場合は最適でない可能性があるようにも思われる。しかし、そのような数というのはどのように配置してもスワップを防ぎきれないものであることがわかる。

以上の数列は$\ a\ $をソートしておき、常に左から順に見るような実装であれば、単純に$\ DFS\ $をするだけで求めることができる。

次に後手が作る最適な数列の構成法を考える。互いに素でない2つの数$\ a_i, a_j(i < j)\ $に関して、$\ a_j\ $から$\ a_i\ $に向かって有効辺を張ったときのトポロジカルソートの中で辞書順最大のものがその最適な数列である(AGC_001 Fとほとんど同じ)。

これは、出次数が$\ 0\ $のものの中で最大の数を一番左にもってきて、その数を消す、という操作を繰り返していくと求めることができる。上に書いたように辺を張ると、辺を削るときに困るので、逆向きに辺を張り、入次数が0のものとして考えると次数を減らす操作が簡単になる。

このようにやったものの、実は挿入ソートをやればよかった。なぜかこれに気づかなかった。実装の仕方はうさぎさんのを真似した。

実装(自力で書いた長くて汚い方)
#include "bits/stdc++.h"
using namespace std;
 
#define all(x)  x.begin(), x.end()
#define mp      make_pair
 
vector<int> g[2020];
int used[2020];
vector<int> a;
vector<int> tmp;
 
void dfs(int v, int prev) {
        used[v] = true;
        tmp.push_back(a[v]);
        vector<pair<int, int>> p;
        for (auto u : g[v]) if (u != prev) p.emplace_back(a[u], u); sort(all(p));
        for (auto u : p) {
                if (!used[u.second]) {
                        dfs(u.second, v);
                }
        }
}
 
int main() {
        int n;
        scanf("%d", &n);
        a.resize(n);
        for (int i = 0; i < n; i ++) scanf("%d", &a[i]);
        sort(all(a));
        for (int i = 0; i < n; i ++) {
                for (int j = i + 1; j < n; j ++) {
                        if (__gcd(a[i], a[j]) != 1) {
                                g[i].push_back(j);
                                g[j].push_back(i);
                        }
                }
        }
        for (int i = 0; i < n; i ++) {
                if (!used[i]) {
                        dfs(i, -1);
                }
        }
        for (int i = 0; i < n; i ++) g[i].clear();
        for (int i = 0; i < n; i ++) {
                for (int j = i + 1; j < n; j ++) {
                        if (__gcd(tmp[i], tmp[j]) != 1) {
                                g[i].push_back(j);
                        }
                }
        }
        vector<int> in_cnt(n, 0);
        for (int i = 0; i < n; i ++) {
                for (auto u : g[i]) {
                        in_cnt[u] ++;
                }
        }
        priority_queue<pair<int, int>> pq;
        for (int i = 0; i < n; i ++) if (in_cnt[i] == 0) pq.push(mp(tmp[i], i));
        vector<int> ans;
        while (!pq.empty()) {
                auto get = pq.top();
                pq.pop();
                ans.push_back(get.first);
                for (auto u : g[get.second]) {
                        in_cnt[u] --;
                        if (in_cnt[u] == 0) pq.push(mp(tmp[u], u));
                }
        }
        for (int i = 0; i < n; i ++) cout << ans[i] << (i == n - 1 ? '\n' : ' ');
        return 0;
}
実装(うさぎさんのコードを真似て書いたコード)
#include "bits/stdc++.h"
using namespace std;

#define all(x)  x.begin(), x.end()

int n;
int used[2020];
vector<int> a, ans;

void dfs(int v) {
        used[v] = true;
        ans.push_back(a[v]);
        for (int u = 0; u < n; u ++) {
                if (!used[u] && __gcd(a[v], a[u]) != 1) dfs(u);
        }
}

int main() {
        scanf("%d", &n);
        a.resize(n);
        for (int i = 0; i < n; i ++) scanf("%d", &a[i]);
        sort(all(a));
        for (int i = 0; i < n; i ++) if (!used[i]) dfs(i);
        for (int i = 0; i < n; i ++) {
                int p = i;
                for (int j = i - 1; j >= 0 && __gcd(ans[i], ans[j]) == 1; j --) {
                        if (ans[j] < ans[i]) p = j;
                }
                rotate(ans.begin() + p, ans.begin() + i, ans.begin() + i + 1);
        }
        for (int i = 0; i < n; i ++) cout << ans[i] << (i == n - 1 ? '\n' : ' ');
        return 0;
}

Atcoder Grand Contest 010 D. Decrementing

Atcoder Grand Contest 010 D. Decrementing

D: Decrementing - AtCoder Grand Contest 010 | AtCoder

感想

奇数の$\ gcd\ $で割ったときに偶奇の個数が変わらないことがポイントだった。

解法

明らかに愚直に考えると厳しいので、とりあえず偶奇によって場合をわけて考えることにする。まず(最初の状態も含めて)ある操作後にすべての数が偶数であるということはありえない。すなわち、一つ以上の奇数が存在する。

まず偶数の個数が奇数個の場合を考えると、いかなる場合においても、偶数の個数が偶数個の状態を相手に渡すことができるので、先手が勝つ。なぜなら、ある偶数を選んで操作によって奇数にすると、それらを$\ gcd\ $で割ったものの偶奇も変わらない($\ gcd\ $が奇数であるため)ので、結局相手は偶数が偶数個の状態を受け取ることになり、そこからはどう操作しても必ず偶数が奇数個の状態になって返ってくる。これを繰り返すことで、結局先手が勝つことがわかる。

逆に偶数の個数が偶数個の場合は、奇数が2個以上ある場合は、先手がどんな操作をしても上に述べた先手必勝の状態を渡すことになるので、後手必勝である。奇数の個数が一個のときは、偶数に操作をしてしまうと上の偶数が奇数個の状態(先手必勝)を渡してしまうことになるので、奇数に対して操作するしか手はない。これによって、すべてが偶数になるので、2以上の$\ gcd\ $で割られることになり、数列の値はすべて半分以下になる。このあとの操作の進み方は上と全く同様になるので、勝敗が決定するまで計算する。計算の性質上明らかにこれは高々$\ \log (max(A_i))\ $回の計算で終了する。よって計算量は$\ O(n \log(max(A_i)))\ $となる。

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

int print(bool first) {
        puts(first ? "First" : "Second");
        return 0;
}

int main() {
        int n;
        scanf("%d", &n);
        vector<int> a(n);
        for (int i = 0; i < n; i ++) scanf("%d", &a[i]);
        int even_cnt = 0;
        for (int i = 0; i < n; i ++) even_cnt += (a[i] % 2 == 0);
        assert(even_cnt != n); //includes at least one odd number
        if (even_cnt & 1) return print(true);
        if (even_cnt != n - 1) return print(false);
        bool f = true;
        while (true) {
                for (int i = 0; i < n; i ++) {
                        if (a[i] & 1) {
                                if (a[i] == 1) {
                                        return print((f && (n - 1) % 2 == 1) || (!f && ((n - 1) % 2 == 0)));
                                }
                                a[i] --;
                                break;
                        }
                }
                f ^= 1;
                int gcd = a[0];
                for (int i = 1; i < n; i ++) gcd = __gcd(a[i], gcd);
                for (int i = 0; i < n; i ++) a[i] /= gcd;
                even_cnt = 0;
                for (int i = 0; i < n; i ++) even_cnt += (a[i] % 2 == 0);
                if (even_cnt & 1) return print(f);
                if (even_cnt != n - 1) return print(!f);
        }
}

Atcoder Grand Contest 006 D. Median Pyramid Hard

Atcoder Grand Contest 006 D. Median Pyramid Hard

D: Median Pyramid Hard - AtCoder Grand Contest 006 | AtCoder

感想

いいところまでは考えられたような気がしたけど結局解説を読んで。
てきとうに書いて投げたら通った。
最近は二分探索をあまりバグらせない気がする。

解法

頂上が$\ x\ $以上であるかどうかで二分探索する。すべての数を、$\ x\ $以上であるかどうかによって1と0のみで分類でき、各マスは下の3マスの多数決になることから、パターンを見出す。

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

int main() {
        int n;
        scanf("%d", &n);
        int N = 2 * n - 1;
        vector<int> a(N);
        for (int i = 0; i < N; i ++) scanf("%d", &a[i]);
        int lb = 1, ub = N;
        while (ub - lb > 1) {
                int mid = (lb + ub) / 2;
                vector<int> b(N);
                for (int i = 0; i < N; i ++) b[i] = a[i] >= mid;
                int m = N / 2;
                if (b[m] == b[m + 1] || b[m] == b[m - 1]) {
                        (b[m] ? lb : ub) = mid;
                } else {
                        int left = m, right = m;
                        while (left > 0 && (b[left] ^ b[left - 1]) == 1) left --;
                        while (right < N && (b[right] ^ b[right + 1]) == 1) right ++;
                        if (m - left < right - m) (b[left] ? lb : ub) = mid;
                        else (b[right] ? lb : ub) = mid;
                }
        }
        printf("%d\n", lb);
        return 0;
}

Atcoder Grand Contest 002 D. Stamp Rally

Atcoder Grand Contest 002 D. Stamp Rally

D: Stamp Rally - AtCoder Grand Contest 002 | AtCoder

解法

二分探索をまとめてやる感じのやつ。各$\ mid\ $の値に関するソートをしておくことで左から順に見ていける。$\ O(m {\log}^2 m)\ $。

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

#define all(x)  x.begin(), x.end()
#define mp      make_pair

struct UnionFind {
        int n;
        vector<int> parent;
        vector<int> rank;
        vector<int> num;
        int find(int x) {
                if (parent[x] == x) return  x;
                return parent[x] = find(parent[x]);
        }
        UnionFind(int n_) {
                n = n_;
                parent.resize(n);
                for (int i = 0; i < n; i ++) parent[i] = i;
                rank.assign(n, 0);
                num.assign(n, 1);
        }
        void unite(int x, int y) {
                if ((x = find(x)) != (y = find(y))) {
                        if (rank[x] < rank[y]) {
                                parent[x] = y;
                                num[y] += num[x];
                        } else {
                                parent[y] = x;
                                if (rank[x] == rank[y]) rank[x] ++;
                                num[x] += num[y];
                        }
                        n --;
                }
        }
        bool same(int x, int y) { return find(x) == find(y); }
        int get() { return n; }
        int get(int x) { return num[find(x)]; }
};

int main() {
        int n, m;
        scanf("%d%d", &n, &m);
        vector<pair<int, int>> es(m);
        for (int i = 0; i < m; i ++) {
                int a, b;
                scanf("%d%d", &a, &b);
                a --, b --;
                es[i] = mp(a, b);
        }
        int q;
        scanf("%d", &q);
        vector<int> x(q), y(q), z(q);
        vector<int> lb(q), ub(q);
        for (int i = 0; i < q; i ++) {
                scanf("%d%d%d", &x[i], &y[i], &z[i]);
                x[i] --, y[i] --;
                lb[i] = 0, ub[i] = m;
        }
        vector<int> idx;
        for (int i = 0; i < q; i ++) idx.push_back(i);
        for (int loop = 0; loop < 20; loop ++) {
                sort(all(idx), [&](const int &a, const int &b) {
                        return (lb[a] + ub[a]) / 2 < (lb[b] + ub[b]) / 2;
                });
                UnionFind uf(n);
                int p = 0;
                for (auto &i : idx) {
                        int mid = (lb[i] + ub[i]) / 2;
                        while (p <= mid) {
                                uf.unite(es[p].first, es[p].second);
                                p ++;
                        }
                        int sum = uf.get(x[i]) + uf.get(y[i]);
                        if (uf.same(x[i], y[i])) sum /= 2;
                        if (sum < z[i]) { 
                                lb[i] = mid + 1;
                        } else { 
                                ub[i] = mid;
                        }
                }
        }
        for (int i = 0; i < q; i ++) printf("%d\n", lb[i] + 1);
        return 0;
}

Atcoder Grand Contest 007 C. Pushing Balls

Atcoder Grand Contest 007 C. Pushing Balls

C: Pushing Balls - AtCoder Grand Contest 007 | AtCoder

感想

難しいよ

解法

解説動画がわかりやすい。各ボールの距離に関する数列を書いて実験すると、その次のステップ(の期待値)の数列も同様に等差数列になることが証明される。

等差数列になることが証明できれば、あとは今の数列の長さ$\ N_{now}\ $と初項$\ d_{now}\ $と公差$\ x_{now}\ $より次のそれらを計算していけば良い。計算のたびに、その移動の総和の期待値、すなわち(等差数列の総和) / (項数)を足していけば答えになる。

具体的に計算すると、$\ N_{next} = N_{now} - 2,\ d_{next} = \cfrac {(N + 2) d_{now} + 5x_{now}} {N_{now}},\ x_{next} = \cfrac {(N + 4)x_{now}} {N_{now}}\ $となるので、そのように書く。

実装
#include &quot;bits/stdc++.h&quot;
using namespace std;

double calc(double n, double d, double x) {
        if (n == 0) return 0;
        double res = n * (2.0 * d + (n - 1) * x) / (2.0 * n);
        res += calc(n - 2, ((n + 2) * d + 5 * x) / n, (n + 4) * x / n);
        return res;
}

int main() {
        double n, d, x;
        scanf(&quot;%lf%lf%lf&quot;, &n, &d, &x);
        double ans = calc(2 * n, d, x);
        printf(&quot;%.15lf\n&quot;, ans);
        return 0;
}

Atcoder Grand Contest 019 C. Fountain Walk

Atcoder Grand Contest 019 C. Fountain Walk

感想

500点くらいの問題

解法

一般性を失わずに左上にスタート、右下にゴールがあると仮定して、それらを頂点とする長方形を考える。このとき、明らかにこの長方形の外に出て遠回りする方が経路長が短くなるようなことはない。

この長方形の内部で移動することを考えるときに、できるだけ(↓, 噴水, →)という移動をすればよいはずである。ただしこの移動をするために遠回りする必要はなく、まず通過できる噴水の最大値を$\ LIS\ $で求める。さらに図を書いて実験すると、条件を満たすような噴水の置き方の中で、最大個数、すなわち$\ min(gy - sy, gx - sx) + 1\ $個より少ない場合は、通過可能なすべての噴水をこの移動の仕方に使うことができる。$\ min(gy - sy, gx - sx) + 1\ $に等しい場合は、一回だけ噴水を通過して180度回るような移動をしなければいけない(これが最適)。ここを場合分けして素直に計算すればよい。

スタートの位置とゴールの位置は実際には異なるので、うまく処理する。

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

#define all(x)  x.begin(), x.end()

static const int INF = 1 << 30;
static const double PI = acos(-1);

int dp[202020];

int main() {
        int sx, sy, gx, gy;
        scanf("%d%d%d%d", &sx, &sy, &gx, &gy);
        int n;
        scanf("%d", &n);
        vector<pair<int, int>> p(n), q;
        for (int i = 0; i < n; i ++) scanf("%d%d", &p[i].first, &p[i].second);
        for (int i = 0; i < n; i ++) {
                if (min(sx, gx) <= p[i].first && p[i].first <= max(sx, gx) && min(sy, gy) <= p[i].second && p[i].second <= max(sy, gy)) {
                        q.push_back(p[i]);
                }
        }
        if (sy > gy) for (int i = 0; i < q.size(); i ++) q[i].second *= -1;
        sort(all(q));
        if (sx > gx) reverse(all(q));
        for (int i = 0; i < 202020; i ++) dp[i] = INF;
        for (int i = 0; i < q.size(); i ++) {
                *lower_bound(dp, dp + 202020, q[i].second) = q[i].second; 
        }
        int len = lower_bound(dp, dp + 202020, INF) - dp;
        double ans = (long long) (abs(gy - sy) + abs(gx - sx)) * 100;
        if (len < min(abs(gy - sy), abs(gx - sx)) + 1) {
                ans -= (20.0 - 5.0 * PI) * len;
        } else {
                ans -= (20.0 - 5.0 * PI) * (len - 1);
                ans += 10.0 * PI - 20;
        }
        printf("%.15lf\n", ans);
        return 0;
}