AOJ 1148: ログイン/ログアウト記録の解析 / Analyzing Login/Logout Records

,

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

solution

人数$M$も時刻$t \in \mathbb{N}$も少ないので愚直にやる。imos法っぽくやると楽だがそうでなくても間に合う。$T = \max t_i - \min t_i$として$O(r + MT + QT)$。

implementation

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

constexpr int max_t = 1260;
int main() {
    while (true) {
        int n, m; scanf("%d%d", &n, &m);
        if (n == 0 and m == 0) break;
        auto login = vectors(m, max_t + 2, int());
        int r; scanf("%d", &r);
        while (r --) {
            int t, i, j, s; scanf("%d%d%d%d", &t, &i, &j, &s); -- i; -- j;
            login[j][t] += s ? +1 : -1;
        }
        repeat (j, m) {
            repeat (t, max_t + 1) {
                login[j][t + 1] += login[j][t];
            }
        }
        int q; scanf("%d", &q);
        while (q --) {
            int l, r, j; scanf("%d%d%d", &l, &r, &j); -- j;
            int result = 0;
            repeat_from (t, l, r) {
                result += bool(login[j][t]);
            }
            printf("%d\n", result);
        }
    }
    return 0;
}

AOJ 1147: ICPC 得点集計ソフトウェア / ICPC Score Totalizer Software

,

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

solution

やるだけ。sortして先頭と末尾を落として平均を取る。$O(n \log n)$。

implementation

#include <algorithm>
#include <cstdio>
#include <numeric>
#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;

int main() {
    while (true) {
        int n; scanf("%d", &n);
        if (n == 0) break;
        vector<int> a(n); repeat (i, n) scanf("%d", &a[i]);
        whole(sort, a);
        int result = (whole(accumulate, a, 0) - a.front() - a.back()) / (n - 2);
        printf("%d\n", result);
    }
    return 0;
}

AOJ 2255: 6/2(1+2)

,

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

solution

字句解析 + 括弧までの構文解析して区間DP。各<expr>をそのあり得る値の集合へ写す。入力の長さを$N$、演算子の数を$K$として$O(N + 2^K)$。

区間DPの部分は以下でもできるようだが、実装量も速度も悪そうなので勧めない。

  • 再帰 どこで分割するかを毎回全部試す (これをメモ化すれば先に言った区間DP)
  • 演算子の優先順位を全列挙 next_permutationとかで頑張る

implementation

#include <cassert>
#include <cctype>
#include <iostream>
#include <set>
#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 <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); }

struct expr_t {
    int immidiate;
    vector<expr_t> value;
    vector<char> op;
};
expr_t parse_value(string::const_iterator & first, string::const_iterator last) {
    assert (first != last);
    assert (isdigit(*first));
    int acc = 0;
    while (first != last and isdigit(*first)) {
        acc = acc * 10 + (*first - '0');
        ++ first;
    }
    return (expr_t) { acc };
}
expr_t parse_expr(string::const_iterator & first, string::const_iterator last);
expr_t parse_term(string::const_iterator & first, string::const_iterator last) {
    assert (first != last);
    if (*first == '(') {
        ++ first;
        expr_t expr = parse_expr(first, last);
        assert (*first == ')');
        ++ first;
        return expr;
    } else {
        return parse_value(first, last);
    }
}
expr_t parse_expr(string::const_iterator & first, string::const_iterator last) {
    assert (first != last);
    expr_t expr = { -1 };
    expr.value.push_back(parse_term(first, last));
    while (first != last and *first != ')') {
        assert (*first == '+' or *first == '-' or *first == '*' or *first == '/');
        expr.op.push_back(*first);
        ++ first;
        expr.value.push_back(parse_term(first, last));
    }
    return expr;
}
expr_t parse(string const & s) {
    auto first = s.begin();
    expr_t expr = parse_expr(first, s.end());
    assert (first == s.end());
    return expr;
}

set<int> solve(expr_t const & expr) {
    if (expr.immidiate != -1) {
        return set<int>({ expr.immidiate });
    } else {
        int n = expr.value.size();
        auto dp = vectors(n, n + 1, set<int>());
        repeat (i, n) {
            dp[i][i + 1] = solve(expr.value[i]);
        }
        repeat_from (len, 2, n + 1) {
            repeat_from (r, len, n + 1) {
                int l = r - len;
                repeat_from (m, l, r - 1) {
                    set<int> & left  = dp[l][m + 1];
                    set<int> & right = dp[m + 1][r];
                    char op = expr.op[m];
                    if (op == '+') {
                        for (int a : left) for (int b : right) dp[l][r].insert(a + b);
                    } else if (op == '-') {
                        for (int a : left) for (int b : right) dp[l][r].insert(a - b);
                    } else if (op == '*') {
                        for (int a : left) for (int b : right) dp[l][r].insert(a * b);
                    } else if (op == '/') {
                        for (int b : right) if (b != 0) for (int a : left) dp[l][r].insert(a / b);
                    }
                }
            }
        }
        return dp[0][n];
    }
}

