Atcoder Beginner Contest 057 D. Maximum Average Sets

Atcoder Beginner Contest 057 D. Maximum Average Sets

D: Maximum Average Sets - AtCoder Beginner Contest 057 | AtCoder

感想

なぜかWAのまま放置していた。

解法

なんかやるだけ。
ただし$\ {}_n C _r \ $を求めるためにはパスカルの三角形による計算をしなければいけないので一応メモっておく（今まで使ってことがなかったので、初めはBigintライブラリを貼り付けて適当に通した）。
$\ mod\ $をとる計算をしないので、$\ n \geq 67\ $のときlong long型ではオーバーフローするようだ。

実装

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

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

long long com[70][70]; //67以上でオーバーフロー
void init(int n) {
        for (int i = 0; i <= n; i ++) {
                for (int j = 0; j <= i; j ++) {
                        if (j == 0 || j == i) com[i][j] = 1LL;
                        else com[i][j] = com[i - 1][j - 1] + com[i - 1][j];
                } 
        }
}
long long nCr(int n, int r) { return com[n][r]; }

int main() {
        int n;
        init(66);
        cin >> n;
        long long a, b;
        cin >> a >> b;
        vector<long long> v(n);
        for (int i = 0; i < n; i ++) cin >> v[i];
        sort(all(v));
        reverse(all(v));
        long long sum = 0;
        long long mi;
        for (int i = 0; i < a; i ++) { 
                sum += v[i];
                if (i == a - 1) mi = v[i];
        }
        cout << setprecision(10) << (double)sum / (double)a << endl;
        bool can_add = true;
        for (int i = 0; i < a; i ++) if (v[i] != mi) can_add = false;
        int cnt_A = 0, cnt_B = 0, cnt_all = 0;
        for (int i = 0; i < a; i ++) if (v[i] == mi) cnt_A ++;
        for (int i = 0; i < b; i ++) if (v[i] == mi) cnt_B ++;
        for (int i = 0; i < n; i ++) if (v[i] == mi) cnt_all ++;
        long long ans = 0;
        for (int i = cnt_A; i <= (can_add ? cnt_B : cnt_A); i ++) ans += nCr(cnt_all, i);
        cout << ans << endl;
        return 0;
}

Atcoder Grand Contest 019 D. Shift and Flip

Atcoder Grand Contest 019 D. Shift and Flip

感想

結局やるだけだったけど、ひたすら補題の実装ができなかった。解説は自明なパートだけだらだらと書いていて最も知りたい部分が省略されていた。

解法

まず最終的に$\ a\ $のどの部分が$\ b\ $のどの部分に対応するのかを決定して$\ O(n)\ $。あとでreverseで逆の場合を考えれば、このshiftは左にするものと考えて良い。flipの回数も一意に決定でき、あとはすべてのflipさせるべき位置がbが1であるような位置を通過するように移動の仕方を考えれば良い。

そのために最初に各位置について左と右でそれぞれbが1であるような位置までの距離を求めておく。そして、これを$\ (l, r)\ $とすれば、左に$\ x\ $回shiftしたとすると、bが1であるような位置までの距離は$\ (max(l - x, 0), r)\ $になると考えてよい。すべてのflipさせるべき位置についてこれをまとめたものを$\ V\ $とする。

すると、次の補題を解けばよい。

すべての$\ v \in V\ $に対して$\ v.first \leq a\ $または$\ v.second \leq b\ $が成り立つような$\ (a, b)\ $について$\ a + b\ $の最小値を求めよ。

この部分だけ強い人のコードを参考に書いた。まず$\ V\ $を降順にソートする。sumが求めたい答えで、sum = INFならば当然条件を満たすのでそれで初期化する。maで今まで見た中でsecondの最大値をいれる。firstの降順に見ているので、ある時点においてそれ以降に登場するものはすべてfirstによってカバーできるはずである。逆に、それ以外はfirstによってはカバーできていないので、それまでに出てきたsecondの最大値以上のsecondとしての値が必要である。よって以下のコードでうまく動く。

sort(all(V));
reverse(all(V));
int sum = INF;
int ma = 0;
for (int i = 0; i < V.size(); i ++) {
        sum = min(sum, V[i].first + ma);
        ma = max(ma, V[i].second);
}
sum = min(sum, ma);

これを求めればあとは簡単で、このsumの回数だけ寄り道して戻るので、結局答えは、shiftした回数$\ +\ $flipした回数$\ +\ sum * 2\ $である。

ソート部分が最も計算量が大きいので全体で$\ O(n^2\log n)\ $。

実装

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

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

static const int INF = 0x3f3f3f3f;

