CS Academy 050 Div.2 E. Min Swaps

CS Academy 050 Div.2 E. Min Swaps

CS Academy

感想

見掛け倒しな感じがある。

解法

まず値が大きいものと小さいものが順に現れるように順列を作れば、なんとなく条件を満たしそうなことから、そのように並べてみる。

その数列が小さいものからスタートすると考え、$\ a_1, a_2, a_3, ..., a_n\ $となったとすると、この数列のコストは、$\ (a_2 - a_1) + (a_2 - a_3) + ... + (a_{n - 2} - a_{n - 1}) + (a_n - a_{n - 1})\ $、すなわち$\ -a_1 + 2 * (a_2 + a_4 + ... ) - 2 * (a_3 + a_5 + ... ) + a_n\ $となる。よって$\ a_1\ $が小さいものの中で最大のもの、$\ a_n\ $が大きいものの中で最小となっていればよい。つまり、$\ a_1 = \frac {n} {2},\ a_n = \frac {n} {2} + 1\ $としておけばよい。

あとは偶数番目の位置に何個の小さい数が入っているかを数えれば、必要なスワップの回数が求められる。

実装

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

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

int get(int n, vector<int> a) {
        int res = 0;
        if (a[0] != n / 2) {
                res ++;
                for (int i = 0; i < n; i ++) if (a[i] == n / 2) swap(a[0], a[i]);
        }
        if (a[n - 1] != n / 2 + 1) {
                res ++;
                for (int i = 0; i < n; i ++) if (a[i] == n / 2 + 1) swap(a[n - 1], a[i]);
        }
        for (int i = 1; i < n - 1; i += 2) if (a[i] < n / 2) res ++;
        return res;
}

void solve() {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i ++) cin >> a[i];
        int ans = get(n, a);
        reverse(all(a));
        ans = min(ans, get(n, a));
        cout << ans << endl;
        return;
}

int main() {
        ios::sync_with_stdio(false);
        cin.tie(0);
        int t;
        cin >> t;
        while (t --) solve();
        return 0;
}

CS Academy 050 Div. 2 Check Square

CS Academy 050 Div.2 Check Square

CS Academy

感想

色々やり方がありそうだけど、頂点を見る順番で全探索した。

解法

4点の位置関係がわからないので、その関係を全探索する。順番に点をずらしながら辺を4本とって、その長さがすべて等しくなるような場合が存在するならば正方形になる。実際の距離で考えると誤差が出そうで怖いので距離の二乗で比較する。

実装

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

int dist(int x1, int y1, int x2, int y2) {
        return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}

void solve() {
        vector<int> x(4), y(4);
        for (int i = 0; i < 4; i ++) cin >> x[i] >> y[i];
        vector<int> ord(4);
        for (int i = 0; i < 4; i ++) ord[i] = i;
        bool ans = false;
        do {
                int a = dist(x[ord[0]], y[ord[0]], x[ord[1]], y[ord[1]]);
                int b = dist(x[ord[1]], y[ord[1]], x[ord[2]], y[ord[2]]);
                int c = dist(x[ord[2]], y[ord[2]], x[ord[3]], y[ord[3]]);
                int d = dist(x[ord[3]], y[ord[3]], x[ord[0]], y[ord[0]]);
                if (a == b && b == c && c == d) ans = true;
        } while (next_permutation(all(ord)));
        cout << ans << endl;
        return;
}

int main() {
        ios::sync_with_stdio(false);
        cin.tie(0);
        int t;
        cin >> t;
        while (t --) solve();
        return 0;
}

Codeforces Testing Round 1 C. Circular RMQ

Codeforces Testing Round 1 C. Circular RMQ

Problem - C - Codeforces

感想

区間加算、区間最小値を処理する遅延セグメント木をライブラリに追加したので、貼るだけの問題で試しておいた。

解法

貼るだけ。ただし入力が親切じゃないので、getlineで入力をとって' 'でパースしてどちらのクエリなのかをみないといけない。

実装

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

static const int INF = 0x3f3f3f3f;

