Atcoder Grand Contest 008 F. Black Radius

Atcoder Grand Contest 008 F. Black Radius

F: Black Radius - AtCoder Grand Contest 008 | AtCoder

感想

こちらのei1333さんの記事†全方位木DP†について - ei1333の日記で全方位木dpの概念を学んだところだったので、そこまで苦労しなかった。わかりやすい記事をありがとうございます。

解法

まず重複しないようにすべての配色を数えるために、各頂点について、それが中心になるような配色としてありえるものを数えるという方針をとる。これを辺についても同じように考える。これらの頂点や辺が異なれば、必ずその配色も異なることは明らかである。

まず頂点を$\ v\ $に固定して考える。もしこの点がお気に入りの点であるならば、その半径$\ r\ $とすると、$\ 0 \leq r \leq d_1\ $の範囲で連続的に$\ r\ $を動かしていくことができる。そしてこれらは明らかに異なる配色になる。この上限$\ d_1\ $というのは、絵を書いてみればわかるように、$\ v\ $が中心になるようにするためには、$\ v\ $からのびる部分木の中で、深さが2番目に大きいものでなければいけない。　

この点がお気に入りの点でない場合は、その半径を$\ r\ $とすると、$\ d_2 \leq r \leq d_1\ $の範囲で連続的に変化させることができる。ただし、$\ d_1\ $は上と同じである。一方下限の方は、まずその色を塗るためのお気に入りの点が含まれている部分木がある必要がある。その頂点から、$\ v\ $を通り越して別の部分木に同じだけの$\ r\ $の範囲を塗るものでなければいけないので、その部分木というのは十分深さの小さいものが好ましい。お気に入りの点を含む部分木の中で、深さが最小のもののその深さを$\ d\ $とすると、その部分木内はすべて黒に塗り尽くしてさらに$\ v\ $を通り越して$\ r\ $だけ塗ることになるのだが、結局この$\ r\ $というのは$\ d\ $に一致しているので、この$\ d\ $が下限$\ d_2\ $である。

次に辺が中心になる場合を考える。少し考察すれば、ある辺が中心になるような配色というのは高々1個しかない。なぜなら、その辺が接続する頂点を$\ u, v\ $として、$\ u, v\ $からそれぞれの部分木を同時に塗っていくとき、そのどちらか一方が塗り終わるまでは明らかにどの頂点を選んでもうまく塗ることができない。そして一方が塗り終わったその時に限り、その辺が中心になるようなバランスを崩すことなく、その塗り終えた部分木の中からある頂点を選んでそこから上手く塗ることができる。よってこのようなことができるどうかの判定は、$\ u, v\ $を根とする部分木のうち深さが小さい方にお気に入りの点が含まれているかどうかを見るだけで良い。

実装は、まず1回目のdfs1では、$\ 0\ $を根とする根付き木について、各部分木の最大の深さfarとその部分木にお気に入りの点が含まれているかどうかのin_favを順に求めておく。

次に、2回目のdfs2をする。親の自分を除く部分木についての最大の深さと、親と自分以外の部分木の中にお気に入りの点が存在するかどうか、という情報を伝播させている。

そのような部分木をchildrenにいれ、その中でもお気に入りの点を含むような部分木を特にfav_childrenにいれる。そしてchildrenについてはその中で2番目に大きいものを記録し、fav_childrenについては最も浅いものを記録する。

辺に関する探索は各頂点から次の頂点に移動する、その直前にちょうど必要な情報が揃っているので、それでぱぱっと答えに足しておく。

実装自体は書いてみたあとでは意外と単純なことに気がつく。全方位木dpについて注意することは、とにかく「次に探索しようとする部分木の情報（自分自身の情報）」が入らないようにして伝播させること。そして根の次数が$\ 1\ $である場合などにうまく適切な値を伝播させることができるように、最初に適切な初期値をchildrenなどの中にいれておくこと。

実装

#include "bits/stdc++.h"
using namespace std;
 
#define all(x)  x.begin(), x.end()
#define mp      make_pair
#define pii     pair<int, int>
 
int n;
vector<int> g[202020];
bool fav[202020];
int far[202020];
int second_farthest[202020];
int closest[202020];
bool in_fav[202020];
long long ans = 0;
 
static const int INF = 0x3f3f3f3f;
 
void dfs1(int v, int prev) {
        if (fav[v]) in_fav[v] = true;
        for (auto u : g[v]) if (u != prev) {
                dfs1(u, v);
                in_fav[v] |= in_fav[u];
                far[v] = max(far[v], far[u] + 1);
        }
}
 
