bit演算による集合の列挙

,

順序数

簡単のための略記としてVon Neumannによる順序数を有限の範囲で導入しておく。 つまり自然数$n \ge 0$は集合$\{ 0, 1, 2, \dots, n - 1 \}$と同一視するものとする。

順序数$n$の部分集合$x \subseteq n$

$2^n$個存在。

昇順に列挙:

for (int x = 0; x < (1 << n); ++ x) {
    ...
}

逆順にしたい場合も簡単。

集合$z$の部分集合$y \subseteq z$

$2^{|z|}$個。

昇順なら:

for (int y = 0; ; y = (y - z) & z) {
    ...
    if (y == z) break;
}

降順なら:

for (int y = z; ; y = (y - 1) & z) {
    ...
    if (y == 0) break;
}

更新部分は-- y &= xとしてもよい。

集合$x$を包含する集合$y \supseteq x$ (ただし$y \subseteq n$)

$2^{n - |y|}$個。

昇順:

for (int y = x; y < (1 << n); y = (y + 1) | x) {
    ...
}

更新部分は++ y |= xとしてもよい。

降順に列挙するには次の$x \subseteq y \subseteq z$において$z = n$とすればよい。

集合$x, y$に対し集合$y$で$x \subseteq y \subseteq z$

$2^{|z| - |x|}$個。

$z \setminus x$の部分集合$y^{-}$を列挙して$y = y^{-} \cup x$とすればよい。

要素数$|x| = k$な集合$x$ (ただし$x \subseteq n$)

${}_nC_k$個。

昇順:

for (int x = (1 << k) - 1; x < (1 << n); ) {
    ...
    int t = x | (x - 1);
    x = (t + 1) | (((~ t & - ~ t) - 1) >> (__builtin_ctz(x) + 1));
}

更新部分は次のようにもできるが、除算を含むため遅い。

    int y = x & - x;
    int z = x + y;
    x = (((x & ~ z) / y) >> 1) | z;

集合$y$の要素のsingleton $\{ x \} \; \text{for} \; x \in y$

${}_{|y|}C_1 = |y|$個。

昇順:

for (int x = y & - y; x; x = y & (~ y + (x << 1))) {
    ...
}

更新はy = x & ~ (x - (y << 1))でもよい。 立っているbitだけを考えたときに連続する$k$bitなども同じ更新方法で列挙できるが、あまり使わないだろう。

$x$から最下位bitを取り出して破壊的に消していくのでもよい。

要素数$|x| = k$な部分集合$x \subseteq y$

${}_{|y|}C_k$個。

難しいようだ。 $k$が定数の場合に限るが、singletonの取り出しで$k$重loopを作ることで実現可能。 $x \supseteq z$という制約を加えたいときは、要素数を固定しない場合にしたのと同様の修正をする。

参考文献


AtCoder Regular Contest 078: F - Mole and Abandoned Mine

,

http://arc078.contest.atcoder.jp/tasks/arc078_d

solution

$1$から$N$への単純pathの頂点が完全代表系になるように成分に分解して、同じ成分間の辺のコストの総和を最大化。定数倍を頑張る。$O(N2^{3N})$で抑えられる。

残す唯一$1$から$N$への単純path $P$を固定したとする。 このとき$P$に含まれない辺でも、$P$の唯一性を保てるなら削除しなくてよい。 そのための条件を整理する。 $P$に含まれない辺の集合$E$を残せるのは、$E$による部分グラフの連結成分を見たときに$P$の両端含む頂点が全て異なる成分に属すとき。 辺はできるだけ残したいので、$P$の頂点と同じ数の連結成分ができるのが最適。 ここで$P$の頂点集合しか見ておらず、path中での順序が無視できる。

よって次のようにする。 まず集合$X \subseteq V = \{ 1, 2, \dots, N \}$のそれぞれについて、$X$に含まれる頂点のみを使ってできる$1$から$N$への単純pathの重みの最大値$\mathrm{cost}(X)$を計算する。 これは$O((N + M)2^N)$のDPで求まる。 次に集合$X \subseteq V$に含まれない頂点$Y = V \setminus X$を$X$のどの頂点に対応する連結成分に入れるかを考える。 これは$X$の頂点をひとつずつ見ていきながら、$\mathrm{dp}(y) \gets f(\mathrm{dp}(x), y \setminus x)$ for $x, y \subseteq V$な感じの$O(N2^{2N})$で抑えられるDP。

下手な書き方をすると間に合わないが、適切に実装すれば余裕を持って通る。

implementation

#include <cassert>
#include <cstdio>
#include <functional>
#include <tuple>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;
template <class T> inline void setmax(T & a, T const & b) { a = max(a, b); }
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); }

inline int singleton(int i) { return 1 << i; }
inline int setminus(int s, int t) { return s & ~ t; }
inline int complement(int s, int n) { return setminus((1 << n) - 1, s); }
inline bool is_a(int i, int s) { return s & (1 << i); }

