JOI2015-2016 本選参加記

2/13～14の二日間、つくば旅行に行きました。

本選1週間前

過去問を埋めることにした。最終的にこうなった。

セクション:競技 に移動

前日

起きた。電車に乗った。新幹線に乗った。特急っぽい名前の区間快速に乗った。つくばに着いた。

昼食

yaplusさん御用達のすた丼を食べた。大学生だらけだった。とてもおいしかった。

プラクティス

1時間かからず全完して同級生や後輩と喋った。

.vimrc

set ts=4 sw=4 et nu cin

.bashrc

alias gp='g++ -std=c++11 -Wall -DEVAL -static -O2'
alias gpw='g++ -std=c++11 -Wall -static -O0'

夕食

シールを大量にバラ撒いた。気に入ってもらえたようで何より。

宿

狭かった。ダメ。

プロたちと沢山喋った。onkohdondoプロやsaytakaPCプロの部屋に遊びに行った。ゆゆ式を勧めることはあまりせず、NEW GAME!をひたすら崇めていた。

おすすめ過去問としてWalkを推されたので解いてみた。1時間以上かかってやっと解法に辿り着いた。良問。

Walk

ついでにAmidakujiを解いた。やるだけだった。

Amidakuji

当日

朝

起床に成功した。-INF点を回避。

競技

全問読んでから解き始めた。

1. Oranges

簡単なDP……のはずがなぜか分からなかった。

09:54 使った箱の数で分ける無駄な2次元DPをして計算量 のコードを書く。さすがに70点は取れるかと思ったが一部のケースで1.2秒ぐらいかかって20点しか取れず。

1番(20点)

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define size(v) ((signed)v.size())
#define all(v) begin(v), end(v)
#define IN(a) a; cin >> a
#define max_a(a, v) a = max(a, (v));
#define min_a(a, v) a = min(a, (v));

#define times(n, i) uptil(0, n, i)
#define rtimes(n, i) downto((n)-1, 0, i)
#define upto(f, t, i)    for(int i = (f), i##_end = (t); i <= i##_end; i++)
#define uptil(f, t, i)   for(int i = (f), i##_end = (t); i <  i##_end; i++)
#define downto(f, t, i)  for(int i = (f), i##_end = (t); i >= i##_end; i--)
#define downtil(f, t, i) for(int i = (f), i##_end = (t); i >  i##_end; i--)

#ifdef EVAL
#define debug 0
#define ln << "\n"
#else
#define debug 1
#define ln << endl
#endif

typedef vector<int> VI;
typedef vector<VI> VVI;

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    int IN(N);
    int IN(M);
    int IN(K);
    VI A(N); times(N, i) cin >> A[i];

    VVI pyon(N, VI(M, LLONG_MAX / 5));
    times(N, i) {
        int mi = A[i], ma = A[i];
        times(M, j) {
            if(i + j >= N) break;
            mi = min(mi, A[i + j]);
            ma = max(ma, A[i + j]);
            pyon[i][j] = (j+1) * (ma - mi);
        }
    }

    if(debug) { times(N, i) { times(M, j) cout << pyon[i][j] << " "; cout ln; } cout ln; }

    int ans = LLONG_MAX;
    VVI dp(2, VI(N+1, LLONG_MAX / 2));
    dp[0][0] = 0;
    times(N, i) {
        int k = 0;
        times(N+1, j) {
            while(j - k > M) k++;
            if(j > k) {
                while(j > k + 1 && dp[0][k] + pyon[k][j-k-1] > dp[0][k+1] + pyon[k+1][j-k-2]) k++;
                dp[1][j] = dp[0][k] + pyon[k][j-k-1];
            }
        }
        min_a(ans, dp[1][N] + K * (i + 1));
        dp[0] = dp[1];
        fill(all(dp[1]), LLONG_MAX / 2);
        if(debug) { times(N+1, i) cout << dp[0][i] << " "; cout ln; }
    }

    cout << ans ln;

    return 0;
}

10:08 定数倍改善で70点を通した*1。ここで得た50点は大きい。

1番(70点)

// テンプレ略

#define INF (LLONG_MAX / 3)

int A[20000];
int dp[2][20001];
int pyon[20000][1000];