//区間加算、区間最小値
template<typename Type>
struct LazySegmentTree {
        vector<Type> data, lazy;
        int n;
        LazySegmentTree(int x) {
                n = pow(2, ceil(log2(x)));
                data.resize(2 * n - 1, INF);
                lazy.resize(2 * n - 1, 0);
        }
        void init(int k, Type p) {
                k += n - 1;
                data[k] = p;
                while (k > 0) {
                        k = (k - 1) / 2;
                        data[k] = min(data[k * 2 + 1], data[k * 2 + 2]);
                }
        }
        void add(int a, int b, int x) { return add(a, b, x, 0, 0, n); } //[a, b)
        void add(int a, int b, int x, int k, int l, int r) {
                if (r <= a || b <= l) return;
                if (a <= l && r <= b) {
                        lazy[k] += x;
                        return;
                }
                int m = (l + r) / 2;
                add(a, b, x, k * 2 + 1, l, m);
                add(a, b, x, k * 2 + 2, m, r);
                data[k] = min(data[k * 2 + 1] + lazy[k * 2 + 1], data[k * 2 + 2] + lazy[k * 2 + 2]);
        }
        Type getmin(int a, int b) { return getmin(a, b, 0, 0, n); } //[a, b)
        Type getmin(int a, int b, int k, int l, int r) {
                if (r <= a || b <= l) return INF;
                if (a <= l && r <= b) return data[k] + lazy[k];
                int m = (l + r) / 2;
                Type left = getmin(a, b, k * 2 + 1, l, m);
                Type right = getmin(a, b, k * 2 + 2, m, r);
                return min(left, right) + lazy[k];
        }
};

void solve() {
        int n;
        cin >> n;
        LazySegmentTree<int> st(n);
        for (int i = 0; i < n; i ++) { 
                int a;
                cin >> a;
                st.init(i, a);
        }
        int q;
        cin >> q;
        cin.ignore();
        while (q --) {
                string s;
                getline(cin, s);
                int cnt = 0;
                for (int i = 0; i < s.size(); i ++) cnt += s[i] == ' ';
                if (cnt == 1) {
                        int sp;
                        for (int i = 0; i < s.size(); i ++) {
                                if (s[i] == ' ') { 
                                        sp = i;
                                        break;
                                }
                        }
                        int l = stoi(s.substr(0, sp));
                        int r = stoi(s.substr(sp, s.size()));
                        if (l <= r) cout << st.getmin(l, r + 1) << endl;
                        else cout << min(st.getmin(0, r + 1), st.getmin(l, n)) << endl;
                } else {
                        int sp1 = 0, sp2;
                        for (int i = 0; i < s.size(); i ++) {
                                if (s[i] == ' ' && !sp1) {
                                        sp1 = i;
                                        continue;
                                }
                                if (s[i] == ' ' && sp1) {
                                        sp2 = i;
                                }
                        }
                        int l = stoi(s.substr(0, sp1));
                        int r = stoi(s.substr(sp1, sp2));
                        int v = stoi(s.substr(sp2, s.size()));
                        if (l <= r) { 
                                st.add(l, r + 1, v);
                        } else {
                                st.add(0, r + 1, v);
                                st.add(l, n, v);
                        }
                }
        }
        return;
}

int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        solve();
        return 0;
}

CS Academy 048 D. Dominant Free Sets

CS Academy 048 D. Dominant Free Sets

CS Academy

感想

アルゴリズムの正当性を証明していたにも$\ AC\ $できず......。結局FenwickTreeのクエリ処理時にMODをとっていなかっただけだった。

解法

まず$\ x\ $に関してソートしておき、その列の上で順に$\ y\ $を見ていくことを考える。取り出す部分列の中で、ある$\ i\ $について、$\ x_i < x_{i + 1}\ $となっているならば、$\ y_i > y_{i + 1}\ $となっていればよい。$\ x_i = x_{i + 1}\ $となっているならば、$\ y\ $はどうなっていてもいけない（$\ =\ $は$\ \leq\ $でもあり$\ \geq\ $でもあるからだ）。これは結局、$\ x\ $が同じものについては$\ y\ $についてソートしておけばよい（つまり普通にペアのソートをする）。