vector<int> calculate_component_wieghts(int n, vector<tuple<int, int, int> > const & edges) {
    vector<int> component_wieght(1 << n);
    repeat (x, 1 << n) {
        for (auto edge : edges) {
            int a, b, c; tie(a, b, c) = edge;
            if (is_a(a, x) and is_a(b, x)) {
                component_wieght[x] += c;
            }
        }
    }
    return component_wieght;
}

vector<int> enumerate_paths(int n, vector<vector<pair<int, int> > > const & g) {
    const int start = 0;
    const int goal = n - 1;
    vector<vector<int> > dp = vectors(n, 1 << n, -1);
    dp[start][1 << start] = 0;
    repeat (used, 1 << n) {
        repeat (i, n) if (is_a(i, used) and dp[i][used] != -1) {
            for (auto edge : g[i]) {
                int j, cost; tie(j, cost) = edge;
                if (is_a(j, used)) continue;
                setmax(dp[j][used | singleton(j)], dp[i][used] + cost);
            }
        }
    }
    return dp[goal];
}

int use_remaining_edges(int used, int n, vector<tuple<int, int, int> > const & edges, vector<int> const & component_wieght) {
    vector<int> cur(1 << n, -1), prv;
    cur[0] = 0;
    int acc = 0;
    repeat (i, n) if (is_a(i, used)) {
        cur.swap(prv);
        cur.assign(1 << n, -1);
        int z = complement(acc | used, n);
        for (int x = 0; ; x = (x - z) & z) { // x \subseteq z
            int zx = z ^ x; // z \setminus x
            for (int y = 0; ; y = (y - zx) & zx) { // y \subseteq zx
                setmax(cur[x | acc | y | singleton(i)], prv[x | acc] + component_wieght[y | singleton(i)]);
                if (y == zx) break;
            }
            if (x == z) break;
        }
        acc  ^= singleton(i);
        used ^= singleton(i);
    }
    return cur[(1 << n) - 1];
}

int solve(int n, vector<vector<pair<int, int> > > const & g, vector<tuple<int, int, int> > const & edges) {
    auto path = enumerate_paths(n, g);
    auto component_wieght = calculate_component_wieghts(n, edges);
    int result = 0;
    repeat (used, 1 << n) if (path[used] != -1) {
        setmax(result, path[used] + use_remaining_edges(used, n, edges, component_wieght));
    }
    int total_cost = 0; for (auto edge : edges) total_cost += get<2>(edge);
    return total_cost - result;
}

int main() {
    // input
    int n, m; scanf("%d%d", &n, &m);
    vector<vector<pair<int, int> > > g(n);
    vector<tuple<int, int, int> > edges(m);
    repeat (i, m) {
        int a, b, c; scanf("%d%d%d", &a, &b, &c); -- a; -- b;
        edges[i] = { a, b , c };
        g[a].emplace_back(b, c);
        g[b].emplace_back(a, c);
    }
    // solve
    int result = solve(n, g, edges);
    // output
    printf("%d\n", result);
    return 0;
}

AtCoder Regular Contest 078: E - Awkward Response

,

http://arc078.contest.atcoder.jp/tasks/arc078_c

コーナーケース多い感じなどがなんだかICPCっぽい問題。 ガードレールにぶち当てながらアクセル全開にする感じのプログラミングするのやめたい (やめない)。

solution

実験。judge側は自明なのでこれを書いていい感じのツールに食わせて手元でひたすら試す。

その結果得られるのが以下のアルゴリズム。$O(\log N)$。

  • まずはそのままの二分探索で$\mathrm{str}(N)$の先頭の数字を決定
    • 次で$k = 1$のときはここで得られた数字は嘘なので、最後のstepの前に空文字列のような扱いにしておく
  • 次に$9, 99, 999, \dots$のようにして答えの桁数$k$を決定
    • ただし先頭の数字が$9$ならば$1, 10, 100, 1000, \dots$とする
    • $N = 1$のときは停止しないので、$k$が十分大きくなったら打ち切ってそう答える
  • 最後に答えを構成。上の桁から順番に二分探索
    • ただし最後の桁は別で、末尾に$0$を付ける必要がある。例えばそこまでが$3456$と判明してるときは$345650, 345680, 345690$などと試す。

implementation

#!/usr/bin/env python3

def binsearch(l, r, pred): # [l, r)
    assert l < r
    l -= 1
    while r - l > 1:
        m = (l + r) // 2
        if pred(m):
            r = m
        else:
            l = m
    return r

import sys
def pred(n):
    assert 1 <= n and n <= 10 ** 18
    print('?', n)
    sys.stdout.flush()
    return input() == 'Y'

def solve():
    s = ''
    s += str(binsearch(1, 9 + 1, lambda c: not pred(int(s + str(c)))) - 1)

    if s == '9':
        f = lambda k: pred(int('1' + '0' * k))
    else:
        f = lambda k: not pred(int('9' * k))
    k = 1
    while f(k):
        k += 1
        if k >= 13:
            return 1
    if k == 1:
        s = ''

    for _ in range(k - 2):
        s += str(binsearch(0, 9 + 1, lambda c: not pred(int(s + str(c)))) - 1)
    s += str(binsearch(0, 9 + 1, lambda c: pred(int(s + str(c) + '0'))))

    return int(s)

