AOJ 0552 - Exposition

コードがやばい．

解法

(x, y) -> (x+y, x-y)という変換(45度回転)をすると，施設iと施設jの距離は
max{|x[i]-x[j]|, |y[i]-y[j]|}
と表されます．以下，変換後の座標系で話をすすめます．
まず，x座標とy座標で幅の広い方(最小値と最大値の差が大きい方．同じときはどちらでもいい)を選び，その座標の最小値と最大値を求める．
この2つが同じテーマだと，どう頑張っても最長になってしまうので違うテーマに分けてあげます．
その後，各テーマで(最小/最大)の(x座標/y座標)をもちながら，次のようにテーマを割り振る．
それぞれのテーマで最も遠い施設を求め，より距離が遠い方(同じときはどちらでもよい)を，他方のテーマに割り当てる．
すべての施設を割り当てたとき，2つのテーマの(x座標/y座標)の最小・最大の差の大きい方が答えになります．

x座標とy座標で幅の広い方，最も遠い点はどう求めたらいいでしょうか．距離の式がx座標，y座標について分離しているので，x座標でソートしたもの，y座標でソートしたものがあるといいですね．さらに，削除がある程度速いといいですね．これって何てstd::set．(なお，特別なデータ構造をつかわなくても解ける模様．)

コード

Ω\・8・)ﾁｭｰﾝ

// ﾅﾆｿﾚｲﾐﾜｶﾝﾅｲ

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

typedef std::pair<int,int> P;
typedef std::tuple<P,bool,int> Q;
std::set<P> setX, setY;
int N;

Q f(int mnX, int mxX, int mnY, int mxY){
    P p = *setX.begin();
    bool isX = true;
    int l = std::max(std::abs(mnX-p.first),
                     std::abs(mxX-p.first));

    P _p;
    int _l;
    _p = *setX.rbegin();
    if((_l = std::max(std::abs(mnX-_p.first),
                      std::abs(mxX-_p.first))) > l){
        p = _p;
        l = _l;
    }

    _p = *setY.begin();
    if((_l = std::max(std::abs(mnY-_p.first),
                      std::abs(mxY-_p.first))) > l){
        p = _p;
        l = _l;
        isX = false;
    }

    _p = *setY.rbegin();
    if((_l = std::max(std::abs(mnY-_p.first),
                      std::abs(mxY-_p.first))) > l){
        p = _p;
        l = _l;
        isX = false;
    }

    return std::make_tuple(p, isX, l);
}

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

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

        int x_ = x+y, y_ = x-y;
        setX.insert(std::make_pair(x_, y_));
        setY.insert(std::make_pair(y_, x_));
    }

    int mnX1, mxX1, mnY1, mxY1,
        mnX2, mxX2, mnY2, mxY2;
    if(setX.rbegin()->first-setX.begin()->first >
       setY.rbegin()->first-setY.begin()->first){
        mnX1 = setX.begin()->first;
        mxX1 = mnX1;
        mnY1 = setX.begin()->second;
        mxY1 = mnY1;
        mnX2 = setX.rbegin()->first;
        mxX2 = mnX2;
        mnY2 = setX.rbegin()->second;
        mxY2 = mnY2;

        P p1 = *setX.begin(), p2 = *setX.rbegin();
        setY.erase(std::make_pair(p1.second, p1.first));
        setY.erase(std::make_pair(p2.second, p2.first));
        setX.erase(p1);
        setX.erase(p2);
    }else{
        mnX1 = setY.begin()->second;
        mxX1 = mnX1;
        mnY1 = setY.begin()->first;
        mxY1 = mnY1;
        mnX2 = setY.rbegin()->second;
        mxX2 = mnX2;
        mnY2 = setY.rbegin()->first;
        mxY2 = mnY2;

        P p1 = *setY.begin(), p2 = *setY.rbegin();
        setX.erase(std::make_pair(p1.second, p1.first));
        setX.erase(std::make_pair(p2.second, p2.first));
        setY.erase(p1);
        setY.erase(p2);
    }
    
    for(;!setX.empty();){
        Q q1 = f(mnX1, mxX1, mnY1, mxY1),
          q2 = f(mnX2, mxX2, mnY2, mxY2);

        if(std::get<2>(q1) > std::get<2>(q2)){
            mnX2 = std::min(mnX2, std::get<1>(q1) ? std::get<0>(q1).first : std::get<0>(q1).second);
            mxX2 = std::max(mxX2, std::get<1>(q1) ? std::get<0>(q1).first : std::get<0>(q1).second);
            mnY2 = std::min(mnY2, std::get<1>(q1) ? std::get<0>(q1).second : std::get<0>(q1).first);
            mxY2 = std::max(mxY2, std::get<1>(q1) ? std::get<0>(q1).second : std::get<0>(q1).first);

            setX.erase(std::get<1>(q1) ? std::get<0>(q1) : std::make_pair(std::get<0>(q1).second, std::get<0>(q1).first));
            setY.erase(std::get<1>(q1) ? std::make_pair(std::get<0>(q1).second, std::get<0>(q1).first) : std::get<0>(q1));
        }else{
            mnX1 = std::min(mnX1, std::get<1>(q2) ? std::get<0>(q2).first : std::get<0>(q2).second);
            mxX1 = std::max(mxX1, std::get<1>(q2) ? std::get<0>(q2).first : std::get<0>(q2).second);
            mnY1 = std::min(mnY1, std::get<1>(q2) ? std::get<0>(q2).second : std::get<0>(q2).first);
            mxY1 = std::max(mxY1, std::get<1>(q2) ? std::get<0>(q2).second : std::get<0>(q2).first);

            setX.erase(std::get<1>(q2) ? std::get<0>(q2) : std::make_pair(std::get<0>(q2).second, std::get<0>(q2).first));
            setY.erase(std::get<1>(q2) ? std::make_pair(std::get<0>(q2).second, std::get<0>(q2).first) : std::get<0>(q2));
        }
        
    printf("%d\n", std::max({mxX1-mnX1, mxY1-mnY1,
                    mxX2-mnX2, mxY2-mnY2}));
}