int main() {
    while (true) {
        string s; cin >> s;
        if (s == "#") break;
        expr_t expr = parse(s);
        int result = solve(expr).size();
        printf("%d\n", result);
    }
    return 0;
}

AOJ 2700: 空港コード / Airport Codes

,

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

solution

答え$K$を全探索。愚直にset<string>に突っ込んで大きさが$n$か見ればよい。 $L = \max |s_i|$として$O(n L \log L)$。

implementation

#include <algorithm>
#include <iostream>
#include <set>
#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;

bool is_vowel(char c) {
    switch (c) {
        case 'a':
        case 'i':
        case 'u':
        case 'e':
        case 'o':
            return true;
        default:
            return false;
    }
}
int main() {
    while (true) {
        int n; cin >> n;
        if (n == 0) break;
        vector<string> code(n);
        repeat (i, n) {
            string s; cin >> s;
            code[i] += s[0];
            repeat (j, s.length() - 1) {
                if (is_vowel(s[j])) {
                    code[i] += s[j + 1];
                }
            }
        }
        constexpr int inf = 64;
        int k = 0;
        for (; k < inf; ++ k) {
            set<string> used;
            repeat (i, n) {
                used.insert(code[i].substr(0, min<int>(code[i].length(), k)));
            }
            if (used.size() == n) {
                break;
            }
        }
        printf("%d\n", k == inf ? -1 : k);
    }
    return 0;
}

polictf 2017: Lucky Consecutive Guessing

,

https://scoreboard.polictf.it

しほさんがURLを置いてくれていたので実装するだけだった。 他のcryptoやguessingは解けずだったのでやったのはこれだけ。 ところで私もプロとカラオケでCTFするやつやりたい。

そういえば大きい数で割って変数を消すのはWiener’s Attackでも見た気がする。よくある手法なのか。

problem

$ nc lucky.chall.polictf.it 31337
Welcome!
Do you feel lucky? Try to guess the numbers I'm thinking of.
You have one minute to reach 100 points. Good Luck!
You have 10 points.
Guess the next number:
42
Wrong, the correct number was 2914548618.
You have 9 points.
Guess the next number:

定数が既知の線形合同法による出力の列が与えられる。 ただし出力として与えられるのは上位bitのみ。 ここから状態を復元する問題。

solution

Read this: https://crypto.stackexchange.com/questions/10608/how-to-attack-a-fixed-lcg-with-partial-output.

内部状態が$\mathrm{nbits}$bitあり生成式$X’ = (aX + b) \bmod 2^{\mathrm{nbits}}$、その内で観測できるのが$\mathrm{output}$bitであったとする。 このとき$\mathrm{hidden} = \mathrm{nbits} - \mathrm{output}$に対し$a \gt 2^{\mathrm{hidden}}$であれば、この$a$で諸々を割ることで秘匿されている部分の値を式から消去してやれるよね、というのが概要。

implementation

#!/usr/bin/env python2
from pwn import * # https://pypi.python.org/pypi/pwntools
import argparse
parser = argparse.ArgumentParser()
parser.add_argument('host', nargs='?', default='lucky.chall.polictf.it')
parser.add_argument('port', nargs='?', default=31337, type=int)
parser.add_argument('--log-level', default='debug')
args = parser.parse_args()
context.log_level = args.log_level
p = remote(args.host, args.port)

a = 0x66e158441b6995
b = 0xB
nbits = 85
output = 32
hidden = nbits - output

# https://crypto.stackexchange.com/questions/10608/how-to-attack-a-fixed-lcg-with-partial-output
assert a >= 2 ** hidden
r = []
for i in range(9):
    p.recvuntil('Guess the next number:')
    p.sendline('0')
    p.recvuntil('Wrong, the correct number was ')
    number = int(p.recvline().rstrip().rstrip('.'))
    r += [ number ]
    log.info('output %d: %d', i, number)
