2013-07-31

AOJ 1186 Integral Rectangles (ICPC国内予選2013問題A)

AOJ ICPC

問題文

正整数w, h(1 <= w, h <= 100 かつ h < w)が与えられ, (w^2 + h^2, h)と(W^2 + H^2, H)を辞書式順序で比較した際に(H < W)かつ(w^2 + h^2, h)以上で最小の(W^2 + H^2, H)を求め、H, Wを出力する問題です。

解のW, Hはともに150以下であることが保証されているので1以上150以下でH < Wを満たす任意のW, Hについて比較して調べるとよいです。
ペアの比較はC++ならpairを使うと最初から比較が辞書式順序になっているので楽です。

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

typedef pair<int,int> P;

int main(){
    int w, h;
    while( cin >> h >> w , h || w ){
        pair<P,int> p(P(w*w + h*h, h), w);
        vector<pair<P,int> > v;
        for(int h_ = 1; h_ <= 150; h_++){
            for(int w_ = 1; w_ <= 150; w_++){
                if( h_ < w_ ){
                    v.push_back( pair<P,int>(P(w_*w_ + h_*h_, h_), w_) );
                }
            }
        }
        sort(v.begin(), v.end());
        for(int i = 0; i < v.size(); i++){
            if( p < v[i] ){
                cout << v[i].first.second << " " << v[i].second << endl;
                break;
            }
        }
    }
}

2013-07-31

AOJ 1187 ICPC Ranking (ICPC国内予選2013問題B)

AOJ ICPC

問題文

模擬国内予選2012問題Bとよく似た問題でコンテストの提出履歴が与えられた時にICPCルールで順位付けをしてチーム番号を順位の高い方から出力します。C++なら比較関数を用意してソートするとよいです。

この問題では順位が同一のときには、それらのチーム間をカンマでなく'='で区切る必要があるので気をつけましょう。また正解していない問題に対してはペナルティは加算されない点にも注意しましょう。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Team{
    vector<bool> is_solve;
    vector<int> WA;
    int team_id, time, solved;
    Team(){}
    Team(int P, int id){
        is_solve = vector<bool>(P, false);
        WA = vector<int>(P, 0);
        team_id = id;
        time = 0;
        solved = 0;
    }
};
bool operator<(const Team &a, const Team &b){
    if( a.solved == b.solved ){
        if( a.time == b.time ){
            return a.team_id > b.team_id;
        }
        return a.time < b.time;
    }
    return a.solved > b.solved;
}
bool operator==(const Team &a, const Team &b){
    return a.solved == b.solved && a.time == b.time;
}

int main(){
    int M, T, P, R;
    while( cin >> M >> T >> P >> R, M ){
        vector<Team> v;
        for(int i = 0; i < T; i++){
            v.push_back( Team(P, i) );
        }
        
        for(int i = 0; i < R; i++){
            int m, t, p, j;
            cin >> m >> t >> p >> j;
            t--; p--;
            if( j == 0 ){ // Correct Answer
                for(int k = 0; k < v.size(); k++){
                    if( v[k].team_id == t ){
                        v[k].is_solve[p] = true;
                        v[k].solved++;
                        v[k].time += m;
                        v[k].time += 20 * v[k].WA[p];
                        break;
                    }
                }
            }else{ // Wrong Answer
                for(int k = 0; k < v.size(); k++){
                    if( v[k].team_id == t ){
                        v[k].WA[p]++;
                        break;
                    }
                }
            }
        }
        
        sort(v.begin(), v.end());
        for(int i = 0; i < v.size(); i++){
            if( i ){
                bool flag = (v[i-1] == v[i]);
                cout << (flag? "=" : ",");
            }
            cout << v[i].team_id + 1;
        }
        cout << endl;
    }
}

2013-07-31

AOJ 1188 Hierarchical Democracy (ICPC国内予選2013問題C)

AOJ ICPC

問題文

括弧の始まり('[')が来たときに再帰呼び出しをしてその括弧の始まりに対応する括弧の終わり(']')が来た時にその選挙区で必要な最小の得票数を計算してその結果を返せばよいです。
第 1 段階の有権者数で必要な最小の得票数は有権者の過半数の票なので、有権者の数を c とすると必要な最小の得票数は (c + 1)/2 です。なので数字が来たときは適切にパースして最小の得票数 (c + 1)/2 を vector にでも入れます。

第 k 段階で必要な最小の得票数は、この選挙区に含まれる第 k − 1 段階の選挙区のうち過半数で勝った候補者の最小の得票数となります。つまり第 k 段階の選挙区に含まれる第 k − 1 段階のそれぞれの候補者の必要な最小の得票数を
{c1 ,c2 , ... ,cn} (n が必ず奇数)
とするとこれらをソートして小さい方から (n + 1)/2 個の合計が第 k 段階の必要な最小の得票数となります。

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