ORSolitaire - TopCoder SRM Div1 #600 Easy

これは解ける．223.84pt(Practice)

解法

まず，各整数がgoalをつくるのに使えるかを調べる．
整数nがn | ~goal = 0を満たすならば，nはgoalをつくるのに使える．
(等式を満たさないならば，goalにない1の立つビットができてしまう．)
満たす整数のORをとり，goalにならなければ，そもそもできないので，0を出力する．
そうでなければ，goalの1であるビットに着目する．そのビットが1である整数をすべて削除すれば，goalをつくることはできない．よって，各ビットに対し，そこが1である整数を数えて，その最小の個数を求めればいい．

コード

class ORSolitaire {
public:
    int getMinimum(vector<int> numbers, int goal) {
        int x = 0;
        std::vector<int> v;
        for(int n : numbers){
            if(n & ~goal){continue;}
            x |= n;
            v.push_back(n);
        }

        if(x != goal){return 0;}
        
        int res = 252521;
        for(int i=0;i<=30;i++){
            if(!(goal >> i & 1)){continue;}
            int c = 0;
            for(int j : v){
                if(j >> i & 1){++c;}
            }
            res = std::min(res, c);
        }

        return res;
    }
};

不定期やるだけ(AOJ)

やるだけ．

Flick Input(AOJ 2417)

時代を感じる．

#include <iostream>

std::string table = "  kstnhmyr", table2 = "aiueo", table3 = "TLURD";

int main(){
    std::string S, T = "";
    std::cin >> S;
    for(int i=0;i<S.size();i+=2){
        if(S[i] == '0'){
            if(S[i+1] == 'T'){T += "wa";}
            else if(S[i+1] == 'D'){T += "wo";}
            else{T += "nn";}
        }else if(S[i] == '1'){
            T += table2[table3.find(S[i+1])];
        }else{
            T += table[S[i]-'0'];
            T += table2[table3.find(S[i+1])];
        }
    }

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

Kagisys(AOJ 2440)

unordered_mapで殴る．

#include <iostream>
#include <unordered_map>

std::unordered_map<std::string, int> m;

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

    for(int i=0;i<N;i++){
        std::string key;
        std::cin >> key;

        ++m[key];
    }

    int M;
    std::cin >> M;

    bool locked = true;
    for(int i=0;i<M;i++){
        std::string id;
        std::cin >> id;

        if(m[id] > 0){
            if(locked){
                std::cout << "Opened by " << id << std::endl;
            }else{
                std::cout << "Closed by " << id << std::endl;
            }
            locked ^= 1;
        }else{
            std::cout << "Unknown " << id << std::endl;
        }
    }
}

