Yukicoder No.69 文字を自由に並び替え

,

https://yukicoder.me/problems/no/69

solution

高級言語で書くなら、ソートして一致するか見ればよい。$O(N \log N)$。 そうでなければ、rolling hashのように多項式を使ったhash関数$H(x) = \sum f(x_i)$を用いて比較する。加算に$O(a)$で乗算を$O(b)$と仮定すると$O(N(a + b)^{\mathrm{deg}(f)})$。

implementation

提出: https://yukicoder.me/submissions/202298

整形前

#!/usr/bin/env bfi
>
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++> O
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++> N
>
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++> S
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++> E
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++> Y
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++> V
[ +[-<+] ]
#
+[->,+]
<-[+[-<]>[>]<-]
<[-<]
<[>>[>]+[>]<[-<]<-]

#
>>[>]>[>]<
[
    >+++>+<[->[-<<[->>>+>+<<<<]>>>>[-<<<<+>>>>]<<]>[-<+>]<<]
    >[<<[<]<[<]<+>>[>]>[>]>-]
    <<[-]
    <
]
#
<[
    >+++>+<[->[-<<[->>>+>+<<<<]>>>>[-<<<<+>>>>]<<]>[-<+>]<<]
    >[<<[<]<->>[>]>-]
    <<[-]
    <
]
<[<]<[.<]
daaaaaaaaa
bbbbbbbbba

Japan Alumni Group Summer Camp 2017 Day 3: F - Endless BFS

,

http://jag2017summer-day3.contest.atcoder.jp/tasks/jag2017summer_day3_f

頂点への訪問情報をふたつ持つDFSでいけそうと言っていたら、後輩が(同じなのだが)二部グラフだと整理してくれた。 実装は彼に任せた。でも変なDijkstraライブラリ貼ってバグらせてた。

problem

与えられたグラフ上で問題文中のBFSっぽいコードを実行して、停止するか、するとしたら何ステップ後か答えよ。

solution

元の頂点をそれぞれ複製し辺は斜めに貼り替えて二部グラフを作る。 これが連結でなければ停止しない。 この上でBFSし、それぞれの色の中での距離の最大値を求め、そのふたつの中の最小値が答え。

implementation

#include <algorithm>
#include <cstdio>
#include <limits>
#include <queue>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;

vector<int> breadth_first_search(int root, vector<vector<int> > const & g) {
    vector<int> dist(g.size(), numeric_limits<int>::max());
    queue<int> que;
    dist[root] = 0;
    que.push(root);
    while (not que.empty()) {
        int i = que.front();
        que.pop();
        for (int j : g[i]) if (dist[j] == numeric_limits<int>::max()) {
            dist[j] = dist[i] + 1;
            que.push(j);
        }
    }
    return dist;
}

int main() {
    int n, m; scanf("%d%d", &n, &m);
    vector<vector<int> > g(2 * n);
    repeat (i, m) {
        int u, v; scanf("%d%d", &u, &v); -- u; -- v;
        g[u].push_back(v + n);
        g[v + n].push_back(u);
        g[v].push_back(u + n);
        g[u + n].push_back(v);
    }
    vector<int> dist = breadth_first_search(0, g);
    int a = *max_element(dist.begin(), dist.begin() + n);
    int b = *max_element(dist.begin() + n, dist.end());
    int result = min(a, b);
    if (result == numeric_limits<int>::max()) result = -1;
    printf("%d\n", result);
    return 0;
}

Japan Alumni Group Summer Camp 2017 Day 3: E - Route Calculator

,

http://jag2017summer-day3.contest.atcoder.jp/tasks/jag2017summer_day3_e

チームメンバーに任せた(私のlaptopの電源が切れたので)が、バグったので私が$0$から書き直した。 私$\to$彼と私$\gets$彼のどちらの向きでも、大きめのコードをバグらせたら交代して$0$からが良いと踏んでいるがどうなのだろうか。

problem

下図のような文字列が与えられる。左上から右下への経路で、それを数式として読んだとき最大になるようなものの値を答えよ。

8+9*4*8
*5*2+3+
1*3*2*2
*5*1+9+
1+2*2*2
*3*6*2*
7*7+6*5
*5+7*2+
3+3*6+8

solution