int solve(string a, string b) {
        int n = a.size();
        int left = 0, right = 0;
        for (int i = 0; i < n; i ++) {
                if (b[i] == '0') left ++;
                else break;
        }
        for (int i = n - 1; i >= 0; i --) {
                if (b[i] == '0') right ++;
                else break;
        }
        vector<int> one;
        for (int i = 0; i < n; i ++) if (b[i] == '1') one.push_back(i);
        int op = 0;
        vector<pair<int, int>> dis(n);
        for (int i = 0; i < n; i ++) {
                if (one[op] == i) { 
                        dis[i] = mp(0, 0);
                        op ++;
                } else if (op == 0) dis[i] = mp(i + 1 + right, one[op] - i);
                else if (op == one.size()) dis[i] = mp(i - one[op - 1], n - i + left);
                else dis[i] = mp(i - one[op - 1], one[op] - i);
        }
        int ans = INF;
        for (int shift = 0; shift <= n; shift ++) {
                int flip_cnt = 0;
                vector<bool> flip(n, false);
                for (int i = 0; i < n; i ++) {
                        if (a[i] != b[(i - shift + n) % n]) {
                                flip_cnt ++;
                                flip[i] = true;
                        }
                }
                vector<pair<int, int>> dis_modified;
                for (int i = 0; i < n; i ++) if (flip[i]) { 
                        dis_modified.emplace_back(max(dis[i].first - shift, 0), dis[i].second);
                }
                sort(all(dis_modified));
                reverse(all(dis_modified));
                int sum = INF;
                int ma = 0;
                for (int i = 0; i < dis_modified.size(); i ++) {
                        sum = min(sum, dis_modified[i].first + ma);
                        ma = max(ma, dis_modified[i].second);
                }
                sum = min(sum, ma);
                int res = shift + flip_cnt + 2 * sum;
                ans = min(ans, res);
        }
        return ans;
}
int main() {
        string a, b;
        cin >> a >> b;
        int n = a.size();
        if (b == string(n, '0')) {
                cout << (a == string(n, '0') ? 0 : -1) << endl;
                return 0;
        }
        int ans = solve(a, b);
        reverse(all(a));
        reverse(all(b));
        ans = min(ans, solve(a, b));
        cout << ans << endl;
        return 0;
}

Atcoder Regular Contest 054 B. ムーアの法則

Atcoder Regular Contest 054 B. ムーアの法則

B: ムーアの法則 - AtCoder Regular Contest 054 | AtCoder

感想

はじめて三分探索を書いた。凸関数の解を求めるときに使えるやつ。零点が手で計算できるときはそっちの方が良いんだと思う。

解法

三分探索で、はい。
一般的な書き方は知らないので、とりあえず動くように適当に書いた。

実装

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

static const int INF = 0x3f3f3f3f;

int main() {
        double p;
        cin >> p;
        double lb = 0, ub = (double) INF;
        int loop = 1000;
        double newp_left, newp_right;
        while (loop --) {
                double left = lb + (ub - lb) / 3.0;
                double right = lb + (ub - lb) * 2.0 / 3.0;
                newp_left = left + p / pow(2.0, left / 1.5);
                newp_right = right + p / pow(2.0, right / 1.5);
                if (newp_left < newp_right) ub = right;
                else lb = left;
        }
        cout << setprecision(15) << newp_right << endl;
        return 0;
}

Atcoder Regular Contest 076 E. Connected?

Atcoder Regular Contest 076 E. Connected?

E: Connected? - AtCoder Regular Contest 076 | AtCoder

感想

だいぶ前に線分の交差判定などで解こうとしたけどダメだったので放置していた。条件をもう少し本質的にとらえることと、周を1次元に落とし込むことの両方ができていなかった。

解法

まず線分の少なくとも一方の端点が長方形の周上にない場合は、この線分はないものとして考えて良い（他の線分を妨げることがないため）。

端点が両方周上にあるものについて、その端点を$\ A\ $と$\ a\ $というようなペアで考える。このとき、周上のある点からぐるっと一周しながら点をみていったときに、$\ A, B, a, b\ $というような順番になっていればこれらの一方はどうしても結ぶことができない。逆に、うまく結ぶことができる順番というのは、かっこ（）を矛盾なく組み合わせたような順番である。例えば（（（））（））が$\ A, B, C, c, b, D, d, a\ $などに対応する。ここまで考えるとあとはstackで簡単に書ける。

実装は簡単。

実装

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

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

int h, w;

bool on(int y, int x) {
        if (x == 0 || x == w || y == 0 || y == h) return true;
        return false;
}