Parentheses(AOJ 2490)

同じ問題3回ぐらいみた．

#include <iostream>

int N;

bool solve(){
    int opened = 0;
    for(int i=0;i<N;i++){
        char c;
        int n;
        std::cin >> c >> n;

        if(c == '('){
            opened += n;
        }else{
            if(n > opened){return false;}
            opened -= n;
        }
    }

    return opened == 0;
}

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

    std::cout << (solve() ? "YES" : "NO") << std::endl;
}

Summer of KMC(AOJ 2216)

コミケ行ってみたい．

#include <cstdio>

int main(){
    int A, B;
    while(scanf("%d %d", &A, &B), A || B){
        B -= A;
        printf("%d %d %d\n", B % 500 / 100, B % 1000 / 500, B / 1000);
    }
}

koukyoukoukokukikou(AOJ 2252)

the やるだけって感じ．

#include <iostream>

int main(){
    std::string right = "yuiophjklnm";
    std::string S;
    while(std::cin >> S, S != "#"){
        int prev = -1, res = 0;
        for(const auto &c : S){
            int which = right.find(c) != std::string::npos;
            if(prev == -1){
                prev = which;
            }else if(which != prev){
                ++res; prev = which;
            }
        }

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

KUPC(AOJ 2271)

JOI Emblem．

#include <iostream>
#include <algorithm>

int count[26];

int main(){
    std::string S;
    std::cin >> S;

    for(const auto& c : S){
        if(std::islower(c)){continue;}
        ++count[c&63];
    }

    printf("%d\n", std::min({count['K'&63], count['U'&63], count['P'&63], count['C'&63]}));
}

Palindromic Number(AOJ 2489)

疲れてきた．

#include <iostream>

bool isPalindromic[10002];
int A[10002], B[10002];

int main(){
    for(int i=0;i<=10001;i++){
        std::string s = std::to_string(i);
        bool f = true;
        for(int j=0;j<s.size();j++){
            if(s[j] != s[s.size()-1-j]){f = false; break;}
        }
        if(f){isPalindromic[i] = true;}
    }
    
    int prev;
    for(int i=0;i<=10001;i++){
        if(isPalindromic[i]){prev = i;}
        A[i] = prev;
    }

    for(int i=10001;i>=0;i--){
        if(isPalindromic[i]){prev = i;}
        B[i] = prev;
    }
    
    int N;
    std::cin >> N;

    if(std::abs(N-A[N]) <= std::abs(N-B[N])){
        std::cout << A[N]<< std::endl;
    }else{
        std::cout << B[N]<< std::endl;
    }
    
}

Programming Contest(AOJ 2259)

YukiCoderは偉大．(49byte)

gets;p$<.map{|s|s.split.map(&:to_i).inject:+}.max

AOJ 2407 - Simple Othello

ふんふむ．

解法

かたまりで見る．
例. ooxox -> oxox， xoooox -> xox
(1) かたまりが1つ(o, x)
両者はパスするしかないので，そのかたまりの色の方が勝つ．

(2) かたまりが偶数個
oが勝つ．

(3) かたまりが奇数個
端っこの色のほうが勝つ．
例. oxoxo -> oの勝ち，xox -> xの勝ち

コード

#include <iostream>

int main(){
    std::string S;
    std::cin >> S;

    char prev = '*';
    int l = 0;
    for(const char &c : S){
        if(c != prev){
            ++l; prev = c;
        }
    }

    if(l == 1 || l & 1){
        std::cout << S[0] << std::endl;
    }else{
        std::cout << 'o' << std::endl;
    }
}

AOJ 2408 - Social

うさぎ社会の闇．

解法

やるだけ．

コード

#include <cstdio>

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

    int M[50], bunny[50][50];
    for(int i=0;i<K;i++){
        scanf("%d", M+i);

        for(int j=0;j<M[i];j++){
            scanf("%d", &bunny[i][j]);
            --bunny[i][j];
        }
    }

    int R, d[50][50];
    scanf("%d", &R);
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            d[i][j] = 0;
        }
    }
    for(int i=0;i<R;i++){
        int p, q;
        scanf("%d %d", &p, &q);
        --p; --q;
        
        d[p][q] = 1;
        d[q][p] = 1;
    }
    
    int res = 0;
    for(int i=0;i<K;i++){
        for(int j=0;j<M[i];j++){
            for(int k=0;k<M[i];k++){
                if(d[bunny[i][j]][bunny[i][k]]){++res; break;}
            }
        }
    }

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