string s;
int p = 0;

bool is_digit(char c){
    return '0' <= c && c <= '9';
}

int dfs(){
    vector<int> v;
    while( p < s.size() ){
        if( is_digit(s[p]) ){
            int res = 0;
            while( is_digit(s[p]) ){
                res *= 10;
                res += s[p] - '0';
                p++;
            }
            v.push_back((res + 1) / 2);
        }else if( s[p] == '[' ){
            p++;
            v.push_back( dfs() );
        }else if( s[p] == ']' ){
            p++;
            int n = v.size();
            vector<int> a = v;
            sort(a.begin(), a.end());
            int res = 0;
            for(int i = 0; i <= n/2; i++){
                res += a[i];
            }
            return res;
        }
    }
}

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> s;
        p = 1;
        cout << dfs() << endl;
    }
}

2013-07-31

AOJ 1189 Prime Caves (ICPC国内予選2013問題D)

AOJ ICPC

問題文

1から m まで(1 <= m <= 10^6)まで螺旋状に書かれたとき, 数字 n (1 <= n <= m)からスタートして下・右下・左下の移動を繰り返し移動します。そのような経路の中で通った素数の個数が最大の経路を求め, その個数と最後に通った素数を出力します。

ある整数が素数かどうかO(1)で判定できるようにエラトステネスの篩等で最初に素数を列挙しておきます。次に螺旋状に数字を書きます。バグりやすいので気をつけましょう。ここまでできたらDPで解を計算するだけです。
dp[y][x] := (x,y) までたどりつくときに通った素数の個数
is_p[n] := 整数 n が素数のとき 1, そうでないときは 0 を返す
a[y][x] := (x,y) に書かれた数字を返す
として
dp[y+1][x] = max(dp[y][x-1] + is_p[a[y][x-1]], max(dp[y][x] + is_p[a[y][x]], dp[y][x+1] + is_p[a[y][x+1]]))
という漸化式が成り立つと思います。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_P = 1001000;
const int MAX_W = 1020;
const int dx[4] = {+1,  0, -1,  0};
const int dy[4] = { 0, -1,  0, +1};

// is_p[n] := 正整数 n が素数かどうか
char is_p[MAX_P];
// a[y][x] := (x,y) の洞穴の番号
int a[MAX_W][MAX_W] = {0};
// dp[y][x] := (x,y) にたどり着くまでの素数洞穴を調べた個数
int dp[MAX_W][MAX_W];
// X[k] := 洞穴の番号 k の x 座標 (Yも同様)
int X[MAX_P];
int Y[MAX_P];

void init(){
    // エラトステネスの篩
    fill(is_p, is_p + MAX_P, 1);
    is_p[0] = is_p[1] = 0;
    for(int i = 2; i < MAX_P; i++){
        if( is_p[i] ){
            for(int j = i + i; j < MAX_P; j += i){
                is_p[j] = 0;
            }
        }
    }
}

void make_douketu(int m){
    for(int y = 0; y < MAX_W; y++){
        for(int x = 0; x < MAX_W; x++){
            a[y][x] = 0;
        }
    }
    int k = 1, x = MAX_W / 2, y = MAX_W / 2, dir = 0, d = 2;
    while( k < MAX_P ){
        for(int i = 0; i < (d / 2); i++){
            a[y][x] = k;
            X[k] = x;
            Y[k] = y;
            x += dx[dir];
            y += dy[dir];
            k++;
            if( m < k ) return;
            if( MAX_W <= x || MAX_W <= y ) break;
        }
        dir = (dir + 1) % 4;
        d++;
        if( MAX_W <= x || MAX_W <= y ) break;
    }
}

int main(){
    init();
    int n, m;
    while( cin >> m >> n, n || m){
        make_douketu(m);
        for(int y = 0; y < MAX_W; y++){
            for(int x = 0; x < MAX_W; x++){
                dp[y][x] = -1;
            }
        }
        int sx = X[n], sy = Y[n];
        dp[sy][sx] = is_p[n];
        
        int ans = 0;
        for(int y = 0; y < MAX_W; y++){
            for(int x = 0; x < MAX_W; x++){
                ans = max(ans, dp[y][x]);
                if( a[y][x] == 0 ) continue;
                
                if( dp[y][x] != -1 ){
                    int my = y + 1;
                    if( MAX_W <= my ) continue;
                    
                    int d[3] = {-1,0,1};
                    for(int i = 0; i < 3; i++){
                        int mx = x + d[i];
                        if( mx < 0 || MAX_W <= mx ) continue;
                        
                        int k = a[my][mx];
                        if( k == 0 ) continue;
                        dp[my][mx] = max(dp[my][mx], dp[y][x] + is_p[k]);
                        ans = max(ans, dp[my][mx]);
                    }
                }
            }
        }
        
        if( ans == 0 ){
            cout << "0 0" << endl;
            continue;
        }
        int ans_n = 0;
        for(int y = 0; y < MAX_W; y++){
            for(int x = 0; x < MAX_W; x++){
                if( a[y][x] == 0 ) continue;
                if( dp[y][x] == ans ){
                    int k = a[y][x];
                    if( is_p[k] ){
                        ans_n = max(ans_n, a[y][x]);
                    }
                }
            }
        }
        cout << ans << " " << ans_n << endl;
    }
}

