2013国内予選 E. つながれた風船

E. つながれた風船

解法

• 色々やり方はあるけど、ここでは円の問題に落として2分探索する方針

• 高さhまで風船が上げられるかという問題を考える
  • 高さを決めれば、各ヒモの先端がどの範囲を動けるかは円で表せる
  • その円に共通部分が存在すれば、風船は高さhに上がる事ができる

• 共通部分があれば、それは2つの円の交点か、円の中心のどれかを含む
  • ある円が他の全ての円に内包されるケースがあるので、交点だけだと不十分
  • 含む点の全ての候補について、その点が全ての円に内包されてるか調べれば良い
    • 1個でも内包しない円があれば、その点は共通部分上には無い

• 高さhに上がれない -> 高さh'(>h)にも上がれない なので、あとは2分探索

#include <iostream>
#include <vector>
#include <complex>
#include <cstdio>
#include <cmath>

using namespace std;

const double EPS = 1e-10;

typedef complex<double> P;
typedef pair<P,double> circle;

double cross(P a, P b) { return imag(conj(a)*b); }

bool containPoint(const circle& c, const P& p){
    double dist = abs(c.first-p);
    return dist < c.second+EPS;
}

bool crossCircle(const circle& c1, const circle& c2){
    double r1 = c1.second;
    double r2 = c2.second;
    double d = abs(c1.first-c2.first);
    if(d<r1||d<r2)
        return d-abs(r1-r2)>EPS;
    return r1+r2-d>-EPS;
}

void crossPoint(vector<P> &res, const circle& c1, const circle& c2){
    double r1 = c1.second;
    double r2 = c2.second;
    double r3 = abs(c1.first-c2.first);
    double rc = (r3*r3+r1*r1-r2*r2)/(2*r3);
    double rs = sqrt(r1*r1-rc*rc);
    P dif = (c2.first-c1.first)/r3;
    res.push_back(c1.first+dif*P(rc, rs));
    res.push_back(c1.first+dif*P(rc,-rs));
}

bool valid(const vector<circle>& vc){
    vector<P> vp;
    for(int i=0;i<vc.size();i++){
        vp.push_back(vc[i].first);
        for(int j=i+1;j<vc.size();j++){
            if(crossCircle(vc[i], vc[j]))
                crossPoint(vp, vc[i], vc[j]);
        }
    }
    for(int i=0;i<vp.size();i++){
        bool ok = true;
        for(int j=0;j<vc.size();j++)
            if(!containPoint(vc[j], vp[i])) ok = false;
        if(ok) return true;
    }
    return false;
}

int main(){
    int n;
    int x[10], y[10], l[10]; 
    while(cin >> n &&  n){
        int minL = 100000;
        for(int i=0;i<n;i++){
            cin >> x[i] >> y[i] >> l[i];
            minL = min(minL, l[i]);
        }
        double low = 1.0, high = minL;
        for(int i=0;i<200;i++){
            double mid = 0.5*(low+high);
            vector<circle> vc;
            for(int j=0;j<n;j++){
                double r = sqrt(l[j]*l[j]-mid*mid);
                vc.push_back(make_pair(P(x[j], y[j]), r));
            }
            if(valid(vc)) low  = mid;
            else          high = mid;
        }
        printf("%.8lf\n", 0.5*(low+high));
    }
}

2013国内予選 C. 階層民主主義

C. 階層民主主義

解法

• 第1段階では過半数ギリギリで勝つのが最適
• 第k段階(k>1)について考えると、
  • 過半数ギリギリの選挙区で勝てば良い
  • 勝つのに必要な票数が少ない方から半数の選挙区でだけ票を取る
  • 負けても良い選挙区では0票としてしまって良い

• という感じの計算を、inputを再帰下降で見ながらやってみたのが以下のコード

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int solve(const string& str, int& idx){
    int res = 0;
    ++idx;
    if(str[idx] != '['){
        while(isdigit(str[idx])){
            res = 10*res + str[idx]-'0';
            ++idx;
        }
        res = res/2+1;
    } else {
        vector<int> vi;
        while(str[idx] == '[')
            vi.push_back(solve(str, idx));
        sort(vi.begin(), vi.end());
        for(int i=0;i<vi.size()/2+1;i++)
            res += vi[i];
    }
    ++idx;
    return res;
}

int main(){
    int n; cin >> n;
    while(n--){
        string str; cin >> str;
        int idx = 0;
        cout << solve(str, idx) << endl;
    }
}

2013国内予選 B. 整長方形

B. ICPCの順位付け

解法

• シンプルなシミュレーションの問題
  • 基本的には問題文で言われたとおりに実装すれば良い

• 順位付けはpairとか使って頑張っても良いけど、ここではoperatorを定義。

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

using namespace std;

class Score {
public:
    int teamID;
    int solved;
    int penalty;
    Score(int id) : teamID(id), solved(0), penalty(0) {}
    bool operator < (const Score& sc) const {
        if(solved != sc.solved) return solved < sc.solved;
        if(penalty != sc.penalty) return penalty > sc.penalty;
        return teamID < sc.teamID;
    }
    bool operator == (const Score& sc) const {
        return solved == sc.solved && penalty == sc.penalty;
    }
};