*, +を辺と見てそれぞれだけでグラフ$G_\times, G_+$を作る。 この上でDP。 頂点$(y, x)$から$G_\times$の辺を任意回使って到達可能な頂点から$G_+$の辺をちょうど$1$本使っていける頂点の値を見ていい感じにする。 右下まで直接行ける場合は例外。 $O(H^2W^2)$。

implementation

#include <cctype>
#include <cmath>
#include <cstdio>
#include <queue>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_reverse(i, n) for (int i = (n)-1; (i) >= 0; --(i))
using ll = long long;
using namespace std;
template <class T> inline void setmax(T & a, T const & b) { a = max(a, b); }

int main() {
    // input
    int h, w; scanf("%d%d", &h, &w);
    vector<char> f(h * w);
    repeat (y, h) repeat (x, w) {
        scanf(" %c", &f[y * w + x]);
    }

    // solve
    // // make graphs
    vector<vector<int> > mul(h * w);
    vector<vector<int> > add(h * w);
    repeat (y, h) repeat (x, w) if (isdigit(f[y * w + x])) {
        int z = y * w + x;
        if (y + 1 < h) {
            auto & g = (f[(y + 1) * w + x] == '*' ? mul : add);
            if (y + 2 < h) g[z].push_back((y + 2) * w + x);
            if (x + 1 < w) g[z].push_back((y + 1) * w + (x + 1));
        }
        if (x + 1 < w) {
            auto & g = (f[y * w + (x + 1)] == '*' ? mul : add);
            if (x + 2 < w) g[z].push_back(y * w + (x + 2));
            if (y + 1 < h) g[z].push_back((y + 1) * w + (x + 1));
        }
    }
    // // dp
    vector<double> dp(h * w);
    vector<double> muls(h * w);
    queue<int> que;
    repeat_reverse (y, h) repeat_reverse (x, w) if (isdigit(f[y * w + x])) {
        int z = y * w + x;
        muls.assign(h * w, - INFINITY);
        muls[z] = f[z] - '0';
        que.push(z);
        while (not que.empty()) {
            int z = que.front();  // shadowing
            que.pop();
            for (int nz : mul[z]) {
                if (isinf(muls[nz])) {
                    que.push(nz);
                }
                setmax(muls[nz], muls[z] * (f[nz] - '0'));
            }
        }
        repeat (nz, h * w) if (not isinf(muls[nz])) {
            for (int nnz : add[nz]) {
                setmax(dp[z], muls[nz] + dp[nnz]);
            }
        }
        setmax(dp[z], muls[h * w - 1]);
    }

    // output
    if (dp[0] <= 1e16 and ll(dp[0]) <= 1000000000000000ll) {
        printf("%lld\n", ll(dp[0]));
    } else {
        printf("-1\n");
    }
    return 0;
}

Japan Alumni Group Summer Camp 2017 Day 3: D - Janken Master

,

http://jag2017summer-day3.contest.atcoder.jp/tasks/jag2017summer_day3_d

AtCoderのレートが高いとじゃんけんで有利であるのは有名事実ですが、斜め読みしてる英文中に出てくると混乱するのでやめてほしい。

problem

$N$人でじゃんけんをする。自分以外の人はあらかじめ決められた確率に従い手を得らぶ。 引き分けならレートが最も高い人が勝ち。

solution

bit DP。$O(N3^N)$。$t \subseteq s \subseteq n = \{ 0, 1, \dots, n - 1 \}$な対$(t, s)$は$3^n$個存在する。 引き分けの確率は勝ちも負けもしない確率として$1$からの引き算で求めると楽。

implementation

#include <array>
#include <cstdio>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i, m, n) for (int i = (m); (i) < int(n); ++(i))
using namespace std;
template <class T> inline void setmax(T & a, T const & b) { a = max(a, b); }

