CODE FESTIVAL 2017 qual B C. 3 Steps

CODE FESTIVAL 2017 qual B C. 3 Steps

C: 3 Steps - CODE FESTIVAL 2017 qual B | AtCoder

感想

qual Aには出れなかったので、qual Bから参戦していた。40分で3完し、そのあとはひたすらDのバグをつぶそうとしていた。

総合243位、日本人98位なので本戦には行けないが、得意な感じの問題がCで出てくれたのでパフォーマンスは悪くなかった。そのCについて解法をまとめておく。

解法

移動をスタートする頂点を$\ S\ $に固定して考える。まず頂点$\ S\ $には$\ 0\ $と書き、$\ S\ $から進んだ距離を各頂点に書いていくことにする。ただし、$\ 2\ $と書いた次の頂点には、$\ 1\ $と書くことにする（つまり交互に書く）。なぜなら、本来$\ 3\ $と書かれるべき頂点には、$\ S\ $から辺を張れるので、それは$\ 1\ $とみなせるからである。すると、$\ S\ $を除くすべての頂点が$\ 1\ $または$\ 2\ $で塗られることになる。ただし、これは少し嘘で、塗り方に矛盾が生まれる場合があって、それは奇閉路が存在するときに限る。$\ 1\ $と書かれた頂点には辺を張ることが可能であり、$\ 2\ $と書かれた頂点には辺を張ることが不可能である。先に述べたように、奇閉路があるときは、すべての頂点を$\ 1\ $で塗れるので、すべての頂点に辺を張ることが可能である。
グダグダ書いたが結局二部グラフかどうかを見て、適当に完全グラフまたは二部グラフを作って辺を数えればよい。$\ O(n)\ $。答えは最大$\ 10^{10}\ $程度にまで大きくなるのでオーバーフローに気をつけること。

実装

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

void dfs(int v, int prev, int color, vector<int> &used, vector<vector<int>> &g, bool &can) {
        used[v] = color;
        for (auto u : g[v]) if (u != prev) {
                if (used[u] == -1) dfs(u, v, 1 - color, used, g, can);
                else if (used[u] != 1 - color) can = true;
        }
}

int main() {
        int n, m;
        cin >> n >> m;
        vector<vector<int>> g(n);
        for (int i = 0; i < m; i ++) {
                int a, b;
                cin >> a >> b;
                a --, b --;
                g[a].push_back(b);
                g[b].push_back(a);
        }
        vector<int> used(n, -1);
        bool can = false;
        dfs(0, -1, 0, used, g, can);
        long long ans;
        if (can) ans = (long long) n * (n - 1) / 2;
        else {
                int black = 0;
                for (int i = 0; i < n; i ++) black += used[i];
                ans = (long long) black * (n - black);
        }
        cout << ans - m << endl;
        return 0;
}

CODE FESTIVAL 2017 qual B D. 101 to 010

CODE FESTIVAL 2017 qual B D. 101 to 010

D: 101 to 010 - CODE FESTIVAL 2017 qual B | AtCoder

感想

コンテスト中はあやふやな実装でバグらせた。
DEGwerさんの提出コードを見ると、驚くほどわかりやすく実装されていたのでさすがだと思った。左右端の処理もきれい。
考えていることをしっかり整理してコードに落とす力が足りていない。

解法

左から普通にDPをする。DPの更新は101となっている部分に到達した時に、左側と右側の$\ 1\ $の個数をみていくようなDPで構わない。一見すると$\ O(n^2)\ $に見えるが、よく考えると各$\ 1\ $は高々$\ 2\ $回しか見ないので、$\ O(n)\ $で高速に計算される。

実装

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

int dp[505050];

int main() {
        int n; 
        scanf("%d", &n);
        string s; 
        cin >> s;
        s = "0" + s + "0";
        for (int i = 1; i < s.size() - 1; i ++) {
                dp[i + 1] = max(dp[i + 1], dp[i]);
                if (s[i - 1] == '1' && s[i] == '0' && s[i + 1] == '1') {
                        int prev = i - 1, next = i + 1;
                        while (s[prev] != '0') {
                                dp[i + 1] = max(dp[i + 1], dp[prev - 1] + (i - prev));
                                prev --;
                        }
                        while (s[next] != '0') {
                                dp[next] = max(dp[next], dp[i - 2] + (next - i));
                                next ++;
                        }
                }
        }
        printf("%d\n", dp[s.size() - 1]);
        return 0;
}

第16回日本情報オリンピック予選 E. 尾根(Ridge)

第16回日本情報オリンピック予選 E. 尾根(Ridge)

E: 尾根 (Ridge) - 第１６回日本情報オリンピック 予選（オンライン） | AtCoder

感想

典型的なdfsに落とし込む問題

解法

水が流れる方向に沿って、辺を張る。このとき、出次数が0であるような頂点がそれ以降どこにも水が流れない「谷」である。ある頂点が尾根であるための必要十分条件は、その頂点からスタートして、2つ以上の異なる谷に到達可能であることである。よって、各頂点からdfsをして、そこから到達可能な点が一つならば、その頂点の番号を記録し、2つ以上ある場合はINFなどと記録しておくようなdpで解くことができる。$\ O(hw)\ $。

実装

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

static const int INF = 0x3f3f3f3f;

vector<int> g[1010101];
bool used[1010101];
int dest[1010101];
int h, w;

void add(int fromy, int fromx, int toy, int tox) {
        g[fromy * w + fromx].push_back(toy * w + tox);
}

void dfs(int v) {
        used[v] = true;
        if (g[v].size() == 0) {
                dest[v] = v;
                return;
        }
        set<int> can;
        for (auto u : g[v]) {
                if (!used[u]) dfs(u);
                can.insert(dest[u]);
        }
        if (can.size() > 1) dest[v] = INF;
        else for (auto c : can) dest[v] = c;
        return;

}

void solve() {
        cin >> h >> w;
        vector<vector<int> > s(h, vector<int> (w));
        for (int y = 0; y < h; y ++) {
                for (int x = 0; x < w; x ++) {
                        cin >> s[y][x];
                }
        }
        for (int y = 0; y < h; y ++) {
                for (int x = 0; x < w - 1; x ++) {
                        if (s[y][x] < s[y][x + 1]) add(y, x + 1, y, x);
                        else add(y, x, y, x + 1);
                }
        }
        for (int x = 0; x < w; x ++) {
                for (int y = 0; y < h - 1; y ++) {
                        if (s[y][x] < s[y + 1][x]) add(y + 1, x, y, x);
                        else add(y, x, y + 1, x);
                }
        }
        for (int i = 0; i < h * w; i ++) if (!used[i]) dfs(i);
        int ans = 0;
        for (int i = 0; i < h * w; i ++) ans += dest[i] == INF;
        cout << ans << endl;
        return;
}

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

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