print('!', solve())

judge program

#!/usr/bin/env python3
import sys
import random

import argparse
parser = argparse.ArgumentParser()
parser.add_argument('N', nargs='?', default=random.randint(1, 10 ** 9), type=int)
args = parser.parse_args()
y = args.N
print('[*] y =', y, file=sys.stderr)

for k in range(65):
    c, x = input().split()
    x = int(x)
    print('[*] %d-th query: %s %d' % (k, c, x), file=sys.stderr)
    assert 1 <= x <= 10 ** 18
    if c == '?':
        if (x <= y and str(x) <= str(y)) or (x > y and str(x) > str(y)):
            result = 'Y'
        else:
            result = 'N'
        print(result)
        sys.stdout.flush()
        print('[*] %d-th query: %s' % (k, result), file=sys.stderr)
    elif c == '!':
        assert y == x
        break
    else:
        assert False
    sys.stdout.flush()

AtCoder Regular Contest 078: D - Fennec VS. Snuke

,

http://arc078.contest.atcoder.jp/tasks/arc078_b

solution

ad-hoc。 お互いにできるだけ相手に近付くように一直線に伸ばしていく。 一度黒色と白色のマスが隣接するとそれ以降はどう塗って最終的に塗れる頂点は同じ。そのような境界で黒い木と白い木の$2$本に分割されるが、どちらの色の木が大きいかが答え。 $O(N)$。

implementation

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

int main() {
    // input
    int n; scanf("%d", &n);
    vector<vector<int> > g(n);
    repeat (i, n - 1) {
        int a, b; scanf("%d%d", &a, &b); -- a; -- b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    // solve
    vector<int> parent(n, -1);
    vector<int> size(n, 1);
    vector<int> depth(n);
    function<void (int)> go = [&](int i) {
        for (int j : g[i]) if (j != parent[i]) {
            parent[j] = i;
            depth[j] = depth[i] + 1;
            go(j);
            size[i] += size[j];
        }
    };
    go(0);
    int i = n - 1;
    repeat (j, (depth[n - 1] - 1) / 2) {
        i = parent[i];
    }
    int second = size[i];
    int first = n - second;
    // output
    printf("%s\n", first > second ? "Fennec" : "Snuke");
    return 0;
}

AtCoder Regular Contest 078: C - Splitting Pile

,

http://arc078.contest.atcoder.jp/tasks/arc078_a

友人が

高々10^5の数字でも10^9個も足すと普通にオーバーフローするって事を学習しました。

って言っていました。みんな一度はやったことあるやつ。

solution

$2$回舐める。まず総和を計算して、前から累積和を取って答え(の候補)を更新しつつもう$1$周。$O(N)$。

implementation

#include <algorithm>
#include <cstdio>
#include <numeric>
#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))
#define whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using ll = long long;
using namespace std;
template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); }

int main() {
    int n; scanf("%d", &n);
    vector<ll> a(n); repeat (i, n) scanf("%lld", &a[i]);
    ll x = a[0];
    ll y = whole(accumulate, a, 0ll) - a[0];
    ll result = abs(x - y);
    repeat_from (i, 1, n - 1) {
        x += a[i];
        y -= a[i];
        setmin(result, abs(x - y));
    }
    printf("%lld\n", result);
    return 0;
}

Yukicoder No.545 ママの大事な二人の子供

,

サンプルが弱いようには見えないがなぜかすり抜け$2$WAを生やした。

solution

半分全列挙。$A_i$と$- B_i$のどちらかを選んで足し合わせると言い換えて、絶対値を$0$に近付けるようにする。$O(2^\frac{N}{2})$。

implementation

#include <algorithm>
#include <cassert>
#include <climits>
#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))
#define whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using ll = long long;
using namespace std;
template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); }

template <typename UnaryPredicate>
ll binsearch(ll l, ll r, UnaryPredicate p) { // [l, r), p is monotone
    assert (l < r);
    -- l;
    while (r - l > 1) {
        ll m = (l + r) / 2;
        (p(m) ? r : l) = m;
    }
    return r; // = min { x in [l, r) | p(x) }, or r
}

vector<ll> calc_sums(int l, int r, vector<ll> const & a, vector<ll> const & b) {
    vector<ll> cur, prv;
    cur.push_back(0);
    repeat_from (i, l, r) {
        cur.swap(prv);
        cur.clear();
        for (ll x : prv) {
            cur.push_back(x + a[i]);
            cur.push_back(x - b[i]);
        }
    }
    whole(sort, cur);
    cur.erase(whole(unique, cur), cur.end());
    return cur;
}