そうすると、$\ y\ $の数列について、狭義単調減少な部分列の個数を求める問題に帰着する。これをdpで求める。

dp[i] := i - 1までの、y[i]より大きい数を末尾とする部分列の個数 + 1（自分自身だけで作る部分列の個数）+ dp[i - 1]（自分自身を使わない部分列の個数）

となる。最初の2項が自分自身が末尾になる部分列の個数であるから、その値を保存しておきたい。そしてその総和をとりたいので、FenwickTreeで位置y[i]にその値を加えることで、うまく総和をとれるようにする。

あとは正しくMODをとりながら計算してdp[n - 1]を出力する。

実装

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

#define all(x)  x.begin(), x.end()
#define mp      make_pair
#define pii     pair<int, int>
#define ll      long long

static const int MOD = 1000000007;

//0-origin
template <typename T>
struct FenwickTree {
	vector<T> data;
	FenwickTree(int n) : data(n, 0) {}
        //v[i] += x
	void add(int i, T x) { for (int p = i; p < (int)data.size(); p |= p + 1) data[p] += x; }
        //[0, i)
	T sum(int i) {
		T s = 0;
                for (int p = i - 1; p >= 0; p = (p & (p + 1)) - 1) s += data[p];
		return s;
	}
        //[l, r)
	T sum(int l, int r) { return sum(r) - sum(l); }
};

void solve() {
        int n;
        cin >> n;
        vector<pair<long long, long long>> p(n);
        for (int i = 0; i < n; i ++) cin >> p[i].first >> p[i].second;
        sort(all(p));
        FenwickTree<long long> ft(101010);
        vector<long long> v(n);
        for (int i = 0; i < n; i ++) v[i] = p[i].second;
        long long dp[101010];
        dp[0] = 1;
        for (int i = 0; i < n; i ++) {
                long long sum = ft.sum(v[i] + 1, 101010) % MOD;
                ft.add(v[i], (sum + 1) % MOD);
                dp[i] = ((i == 0 ? 0 : dp[i - 1]) + sum + 1) % MOD;
        }
        cout << dp[n - 1] % MOD << endl;
        return;
}

int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        solve();
        return 0;
}

Atcoder Grand Contest 002 F. Leftmost Ball

Atcoder Grand Contest 002 F. Leftmost Ball

F: Leftmost Ball - AtCoder Grand Contest 002 | AtCoder

感想

前半の考察はできたが、あとはなにも手を動かせなかった。
順序制限のある組み合わせの問題であることから、各数を頂点と見たグラフに落とし込み、そのトポロジカルソートの個数を求めることと等価であるところまで詰める考え方が、個人的におもしろかった。

解法

$\ n\ $個の$\ 0\ $と$\ k - 1\ $個の各数を並べる問題。左から見て初めて現れる数は$\ 1, 2, ..., n\ $となっているものとして、最後に$\ n!\ $をかける。$\ 0\ $が出現するたびに、並べることができる数が増加する。

editorialにある図を参考にして適当にdpすると答えが出る。「$\ B\ $の左側には必ず$\ A\ $が無ければならない」などというような制限のもとで順列を考えるときにはこのように考えるのが有効なのだろう（それはそう）。

組み合わせについては、最大$\ n * k\ $くらいまで大きくなるので、いつもの組み合わせのやつ（？）が使えないので、あらかじめfactとinvfactを求めておく方法をとる。invfactについては、$\ \cfrac {1} {x !} = \cfrac {1} {(x + 1)!} * (x + 1)\ $なので、大きい方から再帰的に求めらる。

組み合わせのライブラリがまた長くなった。。。

実装

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

static const int MOD = 1000000007;

long long inv(long long a) {
        long long res = 1;
        long long n = MOD - 2;
        while (n > 0) {
                if (n & 1) res = res * a % MOD;
                a = a * a % MOD;
                n >>= 1;
        }
        return res;
}