AOJ 2254 - Fastest Route

やるだけ．

解法

bitDP．

コード

たまにはループで．

#include <cstdio>
#include <algorithm>

int T[16][17], T_[1<<16][16];
int dp[1<<16][16];

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

        for(int i=0;i<1<<N;i++){
            for(int j=0;j<N;j++){
                int mn = T[j][0];
                for(int k=0;k<N;k++){
                    if(!(i >> k & 1)){continue;}
                    mn = std::min(mn, T[j][k+1]);
                }
                T_[i][j] = mn;
            }
        }

        for(int i=0;i<1<<N;i++){
            for(int j=0;j<N;j++){
                dp[i][j] = i == 0 ? 0 : 1001001001;
            }
        }

        for(int i=0;i<1<<N;i++){
            for(int j=0;j<N;j++){
                for(int k=0;k<N;k++){
                    if(i >> k & 1){continue;}
                    int ni = i | (1 << k);
                    dp[ni][k] = std::min(dp[ni][k], dp[i][j] + T_[i][k]);
                }
            }
        }

        int res = 1001001001;
        for(int i=0;i<N;i++){
            res = std::min(res, dp[(1<<N)-1][i]);
        }

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

AOJ 2009 - Area Separation

毎回どうだっけってなる．

解法

1本ずつ直線を足していく．(今までの直線(正方形の辺を含む)と加えた直線の交点)-1だけ領域が増える．但し，正方形内にない交点は含まない．
重複して数えないよう注意する．例えば，

から

のように直線を加えたとき，交点は3つである．

コード

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

#include <cstdio>
#include <algorithm>

double EPS = 1e-9;

int N;
bool used[25252];
P line[104][2];

int main(){
    line[0][0] = {-100.0, -100.0};
    line[0][1] = {-100.0, 100.0};
    line[1][0] = {-100.0, 100.0};
    line[1][1] = {100.0, 100.0};
    line[2][0] = {100.0, 100.0};
    line[2][1] = {100.0, -100.0};
    line[3][0] = {100.0, -100.0};
    line[3][1] = {-100.0, -100.0};
    
    while(scanf("%d", &N), N){
        for(int i=4;i<N+4;i++){
            double x1, y1, x2, y2;
            scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);

            line[i][0].real(x1);
            line[i][0].imag(y1);
            line[i][1].real(x2);
            line[i][1].imag(y2);
        }

        std::vector<P> v{{-100, -100}, {-100, 100}, {100, 100}, {100, -100}};
        int res = 1;
        for(int i=4;i<N+4;i++){
            for(int j=0;j<25252;j++){used[j] = false;}
            
            for(int j=0;j<i;j++){
                if(areIntersectedLines(line[i][0], line[i][1], line[j][0], line[j][1])){
                    P p = intersection(line[i][0], line[i][1], line[j][0], line[j][1]);
                    double x = real(p), y = imag(p);
                    if(x < -100.0 - EPS || x > 100.0 + EPS || y < -100.0 - EPS || y > 100.0 + EPS){continue;}

                    bool f = true;
                    for(int k=0;k<v.size();k++){
                        if(std::abs(dist(p-v[k])) < 1e-10){
                            if(!used[k]){used[k] = true; res++;}
                            f = false;
                            break;
                        }
                    }
                    if(f){res++; v.push_back(p);}
                }
            }
            res--;
        }

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