ll solve(int n, vector<ll> const & a, vector<ll> const & b) {
    if (n == 1) {
        return min(a[0], b[0]);
    }
    vector<ll> left  = calc_sums(0, n / 2, a, b);
    vector<ll> right = calc_sums(n / 2, n, a, b);
    ll result = LLONG_MAX;
    for (ll x : left) {
        int i = binsearch(0, right.size(), [&](int i) {
            return x + right[i] >= 0;
        });
        for (int di = -1; di <= +1; ++ di) {
            if (0 <= i + di and i + di < right.size()) {
                setmin(result, abs(x + right[i + di]));
            }
        }
    }
    return result;
}

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

ICPC 2017 国内予選: F. リボンたたみ

,

$2$進数でいい感じにするのだろうけどなんだか面倒だな、と思ってたら後輩氏が解法を投げてきた問題。

入出力が入手できていないのでACをするかどうかは未確認

solution

印の高さに注目すれば、$k$回目の折り畳みの操作において上側になるか下側になるかが定まる。これから操作列が復元できる。$O(n)$。

最後の折り畳みの後に印のついた位置は上から$i$番目にある。このときリボンの厚み$h = 2^n$として$i <= h/2$であれば最後の折り畳みにおいて印は上側であったことが分かり、そうでなければ下側であったと分かる。 そのようにすると最後から$2$番目の折り畳みの後に上から何番目の層に印があるかが分かる。 再帰的にすると各$k$回目の折り畳みの後に上から何番目の層に印があるかが分かり、特に$k$回目の折り畳みにおいて印が上側か下側かが分かる。

この情報を参照すると、印が左から$j$番目にあるという情報と合わせると最初の折り畳みがLRが決定する。 この後に左から何番目かは分かるので、これも再帰的にやる。

implementation

#include <iostream>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
using ll = long long;
using namespace std;

int main() {
    while (true) {
        int n; ll i, j; cin >> n >> i >> j;
        if (n == 0 and i == 0 and j == 0) break;
        vector<bool> is_up(n); {
            ll y = i - 1;
            repeat (k, n) {
                ll mid = 1ll << (n - k - 1);
                if (y < mid) {
                    is_up[n - k - 1] = true;
                    y = mid - y - 1;
                } else {
                    y -= mid;
                }
            }
        }
        string result; {
            ll x = j - 1;
            repeat (k, n) {
                ll mid = 1ll << (n - k - 1);
                if (is_up[k]) {
                    if (x < mid) {
                        result += 'L';
                        x = mid - x - 1;
                    } else {
                        result += 'R';
                        x = mid - (x - mid) - 1;
                    }
                } else {
                    if (x < mid) {
                        result += 'R';
                    } else {
                        result += 'L';
                        x -= mid;
                    }
                }
            }
        }
        cout << result << endl;
    }
    return 0;
}

ICPC 2017 国内予選: 参加記

,

http://icpc.iisf.or.jp/2017-tsukuba/domestic/

cormoranこうきとチームTEAM NAGATOとして参加した。 ABCDEGの$6$完遅くて$13$位。

チーム

今年から私の師匠であるところのizが参加権を失なった (つらい)。 なので有望な後輩がチームに加わった。

大学からは全体で$5$チーム出場。以前と比べてすごく増えた。

模擬国内の結果などから$2$チーム目のアジア進出が期待されていた。 結果としては$2$チーム目は$39$位で、繰り上がり多数でなければ進出失敗。 我々のチームがなければ通過できている順位ではある。 私が選抜条件を勘違いしてぬか喜びさせてしまったのは申し訳なかった。

インフラ

問題を解くには当然ネットワーク環境が必要。 監督の先生に確保して貰った教室には静的IPが降ってきており、ルータとスイッチでLANを構築し以下を繋いだ。

  • 計算機$5$台
  • プリンタ$3$台

以前はDHCPであったのだが、今年は静的IPが降ってくる。しかし渡されたルータは安物のためDHCP/PPPoEのみしか設定できないという問題が発生。ファームウェアの更新などをしてもだめなので、仕方なく他の場所からルータを外して持ってくることになった。

プリンタは例年の様に苦労した。$3$台あったが$2$台しかネットワークには繋がらなかった。 そして本番で実質的に動いたのは$0$台といった状況。 混乱を避けるため開始直後に我々のチームが$2$台のプリンタを用いて全チーム分の印刷をする手筈でそのようにしたのだが、ジョブをたくさん投げたのにまったく紙が出てこなかった。 結局は監督権限で遠い場所のプリンタが用いられた。 障害の原因のひとつはFirefoxから直接印刷をしたためで、いったんPDFに変換してから印刷や直接lpすると(多少は)印刷が可能のようだった。 思えばFirefoxによる問題は昨年も発生していたので、来年はきちんと対処したい。

/etc/sudoers破壊の実績が解除された。 借りた計算機の設定の際にどうしてもroot権限が必要であり、頻繁に要求されて面倒なのでsudo権限を付与しようということになった。 visudoを用いて設定を変更したが記述ミスによりこれが論理的に破壊されてしまい、任意のlogin可能なuserが一切の権限を失った。 visudoは編集結果のsyntax errorを防ぐのみでありsemanticsのerrorは素通りしてしまう。wheelsudoといった名前のuser groupに対象userを追加するのが安全面での正解。 しかたがないのでUbuntuのlive USBを作成し、そちらからbootして復元することで対処した。 UEFI secure bootの問題やHDDの暗号化とかがあったら詰んでいるところだったが運が良かった。