int convert(int y, int x) {
        if (x == 0) return y;
        if (y == h) return h + x;
        if (x == w) return h + w + h - y;
        if (y == 0) return h + w + h + w - x;
        assert(0);
}

int main() { int n;
        cin >> h >> w >> n;
        vector<pii> pos;
        for (int i = 0; i < n; i ++) {
                int y1, x1, y2, x2;
                cin >> y1 >> x1 >> y2 >> x2;
                if (on(y1, x1) && on(y2, x2)) {
                        pos.push_back(mp(convert(y1, x1), i));
                        pos.push_back(mp(convert(y2, x2), i));

                }
        }
        sort(all(pos));
        stack<int> st;
        for (int i = 0; i < pos.size(); i ++) {
                if (st.empty() || st.top() != pos[i].second) st.push(pos[i].second);
                else st.pop();
        }
        cout << (st.empty() ? "YES" : "NO") << endl;
        return 0;
}

Atcoder Regular Contest 079 F. Namori Grundy

Atcoder Regular Contest 079 F. Namori Grundy

F: Namori Grundy - AtCoder Regular Contest 079 | AtCoder

感想

こういうグラフをNamoriグラフというらしい。

解法

まずグラフの形状が常に閉路を一つ含み、そこから木が外側に向かって生えたようなグラフになることに気づかねばならない。証明は絵を描いてごにょればわかる。

こうすると閉路に含まれない頂点のgrundy数$\ g\ $は葉から決めていくことで確定する。あとは閉路の部分の$\ g\ $が矛盾なく決定できるかどうかを見る。

さて、閉路中のある頂点$\ v\ $に注目し、$\ g\ $がすでに確定している遷移先の$\ g\ $の$\ mex\ $を$\ m\ $とすると、まだ確定していない遷移先$\ u\ $について、$\ g_u = m\ $となるならば、この数を加えた$\ mex\ $が$\ g_v\ $になり、$\ g_u \neq m\ $ならば$\ g_v = m\ $とすれはよいので、結局この2つを$\ g_v\ $として試して整合性をチェックすれば良い。

実装は汚くなってしまった。

実装

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

static const int INF = 0x3f3f3f3f;

vector<int> g[202020];
int grundy[202020];
bool used[202020];

int dfs(int v, int prev) {
        used[v] = true;
        set<int> s;
        for (auto u : g[v]) if (u != prev) {
                if (used[u]) s.insert(grundy[u]);
                else s.insert(dfs(u, v));
        }
        if (s.count(-1)) return grundy[v] = -1;
        int g = 0;
        while (s.count(g)) g ++;
        return grundy[v] = g;
}

int main() {
        int n;
        cin >> n;
        for (int i = 0; i < n; i ++) {
                int p;
                cin >> p;
                p --;
                g[p].push_back(i);
        }
        memset(grundy, -1, sizeof(grundy));
        for (int i = 0; i < n; i ++) if (!used[i]) dfs(i, -1);
        int start;
        for (int i = 0; i < n; i ++) {
                if (grundy[i] == -1) {
                        start = i;
                        break;
                }
        }
        set<int> s;
        for (auto t : g[start]) {
                if (grundy[t] == -1) continue;
                s.insert(grundy[t]);
        }
        int mi1 = 0, mi2 = 0;
        while (s.count(mi1)) mi1 ++;
        s.insert(mi1);
        while (s.count(mi2)) mi2 ++;
        grundy[start] = mi1;
        int check[202020] = { 0 };
        for (int i = 0; i < n; i ++) if (grundy[i] == -1) check[i] = -1;
        for (int i = 0; i < n; i ++) if (grundy[i] == -1) used[i] = false;
        for (int i = 0; i < n; i ++) if (!used[i]) dfs(i, -1);
        set<int> s1;
        for (auto t : g[start])  s1.insert(grundy[t]);
        int gr = 0;
        while (s1.count(gr)) gr ++;
        if (gr == grundy[start]) {
                cout << "POSSIBLE" << endl;
                return 0;
        }
        for (int i = 0; i < n; i ++) if (check[i] == -1) grundy[i] = -1;
        grundy[start] = mi2;
        for (int i = 0; i < n; i ++) if (grundy[i] == -1) used[i] = false;
        for (int i = 0; i < n; i ++) if (!used[i]) dfs(i, -1);
        set<int> s2;
        for (auto t : g[start]) s2.insert(grundy[t]);
        gr = 0;
        while (s2.count(gr)) gr ++;
        if (gr == grundy[start]) {
                cout << "POSSIBLE" << endl;
                return 0;
        }
        cout << "IMPOSSIBLE" << endl;
        return 0;
}

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