AOJ 1298 - Separate Points

ミナリンスキー和．

解法

n>=mとして一般性を失わない．(必要なのは白か黒かという区別だけである．)
(1) n=1のとき
m=1である．点は重ならないといっているので，適当な直線で分けられる．

(2) n=2のとき
m=1ならば，黒の2頂点を結ぶ線分内に白い点が入っていないときのみ，分けることができる．
m=2ならば，白黒それぞれの2頂点を結ぶ線分が交点をもたないときのみ，分けることができる．

(3) n>=3のとき
黒い点の凸包を求め，白い点がその凸包に含まれているかどうか調べる．
1点でも含まれていれば，分けることはできない．
同様に白い点に対して，凸包をとり，黒い点がそれに含まれているか調べる．

コード

ライブラリ部分は省略しています．

#include <cstdio>
#include <vector>
#include <algorithm>

typedef long long ll;

int N, M;
std::vector<P> bs, ws;

int main(){
    while(scanf("%d %d", &N, &M), N || M){
        bs.resize(N);
        ws.resize(M);
        
        for(int i=0;i<N;i++){
            ll x, y;
            scanf("%lld %lld", &x, &y);

            bs[i].real(x);
            bs[i].imag(y);
        }
        for(int i=0;i<M;i++){
            ll x, y;
            scanf("%lld %lld", &x, &y);

            ws[i].real(x);
            ws[i].imag(y);        
        }

        if(N == 1 && M == 1){
            puts("YES");
            continue;
        }

        if(N < M){std::swap(bs, ws); std::swap(N, M);}

        if(N == 2){
            if(M == 1){
                puts(ccw(bs[0], bs[1], ws[0]) ? "YES" : "NO");
                continue;
            }else{
                puts(!areIntersectedLines(bs[0], bs[1], ws[0], ws[1]) ? "YES" : "NO");
                continue;
            }
        }
        
        std::vector<P> ch = convex_hull(bs);

        bool res = true;
        for(int i=0;i<M;i++){
            if(isIn(ws[i], ch)){res = false; break;}
        }

        if(M >= 3){
            ch = convex_hull(ws);

            for(int i=0;i<N;i++){
                if(isIn(bs[i], ch)){res = false; break;}
            }
        }

        puts(res ? "YES" : "NO");
    }
}

AOJ 2006 - Keitai Message

軽い実装ゲー．コピペを頑張る．

最初に

やはり今頃感がある．

std::string table[10] = {"",
                         ".,!? ",
                         "abc",
                         "def",
                         "ghi",
                         "jkl",
                         "mno",
                         "pqrs",
                         "tuv",
                         "wxyz"};

解法

実装する．

コード

#include <iostream>

std::string table[10] = {"",
                         ".,!? ",
                         "abc",
                         "def",
                         "ghi",
                         "jkl",
                         "mno",
                         "pqrs",
                         "tuv",
                         "wxyz"};

int main(){
    int N;
    std::cin >> N;

    for(;N--;){
        std::string S;
        std::cin >> S;

        int key = -1, index = -1;
        std::string T = "";
        for(char c : S){
            if(c == '0'){
                if(~key){
                    T += table[key][index];
                    key = -1;
                    index = -1;
                }
            }else{
                if(!~key){
                    key = c - '0';
                    index = 0;
                }else{
                    index = (index+1) % table[key].size();
                }
            }
        }

        std::cout << T << std::endl;
    }
}

AOJ 2000 - Misterious Gems

REだったけど，何かstd::cinつかったらできた．

解法

言われたとおりにシミュレーションする．

コード

元がC言語で書いてたものだから，C++って感じしない．

#include<cstdio>
#include<cstring>
#include<iostream>
 
#define FOR(i,a,b) for(i=(a);i<(b);i++)
#define REP(i,j) FOR(i,0,j)
 
const int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
 
int main(){
    int N;
    while(scanf("%d", &N), N){
        int map[21][21];
        memset(map, 0, sizeof(map));
 
        int i, j;
        REP(i, N){
            int x, y;
            scanf("%d %d", &x, &y);
 
            map[y][x] = 1;
        }
 
        int m;
        scanf("%d", &m);
 
        int x = 10, y = 10, res = map[10][10];
        REP(i, m){
            char d;
            int l;
            std::cin >> d >> l;
         
            if(d == 'N'){
                d = 0;
            }else if(d == 'S'){
                d = 1;
            }else if(d == 'E'){
                d = 2;
            }else{
                d = 3;
            }
 
            REP(j, l){
                x += dx[d];
                y += dy[d];
 
                res += map[y][x];
                map[y][x] = 0;
            }
        }
 
        if(res == N){
            puts("Yes");
        }else{
            puts("No");
        }
    }

    return 0;
}