インフラ構築で手間取ったのでリハーサルはほぼ行えず。 リハーサルといえば、B1さんたちのチームはそもそも$3$限に食われてリハーサル終了後に会場到着していた。ICPCで単位が出る大学に行きたい。

作戦

チームの作戦は次。そのように行なわれた。

  • ABCを他のメンバーを信じて全て任せ、私がGやHを読む。

「全部私が読んでそのまま実装し、バグらせたりしたら助けてもらう」という案も存在したが、それでは面白くないしそのようなギリギリを攻めなくても通るだろうという判断により棄却された。 アジアではありかもと思っている (ふたりに比べて私の英語力が低いので読解を任せたい)。

本番

ABは全て任せて通してもらった。 次にCは私が見る側でペアプロ、なんだか実質的に私が書いてた感じもあるがキーボードには触れなかった。 予定通りEDGはこの順に私が解いて私が書いた。 Dの制約見落としして「なんでこんなに解かれてるんだ?」って言ったりもした。 DEは私が得意な種類の問題なので、もう少し難しくしてGHぐらいに置いてほしかった。 実装は間に合わなかったが、Fはこうきくんが解法を見つけていた。Hはまあやればできそうだし全完チームの存在はまあ分かる。


ICPC 2017 国内予選: G. 迷宮を一周

,

チームメンバーの助けを多いに借りて、いい感じに実装したらあまりよく分からないまま通った。

solution

左手法、つまり壁に沿って一周するのでよい。$O(HW)$だと思う。

注意するのは次のような場合。不用意に細道に入ってはいけない。

...#.#...
...#.#...
...#.#...
...#.#...
...#.#...
.........
.........
.........

いい感じに実装する。

implementation

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

const int dx[] = {0, 1, 0, -1}; // up right down left
const int dy[] = {-1, 0, 1, 0};

bool solve(int h, int w, const vector<string> & f) {
    auto is_on_field = [&](int y, int x) {
        return 0 <= x and x < w and 0 <= y and y < h;
    };
    vector<vector<bool> > visited(h, vector<bool>(w));
    function<bool (int, int, int, int)> go = [&](int y, int x, int tresuare, int left_hand) {
        assert (is_on_field(y, x) and f[y][x] == '.');
        if (y == 0     and x == w - 1 and tresuare == 0) tresuare += 1;
        if (y == h - 1 and x == w - 1 and tresuare == 1) tresuare += 1;
        if (y == h - 1 and x ==     0 and tresuare == 2) tresuare += 1;
        if (y == 0     and x ==     0 and tresuare == 3) return true;
        if (visited[y][x]) return false;
        visited[y][x] = true;
        for (int rotate = -1; rotate <= 1; ++ rotate) {
            int dir = (left_hand + rotate + 1) % 4;
            int ny = y + dy[dir];
            int nx = x + dx[dir];
            if (is_on_field(ny, nx) and f[ny][nx] == '.') {
                if (go(ny, nx, tresuare, (left_hand + rotate + 4) % 4)) return true;
            }
        }
        return false;
    };
    return go(0, 0, 0, 0);
}

int main() {
    while(true) {
        int h, w; cin >> h >> w;
        if (h == 0 and w == 0) break;
        vector<string> f(h);
        repeat (y, h) cin >> f[y];
        bool result = solve(h, w, f);
        cout << (result ? "YES" : "NO") << endl;
    }
}

ICPC 2017 国内予選: E. 論理式圧縮機

,

solution

文法はLL(1)なので再帰下降構文解析やるだけ。 ここで定義される論理式$E$は$4$つの真偽値$a, b, c, d \in 2 = \{ 0, 1 \}$から真偽値への関数と見做せる。 つまり$E : 2^4 \to 2$であり、そのような関数はちょうど$65536 = 2^{2^4}$種しかない。 これら全てに対してそれを表現するのに必要な記号列の長さを事前計算しておけば、各クエリに対しては構文解析$O(|E|)$の後に表引きで$O(1)$で答えられる。 表の構築は、例えばBellman-Ford法のように、変化がなくなるまで更新し続けるDPで無理矢理やればよい。

implementation

#include <bitset>
#include <cassert>
#include <iostream>
#include <queue>
#include <tuple>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < (n); ++ (i))
using namespace std;