r0 = r[0]
r1 = r[1]
t = ((r1 - a * r0 + 1) * 2 ** hidden - b - 1) % (2 ** nbits)
for k in range((a * 2 ** hidden - 1 - t) // (2 ** nbits) + 1):
    if (t + k * 2 ** nbits) % a < 2 ** hidden:
        x0 = (t + k * 2 ** nbits) // a + r0 * 2 ** hidden
        x = x0
        for i in range(9):
            if x >> hidden != r[i]:
                break
            x = (a * x + b) % (2 ** nbits)
        else:
            break
log.info('found: %d', x0)

x = x0
for _ in range(9):
    x = (a * x + b) % (2 ** nbits)
    log.info('%d : %d', x, x >> hidden)
while True:
    p.recvuntil('Guess the next number:')
    p.sendline(str(x >> hidden))
    x = (a * x + b) % (2 ** nbits)

AtCoder Grand Contest 017: B - Moderate Differences

,

http://agc017.contest.atcoder.jp/tasks/agc017_b

solution

増加の回数を$k$、減少の回数を$N - k$としてこの$k$を全探索。$O(N)$。

区間$[l, r]$を関数$X \mapsto \{ x + \delta \mid x \in X, \delta \in [l, r]\}$と見る。 この関数は明らかに可換: $[l, r] \circ [l’, r’] = [l’, r’] \circ [l, r] = [l + l’, r + r’]$。 また$x, x’$が隣り合っているとき、$x’ \in C, D$または$x’ \in -D, -C$が成り立つことが条件。 よって問題全体は$B \in ({[C, D]}^k \circ {[-D, -C]}^{N-k})(\{ A \})$であるような$k$が存在するか否かであると整理される。

implementation

#include <algorithm>
#include <cstdio>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
using ll = long long;
using namespace std;
int main() {
    int n; ll a, b, c, d; scanf("%d%lld%lld%lld%lld", &n, &a, &b, &c, &d);
    bool found = false;
    repeat (k, n) {
        ll r1 = d * k;
        ll l1 = c * k;
        ll r2 = - c * (n - 1 - k);
        ll l2 = - d * (n - 1 - k);
        ll r = r1 + r2;
        ll l = l1 + l2;
        if (l <= abs(b - a) and abs(b - a) <= r) {
            found = true;
        }
    }
    printf("%s\n", found ? "YES" : "NO");
    return 0;
}

AtCoder Grand Contest 017: A - Biscuits

,

http://agc017.contest.atcoder.jp/tasks/agc017_a

solution

普通に数える。$O(N^3)$。

数列$A$中の偶数な項の数を$E$、奇数な項の数を$O$とする。 偶数を足しても偶奇は保たれるので偶数な項の使用は自由で、$2^E$通り。 奇数な項はちょうど$P \pmod{2}$個使わなければならないので、$\sum_{0 \le r \le O \land r \equiv P \pmod{2}} {}_OC_r$通り。 この積が答え。

implementation

#include <algorithm>
#include <cstdio>
#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 ll = long long;
using namespace std;

ll choose(int n, int r) { // O(r) for small n
    ll acc = 1;
    repeat (i,r) acc = acc * (n-i) / (i+1);
    return acc;
}
int main() {
    int n, p; scanf("%d%d", &n, &p);
    vector<int> a(n); repeat (i, n) scanf("%d", &a[i]);
    int even = whole(count_if, a, [](int a_i) { return a_i % 2 == 0; });
    int odd = n - even;
    ll result = 0;
    for (int k = p; k <= odd; k += 2) {
        result += choose(odd, k);
    }
    result *= 1ll << even;
    printf("%lld\n", result);
    return 0;
}

Hamako Online Judge #097 ukuku09: 005 - devilswalk

,

$5$完で$6$位。やったね。

solution

隣接行列を$T$乗する。$O((WH)^3 \log T)$。速めの行列積を書けば通る。

implementation

#include <array>
#include <cmath>
#include <cstdio>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
using ll = long long;
using namespace std;
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; }

constexpr int max_h = 16;
constexpr int max_w = 16;
constexpr int mod = 1e9+7;
using type = array<array<int, max_h * max_w>, max_h * max_w>;
type append(type const & a, type const & b) {
    type tb;
    repeat (i, max_h * max_w) {
        repeat (j, max_h * max_w) {
            tb[i][j] = b[j][i];
        }
    }
    type c;
    repeat (i, max_h * max_w) {
        repeat (j, max_h * max_w) {
            ll acc = 0;
            repeat (k, max_h * max_w) {
                acc += a[i][k] *(ll) tb[j][k] % mod;
            }
            c[i][j] = acc % mod;
        }
    }
    return c;
}