AOJ 2406 - Al dente

ふむふむ．

解法

各xに対し，T-E<=kxを満たす最小のkを求める．このとき，T-E<=kx<=T+Eを満たしていればその砂時計を使えばいい．

コード

#include <cstdio>

int main(){
    int N, T, E;
    scanf("%d %d %d", &N, &T, &E);

    for(int i=1;i<=N;i++){
        int x;
        scanf("%d", &x);

        int t;
        for(t=0;t<T-E;t+=x);
        if(t <= T+E){printf("%d\n", i); return 0;}
    }
    puts("-1");
}

AOJ 1188 - Hierarchical Democracy

iteratorはミスるなあ．

解法

簡単な構文解析(というほど大げさじゃない？)

コード

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>

typedef std::string::const_iterator State;

std::string S;

int solve(State& s){
    s++;
    if(std::isdigit(*s)){
        int n = 0;
        for(;std::isdigit(*s);s++){
            n = 10 * n + (*s - '0');
        }
        s++;
        return (n+1) / 2;
    }

    std::vector<int> v;
    for(;;){
        if(*s == '['){
            v.push_back(solve(s));
        }else{
            break;
        }
    }
    s++;

    std::sort(v.begin(), v.end());
    int res = 0;
    for(int i=0;i<(v.size()+1)/2;i++){
        res += v[i];
    }

    return res;
}

int main(){
    int N;
    std::cin >> N;

    while(N--){
        std::cin >> S;

        State s = S.begin();
        std::cout << solve(s) << std::endl;
    }
}

AOJ 1193 - Chain Disappearance Puzzle

いい感じのシミュレーション．

解法

シミュレーション．

コード

#include <cstdio>
#include <algorithm>

const int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};

int H, W = 5;
int map[10][5];

int main(){
    while(scanf("%d", &H), H){
        for(int i=0;i<H;i++){
            for(int j=0;j<W;j++){
                scanf("%d", &map[i][j]);
            }
        }

        int res = 0;
        while(true){
            bool updated = false;
            for(int i=0;i<H;i++){
                for(int j=0,k=0;j<W;){
                    while(k < W && map[i][k] == map[i][j]){k++;}
                    if(k-j >= 3 && ~map[i][j]){
                        res += (k-j) * map[i][j];
                        for(;j<k;j++){
                            map[i][j] = -1;
                        }
                        updated = true;
                    }else{
                        j = k;
                    }
                }
            }
        
            if(!updated){break;}

            for(int i=0;i<5;i++){
                for(int j=H-1,k=H-1;j>=0;j--,k--){
                    while(k >= 0 && !~map[k][i]){k--;}
                    if(k == -1){break;}
                    std::swap(map[j][i], map[k][i]);
                }
            }      
        }

        printf("%d\n", res);
    }
}

RUPC 2015 Day 1

立命館は(どこにあるか知らないレベルで)遠かったので，家から参加しました．
結果はABCDの4完でした．

A(Soccer)

問題文はちゃんと読みましょう．

解法

言われたとおりに書く．

コード

#include <cstdio>
#include <cmath>

typedef long long ll;

ll F0[100], X0[100], Y0[100], A0[100], T0[100];

int main(){
    int N;
    scanf("%d", &N);

    for(int i=0;i<N;i++){
        scanf("%lld %lld %lld %lld %lld", F0+i, A0+i, T0+i, X0+i, Y0+i);
    }

    ll longest[2] = {-1, -1}, shortest[2] = {-1, -1};
    for(int i=0;i+1<N;i++){
        if(T0[i] != T0[i+1] || A0[i] == A0[i+1]){continue;}

        ll df = F0[i+1] - F0[i],
            dx = X0[i+1] - X0[i],
            dy = Y0[i+1] - Y0[i],
            dist2 = dx * dx + dy * dy;

        if(dist2 > longest[T0[i]]){
            longest[T0[i]] = dist2;
            shortest[T0[i]] = df;
        }else if(dist2 == longest[T0[i]] && df < shortest[T0[i]]){
            shortest[T0[i]] = df;
        }
    }

    for(int i=0;i<2;i++){
        if(longest[i] == -1){
            puts("-1 -1");
        }else{
            printf("%.6f %.6f\n", std::sqrt(longest[i]), 1. * shortest[i] / 60);
        }
    }

}