//                         fed          210
const bitset<16> bitset_a("1111111100000000");
const bitset<16> bitset_b("1111000011110000");
const bitset<16> bitset_c("1100110011001100");
const bitset<16> bitset_d("1010101010101010");
bitset<16> evaluate(string::const_iterator & first, string::const_iterator last) {
    assert (first != last);
    if (*first == '0') {
        ++ first;
        return bitset<16>();
    } else if (*first == '1') {
        ++ first;
        return bitset<16>().flip();
    } else if (*first == 'a') {
        ++ first;
        return bitset_a;
    } else if (*first == 'b') {
        ++ first;
        return bitset_b;
    } else if (*first == 'c') {
        ++ first;
        return bitset_c;
    } else if (*first == 'd') {
        ++ first;
        return bitset_d;
    } else if (*first == '-') {
        ++ first;
        return bitset<16>(evaluate(first, last)).flip();
    } else {
        assert (*first == '(');
        ++ first;
        auto l = evaluate(first, last);
        char op = *first;
        ++ first;
        auto r = evaluate(first, last);
        assert (*first  == ')');
        ++ first;
        if (op == '^') {
            return l ^ r;
        } else if (op == '*') {
            return l & r;
        } else {
            assert (false);
        }
    }
}
bitset<16> evaluate(string const & s) {
    string::const_iterator it = s.begin();
    auto value = evaluate(it, s.end());
    assert (it == s.end());
    return value;
}

constexpr int inf = 1e9+7;
vector<int> generate_table() {
    vector<int> table(1 << 16, inf);
    queue<pair<int, int> > que;
    auto push = [&](bitset<16> value, int length) {
        if (length < table[value.to_ulong()]) {
            table[value.to_ulong()] = length;
            que.emplace(length, value.to_ulong());
        }
    };
    push(bitset<16>(), 1); // 0
    push(bitset<16>().flip(), 1); // 1
    push(bitset_a, 1);
    push(bitset_b, 1);
    push(bitset_c, 1);
    push(bitset_d, 1);
    while (not que.empty()) {
        int int_value, length; tie(length, int_value) = que.front(); que.pop();
        if (table[int_value] < length) continue;
        bitset<16> value(int_value);
        repeat (i, 1<<16) if (table[i] != inf) {
            push(bitset<16>(value).flip(), length + 1);
            push(value ^ bitset<16>(i), length + table[i] + 3);
            push(value & bitset<16>(i), length + table[i] + 3);
        }
    }
    return table;
}

int main() {
    auto table = generate_table();
    while (true) {
        string s; cin >> s;
        if (s == ".") break;
        auto value = evaluate(s);
        cout << table[value.to_ulong()] << endl;
    }
}

ICPC 2017 国内予選: D. 弁当作り

,

問題文の$1 \le n \times m \le 500$は太字で書かれていて親切。しかし印刷した紙ではまったく気付かなかった。

solution

$n \times m \le 500$の制約を使って場合分け。$n$が小さいときはレシピの部分集合を全部試して$O(2^nm)$。$m$が小さいときは余った食材を引数とするDPで$O(n2^m)$。

implementation

#include <bitset>
#include <cassert>
#include <iostream>
#include <tuple>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < (n); ++ (i))
using namespace std;

int main() {
    while (true) {
        int n, m; cin >> n >> m;
        if (n == 0 and m == 0) break;
        vector<vector<bool> > b(n, vector<bool>(m));
        repeat (y, n) {
            repeat (x, m) {
                char c; cin >> c;
                b[y][x] = c - '0';
            }
        }
        int result = 0;
        // if ((1ll << n) < (n * (1ll << m))) {
        if (m >= 20) {
            // n is small
            vector<bitset<500> > bs(n);
            repeat (y, n) {
                repeat (x, m) {
                    bs[y][x] = b[y][x];
                }
            }
            vector<pair<bitset<500>, int> > cur, prv;
            cur.emplace_back(bitset<500>(), 0);
            repeat (i, n) {
                cur.swap(prv);
                cur = prv;
                for (auto const & it : prv) {
                    bitset<500> bs_j; int cnt; tie(bs_j, cnt) = it;
                    if ((bs[i] ^ bs_j).none()) {
                        result = max(result, cnt + 1);
                    }
                    cur.emplace_back(bs[i] ^ bs_j, cnt + 1);
                }
            }
        } else {
            assert (m < 30);
            // m is small
            vector<int> bi(n);
            repeat (y, n) {
                repeat (x, m) {
                    if (b[y][x]) {
                        bi[y] |= 1 << x;
                    }
                }
            }
            vector<int> cur(1 << m, -1), prv;
            cur[0] = 0;
            repeat (i, n) {
                cur.swap(prv);
                cur = prv;
                repeat (j, 1 << m) if (prv[j] != -1) {
                    if ((bi[i] ^ j)  == 0) {
                        result = max(result, prv[j] + 1);
                    }
                    cur[bi[i] ^ j] = max(cur[bi[i] ^ j],  prv[j] + 1);
                }
            }
        }
        cout << result << endl;
    }
}

ICPC 2017 国内予選: C. 池のある庭園

,

solution

縦幅$d \le 10$かつ横幅$w \le 10$と小さい。 枠となる長方形を全て試し、内部についても愚直にやる。$O((dw)^3)$。

implementation

本番にペアプロしたやつそのまま。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int inf = 1e9 + 7;