signed main() {
    int N, M, K; scanf("%lld%lld%lld", &N, &M, &K);
    times(N, i) scanf("%lld", A+i);

    times(N, i) times(M, j) pyon[i][j] = INF;
    times(N, i) {
        int mi = A[i], ma = A[i];
        times(M, j) {
            if(i + j >= N) break;
            mi = min(mi, A[i + j]);
            ma = max(ma, A[i + j]);
            pyon[i][j] = (j+1) * (ma - mi);
        }
    }

    if(debug) { times(N, i) { times(M, j) cout << pyon[i][j] << " "; cout ln; } cout ln; }

    int ans = LLONG_MAX;
    times(2, i) times(N+1, j) dp[i][j] = INF;
    dp[0][0] = 0;
    times(N, i) {
        int e = i&1, d = !e;
        times(N+1, j) times(min(M, j), k) {
            min_a(dp[d][j], dp[e][j-k-1] + pyon[j-k-1][k]);
        }
        min_a(ans, dp[d][N] + K * (i + 1));
        times(N+1, j) dp[e][j] = INF;
        if(debug) { times(N+1, i) cout << dp[d][i] << " "; cout ln; }
    }

    printf("%lld\n", ans);

    return 0;
}

2. Collecting Stamps 2

少なくとも1番よりは簡単。ただの 。

10:22 普通に書いて100点。

2番(100点)

// テンプレ略

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    int IN(N);
    string IN(S);

    int ja = 0, oa = 0, ia = 0;

    int oi = 0, i = 0;
    rtimes(N, k) {
        if(S[k] == 'J') ja += oi;
        if(S[k] == 'O') oi += i;
        if(S[k] == 'I') i++;
    }
    ja += oi;

    int jo = 0, j = 0;
    times(N, k) {
        if(S[k] == 'J') j++;
        if(S[k] == 'O') jo += j;
        if(S[k] == 'I') ia += jo;
    }
    ia += jo;

    j = 0; // i = [S.count 'I']
    int ji = 0;
    times(N, k) {
        if(S[k] == 'J') j++;
        if(S[k] == 'O') oa += j * i;
        if(S[k] == 'I') i--;
        max_a(ji, j * i);
        if(debug) cout << j << " " << i << " " << ji << " " << oa ln;
    }
    oa += ji;

    if(debug) cout << ja << " " << oa << " " << ia ln;

    cout << max({ja, oa, ia}) ln;

    return 0;
}

3. Train Fare

Dijkstaするときに直前の頂点を保持しておく(複数経路が同コストの場合は全ての親を保存)。ついでに子(直後の頂点)セットも作る。
各クエリ(辺の削除と見なせる)について、片方がもう一方の直前の頂点なら親子の情報を消す。子頂点について、この親を消したことで親の数が0になったなら各孫との間の辺をさらに削除していく。以降再帰。計算量はたぶん 。

11:06 重めに書いて100点。

3番(100点)

// テンプレ略
typedef set<int> SI;
typedef vector<SI> VSI;
typedef pair<int, int> PI;
typedef vector<PI> VPI;
typedef tuple<int, int, int> TI;
typedef vector<TI> VTI;

VVI line;
VI costs;
VSI parents;
VSI children;
int ans = 0;

void remove(int t, int p) {
    if(debug) cout << "remove " << t << " from " << p ln;
    parents[t].erase(parents[t].find(p));
    children[p].erase(children[p].find(t));
    if(parents[t].empty()) {
        ans++;
        for(int s : children[t]) {
            remove(s, t);
        }
    }
}

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    int IN(N);
    int IN(M);
    int IN(Q);
    VI U(M), V(M);
    line = VVI(N);
    times(M, i) {
        cin >> U[i] >> V[i];
        U[i]--; V[i]--;
        line[U[i]].push_back(V[i]);
        line[V[i]].push_back(U[i]);
    }

    priority_queue<TI, VTI, greater<TI>> pq;
    pq.push(TI(0, 0, 0));
    costs = VI(N, INT_MAX);
    parents = VSI(N);
    while(!pq.empty()) {
        int c, t, p; tie(c, t, p) = pq.top(); pq.pop();
        if(costs[t] >= c)
            parents[t].insert(p);
        if(costs[t] > c) {
            costs[t] = c;
            for(int s : line[t]) {
                if(costs[s] > c) {
                    pq.push(TI(c+1, s, t));
                }
            }
        }
    }
    children = VSI(N);
    times(N, i) {
        if(size(parents[i]) <= Q) {
            for(auto& p : parents[i]) {
                if(p != i) children[p].insert(i);
            }
        }
    }

    times(Q, i) {
        int IN(R); R--;
        times(2, j) {
            if(children[U[R]].find(V[R]) != children[U[R]].end()) remove(V[R], U[R]);
            swap(U[R], V[R]);
        }
        if(debug) {
            cout << "children: "; times(N, i) { cout << "{"; for(int c : children[i]) cout << c << " "; cout << "} "; } cout ln;
            cout << "parents: ";  times(N, i) { cout << "{"; for(int c : parents [i]) cout << c << " "; cout << "} "; } cout ln;
        }
        cout << ans ln;
    }

    return 0;
}

