JOI予選(2015-2016)

テンプレ: https://gist.github.com/akouryy/7450d21b24aaa2bcbbaa

1.cpp

auto ABCD = next<vector<int>>(4);
cout << sum(ABCD) - min(ABCD) + max(next<vector<int>>(2)) << "\n";

2.cpp

auto N = next<int>();
auto M = next<int>();
auto A = next<vector<int>>(N);

upto(1, M, k) {
    times(N - 1, i) {
        if(A[i] % k > A[i + 1] % k) swap(A[i], A[i + 1]);
    }
}

times(N, i) cout << A[i] << "\n";

3.cpp

auto N = next<int>();
auto M = next<int>();
auto F = next<vector<string>>(N);

int ans = INT_MAX;
upto(2, N - 1, j) upto(1, j - 1, i) {
    int count = 0;
    times(N, x) times(M, y) {
        if(x < i) {
            if(F[x][y] != 'W') count++;
        } else if(x < j) {
            if(F[x][y] != 'B') count++;
        } else {
            if(F[x][y] != 'R') count++;
        }
    }
    minA(ans, count);
}

cout << ans << "\n";

4.cpp

auto N = next<int>();
auto T = next<long long>();
auto Q = next<int>();
vector<long long> A(N);
vector<int> D(N);

vector<long long> stop;

times(N, i) {
    A[i] = next<long long>();
    D[i] = next<int>();
    if(i && D[i - 1] == 1 && D[i] == 2)
        stop.push_back((A[i - 1] + A[i]) / 2);
}

dout << stop << "\n";

times(Q, i) {
    auto X = next<int>() - 1;
    if(D[X] == 1) {
        auto to_stop = lower_bound(all(stop), A[X]);
        if(to_stop == end(stop))
            cout << A[X] + T << "\n";
        else
            cout << min(A[X] + T, *to_stop) << "\n";
    } else {
        auto to_stop = lower_bound(all(stop), A[X]);
        if(to_stop == begin(stop))
            cout << A[X] - T << "\n";
        else
            cout << max(A[X] - T, to_stop[-1]) << "\n";
    }
}

5.cpp

auto N = next<int>();
auto M = next<int>();
auto K = next<int>();
auto S = next<int>();
auto P = next<int>();
auto Q = next<int>();

vector<int> C(K);
vector<bool> c(N, false);
times(K, i) c[C[i] = next<int>() - 1] = true;

vector<vector<int>> road(N);
times(M, j) {
    auto A = next<int>() - 1;
    auto B = next<int>() - 1;
    road[A].push_back(B);
    road[B].push_back(A);
}

vector<bool> dangerous(N, false) = c;

vector<int> danger0 = C;
times(S, _) {
    vector<int> danger1;
    for(int d : danger0) {
        for(int n : road[d]) {
            if(!dangerous[n]) {
                dangerous[n] = true;
                danger1.push_back(n);
            }
        }
    }
    danger0 = danger1;
}
dout << dangerous << "\n";

priority_queue<pair<long long, int>> pyon;
pyon.push(make_pair(0, 0));
vector<long long> costs(N, -1);

while(!pyon.empty()) {
    auto pair = pyon.top(); pyon.pop();
    auto cost = pair.first;
    auto d = pair.second;
    if(costs[d] != -1) continue;
    costs[d] = -cost;
    dout << d << ": " << costs[d] << "\n";
    for(int n : road[d]) {
        if(c[n] || costs[n] != -1) continue;
        //dout << "[" << n << "]" << "\n";
        pyon.push(make_pair(cost - (dangerous[n] ? Q : P), n));
    }
}

cout << costs[N - 1] - (dangerous[N - 1] ? Q : P) << "\n";

6.cpp

// 過去最高級の恥

int encode(bool a, bool b, bool c, bool d, bool e, bool f, bool g, bool h) {
    return a * 128 + b * 64 + c * 32 + d * 16 + e * 8 + f * 4 + g * 2 + h;
}

void decode(int k, bool& a, bool& b, bool& c, bool& d, bool& e, bool& f, bool& g, bool& h) {
    a = k & (1 << 7);
    b = k & (1 << 6);
    c = k & (1 << 5);
    d = k & (1 << 4);
    e = k & (1 << 3);
    f = k & (1 << 2);
    g = k & (1 << 1);
    h = k & (1 << 0);
}

vector<long long> dp[2][1001];


// main

auto H = next<int>();
auto W = next<int>();
vector<vector<int>> map(H, vector<int>(W, 0));
times(H, i) {
    string s = next<string>();
    times(W, j) if(s[j] != '.') map[i][j] = s[j] - '0';
}

upto(0, 1, i) upto(0, W, j) dp[i][j] = vector<long long>(256, LLONG_MAX / 2);
// 256: 0bABCDEFGH
//  AB
// CDE
// FGH
dp[0][0][encode(0, 0, 0, 1, 1, 0, 1, 1)] = 0;

times(H, i) {
    times(W, j) times(256, k) {
        long long cost = dp[0][j][k];
        bool a, b, c, d, e, f, g, h;
        decode(k, a, b, c, d, e, f, g, h);
    
        if(cost >= LLONG_MAX / 2) continue;
    
        // dout << " " << a << b << " " << cost << " " << i << " " << j << "\n" << c << d << e << "\n" << f << g << h << endl;
    
        if(d) cost += map[i][j];
    
        int aa = a ? map[i - 1][j    ] : 0,
            cc = c ? map[i    ][j - 1] : 0,
            ee = e ? map[i    ][j + 1] : 0,
            gg = g ? map[i + 1][j    ] : 0;
    
        bool I1 = i + 1 < H, J1 = j + 1 < W, I2 = i + 2 < H, J2 = j + 2 < W;
        #define PYON(E, G, C) \
            minA(dp[1][j    ][encode(0, E, f, G, h, j && I2, I2, I2 && J1)], cost + C); \
            minA(dp[0][j + 1][encode(b, i && J2, 0, E, J2, G, h, I1 && J2)], cost + C)

        PYON(0, 0, min(aa, cc) + ee + gg);
        PYON(e, 0, aa + cc + gg);
        PYON(0, g, aa + cc + ee);
    }
    if(i != H - 1) {
        upto(0, W, j) times(256, k) dp[0][j][k] = dp[1][j][k];
        upto(0, W, j) dp[1][j] = vector<long long>(256, LLONG_MAX / 2);
    }
}

times(H, i) { times(W, j) dout << min(dp[i][j]) << " "; dout << "\n"; }

cout << min(min(dp[0][W]), min(dp[1][W - 1])) << "\n";

#ifdef debug
    cout << dp[2][1][encode(1,1,0,0,1,1,1,1)] << "\n";
    cout << dp[3][1][encode(0,0,1,0,1,1,1,1)] << "\n";
    times(H, i) times(W, j) times(256, k) if(dp[i][j][k] == min(dp[i][j])) cout << i << " " << j << " " << (bitset<8>)k << " " << dp[i][j][k] << "\n";
#endif