int main() {
    int w, h, t; scanf("%d%d%d", &w, &h, &t);
    array<array<bool, max_h>, max_w> object = {};
    repeat (y, max_h) repeat (x, max_w) {
        object[y][x] = not is_on_field(y, x, h, w);
    }
    int object_count; scanf("%d", &object_count);
    repeat (i, object_count) {
        int x, y; scanf("%d%d", &x, &y); -- x; -- y;
        object[y][x] = true;
    }
    type e = {};
    repeat (y, h) repeat (x, w) {
        if (object[y][x]) continue;
        repeat (i, 4) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (not is_on_field(ny, nx, h, w)) continue;
            if (object[ny][nx]) continue;
            e[y * max_w + x][ny * max_w + nx] += 1;
        }
    }
    type result = {};
    repeat (y, h) repeat (x, w) {
        if (object[y][x]) continue;
        result[y * max_w + x][y * max_w + x] = 1;
    }
    for (int i = 1; i <= t; i <<= 1) {
        if (t & i) {
            result = append(result, e);
        }
        e = append(e, e);
    }
    int query; scanf("%d", &query);
    while (query --) {
        int sx, sy, gx, gy; scanf("%d%d%d%d", &sx, &sy, &gx, &gy); -- sx; -- sy; -- gx; -- gy;
        printf("%d\n", result[sy * max_w + sx][gy * max_w + gx]);
    }
    return 0;
}

Hamako Online Judge #097 ukuku09: 004 - ghoststudents2

,

テストケースが弱いので嘘高速化で通ってしまった。

solution

set<int>::lower_boundを使うと$O(Q N \log N)$。これだけだと間に合わないので平方分割して荒い範囲で検索し、それで見付からなかったやつだけにlower_boundを呼ぶようにする。 質問クエリだけ飛んでくる場合を考えればこれだけでは不十分だが、テストケースが弱いのでこれで通る。

implementation

bitset<N>は主にコード長のためであり、vector<bool>で通るか否かは確認していない。

#include <array>
#include <bitset>
#include <cstdio>
#include <set>
#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;

constexpr int sqrt_width = 1e3;
constexpr int max_n = 1e3;
int main() {
    int n, query; scanf("%d%d", &n, &query);
    vector<set<int> > used(n);
    array<bitset<max_n>, sqrt_width> bucket = {};
    while (query --) {
        int type; scanf("%d", &type);
        if (type == 1) {
            int a, b; scanf("%d%d", &a, &b); -- a; -- b;
            used[b].insert(a);
            bucket[a / sqrt_width][b] = true;
        } else if (type == 2) {
            int c, d; scanf("%d%d", &c, &d); -- c; // [l, r)
            bitset<max_n> found = {};
            int bucket_l = (c - 1) / sqrt_width + 1;
            int bucket_r = d / sqrt_width;
            repeat_from (i, bucket_l, bucket_r) {
                found |= bucket[i];
            }
            int result = found.count();
            repeat (i, n) if (not found[i]) {
                auto it = used[i].lower_bound(c);
                if (it != used[i].end() and *it < d) {
                    result += 1;
                }
            }
            printf("%d\n", result);
        }
    }
    return 0;
}

Hamako Online Judge #097 ukuku09: 003 - repdigit

,

solution

0がなければ結果の整数は111...1222...2333...3.........999...9という形。 ある場合は111000...0111...1222...2.........222000...0222...2333...3.........のように必要最小限だけ前に出す。 これらをいい感じに計算すればよい。 repunit $111 \dots 1$や$10^k$は線形の漸化式を持つので桁数の対数で求められる。階乗する部分が一番重くて$O(N + \sum b_i)$。

implementation

#include <array>
#include <cassert>
#include <cstdio>
#include <tuple>
#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 ll = long long;
using namespace std;

template <int mod>
int fact(int n) {
    static vector<int> memo(1, 1);
    if (memo.size() <= n) {
        int l = memo.size();
        memo.resize(n+1);
        repeat_from (i, l, n+1) memo[i] = memo[i-1] *(ll) i % mod;
    }
    return memo[n];
}
ll powmod(ll x, ll y, ll p) { // O(log y)
    assert (0 <= x and x < p);
    assert (0 <= y);
    ll z = 1;
    for (ll i = 1; i <= y; i <<= 1) {
        if (y & i) z = z * x % p;
        x = x * x % p;
    }
    return z;
}
int repunit(ll n, int mod) { // O(log n)
    ll y = 0;
    ll x = 1;
    for (ll i = 1; i <= n; i <<= 1) {
        if (n & i) y = (y * powmod(10, i, mod) % mod + x) % mod;
        x = (x * powmod(10, i, mod) % mod + x) % mod;
    }
    return y;
}

