KUPC2013 - pes_magic’s blog

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

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時間フルで参加できたのは初でしたが、楽しかったです。