int main(){
    int M, T, P, R;
    int submit[50][10];
    while(cin >> M >> T >> P >> R && M){
        memset(submit, 0, sizeof(submit));
        vector<Score> vs;
        for(int i=0;i<T;i++) vs.push_back(Score(i+1));
        for(int i=0;i<R;i++){
            int m, t, p, j;
            cin >> m >> t >> p >> j;
            --t; --p;
            if(j != 0) submit[t][p]++;
            else {
                vs[t].solved++;
                vs[t].penalty += m + 20*submit[t][p];
            }
        }
        sort(vs.rbegin(), vs.rend());
        cout << vs[0].teamID;
        for(int i=1;i<vs.size();i++){
            if(vs[i] == vs[i-1]) cout << "=" << vs[i].teamID;
            else                 cout << "," << vs[i].teamID;
        }
        cout << endl;
    }
}

2013国内予選 A. 整長方形

A. 整長方形

解法

• A問題だし、男は黙って全探索という感じでやってみた
  • 答えの高さと幅は150を超えないので、あり得る答えを全通り試しても余裕

• 全列挙→ソート→upperbound もアリ

#include <iostream>

using namespace std;

int main(){
    int h, w;
    while(cin >> h >> w && h){
        int area = h*h+w*w;
        int resH = 200, resW = 200, resArea = 10000000;
        for(int i=1;i<=150;i++){
            for(int j=i+1;j<=150;j++){
                int newArea = i*i+j*j;
                if(area > newArea || (area == newArea && i <= h)) continue;
                if(newArea < resArea || (newArea == resArea && i < resH)){
                    resH = i;
                    resW = j;
                    resArea = newArea;
                }
            }
        }
        cout << resH << " " << resW << endl;
    }
}

KUPC2013

ヒマでしたが外出エネルギーを使い果たしてたので自宅に引きこもって参加。

• -

A : 旧総合研究７号館

• ウォーミングアップ

#include <iostream>
#include <string>

using namespace std;

int main(){
    int N, Q;
    while(cin >> N >> Q){
        string res = "kogakubu10gokan";
        int minYear = 1;
        for(int i=0;i<N;i++){
            int year; string name;
            cin >> year >> name;
            if(minYear < year && year <= Q){
                minYear = year;
                res = name;
            }
        }
        cout << res << endl;
    }
}

B : ライオン

• Bだし全探索やるだけに違いないと思って制約見たらそうだったのでやった。
• nとmをtypoしてたり、答えじゃない変数を出力してたりして2WA(´・ω・｀)

#include <iostream>
#include <vector>

using namespace std;

int l[10], r[10], s[10];
vector<int> res;

void search(int idx, vector<int>& vi, int n, int x, int m){
    if(idx == n){
        bool ok = true;
        for(int i=0;i<m;i++){
            int sum = 0;
            for(int j=l[i]-1;j<=r[i]-1;j++) sum += vi[j];
            if(sum != s[i]) ok = false;
        }
        if(ok){
            int curMax = 0, curSum = 0;
            for(int i=0;i<n;i++){
                curMax += res[i];
                curSum += vi[i];
            }
            if(curMax < curSum) res = vi;
        }
    } else {
        for(int i=0;i<=x;i++){
            vi[idx] = i;
            search(idx+1, vi, n, x, m);
        }
    }
}

int main(){
    int n, x, m;
    while(cin >> n >> x >> m){
        for(int i=0;i<m;i++) cin >> l[i] >> r[i] >> s[i];
        vector<int> vi(n, 0);
        res = vector<int>(n, -1);
        search(0, vi, n, x, m);
        if(res[0] != -1){
            for(int i=0;i<n-1;i++) cout << res[i] << " ";
            cout << res.back() << endl;
        } else {
            cout << -1 << endl;
        }
    }
}

C : チョコレート

• 上にチョコがあれば、という制約があるので1行ずつ調べれば良い。
• 各行では左右から食べたときにどこでぶつかるで全探索。
• N=1とN=2だけ怖かったので特別扱いしてみた。

#include <iostream>
#include <cmath>

using namespace std;

int main(){
    int N, M;
    int a[100];
    while(cin >> M >> N){
        int res = 0;
        for(int i=0;i<M;i++){
            for(int j=0;j<N;j++) cin >> a[j];
            if(i>0) for(int j=0;j<N;j++) a[j] = 1-a[j];
            if(N==1) res += a[0];
            if(N==2) res += abs(a[0]-a[1])+1;
            if(N>2){
                int add = 0;
                int sum = a[0];
                for(int i=1;i<N;i++) sum += 1-a[i];
                add = max(sum, add);
                sum = a[N-1];
                for(int i=0;i<N-1;i++) sum += 1-a[i];
                add = max(sum, add);
                for(int i=1;i<N-1;i++){
                    sum = a[0]+a[N-1]+a[i];
                    for(int j=1;j<N-1;j++){
                        if(i==j) continue;
                        sum += 1-a[j];
                    }
                    add = max(sum, add);
                }
                res += add;
            }
        }
        cout << res << endl;
    }
}

D : カーペット

• スタックに積むだけだなぁと思って積んだら通った。

#include <iostream>
#include <stack>

using namespace std;

int main(){
    int N;
    while(cin >> N){
        int res = 0;
        stack<int> st;
        for(int i=0;i<N;i++){
            int a; cin >> a;
            while(!st.empty() && st.top() > a) st.pop();
            if(st.empty() || st.top() < a){ st.push(a); res++; }
        }
        cout << res << endl;
    }
}

E : すごろく

• 問題名だけ見てリアクティブ枠か…と思いながら開いた。
• 各マスから最短何回の移動でゴールできるかをBFSで調べておく。
• あとはゴールまでの移動数が減るマスに行ける目が来るまで待機。
• 最悪1/6の確率で移動できるし、試行数がマス目の10倍あるし大丈夫だろ的な感じ。

#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
#include <stdlib.h>

using namespace std;