int main() {
    int h, w;
    while (cin >> h >> w) {
        if (h == 0 && w == 0) break;
        vector<vector<ll> > e(h, vector<ll> (w));
        for (int y = 0; y < h; y ++) {
            for (int x = 0; x < w; x ++) {
                cin >> e[y][x];
            }
        }
        ll ans = 0;
        for (int ly = 0; ly < h; ly ++) {
            for(int lx = 0; lx < w; lx ++) {
                for (int ry = ly + 2; ry < h; ry ++) {
                    for (int rx = lx + 2; rx < w; rx ++) { //[l, r]
                        ll sum = 0;
                        ll ma = 0, mi = inf;
                        for (int y = ly; y <= ry; y ++) {
                            mi = min(mi, e[y][lx]);
                            mi = min(mi, e[y][rx]);
                        }
                        for (int x = lx + 1; x <= rx - 1; x ++) {
                            mi = min(mi, e[ly][x]);
                            mi = min(mi, e[ry][x]);
                        }
                        for (int y = ly + 1; y <= ry - 1; y ++) {
                            for (int x = lx + 1; x <= rx - 1; x ++) {
                                ma = max(ma, e[y][x]);
                                sum += e[y][x];
                            }
                        }
                        if (mi > ma) ans = max(ans, mi * ((ry - ly - 1) * (rx - lx - 1)) - sum); 
                    }
                }
            }
        }
        cout << ans << endl;
    }
}

ICPC 2017 国内予選: B. ほとんど同じプログラム

,

B問題 ほとんど同じ プログラム。

本番ではチームメンバーに任せた。C++で書いて$1$WAしていたようだ。

solution

指示された通り実装する。$O(|S|)$。

Pythonを使うべき。

implementation

#!/usr/bin/env python3
IDENTICAL = 'IDENTICAL'
CLOSE = 'CLOSE'
DIFFERENT = 'DIFFERENT'
while True:
    s = input()
    if s == '.':
        break
    t = input()
    if s == t:
        result = IDENTICAL
    else:
        result = CLOSE
        modified = 0
        for i, (a, b) in enumerate(zip(s.split('"') + [ None ], t.split('"') + [ None ])):
            if a is None and b is None:
                pass
            elif a is None or b is None:
                result = DIFFERENT
            else:
                if a != b:
                    modified += 1
                    if i % 2 == 0 or modified >= 2:
                        result = DIFFERENT
    print(result)

ICPC 2017 国内予選: A. 太郎君の買物

,

終了後に解いて書いた。

solution

全部の対を試す。$O(N^2)$。

implementation

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

int main() {
    while (true) {
        int n, m; scanf("%d%d", &n, &m);
        if (n == 0 and m == 0) break;
        vector<int> a(n); repeat (i, n) scanf("%d", &a[i]);
        int result = 0;
        repeat (j, n) repeat (i, j) {
            if (a[i] + a[j] <= m) {
                setmax(result, a[i] + a[j]);
            }
        }
        if (result) {
            printf("%d\n", result);
        } else {
            printf("NONE\n");
        }
    }
    return 0;
}

AOJ 1152: 部陪博士,あるいは,われわれはいかにして左右非対称になったか / Dr. Podboq or: How We Became Asymmetric

,

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1152

solution

問題文を頑張って読んでその通りに実装する。文字列の長さ$N \le 400$くらいに対して$O(N^3)$ぐらい。

以下注意点:

  • struct tree_t { tree_t *l, *r; }のようにするだろうが、一致判定や全順序を入れるのは文字列に戻してからすると楽
  • 問題文中の「構造」とは、単に根付き木としての同型性だけを見ており、子の左右の別はない
  • $-1, 0, +1$を返すはずの関数cmpの戻り値の型をboolにしてWAした

implementation

#include <cassert>
#include <functional>
#include <iostream>
#include <memory>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
using ll = long long;
using namespace std;

struct tree_t {
    shared_ptr<tree_t> l, r;
};

shared_ptr<tree_t> parse_tree(string::const_iterator & first, string::const_iterator last) {
    assert (first != last);
    if (*first == 'x') {
        ++ first;
        return shared_ptr<tree_t>();
    } else {
        assert (*first == '(');
        ++ first;
        auto l = parse_tree(first, last);
        assert (*first == ' ');
        ++ first;
        auto r = parse_tree(first, last);
        assert (*first == ')');
        ++ first;
        return make_shared<tree_t>((tree_t) { l, r });
    }
}
shared_ptr<tree_t> parse_tree(string const & s) {
    auto it = s.begin();
    auto tree = parse_tree(it, s.end());
    assert (it == s.end());
    return tree;
}

struct rational {
    int num, den;
};
bool operator < (rational a, rational b) {
    return a.num *(ll) b.den < b.num *(ll) a.den;
}
bool operator > (rational a, rational b) {
    return a.num *(ll) b.den > b.num *(ll) a.den;
}

string signature(shared_ptr<tree_t> const & tree) {
    if (not tree) {
        return "x";
    } else {
        string l = signature(tree->l);
        string r = signature(tree->r);
        if (l > r) swap(l, r);
        return "(" + l + " " + r + ")";
    }
}