int main() {
    // input
    int n; scanf("%d", &n);
    int a0; scanf("%d", &a0);
    vector<int> a(n - 1);
    vector<array<double, 3> > p(n - 1);
    repeat (i, n - 1) {
        scanf("%d", &a[i]);
        repeat (hand, 3) {
            int q; scanf("%d", &q);
            p[i][hand] = q / 100.0;
        }
    }

    // solve
    vector<double> dp(1 << (n - 1));
    dp[0] = 1.0;
    repeat_from (s, 1, 1 << (n - 1)) {
        repeat (hand, 3) {
            double acc = 0;
            double q_win  = 0;
            double q_lose = 0;
            for (int t = 0; ; t = (t - s) & s) {  // t \subseteq s, t \ne s
                if (t == s) break;
                { // win
                    double q = 1.0;
                    repeat (i, n - 1) {
                        if (t & (1 << i)) {
                            q *= p[i][hand];
                        } else if (s & (1 << i)) {
                            q *= p[i][(hand + 2) % 3];
                        }
                    }
                    q_win += q;
                    acc += q * dp[t];
                }
                { // lose
                    double q = 1.0;
                    repeat (i, n - 1) {
                        if (t & (1 << i)) {
                            q *= p[i][hand];
                        } else if (s & (1 << i)) {
                            q *= p[i][(hand + 1) % 3];
                        }
                    }
                    q_lose += q;
                }
            }
            double q_draw = 1.0 - q_win - q_lose;
            int max_a = 0;
            repeat (i, n - 1) {
                if (s & (1 << i)) {
                    setmax(max_a, a[i]);
                }
            }
            if (max_a < a0) {
                acc += q_draw;
            }
            setmax(dp[s], acc);
        }
    }

    // output
    printf("%.8lf\n", dp[(1 << (n - 1)) - 1]);
    return 0;
}

Japan Alumni Group Summer Camp 2017 Day 3: C - Ninja Map

,

http://jag2017summer-day3.contest.atcoder.jp/tasks/jag2017summer_day3_c

これもバグらせた。それでも私が全部実装する方が速いと思うがやはり不安定。本番こけたらごめんなさいという気持ち。

problem

$N \times N$の格子がある。 頂点番号はshuffleされている。 その$2N^2 - 2N$個の接続関係が全て与えられるので、そのようなものをひとつ構築せよ。

solution

次数が$2$のものをひとつ選んで左上に置き、その隣をひとつ決めれば、後は次数や接続関係が整合するように一意に定まる。 $O(N^2)$。

implementation

#include <algorithm>
#include <cassert>
#include <cstdio>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define whole(x) begin(x), end(x)
using namespace std;
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }
const int dy[] = { -1, 1, 0, 0 };
const int dx[] = { 0, 0, 1, -1 };
bool is_on_field(int y, int x, int h, int w) { return 0 <= y and y < h and 0 <= x and x < w; }

int main() {
    // input
    int n; scanf("%d", &n);
    vector<vector<int> > g(n * n);
    repeat (i, 2 * n * (n - 1)) {
        int a, b; scanf("%d%d", &a, &b); -- a; -- b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    // solve
    auto f = vectors(n, n, -1);
    vector<bool> used(n * n);
    auto use = [&](int y, int x, int i) {
        assert (not used[i]);
        f[y][x] = i;
        used[i] = true;
    };
    repeat (i, n * n) {
        if (g[i].size() == 2) {
            use(0, 0, i);
            break;
        }
    }
    auto touch = [&](int py, int px, int y, int x, int degree) {
        int i = f[py][px];
        for (int j : g[i]) if (not used[j] and g[j].size() == degree) {
            bool valid = true;
            repeat (k, 4) {
                int ny = y + dy[k];
                int nx = x + dx[k];
                if (not is_on_field(ny, nx, n, n)) continue;
                if (f[ny][nx] == -1) continue;
                if (not count(whole(g[j]), f[ny][nx])) {
                    valid = false;
                    break;
                }
            }
            if (valid) {
                use(y, x, j);
                return;
            }
        }
        assert (false);
    };
    repeat (y, n) {
        repeat (x, n - 1) {
            int degree = 4 - (y == 0 or y == n - 1) - (x + 1 == n - 1);
            touch(y, x, y, x + 1, degree);
        }
        if (y + 1 < n) {
            int degree = 3 - (y + 1 == n - 1);
            touch(y, 0, y + 1, 0, degree);
        }
    }

    // output
    repeat (y, n) {
        repeat (x, n) {
            printf("%d%c", f[y][x] + 1, x < n - 1 ? ' ' : '\n');
        }
    }
    return 0;
}

Japan Alumni Group Summer Camp 2017 Day 3: B - Slimming Plan

,

http://jag2017summer-day3.contest.atcoder.jp/tasks/jag2017summer_day3_b

実装が下手でバグらせた。 $D$日ずつまとめて見ていくところを除算でしていたのが悪かった。 チームメンバーにloopでやればよさそうと言われ修正してAC。

problem

体重を$S$から$T$以下に減らしたい。 $d \in \mathbb{N}$日目には体重が$w_{d \bmod D}$減る。 最初に$T$以下になるのは何日目か。

solution

$D$日ずつまとめて飛ばしていき、最後の付近は$1$日ずつ見る。 $D$日間の途中で大きく減るが最後に戻して$1$周期で見るとあまり減らないケースのため、$D$日間での最小値を持つ必要があることに注意。 上手くやれば$O(D)$、安全に倒して書けば$O(D + T)$。

implementation

#include <cstdio>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
using ll = long long;
using namespace std;
template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); }