int main(){
    int M;
    int s, g;
    int a[6];
    int N[300];
    int step[300];
    int visit[300];
    while(cin >> M){
        for(int i=0;i<6;i++) cin >> a[i];
        cin >> s >> g; --s; --g;
        for(int i=0;i<M;i++) cin >> N[i];
        memset(visit, 0, sizeof(visit));
        for(int i=0;i<M;i++) step[i] = 10000000;
        step[g] = 0;
        queue<int> qu; qu.push(g);
        while(!qu.empty()){
            int pos = qu.front(); qu.pop();
            if(visit[pos]) continue;
            visit[pos] = 1;
            for(int i=0;i<M;i++){
                if(i+N[i] == pos){
                    for(int j=0;j<6;j++){
                        if(i+a[j] < M && step[i+a[j]] > step[pos]+1){
                            qu.push(i+a[j]);
                            step[i+a[j]] = step[pos]+1;
                        }
                        if(i-a[j] >= 0 && step[i-a[j]] > step[pos]+1){
                            qu.push(i-a[j]);
                            step[i-a[j]] = step[pos]+1;
                        }
                    }
                }
            }
        }

        int cnt = 0;
        while(s != g){
            int dice;
            scanf("%d", &dice); --dice;
            if(s+a[dice] < M && step[s+a[dice]+N[s+a[dice]]] < step[s]){
                printf("1\n"); fflush(stdout);
                s = s+a[dice]+N[s+a[dice]];
            }
            else if(s-a[dice] >= 0 && step[s-a[dice]+N[s-a[dice]]] < step[s]){
                printf("-1\n"); fflush(stdout);
                s = s-a[dice]+N[s-a[dice]];
            }
            else {
                printf("0\n"); fflush(stdout);
            }
        }
        break;
    }
}

F : ７歳教

• ある星に行って7歳区間が終わる前に旅立って得することは無さそう。
• 7歳区間が終わった星に行く意味も無いので移動経路の候補はDAGで表せる。
• なので、トポロジカルソートして時系列順で最大値を確定させていった。

• 1度はすんなりACしたものの、リジャッジがあってWAになった。
  • 難易度の割に解かれてなかったので何かありそうな気はしてた。
• 初期化がマズくて、最初は各星にmin(r[i], w[s][i])の時間で行けてしまっていた。
• ラスト20分くらいで気づけて無事にACした。

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

typedef vector< vector<int> > graph;

void visit(const graph &g, vector<int> &order, vector<bool> &mark, int pos){
    for(int i=0;i<g[pos].size();i++){
        int next = g[pos][i];
        if(mark[next]) continue;
        visit(g, order, mark, next);
    }
    mark[pos] = true;
    order.push_back(pos);
}

vector<int> topologicalSort(const graph &g){
    vector<int> res;
    vector<bool> mark(g.size(), false);
    for(int i=0;i<g.size();i++){
        if(mark[i]) continue;
        visit(g, res, mark, i);
    }
    reverse(res.begin(), res.end());
    return res;
}

int main(){
    int n, s;
    int l[500];
    int r[500];
    int w[500][500];
    int res[500];
    while(cin >> n >> s){
        --s;
        for(int i=0;i<n;i++) cin >> l[i] >> r[i];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++) cin >> w[i][j];
        }
        for(int k=0;k<n;k++)
            for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                    w[i][j] = min(w[i][k]+w[k][j], w[i][j]);
        vector< vector<int> > g(n);
        for(int i=0;i<n;i++){
            if(w[s][i] >= r[i]) continue;
            for(int j=0;j<n;j++){
                if(i == j) continue;
                if(r[i]+w[i][j] < r[j]) g[i].push_back(j); 
            }
        }
        for(int i=0;i<n;i++){
            int t = w[s][i];
            res[i] = max(0, r[i]-max(t, l[i]));
        }
        vector<int> order = topologicalSort(g);
        for(int i=0;i<order.size();i++){
            int cur = order[i];
            for(int j=0;j<g[cur].size();j++){
                int next = g[cur][j];
                int t = r[cur] + w[cur][next];
                res[next] = max(res[next], res[cur] + r[next] - max(l[next], t));
            }
        }
        int ans = 0;
        for(int i=0;i<n;i++) ans = max(ans, res[i]);
        cout << ans << endl;
    }
}

G : 自由研究

• 脊髄反射でスターグラフ投げたら32点だった。
• その後色々submitしてみるもスターグラフが倒せない。

• 仕方ないので次郎アルゴリズムの期待値を出すコードを書いた。
• サイズ5の完全グラフにいっぱい頂点つけるのが良かったので投げたら通った。

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

using namespace std;

int main(){
/*
    for(int n=40;n<=40;n++){
        for(int sub=1;sub<20;sub++){
            vector< vector<int> > g(n);
            for(int j=0;j<sub;j++){
                for(int i=sub+1;i<n;i++){
                    g[j].push_back(i);
                    g[i].push_back(j);
                }
                for(int i=j+1;i<sub;i++){
                    g[j].push_back(i);
                    g[i].push_back(j);
                }
            }
            double expVal = 0;
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    if(n-1-j-g[i].size() < 0) break;
                    double add = 1.0/n;
                    for(int k=0;k<g[i].size();k++) add *= (n-1.0-j-k)/(n-1.0-k);
                    expVal += add;
                }
            }
            cout << (n-sub)-expVal << endl;
        }
    }
*/
    cout << 40 << endl;
    vector<string> vs(40, string(40, 'N'));
    for(int i=0;i<5;i++){
        for(int j=5;j<40;j++)
            vs[i][j] = vs[j][i] = 'Y';
        for(int j=i+1;j<5;j++)
            vs[i][j] = vs[j][i] = 'Y';
    }
    for(int i=0;i<40;i++) cout << vs[i] << endl;
}