long long fact[4040404];
long long invfact[4040404];

void init() {
        fact[0] = 1;
        for (int i = 1; i < 4040404; i ++) fact[i] = (fact[i - 1] * i) % MOD;
        invfact[4040403] = inv(fact[4040403]);
        for (int i = 4040402; i >= 0; i --) invfact[i] = (invfact[i + 1] * (i + 1)) % MOD;
}

long long nCr(long long n, long long r) {
        if (n < r) return 0;
        if (n - r < r) r = n - r;
        return fact[n] * invfact[n - r] % MOD * invfact[r] % MOD;
}

long long dp[2020][2020];

void solve() {
        init();
        int n, k;
        cin >> n >> k;
        if (k == 1) {
                cout << 1 << endl;
                return;
        }
        memset(dp, 0, sizeof dp);
        dp[0][1] = 1LL;
        for (int i = 0; i <= n; i ++) {
                for (int j = i; j <= n; j ++) {
                        if (i != 0) dp[i][j] = dp[i - 1][j]; 
                        if (i != j) {
                                long long a = nCr(i + j * (k - 1) - 1, k - 2);
                                dp[i][j] = (dp[i][j] + dp[i][j - 1] * a % MOD) % MOD;
                        }
                }
        }
        cout << dp[n][n] * fact[n] % MOD << endl;
        return;
}

int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        solve();
        return 0;
}

Atcoder Grand Contest 012 D. Colorful Balls

Atcoder Grand Contest 012 D. Colorful Balls

感想

前半の考察はできたのに、ほとんど同じの後半の発想がなぜかできなかった。

解法

まずすべての色が等しければ、答えは$\ 1\ $となる。以下は2種類以上の色があるものとする。

操作1では色の配置を変えることができないので、この操作の役割というのはできるだけ操作2ができるような状態にもっていくことである。操作2をするときには、常に操作1によって、その2つのボールの重さをできるだけ小さくなるようにしておくのが最適である。このように考えると結局、すべてのボールについて、そのボールと同じ色であって、かつ交換可能なボールの中で重さの最小値をとって、それをそのボールの重さとしてしまって良い。するとあとは操作2のみを考えればよい。

以下、上の操作によって変化した重さで考える。重さが最も小さいボールに注目すると、このボールと色が異なっていて、かつこのボールと交換可能ではないボールは、他のどのボールとも交換することができない。逆に、このボールと色が異なっていて、交換可能であるならば、それらのボールは、すべて互いに交換可能である。それは最小のボールを仲介にして、スワップを3回することによって、他のボールの位置を全く変えずに任意の2個をスワップできるからである。これらの並び順は重複を含む順列なので簡単に計算できる。

上の重さが最も小さいボールと同じ色のボールに対してはどう考えればよいだろうか？それはやはり上のボールとは異なる色の中で、重さが最小のものをとってくることで、同様に考えることができる。

この2つのボールがもし交換不可能であるならば、どの2つのボールも交換不可能であるので、答えは$\ 1\ $である。交換可能であるならば、これらの和集合の任意の2つは交換可能ということになる。

実装

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

#define all(x)  x.begin(), x.end()
#define mp      make_pair
#define pll     pair<long long, long long>

static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
static const int INF = 0x3f3f3f3f;
static const int MOD = 1000000007;

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

long long inv(long long a) {
        long long res = 1;
        long long n = MOD - 2;
        while (n > 0) {
                if (n & 1) res = res * a % MOD;
                a = a * a % MOD;
                n >>= 1;
        }
        return res;
}
long long fact[202020];

void init() {
        fact[0] = 1;
        for (int i = 1; i < 202020; i ++) fact[i] = fact[i - 1] * i % MOD;
}