constexpr int mod = 1e9+7;
pair<int, int> solve(int n, vector<int> const & a, vector<int> const & b) {
    array<int, 10> cnt = {};
    array<ll, 10> acc = {};
    repeat (i, n) {
        cnt[a[i]] += 1;
        acc[a[i]] += b[i];
    }
    int x = 0;
    int y = 1;
    if (cnt[0]) {
        if (n == 1) return make_pair(0, 1);
        int d = 1;
        while (not cnt[d]) ++ d;
        assert (d <= 9);
        int min_length = mod;
        int min_length_count = 0;
        repeat (i, n) {
            if (a[i] == d and b[i] <= min_length) {
                if (b[i] < min_length) {
                    min_length = b[i];
                    min_length_count = 0;
                }
                min_length_count += 1;
            }
        }
        x = (x *(ll) powmod(10, min_length, mod) + repunit(min_length, mod) *(ll) d % mod) % mod;
        y = y *(ll) min_length_count % mod;
        cnt[d] -= 1;
        acc[d] -= min_length;
    }
    repeat (d, 10) {
        x = (x *(ll) powmod(10, acc[d], mod) + repunit(acc[d], mod) *(ll) d % mod) % mod;
        y = y *(ll) fact<mod>(cnt[d]) % mod;
    }
    return make_pair(x, y);
}

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

Hamako Online Judge #097 ukuku09: 002 - ghoststudents

,

solution

動的構築segment木を貼るだけ。$O(N + Q \log N)$。

implementation

#include <cassert>
#include <cstdio>
#include <deque>
#include <vector>
using ll = long long;
using namespace std;
template <class T> inline void setmax(T & a, T const & b) { a = max(a, b); }

template <class Monoid>
struct dynamic_segment_tree { // on monoid
    typedef Monoid monoid_type;
    typedef typename Monoid::type underlying_type;
    struct node_t {
        int left, right; // indices on pool
        underlying_type value;
    };
    deque<node_t> pool;
    int root; // index
    int width; // of the tree
    int size; // the number of leaves
    Monoid mon;
    dynamic_segment_tree(Monoid const & a_mon = Monoid()) : mon(a_mon) {
        node_t node = { -1, -1, mon.unit() };
        pool.push_back(node);
        root = 0;
        width = 1;
        size = 1;
    }
protected:
    int create_node(int parent, bool is_right) {
        // make a new node
        int i = pool.size();
        node_t node = { -1, -1, mon.unit() };
        pool.push_back(node);
        // link from the parent
        assert (parent != -1);
        int & ptr = is_right ? pool[parent].right : pool[parent].left;
        assert (ptr == -1);
        ptr = i;
        return i;
    }
    int get_value(int i) {
        return i == -1 ? mon.unit() : pool[i].value;
    }
public:
    void point_set(int i, underlying_type z) {
        assert (0 <= i);
        while (width <= i) {
            node_t node = { root, -1, pool[root].value };
            root = pool.size();
            pool.push_back(node);
            width *= 2;
        }
        point_set(root, -1, false, 0, width, i, z);
    }
    void point_set(int i, int parent, bool is_right, int il, int ir, int j, underlying_type z) {
        if (il == j and ir == j+1) { // 0-based
            if (i == -1) {
                i = create_node(parent, is_right);
                size += 1;
            }
            pool[i].value = z;
        } else if (ir <= j or j+1 <= il) {
            // nop
        } else {
            if (i == -1) i = create_node(parent, is_right);
            point_set(pool[i].left,  i, false, il, (il+ir)/2, j, z);
            point_set(pool[i].right, i, true,  (il+ir)/2, ir, j, z);
            pool[i].value = mon.append(get_value(pool[i].left), get_value(pool[i].right));
        }
    }
    underlying_type range_concat(int l, int r) {
        assert (0 <= l and l <= r);
        if (width <= l) return mon.unit();
        return range_concat(root, 0, width, l, min(width, r));
    }
    underlying_type range_concat(int i, int il, int ir, int l, int r) {
        if (i == -1) return mon.unit();
        if (l <= il and ir <= r) { // 0-based
            return pool[i].value;
        } else if (ir <= l or r <= il) {
            return mon.unit();
        } else {
            return mon.append(
                    range_concat(pool[i].left,  il, (il+ir)/2, l, r),
                    range_concat(pool[i].right, (il+ir)/2, ir, l, r));
        }
    }
};

struct plus_t {
    typedef int type;
    int unit() const { return 0; }
    int append(int a, int b) const { return a + b; }
};