B(RUPC)

くるくる．

解法

累積和をとって，二分探索(upper_bound)．

コード

#include <cstdio>
#include <algorithm>

typedef long long ll;

ll A[300000], A_[300000];
ll B[300000], C[300000];

int main(){
    int N;
    scanf("%d", &N);

    for(int i=0;i<N;i++){
        scanf("%lld", A+i);
    }
    std::sort(A, A+N);
    for(int i=0;i<N;i++){
        A_[i] = A[i];
        if(i > 0){A_[i] += A_[i-1];}
    }
    
    int M;
    scanf("%d", &M);

    for(int i=0;i<M;i++){
        scanf("%lld", B+i);
    }
    for(int i=0;i<M;i++){
        scanf("%lld", C+i);
    }
    for(int i=0;i<M;i++){
        if(A[0] > B[i]){
            puts(C[i] == 0 ? "Yes" : "No");
            continue;
        }
        if(A_[std::upper_bound(A, A+N, B[i])-A-1] >= C[i]){
            puts("Yes");
        }else{
            puts("No");
        }
    }
}

C(Shopping)

有向グラフだとおもって，強連結成分分解にしようとしてた．Ω＼ζ°)ﾁｰﾝ

解法

UnionFind木．mapをつかうと楽．

コード

#include <cstdio>
#include <iostream>
#include <unordered_map>

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,j) FOR(i,0,j)

const int MAX_N = 5000;

class UnionFind{
public:
    UnionFind(int n){
        REP(i, n){
            par[i] = i;
            rank[i] = 0;
        }
    }
    int find(int x){
        if(x == par[x])return x;
        return par[x] = find(par[x]);
    }
    bool same(int x, int y){
        return find(x) == find(y);
    }
    void unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y){return;}
        
        if(rank[x] > rank[y]){
            par[y] = x;
        }else{
            par[x] = y;
            if(rank[x] == rank[y]){rank[y]++;}
        }
    }
private:
    int rank[MAX_N], par[MAX_N];
};

int N, M;
int X[5000];
std::unordered_map<std::string, int> map;
UnionFind uf(5000);

int main(){
    scanf("%d", &N);

    for(int i=0;i<N;i++){
        std::string name;
        std::cin >> name >> X[i];

        map[name] = i;
    }

    scanf("%d", &M);
    
    for(int i=0;i<M;i++){
        std::string from, to;
        std::cin >> from >> to;

        uf.unite(map[from], map[to]);
    }

    int sum = 0;
    for(int i=0;i<N;i++){
        int mn = 1001001001;
        for(int j=0;j<N;j++){
            if(uf.same(i, j)){
                mn = std::min(mn, X[j]);
            }
        }

        sum += mn;
    }

    printf("%d\n", sum);
}

D(Hopping Hearts)

ﾅﾆｿﾚｲﾐﾜｶﾝﾅｲ．BIT便利だなあ．

解法

左右をひっくり返して，うさぎが左にジャンプするようにする．
dp[i][j] := i番目のうさぎが位置jにいて，それより前のうさぎが位置jより左にいるような配置の数とすると，
X[i+1]-kA[i+1](kは非負整数)の形で表される整数jに対して，
dp[i+1][j] = dp[i][j-1] + dp[i][j-2] + ... + dp[i][0]
となる．右辺を計算するためにBITをつかう．
うさぎが同じ位置にジャンプする，すなわち，A[i]=0の場合があることに注意．

コード

#include <iostream>
#include <algorithm>
#include <cstring>

typedef long long ll;

const ll MOD = 1000000007ll;

int N, L;
int X[5000], A[5000];
ll BIT[2][5001];

inline void add(int k, ll v, ll (&bit)[5001]){
    k += 1;
    while(k <= L){
        bit[k] = (bit[k] + v) % MOD;
        k += k & -k;
    }
}

inline ll sum(int k, ll (&bit)[5001]){
    k += 1;
    ll res = 0ll;
    while(k > 0){
        res = (res + bit[k]) % MOD;
        k -= k & -k;
    }
    return res;
}