ll solve(ll s, ll t, ll d, vector<int> const & w) {
    ll delta = 0;
    ll min_delta = 0;
    repeat (i, d) {
        if (s + delta <= t) return i;
        delta += w[i];
        setmin(min_delta, delta);
    }
    if (delta >= 0) return -1;
    ll i = 0;
    ll acc = 0;
    for (; s + acc + min_delta > t; i += d) {
        acc += delta;
    }
    for (; s + acc > t; ++ i) {
        acc += w[i % d];
    }
    return i;
}

int main() {
    int s, t, d; scanf("%d%d%d", &s, &t, &d);
    vector<int> w(d); repeat (i, d) scanf("%d", &w[i]);
    ll result = solve(s, t, d, w);
    printf("%lld\n", result);
    return 0;
}

Japan Alumni Group Summer Camp 2017 Day 3: A - Star in Parentheses

,

http://jag2017summer-day3.contest.atcoder.jp/tasks/jag2017summer_day3_a

後からチーム内の練習会で解いた。全体では$6$完。 詳細: https://not-522.appspot.com/contest/6295146601644032

problem

balancedな括弧の列中に*で示された位置のnestの深さを答えよ。

implementation

#!/usr/bin/env python3
s = input()
left = s[: s.index('*')]
print(left.count('(') - left.count(')'))

CODE FESTIVAL 2017 qual A: D - Four Coloring

,

http://code-festival-2017-quala.contest.atcoder.jp/tasks/code_festival_2017_quala_d

問題文を読んでとりあえず雑に上から貪欲に決めていく実験を書き綺麗な模様を見たが、コードに落とすのを面倒がって貪欲を修正したもので通そうとした。 盤面の境界の影響でずれなどがあり、できそうに見えたが思っていたより難しくて時間を解かした。 結果は日本人内$63$位でパフォはぎりぎり橙。ボーダーは$60$位だったようで通過失敗。 まああと$2$回あるし通るでしょという気はするが、つらい。

solution

実験。$d$が奇数なら市松模様でよい。 $d$が偶数なら$45$度回転したような市松模様。

implementation

#include <cstdio>
#include <string>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

vector<vector<char> > solve(int h, int w, int d) {
    w = max(2 * h, w);
    auto f = vectors(h, w, char());
    if (d % 2 == 1) {
        repeat (y, h) repeat (x, w) {
            f[y][x] = (y + x) % 4 + 1;
        }
    } else {
        int k1 = d;
        int k2 = 0;
        int k3 = d;
        int k4 = 0;
        int dir = + 1;
        repeat (y, h) {
            string s = dir > 0 ?
                string(k1, '\x01') + string(k2, '\x02') + string(k3, '\x03') + string(k4, '\x04') :
                string(k2, '\x02') + string(k1, '\x01') + string(k4, '\x04') + string(k3, '\x03') ;
            repeat (x, w) {
                f[y][x] = s[((- y + x) % (2 * d) + 2 * d) % (2 * d)];
            }
            if (k1 - dir * 2 < 0 or k2 + dir * 2 < 0) dir *= -1;
            k1 -= dir * 2;
            k2 += dir * 2;
            k3 -= dir * 2;
            k4 += dir * 2;
        }
    }
    return f;
}

int main() {
    // input
    int h, w, d; scanf("%d%d%d", &h, &w, &d);

    // solve
    auto f = solve(h, w, d);

    // output
    repeat (y, h) {
        repeat (x, w) {
            printf("%c", ".RYGB"[f[y][x]]);
        }
        printf("\n");
    }
    return 0;
}