void dfs2(int v, int ma, bool par_fav, int prev) {
        vector<pair<pii, bool>> children;
        children.push_back(mp(mp(0, -1), false));
        for (auto u : g[v]) {
                if (u == prev) children.push_back(mp(mp(ma + 1, u), par_fav));
                else children.push_back(mp(mp(far[u] + 1, u), in_fav[u]));
        }
        vector<pii> fav_children;
        for (auto c : children) if (c.second) fav_children.push_back(mp(c.first.first, c.first.second));
        sort(all(fav_children));
        if (fav_children.empty()) closest[v] = INF;
        else closest[v] = fav_children[0].first;
        sort(all(children), greater<pair<pii, bool>>());
        second_farthest[v] = children[1].first.first;
        for (auto u : g[v]) if (u != prev) { 
                int maa = children[u == children[0].first.second ? 1 : 0].first.first;
                bool par_f = fav[v] || par_fav;
                if (!in_fav[u]) par_f |= !fav_children.empty();
                else par_f |= fav_children.size() > 1;
                ans += (maa < far[u] && par_f) || (maa > far[u] && in_fav[u]) || (maa == far[u] && (par_f || in_fav[u]));
                dfs2(u, maa, par_f, v);
        }
}
 
int main() {
        cin >> n;
        for (int i = 0; i < n - 1; i ++) {
                int a, b;
                cin >> a >> b;
                a --, b --;
                g[a].push_back(b);
                g[b].push_back(a);
        }
        string s;
        cin >> s;                                            
        for (int i = 0; i < n; i ++) fav[i] = s[i] == '1' ? true : false;
        dfs1(0, -1);
        dfs2(0, 0, fav[0], -1);
        for (int i = 0; i < n; i ++) {
                if (fav[i]) ans += 1 + second_farthest[i];
                else ans += max(0, 1 + (second_farthest[i] - closest[i]));
        }
        cout << ans << endl;
        return 0;
}

Atcoder Grand Contest 017 E. Jigsaw

Atcoder Grand Contest 017 E. Jigsaw

E: Jigsaw - AtCoder Grand Contest 017 | AtCoder

感想

新しい感じのdfsをした。

解法

まずある右（左）の形状に対して、対応する左（右）の形状が一意に定まることに注意する。このうまくフィットする形状同士を同一の値（形状が変わる高さ）で管理する。ただし、左右のどちらの形状で何回現れたのかは記録しておく。同じブロックの左右の形状についてその値同士で辺を張っておく。

さて、まず、ある形状の値について床につかないようなパーツの方が多くなっていればこの時点で構成不可能である。逆に、床につくパーツの方が多い分には全く問題ない。なぜなら、そのようなパーツは端っことして使えるからである。この問題では完成したブロックの連結成分が1個でなくてもよいことに注意すること。

次に、この接合部分に関する（各個別の部分、ではなく）dfsをする。言い換えると、すべての同一形状の接合部分は一気に探索する。そして、逐一その個数に関するチェックをし、端っこのパーツをうまく決めれるかどうかをみる。

説明が全然できてない感じがするけど...

実装

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

vector<int> g[505];
int l_cnt[505], r_cnt[505];
bool used[505];

int print(bool ok) {
        if (ok) cout << "YES" << endl;
        else cout << "NO" << endl;
        return 0;
}

bool dfs(int v) {
        used[v] = true;
        bool res = l_cnt[v] != r_cnt[v];
        for (auto u : g[v]) if (!used[u]) res |= dfs(u);
        return res;
}

int main() {      
        int n, h, a, b, c, d;
        cin >> n >> h;
        for (int i = 0; i < n; i ++) {
                cin >> a >> b >> c >> d;
                int lh = (c == 0 ? a : c + 250);
                int rh = (d == 0 ? b + 250 : d);
                l_cnt[lh] ++;
                r_cnt[rh] ++;
                g[lh].push_back(rh);
                g[rh].push_back(lh);
        }
        for (int i = 0; i < h + 1; i ++) if (r_cnt[i] > l_cnt[i]) return print(0);
        for (int i = 251; i < h + 251; i ++) if (l_cnt[i] > r_cnt[i]) return print(0);
        for (int i = 0; i < 501; i ++) if (!used[i]) if (!g[i].empty()) if (!dfs(i)) return print(0);
        return print(1);
}

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