JOI2015 本選 1 ~ 4

試験前の予備日なので, 家で引きこもっていました.
やるべきことに追われ辛かったので, 気晴らしに JOI の問題を解いていました. 今年の目標も昨年と同じく後輩ズに勝つことでした.

オンライン参加して 3 問目まで解いたくらいのところでサーバー障害が起きたのであとはほとんど観戦してました. 4 番むずかったし.

最近は JOI 公式のスバラシイ解説 があるので, 僕のコードを載せるのと, それぞれの問題に対する感想を述べるだけにします. 5 番むずそう...

1. 普段 int から溢れないように後輩にだす問題の制約を決めている身としては, オーバーフローの危険性を即座に察知できました. 本質的でないところ(?) で落としている生徒が結構いそう(例年の問 1 の正解人数と比べると).

#include <bits/stdc++.h>

using namespace std;

typedef long long Int;

int vis[100001];

int main()
{
    int M, N;
    
    scanf("%d %d", &N, &M);
    
    int prev, now;
    for (int i = 0; i < M; i++){
        scanf("%d", &now);
        now--;
        if (i){
            vis[min(prev, now)]++;
            vis[max(prev, now)]--;
        }
        prev = now;
    }
    
    Int ans = 0;
    for (int i = 0; i < N - 1; i++){
        Int A, B, C;
        scanf("%lld %lld %lld", &A, &B, &C);
        if (i) vis[i] += vis[i - 1];
        ans += min(A * vis[i], B * vis[i] + C);
    }
    
    printf("%lld\n", ans);
}

2. これ, すごく IOI 列車と同じ臭いの DP を感じたんですが (状態が $O(N^2)$ 個なのはいいけど, 探索に外から入る回数が 1 回じゃないから計算量が増えそうという先入観を伴う DP), 共感してくれる人がいそうにない...

#include <bits/stdc++.h>

using namespace std;

typedef long long Int;

Int memo[4096][4096];
int A[4096], N;

Int getMax(int L, int R)
{
    if (R - L + 1 <= 2){
        return (max(A[L], A[R]));
    }
    if (~memo[L][R]) return (memo[L][R]);
    
    Int ans1 = 0, ans2 = 0;
    ans1 = A[L] + (A[L + 1] > A[R] ? getMax(L + 2, R) : getMax(L + 1, R - 1));
    ans2 = A[R] + (A[L] < A[R - 1] ? getMax(L, R - 2) : getMax(L + 1, R - 1));
    
    memo[L][R] = max(ans1, ans2);
    if (R + N < 2 * N) memo[L + N][R + N] = memo[L][R];
    if (L - N >= 0) memo[L - N][R - N] = memo[L][R];
    
    return (memo[L][R]);
}

int main()
{
    scanf("%d", &N);
    
    for (int i = 0; i < N; i++){
        scanf("%d", A + i);
        A[i + N] = A[i];
    }
    
    memset(memo, -1, sizeof(memo));
    
    Int ans = 0;
    for (int i = 0; i < N; i++){
        ans = max(ans, getMax(i, i - 1 + N));
    }
    
    printf("%lld\n", ans);
    
    return (0);
}

3. この手の問題は, 似た傾向の問題や, 最小全域木のクラスカル法の思想みたいなものが頭に染み付いているとすぐに答えが見えてきそうですね. 辺が小さい順に取っていくというクラスカル法のアルゴリズムと同じようなことを後半でしました.

#include <bits/stdc++.h>

#define MAX_N (100100)
#define MAX_M (200100)

using namespace std;

typedef long long Int;
typedef pair<Int, int> Stat;

const Int INF = 1001001001001001001ll;

int N, M;
Int C;

int head[MAX_N], to[2 * MAX_M], nxt[2 * MAX_M], cost[2 * MAX_M];
Int dist[MAX_N];

void addEdge(int id, int a, int b, int c)
{
    nxt[id] = head[a];
    to[id] = b;
    cost[id] = c;
    head[a] = id;
}

int main()
{
    scanf("%d %d %lld", &N, &M, &C);
    
    memset(head, -1, sizeof(head));
    
    Int sum = 0;
    for (int i = 0; i < M; i++){
        int A, B, D;
        scanf("%d %d %d", &A, &B, &D);
        addEdge(i * 2    , A, B, D);
        addEdge(i * 2 + 1, B, A, D);
        
        sum += D;
    }
    
    fill(dist + 1, dist + N + 1, INF);
    
    priority_queue<Stat, vector<Stat>, greater<Stat> > pq;
    
    for (pq.push(Stat(0, 1)); pq.size();){
        Stat tmp = pq.top(); pq.pop();
        
        Int d = tmp.first;
        int v = tmp.second;
        
        if (dist[v] != INF) continue;
        dist[v] = d;
        for (int e = head[v]; e != -1; e = nxt[e]){
            pq.push(Stat(d + cost[e], to[e]));
        }
    }
    
    pair<Int, int> distPair[MAX_N];
    for (int i = 1; i <= N; i++){
        distPair[i - 1] = make_pair(dist[i], i);
    }
    
    sort(distPair, distPair + N);
    
    Int ans = sum;
    set<int> s;
    for (int i = 0; i < N;){
        int j;
        for (j = i; j < N && distPair[i].first == distPair[j].first; j++){
            s.insert(distPair[j].second);
            int v = distPair[j].second;
            for (int e = head[v]; e != -1; e = nxt[e]){
                if (s.find(to[e]) != s.end()){
                    sum -= cost[e];
                }
            }
        }
        ans = min(ans, sum + distPair[i].first * C);
        i = j;
    }
    
    printf("%lld\n", ans);
    
    return (0);
}

4. 昨日見た時はまったくアプローチが思いつかなかったものの(正確には二分探索は思い浮かんだがどうすればいいんだ...という気分になった), 解説を読んですごく感銘を受けました.

#include <bits/stdc++.h>

using namespace std;

typedef long long Int;

const int INF = 1001001001;

int N, M;
int val[100000];
vector<int> other;

bool ok(int T)
{
    int dp[200000];
    
    fill(dp, dp + 200000, INF);
    
    for (int i = 0; i < N; i++){
        dp[i] = (~val[i] ? (val[i] >= T ? 0 : INF) : 1);
    }
    
    int ct = 0;
    for (int i = 0;; i++){
        dp[i + N] = min(min(dp[i * 3] + dp[i * 3 + 1],
                            dp[i * 3] + dp[i * 3 + 2]),
                        dp[i * 3 + 1] + dp[i * 3 + 2]);
        dp[i + N] = min(dp[i + N], INF);
        ct = dp[i + N];
        if (i * 3 + 3 == i + N) break;
    }
    
    int ct2 = 0;
    
    for (int i = 0; i < other.size(); i++){
        ct2 += other[i] >= T;
    }
    
    return (ct <= ct2);
}

int main()
{
    scanf("%d %d", &N, &M);
    
    memset(val, -1, sizeof(val));
    
    for (int i = 0; i < M; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        val[--y] = x;
    }
    
    for (int i = 0; i < N - M; i++){
        int x;
        scanf("%d", &x);
        other.push_back(x);
    }
    
    int l = 1, r = 1000000000;
    
    while (l != r){
        int mid = (l + r + 1) >> 1;
        
        if (ok(mid)) l = mid;
        else r = mid - 1;
    }
    
    printf("%d\n", l);
    
    return (0);
}