CODE FESTIVAL 2017 qual A: C - Palindromic Matrix

,

http://code-festival-2017-quala.contest.atcoder.jp/tasks/code_festival_2017_quala_c

solution

$H, W$が奇数のときちょうど中央はまったく自由。 上を除いて、$H$が奇数のとき中央の行は$1$個決めたらもう$1$個も決まる。 それ以外は$1$個決めたらもう$3$個決まる。 つまり$4, 2, 1$刻みで文字種を消費していくことになる。そのようにすれば構成までできる。 $O(HW)$。

implementation

#include <array>
#include <cassert>
#include <cstdio>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;

bool solve(int h, int w, array<int, 26> cnt) {
    int r1 = (h % 2) * (w % 2);
    int r2 = (h % 2) * (w / 2) + (w % 2) * (h / 2);
    assert  ((h * w - 2 * r2 - r1) % 4 == 0);
    int r4 = (h * w - 2 * r2 - r1) / 4;
    for (int c = 0; r4 --; ) {
        while (c < 26 and cnt[c] < 4) ++ c;
        if (c == 26) return false;
        cnt[c] -= 4;
    }
    for (int c = 0; r2 --; ) {
        while (c < 26 and cnt[c] < 2) ++ c;
        if (c == 26) return false;
        cnt[c] -= 2;
    }
    return true;
}

int main() {
    // input
    int h, w; scanf("%d%d", &h, &w);
    array<int, 26> cnt = {};
    repeat (y, h) repeat (x, w) {
        char c; scanf(" %c", &c);
        cnt[c - 'a'] += 1;
    }
    // solve
    bool result = solve(h, w, cnt);
    // output
    printf("%s\n", result ? "Yes" : "No");
    return 0;
}

CODE FESTIVAL 2017 qual A: B - fLIP

,

http://code-festival-2017-quala.contest.atcoder.jp/tasks/code_festival_2017_quala_b

最近競プロを始めた友人はここで詰まっていた。 解けるだろうのに勘違いで落としたようで、後から解法聞いて「なんか悔しいので以降の予選も受けます」って言ってたので将来有望ぽい。

solution

行内や列内での位置は無視できるので、$R$行$C$列反転させると決まれば黒いマスの数が分かる。 $O(HW)$で総当たりすればよい。

implementation

#include <cstdio>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
int main() {
    int h, w, k; scanf("%d%d%d", &h, &w, &k);
    bool result = false;
    repeat (y, h + 1) {
        repeat (x, w + 1) {
            if (y * w + x * h - 2 * y * x == k) {
                result = true;
            }
        }
    }
    printf("%s\n", result ? "Yes" : "No");
    return 0;
}


AtCoder Regular Contest 080: E - Young Maids

,

http://arc080.contest.atcoder.jp/tasks/arc080_c

editorialはOld Maidsになってるの何故。そもそもメイド要素どこ?

solution

逆向きに考える。segment木とpriority queueでいい感じにして$O(N \log N)$。

最終的な$q$の$q_0, q_1$が最初の$p$の$p_i, p_j$だったとすると$i \lt j$であり、$[0, i), [i + 1, j), [j + 1, N)$の範囲をそれぞれ使い切った後に$p_i, p_j$を使うことから$i \equiv j - (i + 1) \equiv N - (j + 1) \equiv 0 \pmod{2}$でなければならない。 逆にこの条件を満たすような$p_i, p_j$は$q$の先頭に持っていける。

単純にはこれを再帰ですればよい。 $i, j$を探すのにはsegment木を使う。 $[0, i), [i + 1, j), [j + 1, N)$のそれぞれについて再帰し結果をmerge sortでまとめればよい。しかしこれでは$O(N^2)$かかり間に合わない。 そこでpriority queueを上手く使う。 $p_i$とできる最小値を優先度として区間$[l, r)$をqueueに入れ、DFSだった再帰をBFSに直したような形で行えばよい。 これは$O(N \log N)$になるので間に合う。

implementation

#include <algorithm>
#include <cassert>
#include <cstdio>
#include <limits>
#include <queue>
#include <tuple>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_reverse(i, n) for (int i = (n)-1; (i) >= 0; --(i))
using namespace std;
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;