int main() {
    int n, query; scanf("%d%d", &n, &query);
    vector<int> last(n);
    dynamic_segment_tree<plus_t> segtree;
    int limit = 0;
    while (query --) {
        int type; scanf("%d", &type);
        if (type == 1) {
            int a, b; scanf("%d%d", &a, &b); -- b;
            if (last[b] < a) {
                if (last[b]) {
                    segtree.point_set(last[b], segtree.range_concat(last[b], last[b] + 1) - 1);
                }
                last[b] = a;
                segtree.point_set(last[b], segtree.range_concat(last[b], last[b] + 1) + 1);
            }
            setmax(limit, a + 1);
        } else if (type == 2) {
            int c; scanf("%d", &c);
            int result = segtree.range_concat(min(c, limit), limit);
            printf("%d\n", result);
            fflush(stdout);
        }
    }
    return 0;
}

Hamako Online Judge #097 ukuku09: 001 - photography

,

solution

累積和の列をsortして潰してしゃくとり法や二分探索。$O(N \log N)$。

数列$X$に対し累積和$a$を取ると答えは$\max \{ r - l \mid a_r - a_l \ge P \}$。 添字$l$を固定したときに$a_r \ge P + a_l$であるような最大の$r$を求められればよい。 $r \lt r’$で$a_r \le a_{r’}$なら$(r, a_r)$はまったく不要であることを使って、そのようなものを除いて列$a_{r_k}$を作ればこれは単調増加列。この上で二分探索とかをすればよい。

implementation

#include <cstdio>
#include <map>
#include <numeric>
#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 ll = long long;
using namespace std;
template <class T> inline void setmax(T & a, T const & b) { a = max(a, b); }
template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); }

int main() {
    // input
    int n; ll p; scanf("%d%lld", &n, &p);
    vector<ll> x(n); repeat (i, n) scanf("%lld", &x[i]);
    // solve
    vector<ll> acc(n + 1); whole(partial_sum, x, acc.begin() + 1);
    map<ll, int> left, right;
    repeat (i, n + 1) {
        if (not  left.count(acc[i])) {  left[acc[i]] = i; } else { setmin( left[acc[i]], i); }
        if (not right.count(acc[i])) { right[acc[i]] = i; } else { setmax(right[acc[i]], i); }
    }
    for (auto it = right.begin(); ; ) {
        auto next = it; ++ next;
        if (next == right.end()) break;
        ll a = it->first;
        ll b = next->first;
        if (a < b and right[a] <= right[b]) {
            right.erase(it);
            it = right.find(b);
            if (it != right.begin()) -- it;
        } else {
            it = next;
        }
    }
    int result = 0;
    auto r = right.begin();
    auto l = left.begin();
    for (; l != left.end(); ++ l) {
        while (r != right.end() and r->first - l->first < p) ++ r;
        if (r == right.end()) break;
        setmax(result, r->second - l->second);
    }
    // output
    printf("%d\n", result);
    return 0;
}

AOJ 2021: お姫様の暗号解読 / Princess, a Cryptanalyst

,

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

solution

開始する単語を決めて後ろに付け足していく。 このとき必ず重なりが発生するように限定し、重ならないようなものに関しては後からbit-DPのようにする。 遷移が少なくなりかつ合流するような無駄がなくなるので十分速くなって通る。 計算量として自明に$O(N!)$だが実際は$O(2^N)$ぐらいな感じ。

implementation

#include <cassert>
#include <functional>
#include <iostream>
#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;

bool is_suffix(string const & a, string const & b) {
    if (a.length() > b.length()) return false;
    return b.compare(b.length() - a.length(), a.length(), a) == 0;
}
void setshort(string & a, string const & b) {
    if (a.empty() or b.length() < a.length() or (a.length() == b.length() and b < a)) {
        a = b;
    }
}

int main() {
    while (true) {
        // input
        int n; cin >> n;
        if (n == 0) break;
        vector<string> word(n); repeat (i, n) cin >> word[i];
        // solve
        vector<string> dp(1 << n);
        function<void (string const &, int)> go = [&](string const & s, int used) {
            repeat (i, n) if (not (used & (1 << i))) {
                if (s.find(word[i]) != string::npos) {
                    used |= 1 << i;
                }
            }
            setshort(dp[used], s);
            repeat (i, n) if (not (used & (1 << i))) {
                repeat_from (sep, 1, word[i].length()) {
                    if (is_suffix(word[i].substr(0, sep), s)) {
                        go(s + word[i].substr(sep), used | (1 << i));
                    }
                }
            }
        };
        repeat (i, n) {
            go(word[i], 1 << i);
        }
        repeat (a, 1 << n) if (not dp[a].empty()) {
            repeat (b, 1 << n) {
                if ((b | a) == a) { // b \subseteq a
                    setshort(dp[b], dp[a]);
                }
            }
        }
        repeat_from (a, 1, 1 << n) {
            assert (not dp[a].empty());
            repeat (b, 1 << n) if (not dp[b].empty()) {
                if (not (a & b)) {
                    setshort(dp[a | b], dp[a] + dp[b]);
                    setshort(dp[a | b], dp[b] + dp[a]);
                }
            }
        }
        // output
        cout << dp[(1 << n) - 1] << endl;
    }
    return 0;
}

