模擬国内予選2013

ACM-ICPC

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");
    }
}