template <class Monoid>
struct segment_tree {
    typedef Monoid monoid_type;
    typedef typename Monoid::underlying_type underlying_type;
    int n;
    vector<underlying_type> a;
    Monoid mon;
    segment_tree() = default;
    segment_tree(int a_n, underlying_type initial_value = Monoid().unit(), Monoid const & a_mon = Monoid()) : mon(a_mon) {
        n = 1; while (n < a_n) n *= 2;
        a.resize(2*n-1, mon.unit());
        fill(a.begin() + (n-1), a.begin() + (n-1 + a_n), initial_value); // set initial values
        repeat_reverse (i, n-1) a[i] = mon.append(a[2*i+1], a[2*i+2]); // propagate initial values
    }
    void point_set(int i, underlying_type z) { // 0-based
        a[i+n-1] = z;
        for (i = (i+n)/2; i > 0; i /= 2) { // 1-based
            a[i-1] = mon.append(a[2*i-1], a[2*i]);
        }
    }
    underlying_type range_concat(int l, int r) { // 0-based, [l, r)
        underlying_type lacc = mon.unit(), racc = mon.unit();
        for (l += n, r += n; l < r; l /= 2, r /= 2) { // 1-based loop, 2x faster than recursion
            if (l % 2 == 1) lacc = mon.append(lacc, a[(l ++) - 1]);
            if (r % 2 == 1) racc = mon.append(a[(-- r) - 1], racc);
        }
        return mon.append(lacc, racc);
    }
};
template <typename T>
struct min_indexed_t {
    typedef pair<T, int> underlying_type;
    underlying_type unit() const { return make_pair(numeric_limits<T>::max(), -1); }
    underlying_type append(underlying_type a, underlying_type b) const { return min(a, b); }
};

int main() {
    // input
    int n; scanf("%d", &n);
    vector<int> p(n); repeat (i, n) scanf("%d", &p[i]);
    assert (n % 2 == 0);

    // solve
    segment_tree<min_indexed_t<int> > even(n), odd(n);
    repeat (i, n) {
        auto & segtree = (i % 2 == 0 ? even : odd);
        segtree.point_set(i, make_pair(p[i], i));
    }
    reversed_priority_queue<tuple<int, int, int> > que;
    auto push = [&](int l, int r) {
        if (l == r) return;
        auto & left  = (l % 2 == 0 ? even : odd);
        int x = left.range_concat(l, r - 1).first;
        que.emplace(x, l, r);
    };
    push(0, n);
    vector<int> result;
    while (not que.empty()) {
        int l, r; tie(ignore, l, r) = que.top(); que.pop();
        auto & left  = (l % 2 == 0 ? even : odd);
        auto & right = (l % 2 == 0 ? odd : even);
        int m1 = left.range_concat(l, r - 1).second;
        int m2 = right.range_concat(m1 + 1, r).second;
        result.push_back(p[m1]);
        result.push_back(p[m2]);
        push(l, m1);
        push(m1 + 1, m2);
        push(m2 + 1, r);
    }

    // output
    repeat (i, n) {
        printf("%d%c", result[i], i < n - 1 ? ' ' : '\n');
    }
    return 0;
}

AOJ 1244. Molecular Formula

,

「先輩のコードは見た目が重たい」と言われた。 競プロ始めたころから気になってはいるが、int parse_molecules(string::const_iterator & first, string::const_iterator last, map<string, int> const & weight);と全部global変数なint MO(char *p);とだと前者を選びたい気がするし、かといってclassを切るのはそれはそれで重いので困っている。

solution

再帰下降構文解析。Moleculeの規則が左再帰を含むのでいい感じに除去する。入力全体の文字数$N$に対し$O(N)$。

implementation

#include <cassert>
#include <cctype>
#include <iostream>
#include <map>
using namespace std;