int main(){
    scanf("%d %d", &N, &L);

    for(int i=0;i<N;i++){
        scanf("%d", X+i);
        X[i] = L-1 - X[i];
    }
    std::reverse(X, X+N);
    
    for(int i=0;i<N;i++){
        scanf("%d", A+i);
    }
    std::reverse(A, A+N);

    if(A[0] == 0){
        add(X[0], 1, BIT[0]);
    }else{
        for(int i=X[0];i>=0;i-=A[0]){
            add(i, 1, BIT[0]);
        }
    }

    int prev = 0, next = 1;
    for(int i=1;i<N;i++){
        memset(BIT[next], 0, sizeof(BIT[next]));

        if(A[i] == 0){
            add(X[i], sum(X[i]-1, BIT[prev]), BIT[next]);
        }else{
            for(int j=X[i];j>=0;j-=A[i]){
                add(j, sum(j-1, BIT[prev]), BIT[next]);
            }
        }

        std::swap(prev, next);
    }

    printf("%lld\n", sum(L-1, BIT[prev]));
}

E(Ocarina of Time)

ダメです．

解法

Warshall-Floyd法とbitDP．
発生済みのイベントを固定して，任意の2つの街の最短距離を求める．
何もイベントが起きていないときについてはWarshall-Floyd法で求め，それ以外は1つずつイベントを追加すれば，それによって生じる道を通る経路と元の最短距離の短い方を選べばよくなる．
前者はO(N^3)，後者は全体でO(2^E E N^2)ぐらい．
得られた最短距離をつかいbitDPをする．[発生済みのイベント][日数][頂点]をもつようにする．
頂点はイベントを発生させる頂点と始点，終点以外はいらないので高々E+2個だけである．
よって，O(2^E R E^2)ぐらい．

コード

これを素で書けるぐらいになりたいなあ．

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <tuple>

typedef std::tuple<int,int,int> T;

const int INF = 1001001001;

int N, M, E, S, T_, R;
int d[1<<8][100][100], dp[1<<8][101][10];
T events[8];
bool used[1<<8];

void rec(int s){
    if(used[s]){return;}
    used[s] = true;
    
    for(int i=0;i<E;i++){
        if(s >> i & 1){continue;}

        int ns = s | (1 << i);
        int a = std::get<0>(events[i]),
            b = std::get<1>(events[i]);
        for(int j=0;j<N;j++){
            for(int k=0;k<N;k++){
                d[ns][j][k] = d[s][j][k];
            }
        }
        for(int j=0;j<N;j++){
            for(int k=0;k<N;k++){
                int nd = std::min(d[ns][j][a] + 1 + d[ns][b][k], d[ns][j][b] + 1 + d[ns][a][k]);
                if(nd > R){continue;}
                d[ns][j][k] = std::min(d[ns][j][k], nd);
            }
        }

        rec(ns);
    }
}

int rec2(int s, int day, int index){
    if(dp[s][day][index] != -1){return dp[s][day][index];}
    
    int u = index == E ? S : std::get<2>(events[index]);
    
    int res = INF;
    for(int i=0;i<E;i++){
        if(s >> i & 1){continue;}
        if(i == index){continue;}
        
        int c = std::get<2>(events[i]);
        if(day + d[s][u][c] <= R){
            res = std::min(res, d[s][u][c] + rec2(s | (1 << i), day + d[s][u][c], i));
        }
    }

    if(day + d[s][u][T_] <= R){
        res = std::min(res, d[s][u][T_]);
    }
    if(day > 0){
        res = std::min(res, rec2(s, 0, E) + 1);
    }

    return dp[s][day][index] = res;
}

int main(){
    scanf("%d %d %d %d %d %d", &N, &M, &E, &S, &T_, &R);

    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            d[0][i][j] = i == j ? 0 : INF;
        }
    }
    
    for(int i=0;i<M;i++){
        int a, b;
        scanf("%d %d", &a, &b);

        d[0][a][b] = 1;
        d[0][b][a] = 1;
    }

    for(int k=0;k<N;k++){
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(d[0][i][k] + d[0][k][j] > R){continue;}
                d[0][i][j] = std::min(d[0][i][j], d[0][i][k] + d[0][k][j]);
            }
        }
    }

    for(int i=0;i<E;i++){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);

        events[i] = std::make_tuple(a, b, c);
    }
    rec(0);
    
    for(int i=0;i<1<<E;i++){
        for(int j=0;j<=R;j++){
            for(int k=0;k<=E;k++){
                dp[i][j][k] = -1;
            }
        }
    }
    int res = rec2(0, 0, E);
    if(res < INF){printf("%d\n", res);}
    else{puts("-1");}
}

F(Tree)

あとで解きたい．