4. Territory

11:17 愚直に書いて時間計算量 、空間計算量 。5点。

11:28 最初の 日を愚直シミュレートすると残りは 日目と同じ分だけ増加することがわかる(1日の移動で最大 ×の範囲しか移動しない。 日後にはスタート地点が 以上動く、または全く動かないため1日目以前の動きは関係なく、同様に 日後には 日目以前の動きは関係ない)。
時間計算量は 、空間計算量は 。小課題1および3が解けて28点。

12:59 setを使えば ×の領域を確保する必要はなさそう。時間計算量 、空間計算量 になり38点。この10点増は競技終了間際だったから昼食で結果が渡されるまで分からなかった。

4番(38点)

// テンプレ略
typedef vector<bool> VB;
typedef vector<VB> VVB;

map<char, int> DX, DY;

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    DX['E'] = 1; DX['W'] = -1; DX['N'] = DX['S'] = 0;
    DY['N'] = 1; DY['S'] = -1; DY['E'] = DY['W'] = 0;

    int IN(N);
    int IN(K);
    string IN(S);

    //if(N > 50) return 0;

    set<PI> s;

    //VVB p(N * (N+1) * 2 + 1, VB(N * (N+1) * 2 + 1, false));
    int x = N*(N*1), y = N*(N*1);
    //p[x][y] = true;
    s.insert({x, y});
    times(min(N, K), i) {
        for(char c : S) {
            x += DX[c];
            y += DY[c];
            //p[x][y] = true;
            s.insert({x, y});
        }
    }

    int ans = 0;
    //times(N * (N+1) * 2, i) times(N * (N+1) * 2, j) {
    //    ans += p[i][j] && p[i+1][j] && p[i][j+1] && p[i+1][j+1];
    //}
    for(auto& p : s) {
        int x, y; tie(x, y) = p;
        if(s.find({x+1, y}) != s.end() &&s.find({x, y+1}) != s.end() &&s.find({x+1, y+1}) != s.end()) ans++;
    }

    if(K > N) {
        for(char c : S) {
            x += DX[c];
            y += DY[c];
            //p[x][y] = true;
            s.insert({x, y});
        }
        int d = 0;
        //times(N * (N+1) * 2, i) times(N * (N+1) * 2, j) {
        //    d += p[i][j] && p[i+1][j] && p[i][j+1] && p[i+1][j+1];
        //}
        for(auto& p : s) {
            int x, y; tie(x, y) = p;
            if(s.find({x+1, y}) != s.end() &&s.find({x, y+1}) != s.end() &&s.find({x+1, y+1}) != s.end()) d++;
        }

       ans += (d - ans) * (K - N);
   }

    cout << ans ln;

    return 0;
}

5. Geologic Fault

12:33 愚直解法(ぐらい)で18点を得る。

5番(18点)

// テンプレ略

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    int IN(N); if(N > 100) return 0;
    int IN(Q);

    VVI a(101, VI(401));
    times(101, i) fill(all(a[i]), i);

    times(Q, q) {
        int IN(X);
        int IN(D);
        int IN(L);
        times(101, i) upto(-200, 200, j) {
            if(D == 1 && j + i <= X) { if(j - L >= -200 && i + L <= 100) a[i][j+200] = a[i + L][j - L+200]; else a[i][j+200] += L; }
            if(D == 2 && j - i >  X) { if(j + L <=  200 && i + L <= 100) a[i][j+200] = a[i + L][j + L+200]; else a[i][j+200] += L; }
        }
        if(debug) {
            times(30, i) { times(41, j) printf("%2lld ", a[i][j+180]); printf("\n"); }
            printf("\n"); fflush(stdin);
        }
    }

    if(debug) {
        //times(101, i) { upto(-200, 200, j) cout << a[i][j+200] << " "; cout ln; }
    }

    times(N, j) cout << a[0][j+1+200] ln;

    return 0;
}

解説

1番を解けなかった自分に絶望した。3番のdijkstra解法かっこ良くてすき。5番の小課題2のクエリを逆に見るやつができなかったのは去年の春合宿のコピペ2に続き反省。

結果

326点(70 - 100 - 100 - 38 - 18)でした。2完ですが優しい部分点だったので300超えしました。

なんかブロック賞を取ってるみたいでこんな2完趣味人間なのに恐縮です。

お世話になったプロ各位、特にcatupperさん、eyさん、本当にありがとうございました！

これから1ヶ月精進します。春合宿もがんばるぞい！

*1:想定部分点解法はO(N M^2)っぽい