struct unknown_atom_exception {};
int parse_number(string::const_iterator & first, string::const_iterator last) {
    assert (first != last);
    int n = 0;
    while (first != last and isdigit(*first)) {
        n *= 10;
        n += *first - '0';
        ++ first;
    }
    return n;
}
string parse_atom(string::const_iterator & first, string::const_iterator last) {
    assert (first != last);
    assert (isupper(*first));
    string name;
    name += *first;
    ++ first;
    if (first != last and islower(*first)) {
        name += *first;
        ++ first;
    }
    return name;
}
int parse_molecules(string::const_iterator & first, string::const_iterator last, map<string, int> const & weight);
int parse_molecule(string::const_iterator & first, string::const_iterator last, map<string, int> const & weight) {
    assert (first != last);
    int value;
    if (isalpha(*first)) {
        string atom = parse_atom(first, last);
        if (weight.count(atom)) {
            value = weight.at(atom);
        } else {
            throw unknown_atom_exception {};
        }
    } else {
        assert (*first == '(');
        ++ first;
        value = parse_molecules(first, last, weight);
        assert (*first == ')');
        ++ first;
    }
    if (first != last and isdigit(*first)) {
        value *= parse_number(first, last);
    }
    return value;
}
int parse_molecules(string::const_iterator & first, string::const_iterator last, map<string, int> const & weight) {
    assert (first != last);
    int value = 0;
    while (first != last and *first != ')') {
        value += parse_molecule(first, last, weight);
    }
    return value;
}
int parse(string const & s, map<string, int> const & weight) {
    try {
        auto it = s.begin();
        return parse_molecules(it, s.end(), weight);
    } catch (unknown_atom_exception e) {
        return -1;
    }
}

int main() {
    map<string, int> weight;
    while (true) {
        string atom; cin >> atom;
        if (atom == "END_OF_FIRST_PART") break;
        cin >> weight[atom];
    }
    while (true) {
        string expr; cin >> expr;
        if (expr == "0") break;
        int result = parse(expr, weight);
        if (result == -1) {
            cout << "UNKNOWN" << endl;
        } else {
            cout << result << endl;
        }
    }
    return 0;
}

AtCoder Regular Contest 083: E - Bichrome Tree

,

http://arc083.contest.atcoder.jp/tasks/arc083_c

solution

木DP。さらに各頂点でknapsack問題のDP。$O(NX)$。

各部分木において、その根を白に塗ったときの黒の頂点の重みの総和の最小値、その根を黒に塗ったときの白の頂点の重みの総和の最小値、をそれぞれ求めるDPをすればよい。 色を反転させれば同じになるので根は必ず白で塗ると仮定してよい。 黒の頂点の重みの総和の最小値は、子についてそれぞれ求めた後$X$が小さいことを利用してknapsack問題を解くことで求まる。

implementation

#include <algorithm>
#include <cstdio>
#include <functional>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define whole(x) begin(x), end(x)
using namespace std;
template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); }

constexpr int inf = 1e9+7;
int main() {
    // input
    int n; scanf("%d", &n);
    vector<vector<int> > children(n);
    repeat (i, n - 1) {
        int p; scanf("%d", &p); -- p;
        children[p].push_back(i + 1);
    }
    vector<int> x(n); repeat (i, n) scanf("%d", &x[i]);

    // solve
    vector<int> dp(n);
    function<void (int)> go = [&](int i) {
        vector<int> cur(x[i] + 1, inf);
        cur[0] = 0;
        for (int j : children[i]) {
            go(j);
            vector<int> prv = move(cur);
            cur.assign(x[i] + 1, inf);
            repeat (acc, prv.size()) if (prv[acc] < inf) {
                if (acc +  x[j] <= x[i]) setmin(cur[acc +  x[j]], prv[acc] + dp[j]);
                if (acc + dp[j] <= x[i]) setmin(cur[acc + dp[j]], prv[acc] +  x[j]);
            }
        }
        dp[i] = *min_element(whole(cur));
    };
    go(0);
    bool result = dp[0] < inf;

    // output
    printf("%s\n", result ? "POSSIBLE" : "IMPOSSIBLE");
    return 0;
}

AtCoder Grand Contest 001: D - Arrays and Palindrome

,

solution

等式制約の片側(つまり「先頭の a1 文字、続く a2 文字、さらに続く a3 文字 … はすべて回文である。」)を図示すると次のようになる。 $a = ( 5, 8, 1, 3 )$である。

          +-------------+
+-------+ | +---------+ |
| +---+ | | | +-----+ | |   +---+
| |   | | | | | +-+ | | |   |   |
A B C b a D E F G g f e d H I J i

このようなグラフを$b$についても作って繋げたときに連結になっていればよい。 各点の次数は高々$2$なので、連結であれば木か閉路のどちらか。 $a$中に奇数の項が$3$つ以上あるとき次数を考えれば明らかに不可能である。