AOJ 2021: お姫様の危機 / Princess in Danger

,

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

solution

Dijkstraやるだけ。$O((NM + MK) \log (NM))$。OJ上の時間制限$8$secは少し厳しいのでpushの回数を減らすなど多少頑張る必要がある。

implementation

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

constexpr int inf = 1e9+7;
int main() {
    while (true) {
        // input
        int n, coldness_limit, machine_count, edge_count, start, goal; scanf("%d%d%d%d%d%d", &n, &coldness_limit, &machine_count, &edge_count, &start, &goal);
        if (n == 0) break;
        vector<bool> has_machine(n);
        repeat (i, machine_count) {
            int x; scanf("%d", &x);
            has_machine[x] = true;
        }
        vector<vector<pair<int, int> > > g(n);
        repeat (i, edge_count) {
            int x, y, t; scanf("%d%d%d", &x, &y, &t);
            if (coldness_limit < t) continue;
            g[x].emplace_back(y, t);
            g[y].emplace_back(x, t);
        }
        // solve
        auto dp = vectors(n, coldness_limit + 1, inf);
        priority_queue<tuple<int, int, int> > que;
        auto push = [&](int x, int coldness, int time) {
            if (dp[x][coldness] <= time) return;
            dp[x][coldness] = time;
            if (x == goal) return;
            que.emplace(time, x, coldness);
        };
        push(start, coldness_limit, 0);
        while (not que.empty()) {
            int time, x, coldness; tie(time, x, coldness) = que.top(); que.pop();
            if (dp[x][coldness] < time) continue;
            if (has_machine[x]) {
                for (int t = 0; coldness + t <= coldness_limit; ++ t) {
                    setmin(dp[x][coldness + t], time + t);
                }
            }
            for (auto edge : g[x]) {
                int y, dist; tie(y, dist) = edge;
                for (int t = 0; t + coldness <= coldness_limit; ++ t) {
                    if (0 <= coldness + t - dist) {
                        push(y, coldness + t - dist, time + t + dist);
                        if (has_machine[y]) break;
                    }
                    if (not has_machine[x]) break;
                }
            }
        }
        // output
        int result = inf;
        repeat (coldness, coldness_limit + 1) {
            setmin(result, dp[goal][coldness]);
        }
        if (result == inf) {
            printf("Help!\n");
        } else {
            printf("%d\n", result);
        }
    }
    return 0;
}

AOJ 2020: お姫様の日本語 / Princess' Japanese

,

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

問題文が難しいがやればできる。

solution

書いてある通り実装するだけ。頑張る。$O(N)$。 前後に番兵のようなものを置くと楽。モーラへの分解などは不要というのに気付かないと地獄を見そう。

implementation

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

bool is_one_of(char c, string const & s) {
    return s.find(c) != string::npos;
}
bool is_vowel(char c) {
    return is_one_of(c, "aiueo");
}
bool is_voiceless_consonant(char c) {
    return is_one_of(c, "ksthp");
}

int main() {
    while (true) {
        string s; cin >> s;
        if (s == "#") break;
        s = string() + "^^^^" + s + "$$$$$$$$";
        string t;
        bool is_canceled = false;
        repeat (i, s.length()) {
            if (s[i] == '^' or s[i] == '$') {
                continue;
            }
            if (is_canceled and is_vowel(s[i])) {
                t += s[i];
                is_canceled = false;
                continue;
            }
            bool is_left_voiceless_consonant_y = is_voiceless_consonant(s[i - 1]) or (is_voiceless_consonant(s[i - 2]) and s[i - 1] == 'y');
            if (is_left_voiceless_consonant_y and is_one_of(s[i], "iu") and (s[i + 1] == '$' or is_voiceless_consonant(s[i + 1]))) { // rule 1
                t += string() + "(" + s[i] + ")";
                is_canceled = true;
                continue;
            }
            if (is_left_voiceless_consonant_y and is_one_of(s[i], "ao") and is_voiceless_consonant(s[i + 1])) {
                if (s[i + 2] == s[i] or (s[i + 2] == 'y' and s[i + 3] == s[i])) { // rule 2
                    t += string() + "(" + s[i] + ")";
                    is_canceled = true;
                    continue;
                }
            }
            t += s[i];
        }
        cout << t << endl;
    }
    return 0;
}

