AOJ 2595 Cookie Counter

解法

1枚も食べない日を考えるとややこしい(し,Dがでかいのでそのまま求められない)ので,D 日のうち一枚も食べない日はあとで決めることにすればよい.
つまり,まずは一日に最低1枚は食べる場合の数を求める.すると,必ずN日目までには食べきるので,O(N^2) の DP に落とし込めそう.
dp[i][j] := i 日目までに j 枚のクッキーを食べる場合の数
としてDPする.一日に X 枚"未満"だけ食べられるので,以下の遷移が成り立つ.
dp[i][j] = dp[i-1][j-1] + dp[i-1][j-2] + ... + dp[i-1][j-X+1]
これを愚直に書くと O(N^3) だが,よく見ると単純に区間和を求めているだけなので,累積和を取れば O(N^2) にできる.

最後に,一日に食べない日を D 日のうちから決めるのだが,D がでかいので Cmb(D, 1) から Cmb(D, min(N, D)) まで順番に求めていけば O(N) で求められる.

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
constexpr ll M = 1e9+7;
 
// calc x
// ax %% 1 (mod M)
ll inv(ll a, ll p) {
    return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
 
int main() {
    ll N, D, X;
    while(cin >> N >> D >> X, N) {
        vector<vector<ll>> dp(N+1, vector<ll>(N+1));
        dp[0][0] = 1;
        vector<vector<ll>> dp_sum(N+1, vector<ll>(N+1));
        fill(dp_sum[0].begin(), dp_sum[0].end(), 1);
        for(int i=1; i<=N; ++i) {
            for(int j=i; j<=N; ++j) {
                if(j-X >= 0) {
                    dp[i][j] = (dp_sum[i-1][j-1] - dp_sum[i-1][j-X] + M) % M;
                } else {
                    dp[i][j] = dp_sum[i-1][j-1];
                }
            }
            for(int j=1; j<=N; ++j) {
                dp_sum[i][j] = (dp_sum[i][j-1] + dp[i][j]) % M;
            }
        }
        ll res = 0;
        ll cmb = 1;
        for(int i=1; i<=min(N, D); ++i) {
            cmb = (cmb * ((D-i+1) % M)) % M;
            cmb = (cmb * inv(i, M)) % M;
            res = (res + dp[i][N] * cmb) % M;
        }
        cout << res << endl;
    }
}

AOJ 2570 Shipura

解法

> が >> なのか S < expr > の > なのかは,数字またはSの直前かどうかで判定ができる.
なので最初に式を後ろから見ていって,どれがシフト演算なのか確定させておく.
それができればあとは普通に左からパースするだけで十分.
シフト演算のときにシフトしすぎないように注意すること.

他の人は右から再帰的にやっていくという方法を取っていて,そっちのほうが良さそうだなーとは思った.

ソースコード

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

using ll = long long;

constexpr ll M = 1e9+7;

vector<bool> f;

ll expr(string const& s, int& p);
ll term(string const& s, int& p);
void sp(string const& s, int& p);
ll number(string const& s, int& p);

ll expr(string const& s, int& p) {
    sp(s, p);
    ll v1 = term(s, p);
    sp(s, p);
    while(p+1 < s.size() && f[p]) {
        p += 2;
        sp(s, p);
        ll v2 = term(s, p);
        if(v2 > 63) {
            v1 = 0;
        } else {
            v1 >>= v2;
        }
        sp(s, p);
    }
    return v1;
}

ll term(string const& s, int& p) {
    sp(s, p);
    if(s[p] == 'S') {
        sp(s, ++p);
        p++; // <
        sp(s, p);
        ll v = expr(s, p);
        sp(s, p);
        p++; // >
        v = (v * v) % M;
        return v;
    }
    return number(s, p);
}

void sp(string const& s, int& p) {
    while(p < s.size() && s[p] == ' ') {
        p++;
    }
}

ll number(string const& s, int& p) {
    int res = 0;
    while(p < s.size() && isdigit(s[p])) {
        res *= 10;
        res += s[p++] - '0';
    }
    return res;
}

int main() {
    while(true) {
        string s;
        getline(cin, s);
        if(s[0] == '#') {
            break;
        }
        int p = 0;
        f.assign(s.size(), false);
        for(int i=s.size()-1; i>=0; --i) {
            if(isdigit(s[i]) || s[i] == 'S') {
                if(isdigit(s[i])) {
                    while(i > 0 && isdigit(s[i])) {
                        --i;
                    }
                } else if(s[i] == 'S') {
                    i--;
                }
                while(i > 0 && s[i] == ' ') {
                    i--;
                }
                if(s[i] == '>') {
                    i--;
                    f[i] = true;
                }
            }
        }
        cout << expr(s, p) << endl;
    }
}

AOJ 2512 Ononokomachi's Edit War

解法

適当に置換 or 削除でminimax法だと明らかに間に合わないので,すこし考える必要がある.
冷静に考えると,N が偶数のときは2ターン,N が奇数のときは1ターンやるのと変わらないことが分かる.
大まかには以下のように考えた.

  • 任意に削除,挿入が可能なので,直前の手番をキャンセルさせることが可能
  • minimax法の要領で,先手は遷移先でもっとも良いものを選ぼうとする
  • 最終的に有利な手が選ばれるのだから,後手としてはキャンセルするほうがよい
  • つまり結局,お互いに最後だけを考えればよい(もちろん最後の手がキャンセルでもよい)

高々 N = 2 と言っているのと同じなので,挿入,削除に関して全通り試しても十分間に合う.
毎回の操作で式として成り立っている必要が有ることに注意.

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
constexpr int INF = 1e9;
 
int expr(string const& s, int& p);
int Or(string const& s, int& p);
int Xor(string const& s, int& p);
int And(string const& s, int& p);
int Plus(string const& s, int& p);
int term(string const& s, int& p);
int factor(string const& s, int& p);
int number(string const& s, int& p);
 
int expr(string const& s, int& p) {
    return Or(s, p);
}
 
int Or(string const& s, int& p) {
    int res = Xor(s, p);
    while(p < s.size() && s[p] == '|') {
        res |= Xor(s, ++p);
    }
    return res;
}
 
int Xor(string const& s, int& p) {
    int res = And(s, p);
    while(p < s.size() && s[p] == '^') {
        res ^= And(s, ++p);
    }
    return res;
}
 
int And(string const& s, int& p) {
    int res = Plus(s, p);
    while(p < s.size() && s[p] == '&') {
        res &= Plus(s, ++p);
    }
    return res;
}
 
int Plus(string const& s, int& p) {
    int res = term(s, p);
    while(p < s.size() && (s[p] == '+' || s[p] == '-')) {
        char op = s[p++];
        if(op == '+') {
            res += term(s, p);
        } else {
            res -= term(s, p);
        }
    }
    return res;
}
 
int term(string const& s, int& p) {
    int res = factor(s, p);
    while(p < s.size() && s[p] == '*') {
        res *= factor(s, ++p);
    }
    return res;
}
 
int factor(string const& s, int& p) {
    if(isdigit(s[p])) {
        if(s[p] == '0') {
            throw runtime_error("");
        }
        return number(s, p);
    }
    if(s[p] == '(') {
        int res = expr(s, ++p);
        ++p;
        return res;
    }
    throw runtime_error("");
}
 
int number(string const& s, int& p) {
    int res = 0;
    while(p < s.size() && isdigit(s[p])) {
        res *= 10;
        res += s[p++] - '0';
    }
    return res;
}
 
 
string pattern = "0123456789*+-&^|";
 
int parse(string const& s) {
    try {
        int p = 0;
        int t = expr(s, p);
        if(p != s.size()) {
            return INF;
        }
        return t;
    } catch(...) {
        return INF;
    }
}
 
int solve(string s, int cnt, int turn) {
    if(cnt == 0) {
        return parse(s);
    }
    int res = (turn == 0 ? -INF : INF);
    // erase
    for(int i=0; i<s.size(); ++i) {
        string t = s;
        t.erase(t.begin()+i);
        if(t.size() == 0 || INF == parse(t)) {
            continue;
        }
        int tmp = solve(t, cnt-1, turn^1);
        if(tmp == INF) {
            continue;
        }
        if(turn == 0) {
            res = max(res, tmp);
        } else {
            res = min(res, tmp);
        }
    }
 
    // insert
    for(int i=0; i<pattern.size(); ++i) {
        for(int j=0; j<=s.size(); ++j) {
            string t = s;
            t.insert(t.begin()+j, pattern[i]);
            if(INF == parse(t)) {
                continue;
            }
            int tmp = solve(t, cnt-1, turn^1);
            if(tmp == INF) {
                continue;
            }
            if(turn == 0) {
                res = max(res, tmp);
            } else {
                res = min(res, tmp);
            }
        }
         
    }
    return res;
}
 
 
int main() {
    int n;
    string s;
    while(cin >> n >> s, n) {
        if(n & 1) {
            cout << solve(s, 1, 0) << endl;
        } else {
            cout << solve(s, 2, 0) << endl;
        }
    }
}

AOJ 2255 6/2(1+2)

解法

BNFどおりに実装する必要はなくて,区間DPをすればよい.
その区間で取りうる値の集合を持たせておく.
区間 [l..r] の演算子を全て見ていって [l..i-1] と [i+1..r] に分ける.
この時,演算子で分けて括弧の対応が崩れるなら一旦スルーしておく必要がある.
たとえば,括弧が ( .. ( .. op_i .. ) .. ) となっていると,op_i で左右に分けることができない.
これは最初に括弧の対応付を調べておけばよい.
また,( expr ) となっているときは, expr に置き換えて処理するとよい.

ソースコード

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

set<int> memo[201][201];
vector<int> par_pos;

int number(string const& s, int p) {
    int res = 0;
    while(p < s.size() && isdigit(s[p])) {
        res *= 10;
        res += s[p++] - '0';
    }
    return res;
}

set<int> solve(string const& s, int l, int r) {
    auto& res = memo[l][r];
    if(res.size() != 0) {
        return res;
    }
    bool f = true;
    for(int i=l; i<=r; ++i) {
        f &= isdigit(s[i]);
    }
    if(f) {
        res.insert(number(s, l));
        return res;
    }
    if(par_pos[l] == r) {
        return res = solve(s, l+1, r-1);
    }
    vector<int> pare(s.size());
    for(int i=l; i<=r; ++i) {
        if(s[i] == '(') {
            pare[i] = 1;
        }
        if(s[i] == ')') {
            pare[i] = -1;
        }
        if(i != l) {
            pare[i] += pare[i-1];
        }
    }
    for(int i=l+1; i<r; ++i) {
        char c = s[i];
        if(pare[i] != 0) {
            continue;
        }
        if(c == '+' || c == '-' || c == '*' || c == '/') {
            set<int> s1 = solve(s, l, i-1);
            set<int> s2 = solve(s, i+1, r);
            for(auto x : s1) {
                for(auto y : s2) {
                    if(c == '+') {
                        res.insert(x + y);
                    } else if(c == '-') {
                        res.insert(x - y);
                    } else if(c == '*') {
                        res.insert(x * y);
                    } else {
                        if(y == 0) {
                            continue;
                        }
                        res.insert(x / y);
                    }
                }
            }
        }
    }
    return res;
}

int main() {
    string s;
    while(cin >> s, s != "#") {
        for(int i=0; i<201; ++i) {
            for(int j=0; j<201; ++j) {
                memo[i][j].clear();
            }
        }
        par_pos.assign(s.size(), -1);
        stack<int> p;
        for(int i=0; i<s.size(); ++i) {
            if(s[i] == '(') {
                p.push(i);
            }
            if(s[i] == ')') {
                par_pos[p.top()] = i;
                p.pop();
            }
        }
        cout << solve(s, 0, s.size()-1).size() << endl;
    }
}

AOJ 1350 There is No Alternative

問題概要

連結グラフ G が与えられる.一般に G の最小全域木は複数存在しうる.G のすべての最小全域木に必ず含まれている辺を求めよ.

・制約
3 <= N <= 500
N-1 <= M <= min(50000, N(N-1)/2)

解法

最小全域木 T を一つ求める.すると,候補の辺は必ずこの T に含まれている.
よって,T に含まれる辺を一つ使えないようにした状態で,最小全域木 T2 を構築してみる.w(T) != w(T2) ならば,この時使えなくした辺は必ず使う辺である.

計算量は O(MlogM + NMα(N)).

ソースコード

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

class union_find {
public:
    union_find(int n)
        : par_(n, -1)
    {}
    void init(int n) {
        par_.assign(n, -1);
    }

    int root(int x) {
        return par_[x] < 0 ? x : par_[x] = root(par_[x]);
    }

    bool unite(int x, int y) {
        x = root(x); y = root(y);
        if(x == y) {
            return false;
        } else {
            if(par_[x] < par_[y]) {
                par_[x] += par_[y];
                par_[y] = x;
            } else {
                par_[y] += par_[x];
                par_[x] = y;
            }
            return true;
        }
    }

    bool same(int x, int y) {
        return root(x) == root(y);
    }

    int size(int x) {
        return -par_[root(x)];
    }

private:
    std::vector<int> par_;
};


using weight = int;

struct edge {
    int u, v;
    weight cost;
    bool operator<(edge const& e) const {
        return cost < e.cost;
    }
};

using edges = std::vector<edge>;
using graph = std::vector<edges>;

int main() {
    int N, M;
    cin >> N >> M;
    edges es(M);
    for(int i=0; i<M; ++i) {
        cin >> es[i].u >> es[i].v >> es[i].cost;
        es[i].u--;
        es[i].v--;
    }
    sort(es.begin(), es.end());
    int mst_sum = 0;
    edges mst;
    union_find uf(N);
    for(int i=0; i<M; ++i) {
        if(!uf.same(es[i].u, es[i].v)) {
            uf.unite(es[i].u, es[i].v);
            mst.push_back(es[i]);
            mst_sum += es[i].cost;
        }
    }
    int cnt = 0, res_sum = 0;
    for(int i=0; i<N-1; ++i) {
        uf.init(N);
        int sum = 0;
        for(auto& e : es) {
            if(!uf.same(e.u, e.v) && (mst[i].u != e.u || mst[i].v != e.v)) {
                uf.unite(e.u, e.v);
                sum += e.cost;
            }
        }
        if(sum != mst_sum) {
            cnt++;
            res_sum += mst[i].cost;
        }
    }
    cout << cnt << ' ' << res_sum << endl;
}

AOJ 1330 Never Wait for Weights

解法

基本は union-find をいじるだけ.
各ノードは,親からの相対重さを持つ.
クエリで a, b, w が与えられたとする. a と b の代表元が異なる場合は,それぞれの集合の根を r1, r2,各ノードの真の重みを W とおくと,

  • W[r1] - W[r2] = -w + (b の r2 からの相対重み) - (a の r1 からの相対重み)

であることが(簡単な計算で)わかる.
あとはこの処理を union-find 木の処理に追加すればよい.

ソースコード

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

constexpr int INF = 1e9;

class union_find {
public:
    union_find(int N)
        : par(N, -1), rank(N), w(N)
    {}

    pair<int, int> root(int x) {
        if(par[x] < 0) {
            return make_pair(x, 0);
        }
        pair<int, int> p = root(par[x]);
        w[x] += p.second;
        p.second = w[x];
        par[x] = p.first;
        return p;
    }

    void unite(int x, int y, int v) {
        int rx = root(x).first, ry = root(y).first;
        if(rx == ry) {
            return;
        }
        if(rank[rx] > rank[ry]) {
            par[ry] = rx;
            w[ry] = v - w[y] + w[x];
        } else {
            par[rx] = ry;
            w[rx] = -v + w[y] - w[x];
            if(rank[rx] == rank[ry]) {
                rank[ry]++;
            }
        }
    }

    int calc(int x, int y) {
        if(root(x).first != root(y).first) {
            return INF;
        }
        return w[y] - w[x];
    }
        
private:
    vector<int> par;
    vector<int> rank;
    vector<int> w;
};

int main() {
    int N, M;
    while(cin >> N >> M, N) {
        union_find uf(N);
        for(int i=0; i<M; ++i) {
            char op; cin >> op;
            if(op == '!') {
                int a, b, v;
                cin >> a >> b >> v;
                a--; b--;
                uf.unite(a, b, v);
            } else {
                int a, b;
                cin >> a >> b;
                a--; b--;
                if(uf.calc(a, b) == INF) {
                    cout << "UNKNOWN" << endl;
                } else {
                    cout << uf.calc(a, b) << endl;
                }
            }
        }
    }
}

AOJ 1318 Long Distance Taxi

解法

単純に d[街の番号][残りのガソリン] で通ってしまって悲しいので,少し違う方針で.
まず,ガソリンスタンドについたら満タンにしてしまっていいので,ガソリンスタンドから cap を超えないように行ける街をあらかじめ M 回ダイクストラすることによって,新しいグラフを作る.新しい辺の重みはそのガソリンスタンドからの距離とする.(当たり前だが,辺を張るときは ガソリンスタンド -> 行ける街 のように張る.勢いで無向グラフにしないように.)
こうしてできたグラフの上で普通のダイクストラをすれば,上のような二次元配列を持つ必要はなくなる.

ソースコード

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

using pii = pair<int, int>;

struct edge {
    int to, cost;
};

using edges = vector<edge>;
using graph = vector<edges>;

constexpr int INF = 1e9;

vector<int> dijkstra(graph& g, int s) {
    vector<int> d(g.size(), INF);
    priority_queue<pii, vector<pii>, greater<pii>> que;
    que.push(make_pair(0, s));
    d[s] = 0;
    while(!que.empty()) {
        pii p = que.top();
        que.pop();
        int v = p.second;
        if(d[v] < p.first) {
            continue;
        }
        for(auto& e : g[v]) {
            if(d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                que.push(make_pair(d[e.to], e.to));
            }
        }
    }
    return d;
}

int main() {
    int N, M, cap;
    while(cin >> N >> M >> cap, N) {
        unordered_map<string, int> idx;
        string src, dest;
        cin >> src >> dest;
        graph g(6001);
        idx[src] = 0; idx[dest] = 1;
        cap *= 10;
        for(int i=0; i<N; ++i) {
            string c1, c2;
            int d;
            cin >> c1 >> c2 >> d;
            if(idx.count(c1) == 0) {
                idx[c1] = idx.size();
            }
            if(idx.count(c2) == 0) {
                idx[c2] = idx.size();
            }
            g[idx[c1]].push_back(edge{idx[c2], d});
            g[idx[c2]].push_back(edge{idx[c1], d});
        }
        vector<int> S = {0, 1};
        for(int i=0; i<M; ++i) {
            string s;
            cin >> s;
            S.push_back(idx[s]);
        }
        graph g2(S.size());
        for(int i=0; i<S.size(); ++i) {
            auto d = dijkstra(g, S[i]);
            for(int j=0; j<S.size(); ++j) {
                if(d[S[j]] <= cap) {
                    g2[i].push_back(edge{j, d[S[j]]});
                }
            }
        }
        auto res = dijkstra(g2, 0);
        cout << (res[1] == INF ? -1 : res[1]) << endl;
    }
}