H : N and K

• 考えのとっかかりにすべく探索で調べてたら部分点の解空間が埋まった。
• 埋め込んで投げた。50点もらった。

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

using namespace std;

int ans[25][25] = {
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {2, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {2, 3, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {2, 3, 5, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {4, 5, 6, 7, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {4, 5, 6, 7, 9, 11, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {4, 5, 6, 7, 9, 11, 13, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {4, 6, 7, 9, 10, 11, 13, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {4, 6, 7, 9, 10, 11, 13, 15, 17, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {4, 6, 7, 9, 10, 11, 13, 15, 17, 19, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {4, 6, 9, 10, 11, 13, 14, 15, 17, 19, 21, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {4, 6, 9, 10, 11, 13, 14, 15, 17, 19, 21, 23, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {4, 6, 9, 10, 11, 13, 14, 15, 17, 19, 21, 23, 25, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {8, 10, 11, 12, 13, 14, 15, 17, 18, 19, 21, 23, 25, 27, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {8, 10, 11, 12, 13, 14, 15, 17, 18, 19, 21, 23, 25, 27, 29, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {8, 10, 11, 12, 13, 14, 15, 17, 18, 19, 21, 23, 25, 27, 29, 31, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {8, 10, 12, 13, 14, 15, 17, 18, 19, 21, 22, 23, 25, 27, 29, 31, 33, 0, 0, 0, 0, 0, 0, 0, 0},
    {8, 10, 12, 13, 14, 15, 17, 18, 19, 21, 22, 23, 25, 27, 29, 31, 33, 35, 0, 0, 0, 0, 0, 0, 0},
    {8, 10, 12, 13, 14, 15, 17, 18, 19, 21, 22, 23, 25, 27, 29, 31, 33, 35, 37, 0, 0, 0, 0, 0, 0},
    {8, 10, 12, 14, 15, 17, 18, 19, 21, 22, 23, 25, 26, 27, 29, 31, 33, 35, 37, 39, 0, 0, 0, 0, 0},
    {8, 10, 12, 14, 15, 17, 18, 19, 21, 22, 23, 25, 26, 27, 29, 31, 33, 35, 37, 39, 41, 0, 0, 0, 0},
    {8, 10, 12, 14, 15, 17, 18, 19, 21, 22, 23, 25, 26, 27, 29, 31, 33, 35, 37, 39, 41, 43, 0, 0, 0},
    {8, 12, 14, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 29, 30, 31, 33, 35, 37, 39, 41, 43, 45, 0, 0},
    {8, 12, 14, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 29, 30, 31, 33, 35, 37, 39, 41, 43, 45, 47, 0},
    {8, 12, 14, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 29, 30, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49}
};

int main(){
    int C;
    while(cin >> C){
        for(int caseNum=0;caseNum<C;caseNum++){
            int N, K; cin >> N >> K;
            if(K > (N+1)/2) cout << -1 << endl;
            else            cout << ans[(N-1)/2][K-1] << endl;
        }
    }
}

J : タイル置き

• ラスト10分の部分点稼ぎに全探索した。

#include <iostream>
#include <cstring>

using namespace std;

int H, W;
int res;
int a[6][6];

void search(int pos, int lest){
    if(lest == 0){
        res++;
        return;
    }
    if(pos == W*H) return ;
    int x = pos%W, y = pos/W;
    search(pos+1, lest);
    if(a[x][y] == 0){
        if(x+1 < W && a[x+1][y] == 0){
            a[x][y] = a[x+1][y] = 1;
            search(pos+1, lest-1);
            a[x][y] = a[x+1][y] = 0;
        }
        if(y+1 < H && a[x][y+1] == 0){
            a[x][y] = a[x][y+1] = 1;
            search(pos+1, lest-1);
            a[x][y] = a[x][y+1] = 0;
        }
    }
}

int main(){
    int N;
    while(cin >> H >> W >> N){
        memset(a, 0, sizeof(a));
        res = 0;
        search(0, N);
        cout << res << endl;
    }
}

• -

結果：2150Pt, 12位

つまらないWAを量産してしまったのがアレでしたが、良い結果でした。
KUPCに5時間フルで参加できたのは初でしたが、楽しかったです。

模擬国内予選2013

Writerした3問+何となく解いたGのソースをコッソリ貼ってみます。
初Writerでしたが、色々難しいなと痛感しました。

• -

C : 双子の読書感想文

• 2年前くらいに思いついたものの問題設定が考えつかず放置してた問題
• ある性質に気づけばあとは国内予選レベルの実装というつもりでしたが、そこに至るハードルが高かった…ごめんなさい。
• 最後のサンプルは、inputがスリーサイズ等のプロフィール、outputが誕生日(某双子の)

#include <iostream>
#include <cstring>

using namespace std;

int main(){
    int N;
    int t[1000], r[1000];
    int dp[2][1000];
    while(cin >> N && N){
        int sumT = 0, sumR = 0, maxIdx = 0;
        for(int i=0;i<N;i++){
            cin >> t[i] >> r[i];
            sumT += t[i];
            sumR += r[i];
            if(t[maxIdx] < t[i]) maxIdx = i;
        }
        int waitTime = max(0, 2*t[maxIdx] - sumT);
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        int cur = 0, next = 1;
        for(int i=0;i<N;i++){
            if(i == maxIdx) continue;
            memcpy(dp[next], dp[cur], sizeof(dp[next]));
            for(int j=0;j+r[i]<=waitTime;j++){
                if(dp[cur][j]==0) continue;
                dp[next][j+r[i]] = 1;
            }
            int maxIdx = 0;
            for(int j=0;j<1000;j++) if(dp[next][j]) maxIdx = j;
            swap(cur, next);
        }
        for(int i=waitTime;i>=0;i--){
            if(!dp[cur][i]) continue;
            cout << sumT + sumR + waitTime - i << endl;
            break;
        }
    }
}

D : 沈みゆく島

• 近年のグラフ問はad-hoc系が出てる+そろそろMSTが出てもおかしくなさそうという考えで作った問題
• Cが実装軽いので、実装が少し重めになるように設定した
• 解説に載せたコーナーケースは自身のwriter解が撃墜されるまで気付いてなかった
• 問題文が分かりにくくてごめんなさい
• 最後のサンプルの答えは某所の郵便番号

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

using namespace std;

int root[200];
int size[200];

int getRoot(int v){ return root[v]==-1 ? v : root[v] = getRoot(root[v]); }

int main(){
    int N, M;
    int height[200];
    while(cin >> N >> M && N){
        vector< vector< pair<int,int> > > g(N);
        vector< pair<int, int> > h;
        for(int i=0;i<N;i++){
            cin >> height[i];
            h.push_back(make_pair(height[i], i));
        }
        sort(h.rbegin(), h.rend());
        int lastIdx = h[0].second;
        int sep = h[0].first+1;
        for(int i=0;i<M;i++){
            int a, b, c; cin >> a >> b >> c;
            g[a-1].push_back(make_pair(b-1,c));
            g[b-1].push_back(make_pair(a-1,c));
        }
        memset(root, -1, sizeof(root));
        for(int i=0;i<N;i++) size[i] = 1;
        for(int i=0;i<N; ){
            int curTime = h[i].first;
            while(i<N && h[i].first == curTime){
                int idx = h[i].second;
                for(int j=0;j<g[idx].size();j++){
                    if(height[g[idx][j].first] < curTime) continue;
                    int p = getRoot(idx);
                    int q = getRoot(g[idx][j].first);
                    if(p!=q){
                        size[p] += size[q];
                        root[q] = p;
                    }
                }
                i++;
            }
            if(size[getRoot(lastIdx)] != i) sep = curTime;
        }
        if(sep == h.back().first){
            cout << 0 << endl;
            continue;
        }
        int res = 0;
        memset(root, -1, sizeof(root));
        for(int i=0;i<N; ){
            vector< pair<int, pair<int,int> > > vp;
            while(i<N && h[i].first >= sep){
                int idx = h[i].second;
                for(int j=0;j<g[idx].size();j++)
                    vp.push_back(make_pair(g[idx][j].second, make_pair(idx, g[idx][j].first)));
                i++;
            }
            int curTime = h[i].first;
            while(i<N && h[i].first == curTime){
                int idx = h[i].second;
                for(int j=0;j<g[idx].size();j++)
                    vp.push_back(make_pair(g[idx][j].second, make_pair(idx, g[idx][j].first)));
                i++;
            }
            sort(vp.begin(), vp.end());
            for(int j=0;j<vp.size();j++){
                if(height[vp[j].second.second] < curTime) continue;
                int p = getRoot(vp[j].second.first);
                int q = getRoot(vp[j].second.second);
                if(p != q){
                    res += vp[j].first;
                    root[q] = p;
                }
            }
        }
        cout << res << endl;
    }
}

F : テトラ姫のパズル

• 2011地区予選で三角グリッドが導入されたので、そろそろ四面体ダイスあたり来るのではと作った問題
• 仕上がりはダイス関係無いけど、ICPCでありそうな重実装を目指してみた
• サンプルは観賞用としても楽しめるように作ってみた(激弱にならないようにしつつ)

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <cstring>

using namespace std;

const int MAX_N = 5000;

int coord[2][16][6] = {
    // 偶数グリッド用
    {
        {-1, 0, 1, 0, 0, -1},
        {-1, -1, 0, -1, 1, -1},
        {-2, 0, -1, 0, -1, 1},
        {1, 1, 1, 0, 2, 0},
        {-1, -2, -1, -1, 0, -1},
        {-1, -1, 0, -1, 1, 0},
        {0, -1, 1, 0, 1, 1},
        {1, 0, 1, 1, 2, 1},
        {1, -2, 1, -1, 0, -1},
        {1, -1, 0, -1, -1, 0},
        {0, -1, -1, 0, -1, 1},
        {-1, 0, -1, 1, -2, 1},
        {-3, 0, -2, 0, -1, 0},
        {-2, 0, -1, 0, 1, 0},
        {-1, 0, 1, 0, 2, 0},
        {1, 0, 2, 0, 3, 0}
    },
    // 奇数グリッド用
    {
        {0, 1, -1, 0, 1, 0},
        {-1, 1, 0, 1, 1, 1},
        {-2, 0, -1, 0, -1, -1},
        {1, -1, 1, 0, 2, 0},
        {-2, -1, -1, -1, -1, 0},
        {-1, -1, -1, 0, 0, 1},
        {-1, 0, 0, 1, 1, 1},
        {0, 1, 1, 1, 1, 2},
        {2, -1, 1, -1, 1, 0},
        {1, -1, 1, 0, 0, 1},
        {1, 0, 0, 1, -1, 1},
        {0, 1, -1, 1, -1, 2},
        {-3, 0, -2, 0, -1, 0},
        {-2, 0, -1, 0, 1, 0},
        {-1, 0, 1, 0, 2, 0},
        {1, 0, 2, 0, 3, 0}
    }
};

bool search(const vector< vector<int> >& g, vector<int>& match, vector<int>& visit, int u){
    if(u == -2) return false; // 使用できない頂点
    if(u == -1) return true;
    for(int i=0;i<g[u].size();i++){
        int next = g[u][i];
        if(visit[next]) continue;
        visit[next] = true;
        if(search(g, match, visit, match[next])){
            match[u] = next, match[next] = u;
            return true;
        }
    }
    return false;
}

int main(){
    int n;
    int x[3*MAX_N], y[3*MAX_N];
    while(cin >> n && n){
        vector< vector<int> > g(n);
        vector< pair<int, int> > nodeCoord;
        map< pair<int, int>, int > nodeIdx;
        set< pair<int, int> > tetraIdx;

        for(int i=0;i<n;i++){
            for(int j=0;j<3;j++){
                cin >> x[3*i+j] >> y[3*i+j];
                tetraIdx.insert(make_pair(x[3*i+j], y[3*i+j]));
            }
        }

        // 各正四面体の最後の一面の位置の候補を列挙する
        for(int i=0;i<n;i++){
            int type = (abs(x[3*i])+abs(y[3*i]))%2;
            for(int j=0;j<16;j++){
                int useID = -1;
                for(int k=0;k<3;k++){
                    int cx = x[3*i]+coord[type][j][2*k  ];
                    int cy = y[3*i]+coord[type][j][2*k+1];
                    if((cx != x[3*i+1] || cy != y[3*i+1]) && (cx != x[3*i+2] || cy != y[3*i+2])){
                        if(useID == -1) useID = k;
                        else if(useID >= 0) useID = -2;
                    }
                }
                if(useID >= 0){
                    int cx = x[3*i]+coord[type][j][2*useID  ];
                    int cy = y[3*i]+coord[type][j][2*useID+1];
                    if(!nodeIdx.count(make_pair(cx, cy))){
                        int newIdx = g.size();
                        nodeCoord.push_back(make_pair(cx, cy));
                        nodeIdx[make_pair(cx, cy)] = newIdx;
                        g.push_back(vector<int>());
                    }
                    int idx = nodeIdx[make_pair(cx, cy)];
                    g[i].push_back(idx);
                    g[idx].push_back(i);
                }
            }
        }

        vector<int> match(g.size(), -1);

        // 各正四面体で指定されているグリッドを使用禁止にする
        for(int i=0;i<nodeCoord.size();i++){
            if(tetraIdx.count(nodeCoord[i])){
                match[n+i] = -2;
            }
        }

        int curMatch = 0;
        vector<int> visit;
        for(int i=0;i<n;i++){
            visit.assign(g.size(), 0);
            curMatch += search(g, match, visit, i);
        }

        if(curMatch == n) cout << "Valid" << endl;
        else {
            vector<int> matchCopy = match;
            vector<int> checkIdx, removeIdx;
            for(int i=0;i<n;i++)
                if(match[i] == -1) checkIdx.push_back(i);

            // 最初の時点でマッチしなかった頂点が5以上ある場合は調べなくて良い．
            if(checkIdx.size() <= 4){
                for(int i=0;i<n;i++){
                    int matchSize = curMatch;
                    match = matchCopy;
                    for(int j=0;j<3;j++){
                        if(nodeIdx.count(make_pair(x[3*i+j], y[3*i+j])))
                            match[nodeIdx[make_pair(x[3*i+j], y[3*i+j])]] = -1;
                    }
                    if(match[i] != -1){
                        match[match[i]] = -1;
                        match[i] = -2;
                        matchSize--;
                    }
                    for(int j=0;j<checkIdx.size();j++){
                        if(checkIdx[j] == i) continue;
                        visit.assign(g.size(), 0);
                        matchSize += search(g, match, visit, checkIdx[j]);
                    }
                    if(matchSize == n-1) removeIdx.push_back(i);
                }
            }
            if(removeIdx.empty()) cout << "Invalid" << endl;
            else {
                cout << "Remove" << endl;
                for(int i=0;i<removeIdx.size();i++)
                    cout << removeIdx[i]+1 << endl;
            }
        }
    }
}

G : 鏡の迷宮

• 作業準備が大変そうだったので解答書いてみた問題。大体解説の通り。
• 実装は重めだけど、実は(?)Fより軽かった

#include <iostream>
#include <vector>
#include <complex>
#include <cmath>
#include <queue>
#include <algorithm>
#include <cstdio>

using namespace std;

const double EPS = 1e-7;
typedef complex<double> P;
typedef vector<P> G;

namespace std{
    bool operator < (const P &a, const P &b){
        return make_pair(real(a), imag(a)) < make_pair(real(b), imag(b));
    }
}

struct L { P p, q; L(P p, P q) : p(p), q(q) {} };

double dot(P a, P b) { return real(conj(a)*b); }
double cross(P a, P b) { return imag(conj(a)*b); }
double angle(P a, P b) { return arg(conj(a)*b); }

bool ssIntersect(const L& a, const L& b){
    if(abs(imag((a.q-a.p)/(b.q-b.p))) < EPS) return false;
    return cross(a.q-a.p, b.p-a.p)*cross(a.q-a.p, b.q-a.p) < EPS &&
           cross(b.q-b.p, a.p-b.p)*cross(b.q-b.p, a.q-b.p) < EPS;
}

bool spIntersect(const L& l, const P& p){
    return abs(abs(l.p-p)+abs(l.q-p)-abs(l.p-l.q)) < EPS;
}

P ssCrosspoint(const L& a, const L& b){
    double A = cross(a.q-a.p, b.q-b.p);
    double B = cross(a.q-a.p, a.q-b.p);
    return b.p + B/A * (b.q-b.p);
}

bool contains(const G& g, const P& p){
    double sumAgl = 0;
    for(int i=0;i<g.size();i++){
        int next = (i+1)%g.size();
        if(spIntersect(L(g[i], g[next]), p)) return true;
        sumAgl += angle(g[next]-p, g[i]-p);
    }
    return abs(sumAgl) > 1;
}

// lの両端点がg内部にあることは予め調べておく
bool containSegment(const G& g, const L& l){
    int n = g.size();
    vector<P> cp;
    for(int i=0;i<n;i++){
        int next = (i+1)%n;
        L seg(g[i], g[next]);
        if(ssIntersect(seg, l))
            cp.push_back(ssCrosspoint(seg, l));
    }
    sort(cp.begin(), cp.end());
    for(int i=0;i+1<cp.size();i++)
        if(!contains(g, 0.5*(cp[i]+cp[i+1]))) return false;
    return true;
}

P footPerp(const L& l, const P& p) {
    return l.p + (l.q-l.p)*(dot(l.q-l.p, p-l.p) / (abs(l.q-l.p)*abs(l.q-l.p)));
}

P lineShadow(const L& l, const P& p){
    return 2.0*footPerp(l, p)-p;
}

int main(){
    int n;
    while(cin >> n && n){
        vector<G> g(n);
        for(int i=0;i<n;i++){
            int m; cin >> m;
            for(int j=0;j<m;j++){
                int x, y; cin >> x >> y;
                g[i].push_back(P(x, y));
            }
        }
        P start, goal, l1, l2;
        cin >> start.real() >> start.imag() >> goal.real() >> goal.imag();
        cin >> l1.real() >> l1.imag() >> l2.real() >> l2.imag();
        L l(l1, l2);

        P startM = lineShadow(l, start);
        P goalM  = lineShadow(l, goal);

        int idxA = -1, idxB = -1;
        for(int i=0;i<n;i++){
            if(contains(g[i], start) && contains(g[i], goal)) idxA = i;
            if(contains(g[i], startM) && contains(g[i], goalM)) idxB = i;
        }
        if(idxA == -1 || idxB == -1){
            printf("impossible\n");
            continue;
        }
        for(int i=0;i<g[idxB].size();i++)
            g[idxB][i] = lineShadow(l, g[idxB][i]);
        vector<P> vp;
        vp.push_back(start);
        vp.push_back(goal);
        for(int i=0;i<g[idxA].size();i++)
            if(contains(g[idxB], g[idxA][i])) vp.push_back(g[idxA][i]);
        for(int i=0;i<g[idxB].size();i++)
            if(contains(g[idxA], g[idxB][i])) vp.push_back(g[idxB][i]);
        vector<int> mark(vp.size(), 0);
        vector<double> dist(vp.size(), 1e12);

        priority_queue< pair<double, int> > qu; qu.push(make_pair(0, 0));
        while(!qu.empty()){
            pair<double, int> pr = qu.top(); qu.pop();
            double d = -pr.first;
            int idx = pr.second;
            if(mark[idx]) continue;
            mark[idx] = 1;
            for(int i=0;i<vp.size();i++){
                if(mark[i]) continue;
                if(containSegment(g[idxA], L(vp[idx], vp[i])) && containSegment(g[idxB], L(vp[idx], vp[i]))){
                    double nd = d + abs(vp[idx]-vp[i]);
                    if(nd < dist[i]){
                        dist[i] = nd;
                        qu.push(make_pair(-nd, i));
                    }
                }
            }
        }
        if(dist[1] < 1e11) printf("%.9lf\n", dist[1]);
        else               printf("impossible\n");
    }
}

Google Code Jam 2013 Round2

残念な結果に終わった昨年のリベンジマッチ。

• -

A : Ticket Swapping

• 問題文長い…と思って一旦飛ばしたものの、他も難しそうだったので結局Aから。
• 端から入退場をシミュレーションして、一番新しいチケットで退場すれば良さそう。
• そのシミュレーションをどう書くかでだいぶ迷ってしまって無駄に時間かかった。
• stackを使うなんて華麗な実装は考えもしなかったぜ…。

• 最初にInput/Outputだけ見てmodには気付いたので、被害者の会入りせずに済んだ。

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

using namespace std;

const int MOD = 1000002013;

int main(){
    int T; cin >> T;
    int N, M;
    for(int test=1;test<=T;test++){
        cin >> N >> M;
        map< int, pair<long long, long long> > mp;
        long long origSum = 0;
        for(int i=0;i<M;i++){
            int o, e, p;
            cin >> o >> e >> p;
            long long cost = ((2LL*N-(e-o)+1)*(e-o)/2)%MOD;
            origSum += (p*cost)%MOD;
            origSum %= MOD;
            if(mp.count(o)) mp[o].first += p;
            else            mp[o] = make_pair(p, 0);
            if(mp.count(e)) mp[e].second += p;
            else            mp[e] = make_pair(0, p);
        }
        long long decSum = 0;
        int prev = -1;
        vector< pair<long long, long long> > vp;
        for(map< int, pair<long long, long long> >::iterator it=mp.begin();it!=mp.end();it++){
            int idx = it->first;
            for(int i=0;i<vp.size();i++){
                long long cost = ((2LL*vp[i].first-(idx-prev)+1)*(idx-prev)/2)%MOD;
                decSum += (vp[i].second*cost)%MOD;
                decSum %= MOD;
                vp[i].first -= (idx-prev);
            }
            if(it->second.first > 0){
                vp.push_back(make_pair(N, it->second.first));
                sort(vp.rbegin(), vp.rend());
            }
            int exitNum = it->second.second;
            for(int i=0;i<vp.size();i++){
                if(exitNum == 0) break;
                if(vp[i].second < exitNum){
                    exitNum -= vp[i].second;
                    vp[i].second = 0;
                } else {
                    vp[i].second -= exitNum;
                    exitNum = 0;
                }
            }
            prev = idx;
        }
        int res = (origSum-decSum+MOD)%MOD;
        printf("Case #%d: %d\n", test, res);
    }
}

B : Many Prizes

• 解像度の関係で2^Nが2^Mに見えて、Mとは一体…としばらく悩んだ。
• 最悪の当たり方をした場合にある人が何位になるかは簡単に求められそう。
  • 最初、i番の人に勝てる人はi人いる。
  • 同じブロックにiさんより強い人がいれば、その中の一人にiさんを負かしてもらう。
  • 次にiさんと同じブロックに残せるiさんより強い人の数は、(i-1)/2人。
  • これをiさんがブロック内で一番強い人になるまで繰り返せば良い。

• で、iさんが最悪でもP位以内に入れれば(i-1)さんも絶対P位以内に入れる。
• 二分探索乙でした。

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

using namespace std;

long long solveWin(int N, long long P){
    long long L = 0, R = 1LL<<N;
    while(R-L>1){
        long long mid = (L+R)/2;
        long long win = mid;
        long long rank = 0;
        for(int i=N-1;i>=0;i--){
            if(win > 0){
                rank += (1LL<<i);
                win = (win-1)/2;
            } else {
                break;
            }    
        }
        if(rank < P) L = mid;
        else         R = mid;
    }
    return L;
}

long long solveLose(int N, long long P){
    long long L = 0, R = 1LL<<N;
    while(R-L>1){
        long long mid = (L+R)/2;
        long long lose = (1LL<<N)-mid-1;
        long long rank = 0;
        for(int i=N-1;i>=0;i--){
            if(lose > 0){
                lose = (lose-1)/2;
            } else {
                rank = (1LL<<(i+1))-1;
                break;
            }
        }
        if(rank < P) L = mid;
        else         R = mid;
    }
    return L;
}

int main(){
    int T; cin >> T;
    int N; long long P;
    for(int test=1;test<=T;test++){
        cin >> N >> P;
        printf("Case #%d: %lld %lld\n", test, solveWin(N, P), solveLose(N, P));
    }
}

C : Erdős–Szekeres

• 最初はSmallすら分からなくてオワタ感あった。

• Aは、最長増加部分列を求めるDPの結果得られるDPテーブルと一緒。
• Bも、ひっくり返した数列に対して作ったDPテーブルみたいなもの。
• そこから考えてみると、
  • i < j について、A[i] >= A[j] なら X[i] > X[j]。
  • i < j のとき、A[i]+1 = A[j] をみたす最大のiに対して X[i] < X[j]
• が言えて、Bについても似たような大小関係が得られる。

• これが十分条件かは自信がなかったものの、
  • X[i] < X[j]をみたす組について、i->jに辺を貼ったグラフを作る
  • 辞書順最小のトポロジカル順序を求める
  • (ﾟдﾟ)ｳﾏｰ
• という作戦を決行してみることに(※辞書順最小を見落としてて1回WAもらった)。

• 辞書順最小のトポロジカル順序をどうするかと思ったものの、O(n^2)で良かったので、
  • 作ったグラフに対して各ノードの入次数を持っておく
  • 入次数0のノードのうち最小のインデックスのものを選ぶ
  • 選んだノードを除いての各ノードの入次数を更新する(O(n))
• という感じでやった。

• 以下のコードは提出コードから要らない部分を除いたもの。

#include <iostream>
#include <vector>
#include <cstring>
#include <cstdio>

using namespace std;

int in[2000];
int road[2000][2000];

int main(){
    int T; cin >> T;
    int N;
    int A[2000], B[2000];
    for(int test=1;test<=T;test++){
        cin >> N;
        for(int i=0;i<N;i++) cin >> A[i];
        for(int i=0;i<N;i++) cin >> B[i];
        memset(in, 0, sizeof(in));
        memset(road, 0, sizeof(road));
        for(int i=0;i<N;i++){
            int lastIdx = -1;
            for(int j=0;j<i;j++){
                if(A[j] >= A[i]) road[i][j] = 1;
                if(A[j]+1 == A[i]) lastIdx = j;
            }
            if(lastIdx != -1) road[lastIdx][i] = 1;
        }
        for(int i=N-1;i>=0;i--){
            int lastIdx = -1;
            for(int j=N-1;j>i;j--){
                if(B[j] >= B[i]) road[i][j] = 1;
                if(B[j]+1 == B[i]) lastIdx = j;
            }
            if(lastIdx != -1) road[lastIdx][i] = 1;
        }

        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++)
                if(road[i][j]) in[j]++;
        }

        vector<int> res(N);

        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(in[j] == 0){
                    res[j] = i+1;
                    for(int k=0;k<N;k++)
                        if(road[j][k]) in[k]--;
                    in[j] = -1;
                    break;
                }
            }
        }

        printf("Case #%d:", test);
        for(int i=0;i<N;i++) printf(" %d", res[i]);
        printf("\n");
    }
}

• -

Rank 79 : /oo/oo/oo/--/ Score 63, Penalty 2:20:02

2010はギリギリ通過で、2011はラスト数分で通過ライン滑り込み、2012は大敗北でしたが、
初めて余裕を持ってRound2を通過することができました。
Round3も0でない点数目指してがんばります。