AOJ 1333: Beautiful Spacing

,

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

solution

動的計画法。$N$単語目まで使ってちょうど行の区切りのとき、そこまでに出てくる空白の長さの最小値を$\mathrm{dp}(N)$とする。 愚直にやって$O(N^2)$。

それでは間に合わないので適当に定数倍高速化する。 具体的には区間min更新/点取得のsegment木を用いて、漸化式中の$\mathrm{dp}(N + k) \gets \min \{ \mathrm{dp}(N), f(N, k) \}$で$f$が単調減少な部分をいい感じにする。 計算量の上では変わらないが、十分速くなって通る。

implementation

#include <cassert>
#include <climits>
#include <cstdio>
#include <numeric>
#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 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
}

template <class OperatorMonoid>
struct dual_segment_tree {
    typedef OperatorMonoid monoid_type;
    typedef typename OperatorMonoid::underlying_type operator_type;
    typedef typename OperatorMonoid::target_type underlying_type;
    int n;
    vector<operator_type> f;
    vector<underlying_type> a;
    OperatorMonoid op;
    dual_segment_tree() = default;
    dual_segment_tree(int a_n, underlying_type initial_value, OperatorMonoid const & a_op = OperatorMonoid()) : op(a_op) {
        n = 1; while (n < a_n) n *= 2;
        a.resize(n, initial_value);
        f.resize(n-1, op.unit());
    }
    underlying_type point_get(int i) { // 0-based
        underlying_type acc = a[i];
        for (i = (i+n)/2; i > 0; i /= 2) { // 1-based
            acc = op.apply(f[i-1], acc);
        }
        return acc;
    }
    void range_apply(int l, int r, operator_type z) { // 0-based, [l, r)
        assert (0 <= l and l <= r and r <= n);
        range_apply(0, 0, n, l, r, z);
    }
    void range_apply(int i, int il, int ir, int l, int r, operator_type z) {
        if (l <= il and ir <= r) { // 0-based
            if (i < f.size()) {
                f[i] = op.append(z, f[i]);
            } else {
                a[i-n+1] = op.apply(z, a[i-n+1]);
            }
        } else if (ir <= l or r <= il) {
            // nop
        } else {
            range_apply(2*i+1, il, (il+ir)/2, 0, n, f[i]);
            range_apply(2*i+2, (il+ir)/2, ir, 0, n, f[i]);
            f[i] = op.unit();
            range_apply(2*i+1, il, (il+ir)/2, l, r, z);
            range_apply(2*i+2, (il+ir)/2, ir, l, r, z);
        }
    }
};

struct min_operator_t {
    typedef int underlying_type;
    typedef int target_type;
    int unit() const { return INT_MAX; }
    int append(int a, int b) const { return min(a, b); }
    int apply(int a, int b) const { return min(a, b); }
};

int main() {
    while (true) {
        // input
        int w, n; scanf("%d%d", &w, &n);
        if (w == 0) break;
        vector<ll> x(n); repeat (i, n) scanf("%lld", &x[i]);
        // solve
        vector<ll> acc(n + 1); whole(partial_sum, x, acc.begin() + 1);
        const int inf = w;
        vector<int> dp(n + 1, inf);
        dual_segment_tree<min_operator_t> segtree(n + 1, inf);
        dp[0] = 1;
        repeat (l, n) {
            setmin(dp[l], segtree.point_get(l));
            int r = l + 2;
            for (; r < n + 1; ++ r) {
                int used = acc[r] - acc[l];
                int k = r - l - 1;
                if (w < used + k) break;
                int it = (w - used + (k - 1)) / k;
                if (it <= dp[l]) break;
                setmin(dp[r], max(dp[l], it));
            }
            if (r < n + 1) {
                int rr = binsearch(r, n + 1, [&](int r) {
                    int used = acc[r] - acc[l];
                    int k = r - l - 1;
                    return w < used + k;
                });
                segtree.range_apply(r, rr, dp[l]);
            }
            if (acc[n] - acc[l] + n - l - 1 <= w) {
                setmin(dp[n], dp[l]);
            }
        }
        // output
        printf("%d\n", dp[n]);
    }
    return 0;
}