$a$中の奇数の項が$2$つ以下なら可能である。 これは両端に奇数の項を配し、偶数の項には$1$だけずらして以下のように重ねればできる。

+-------------+
| +---------+ |
| | +-----+ | |
| | | +-+ | | |
A B C D d c b a z
  | | | +-+ | | |
  | | +-----+ | |
  | +---------+ |
  +-------------+

implementation

#!/usr/bin/env python3
def solve(n, m, a):
    odd = []
    even = []
    for a_i in a:
        if a_i % 2 == 0:
            even += [ a_i ]
        else:
            odd += [ a_i ]
    if len(odd) >= 3:
        return None
    a, b = [], []
    if odd:
        x = odd.pop()
        a += [ x ]
        b += [ x - 1 ]
    else:
        x = even.pop()
        a += [ x ]
        b += [ x - 1 ]
    a += even
    b += even
    if odd:
        x = odd.pop()
        a += [ x ]
        b += [ x + 1 ]
    else:
        b += [ 1 ]
    return a, b

n, m = map(int, input().split())
a = list(map(int, input().split()))
it = solve(n, m, a)
if it is None:
    print('Impossible')
else:
    a, b = it
    b = list(filter(lambda b_i: b_i, b))
    print(*a)
    print(len(b))
    print(*b)

AtCoder Grand Contest 004: D - Teleporter

,

http://agc004.contest.atcoder.jp/tasks/agc004_d

solution

テレポーターの転移先がひとつであることと制約「どの町から出発しても、テレポーターを何回か使うことで首都へ辿り着ける。」により、グラフは首都を根とする有向木のような形になっている。 この木の葉で最も深いものを選んで$K-1$番目の親を首都へ繋ぎ直すことを繰り返すだけでよい。 これを愚直に実装すれば解ける。ただしDFSで整理すればおそらくもっと楽で、計算量は$O(N)$になるだろう。

implementation

実装方針を間違えたため長くなった。

#include <cassert>
#include <cstdio>
#include <functional>
#include <queue>
#include <set>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;

int main() {
    // input
    int n, k; scanf("%d%d", &n, &k);
    vector<int> a(n);
    repeat (i, n) {
        scanf("%d", &a[i]);
        -- a[i];
    }

    // solve

    // // make the graphs
    int result = 0;
    if (a[0] != 0) {
        a[0] = 0;  // make the graph a tree
        ++ result;
    }
    vector<set<int> > b(n);  // backward digraph
    repeat (i, n) {
        b[a[i]].insert(i);
    }

    // // define things
    vector<int> valid(n, -1);
    function<void (int, int)> mark_valid = [&](int i, int limit) {
        if (valid[i] >= limit) return;
        valid[i] = limit;
        if (limit) {
            for (int j : b[i]) if (j != i) {
                mark_valid(j, limit - 1);
            }
        }
    };
    vector<int> depth(n, -1); {
        function<void (int)> go = [&](int i) {
            for (int j : b[i]) if (j != i) {
                depth[j] = depth[i] + 1;
                go(j);
            }
        };
        depth[0] = 0;
        go(0);  // connectivity is assumed
    }
    vector<bool> is_leaf(n);
    priority_queue<pair<int, int> > leaves;
    function<void (int)> update_leaf = [&](int i) {
        if (i == 0) return;
        if (not b[i].empty()) return;
        if (is_leaf[i]) return;
        is_leaf[i] = true;
        leaves.emplace(depth[i], i);
    };
    auto relink = [&](int i) {
        if (a[i] == 0) return;
        int a_i = a[i];
        ++ result;
        b[a[i]].erase(i);
        a[i] = 0;
        b[0].insert(i);
        mark_valid(i, k - 1);
        update_leaf(a_i);
    };
    auto k1th_parent = [&](int i) {
        repeat (iteration, k - 1) {
            i = a[i];
            if (i == 0) break;
        }
        return i;
    };

    // // run
    mark_valid(0, k);
    repeat (i, n) {
        update_leaf(i);
    }
    while (not leaves.empty()) {
        int i = leaves.top().second;
        leaves.pop();
        if (valid[i] == -1) {
            int j = k1th_parent(i);
            relink(j);
        }
        assert (valid[i] != -1);
    }

    // output
    printf("%d\n", result);
    return 0;
}