void normalize(shared_ptr<tree_t> root) {
    unordered_map<string, unordered_set<string> > subtrees; {
        function<void (shared_ptr<tree_t> const &)> go = [&](shared_ptr<tree_t> const & tree) {
            subtrees[signature(tree)].insert(signature(tree));
            if (tree) {
                go(tree->l);
                go(tree->r);
                for (auto it : subtrees[signature(tree->l)]) {
                    subtrees[signature(tree)].insert(it);
                }
                for (auto it : subtrees[signature(tree->r)]) {
                    subtrees[signature(tree)].insert(it);
                }
            }
        };
        go(root);
    }
    unordered_map<string, rational> sim; {
        function<void (shared_ptr<tree_t> const &)> go = [&](shared_ptr<tree_t> const & tree) {
            if (not tree) {
                sim[signature(tree)] = (rational) { 0, 1 };
            } else {
                auto l = subtrees[signature(tree->l)];
                auto r = subtrees[signature(tree->r)];
                int num = 0;
                for (auto it : l) {
                    num += r.count(it);
                }
                int den = l.size() + r.size() - num;
                sim[signature(tree)] = (rational) { num, den };
                go(tree->l);
                go(tree->r);
            }
        };
        go(root);
    }
    const int LT = -1;
    const int EQ =  0;
    const int GT = +1;
    function<int (shared_ptr<tree_t> const &, shared_ptr<tree_t> const &)> cmp = [&](shared_ptr<tree_t> const & a, shared_ptr<tree_t> const & b) {
            rational sim_a = sim[signature(a)];
            rational sim_b = sim[signature(b)];
            // 1.
            if (sim_a < sim_b) return GT;
            if (sim_a > sim_b) return LT;
            // 2.
            if (not a and not b) return EQ;
            // 3.
            auto al = a->l, ar = a->r;
            auto bl = b->l, br = b->r;
            if (cmp(al, ar) == GT) swap(al, ar);
            if (cmp(bl, br) == GT) swap(bl, br);
            int cmp_ar_br = cmp(ar, br);
            if (cmp_ar_br != EQ) return cmp_ar_br;
            // 4.
            int cmp_al_bl = cmp(al, bl);
            if (cmp_al_bl != EQ) return cmp_al_bl;
            // 5.
            return EQ;
    };
    function<void (shared_ptr<tree_t>, bool)> go = [&](shared_ptr<tree_t> tree, bool is_right) {
        if (not tree) {
            // nop
        } else {
            if (cmp(tree->l, tree->r) == (is_right ? GT : LT)) {
                swap(tree->l, tree->r);
            }
            go(tree->l, false);
            go(tree->r, true);
        }
    };
    go(root, false);
}

string format_tree(shared_ptr<tree_t> const & tree) {
    if (not tree) {
        return "x";
    } else {
        return "(" + format_tree(tree->l) + " " + format_tree(tree->r) + ")";
    }
}

int main() {
    while (true) {
        string s; getline(cin, s);
        if (s == "0") break;
        auto tree = parse_tree(s);
        normalize(tree);
        cout << format_tree(tree) << endl;
    }
    return 0;
}

AOJ 1149: ケーキカット / Cut the Cake

,

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1149

何か便利そうなやつという認識があったのでstd::minmaxを使ってみたのだが、参照を返す性質上tieと合わせるとバグになるようだった。

solution

指示されたように実装する。$O(N^2)$でよい。

$s$は周期性と結果をsortすることから、$s \bmod (H + W)$だけ考えればよい。

implementation

#include <algorithm>
#include <cassert>
#include <cstdio>
#include <tuple>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using namespace std;

pair<pair<int, int>, pair<int, int> > split(int h, int w, int s) {
    s %= h + w;
    if (0 < s and s < w) {
        int w1 = s;
        int w2 = w - w1;
        tie(w1, w2) = minmax({ w1, w2 });
        return { { h, w1 }, { h, w2 } };
    } else if (w < s) {
        int h1 = s - w;
        int h2 = h - h1;
        tie(h1, h2) = minmax({ h1, h2 });
        return { { h1, w }, { h2, w } };
    } else {
        assert (false);
    }
}

int main() {
    while (true) {
        int n, initial_w, initial_h; scanf("%d%d%d", &n, &initial_w, &initial_h);
        if (n == 0 and initial_w == 0 and initial_h == 0) break;
        vector<pair<int, int> > piece;
        piece.emplace_back(initial_h, initial_w);
        while (n --) {
            int i, s; scanf("%d%d", &i, &s); -- i;
            int h, w; tie(h, w) = piece[i];
            piece.erase(piece.begin() + i);
            pair<int, int> p1, p2; tie(p1, p2) = split(h, w, s);
            piece.push_back(p1);
            piece.push_back(p2);
        }
        vector<int> area;
        for (auto piece_i : piece) {
            int h, w; tie(h, w) = piece_i;
            area.push_back(h * w);
        }
        whole(sort, area);
        repeat (i, area.size()) {
            printf("%d%c", area[i], i + 1 == area.size() ? '\n' : ' ');
        }
    }
    return 0;
}