void solve() {
        init();
        long long n, x, y;
        cin >> n >> x >> y;
        vector<vector<pll>> color(200000);
        for (int i = 0; i < n; i ++) {
                long long c, w;
                cin >> c >> w;
                color[c - 1].emplace_back(i, w);
        }
        int cnt = 0;
        for (int i = 0; i < n; i++) if (color[i].size() > 0) cnt ++;
        if (cnt == 1) {
                cout << 1 << endl;
                return;
        }
        vector<pll> ball(n);
        for (int i = 0; i < 200000; i ++) if (!color[i].empty()) {
                long long minwei = INFL;
                for (int j = 0; j < color[i].size(); j ++) minwei = min(minwei, color[i][j].second);
                for (int j = 0; j < color[i].size(); j ++) {
                        ball[color[i][j].first] = mp(i, (minwei + color[i][j].second <= x ? minwei : color[i][j].second));
                }
        }       
        int mi1 = INF, idx1, mi2 = INF, idx2;
        for (int i = 0; i < n; i ++) {
                if (ball[i].second < mi1) {
                        mi1 = ball[i].second;
                        idx1 = i;
                }
        }
        for (int i = 0; i < n; i ++) {
                if (ball[i].first != ball[idx1].first && ball[i].second < mi2) {
                        mi2 = ball[i].second;
                        idx2 = i;
                }
        }
        UnionFind uf(n);
        for (int i = 0; i < n; i ++) {
                if (ball[i].second + ball[idx1].second <= y && ball[i].first != ball[idx1].first) uf.unite(i, idx1);
                if (ball[i].second + ball[idx2].second <= y && ball[i].first != ball[idx2].first) uf.unite(i, idx2);
        }
        if (!uf.same(idx1, idx2)) {
                cout << 1 << endl;
        } else {
                int all = uf.get(idx1);
                map<int, int> color_cnt;
                for (int i = 0; i < n; i ++) if (uf.same(i, idx1)) color_cnt[ball[i].first] ++;
                long long ans = fact[all];
                for (auto c : color_cnt) ans = ans * inv(fact[c.second]) % MOD;
                cout << ans % MOD << endl;
        }
        return;
}

int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        solve();
        return 0;
}

CS Academy 46 Div. 1.5 C. Set Subtraction

CS Academy 46 Div. 1.5 C. Set Subtraction

CS Academy

感想

ちょっと応用できそう。

解法

まず数列はソートしておく。そして$\ X\ $について全探索する。全探索といっても$\ X \leq A_{n - 1}\ $ですべて試していると間に合わないので、$\ X\ $の候補としてありうるもの、すなわち$\ A_{n - 1} - A_i (i = 0, 1, ..., n - 2)\ $だけをチェックすれば良い。重複をなくせるようにsetにいれた。

$\ X\ $を固定すると、ある数$\ a\ $に対して、そのペアとなる数が$\ a + X\ $と定まる。よってあらかじめすべての数の出現回数をmapなどで数えておいて、小さい数から順に$\ A_i\ $と$\ A_i + X\ $の回数を$\ 1\ $ずつ減らしながら見ていって、すべてうまくマッチングできるかを考えれば良い。$\ O(n ^ 2)\ $。

実装

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

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

int main() {
        int n;
        cin >> n;
        vector<int> a(2 * n);
        for (int i = 0; i < 2 * n; i ++) cin >> a[i];
        sort(all(a));
        map<int, int> cnt;
        for (int i = 0; i < 2 * n; i ++) cnt[a[i]] ++;
        set<int> x;
        for (int i = 0; i < 2 * n - 1; i ++) x.insert(a.back() - a[i]);
        for (auto X : x) {
                map<int, int> tmp = cnt;
                vector<int> ans;
                for (int i = 0; i < 2 * n; i ++) {
                        if (tmp[a[i]] == 0) continue;
                        tmp[a[i]] --;
                        if (tmp[a[i] + X] == 0) goto next;
                        tmp[a[i] + X] --;
                        ans.push_back(a[i] + X);
                }
                cout << X << endl;
                for (int i = 0; i < ans.size(); i ++) cout << ans[i] << (i == ans.size() - 1 ? '\n' : ' ');
                return 0;
                next:;
        }
        cout << -1 << endl;
        return 0;
}