2013-07-31

AOJ 1190 Anchored Balloon (ICPC国内予選2013問題E)

AOJ ICPC

問題文

一つの杭と紐に注目したときに風船が動ける空間は球になっています。(正確にはz<0の空間には移動できないので球を半分にしたような空間ですが)

n個の杭と紐につながった風船が動ける空間はそれぞれの杭と紐について注目した時に動ける空間の共通部分となっていて、その形は凸になっています。(球は凸集合で、凸集合と凸集合の共通部分も凸集合です)

なのでxについて三分探索し, そのなかでyについて三分探索することで最大の高さを求めることができます。(x,yが決まるとその位置について風船が動ける最大の高さを計算できます)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

int n;
double x[10], y[10], l[10];

double search(double X, double Y){
    double res = 1e+9;
    for(int i = 0; i < n; i++){
        double h = l[i] * l[i] - ((X - x[i]) * (X - x[i])) - ((Y - y[i]) * (Y - y[i]));
        res = min(res, h);
    }
    return res;
}

double searchY(double X){
    double left = -100.0, right = 100.0;
    for(int i = 0; i < 200; i++){
        double mid1 = (2 * left + right) / 3;
        double mid2 = (left + 2 * right) / 3;
        if( search(X, mid1) > search(X, mid2) ){
            right = mid2;
        }else{
            left = mid1;
        }
    }
    return search(X, left);
}

double searchXY(double left = -100.0, double right = 100.0){
    for(int i = 0; i < 200; i++){
        double mid1 = (2 * left + right) / 3;
        double mid2 = (left + 2 * right) / 3;
        if( searchY(mid1) > searchY(mid2) ){
            right = mid2;
        }else{
            left = mid1;
        }
    }
    return searchY(left);
}

int main(){
    while( cin >> n , n ){
        for(int i = 0; i < n; i++) cin >> x[i] >> y[i] >> l[i];
        double ans = sqrt(searchXY());
        printf("%.07f\n", ans);
    }
}

2013-07-23

CODEVS2.1の決勝を観戦しました

プログラミングコンテスト

CODEVS2.1決勝詳細

7/21(日)にCODEVS2.1の決勝を観戦しに東京に行きました。
体力的にも金銭的にもあまり余裕がなくて自宅でニコ生観戦する予定でしたが、予選成績がSILVER(30位以内)の人にも交通費が出るということで会場に行くことにしました。

CODEVS TOTO

観戦者は当日会場に来るとCODEVS TOTOというものがあり、決勝進出者の中から優勝者しそうな1人に投票し予想を当てた人の中から抽選で1名にMacBook Airをプレゼントという企画がありました。

私は予選2位のustimawさんか予選4位のozy4dmさんか予選7位のtek1031さんが優勝するのではないかと見込んでいました。誰に投票するかは迷うところではありますがtek1031さんは前回優勝者で決勝前のツイートでも強そうなことが予想でき、また東北勢なので応援の思いも込めてtek1031さんに投票していました。

決勝戦

結果から言うとustimawさんが優勝しました。強かった(小並感)。
「賞金は何に使いますか？」という質問にustimawさんは「引越しと新しい洗濯機に使いたいです」とのことでした。洗濯機大事ですよね、洗濯機。
それでCODEVS TOTOでustimawさんに投票したのがまさかの2人という状況で、普通ならくじびきをするところをじゃんけんでMacBook Airを貰う人を決めるという予想外の展開となりました。

個人的にはCODEVS TOTOを抜きにしてもtek1031さんに優勝してほしかったですが、1回戦でいきなりustimawさんにあたってしまってちょっと運が悪かったという感じはしました(tek1031さんのプログラムも強かったと思うので2位になる可能性はあったと思う)。

あとkusanoさんのプログラムは3時間の計算できる時間を使いきって時間切れという面白い負け方をしていて、試合をとても盛り上げていたのが印象的でした。kusanoさん大人気でしたね。

決勝進出者の一部の人は戦略をツイートしているようでしたので参考までに。

ustimawさんの戦略
https://twitter.com/ustimaw/status/359258644942036992

tek1031さんの戦略
https://twitter.com/tek1031/status/359260467442618368

nosnosnosさんの戦略
https://twitter.com/nosnosnos/status/359273649443840001
https://twitter.com/nosnosnos/status/359273714707202052