読者です 読者をやめる 読者になる 読者になる

4bitにっき

ぽよ

JOI予選参加記

6問目が例年よりかなり簡単だったみたいです。

結果

全完でした。本選が本当の地獄となるでしょう。

日記

予選が始まる前におやつと野菜ジュース500mlを買ってきました。
500mlの野菜ジュースを探すのが非常に難しかったです。
開始直後はまず5問目を読み、思ったより楽そうだったのでその後6問目を読みました。
6問目も易化していたおかげで頑張って実装しきり、バグるなどして確かここまでで1時間20分前後でした。
かなり時間をかけてしまいましたが、無事6問目の実装が終わったおかげで安心して5問目以下に取り組めました。
上から順番に解いていったので3問目以下を解くときがとても楽しかったです(こなみ)。
ただ、4問目は例年と傾向が違いそうだったので一瞬冷や汗をかかせてくれました。
バグや時間不足が怖かったので、全体的に安全で低速なプログラムを書いた感じです。

解法とコード

1問目

はい。

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

#define int long long

int A[4], B[2];

signed main()
{
    int sum = 0;
    for (int i = 0; i < 4; i++) cin >> A[i], sum += A[i];
    for (int i = 0; i < 2; i++) cin >> B[i], sum += B[i];
    sort(A, A + 4); sort(B, B + 2);
    printf("%lld\n", sum - A[0] - B[0]);
    return 0;
}

2問目

はい。

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

#define int long long

int N, M, A[100];

signed main()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 1; i <= M; i++)
    {
        for (int j = 0; j < N - 1; j++)
        {
            if (A[j]%i > A[j + 1]%i) swap(A[j], A[j + 1]);
        }
    }
    for (int i = 0; i < N; i++)
    {
        printf("%lld\n", A[i]);
    }
    return 0;
}

3問目

はい。

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

#define int long long

const int INF = LLONG_MAX/2;

int N, M;
char fld[50][50];

int CountDiff(int a, int b, char c)
{
    int res = 0;
    for (int i = a; i < b; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (fld[i][j] != c) res++;
        }
    }
    return res;
}

signed main()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> fld[i][j];
        }
    }

    int ans = INF;
    for (int i = 1; i < N - 1; i++)
    {
        for (int j = i + 1; j < N; j++)
        {
            ans = min(ans, CountDiff(0, i, 'W') + CountDiff(i, j, 'B') + CountDiff(j, N, 'R'));
        }
    }
    printf("%lld\n", ans);
    return 0;
}

4問目

考えるのが面倒だったので、計算量を犠牲にして O(NQ)で解きました。
実際はつらら(過去問)みたいにして O(N)でいけます。

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

#define int long long

const int MAX_N = 100000, MAX_Q = 1000;

int N, T, Q, A[MAX_N], D[MAX_N], X[MAX_Q];

int Find(int x, int d)
{
    for (int i = x; 0 <= i && i < N; i += d)
    {
        if (D[i] != d) return i;
    }
    return -1;
}

signed main()
{
    vector<int> a1, a2;
    cin >> N >> T >> Q;
    for (int i = 0; i < N; i++)
    {
        cin >> A[i] >> D[i];
        D[i] = (D[i] == 1) ? 1 : -1;
    }
    for (int i = 0; i < Q; i++)
    {
        cin >> X[i];
        X[i]--;
        int x = Find(X[i], D[X[i]]);
        if (x == -1)
        {
            printf("%lld\n", A[X[i]] + T*D[X[i]]);
            continue;
        }
        int y = Find(x, D[x]);
        if (X[i] == y)
        {
            int t = abs(A[X[i]] - A[x])/2;
            printf("%lld\n", (t <= T) ? (A[X[i]] + A[x])/2 : A[X[i]] + T*D[X[i]]);
            continue;
        }
        int t = abs(A[X[i]] - (A[x] + A[y])/2);
        printf("%lld\n", (t <= T) ? (A[x] + A[y])/2 : A[X[i]] + T*D[X[i]]);
    }
    return 0;
}

5問目

幅+ダイクストラ O(M log_{}{N})です。

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

#define int long long

const int MAX_N = 100000;
const int INF = LLONG_MAX/2;

struct Data
{
    int v, cost;
    Data() {}
    Data(int _v, int _cost)
    {
        v = _v; cost = _cost;
    }

    bool operator < (const Data &a) const
    {
        return cost > a.cost;
    }
};

int N, M, K, S, P, Q, C[MAX_N];
vector<int> edge[MAX_N];
int isDanger[MAX_N];

void BFS()
{
    queue<pair<int, int> > q;
    for (int i = 0; i < K; i++)
    {
        q.push(make_pair(C[i], 0));
    }
    bool isUsed[MAX_N] = {};
    while (!q.empty())
    {
        pair<int, int> f = q.front(); q.pop();
        if (f.second > S) return;
        if (isUsed[f.first]) continue;
        isUsed[f.first] = true;
        isDanger[f.first] = ((f.second == 0) ? 2 : 1);
        for (int i = 0; i < edge[f.first].size(); i++)
        {
            q.push(make_pair(edge[f.first][i], f.second + 1));
        }
    }
}

int Dijkstra()
{
    priority_queue<Data> q;
    q.push(Data(0, 0));
    bool d[MAX_N] = {};
    while (!q.empty())
    {
        Data t = q.top(); q.pop();
        if (t.v == N - 1) return t.cost;
        if (d[t.v]) continue;
        d[t.v] = true;
        if (t.v > 0) t.cost += (isDanger[t.v] == 0) ? P : Q;
        for (int i = 0; i < edge[t.v].size(); i++)
        {
            if (isDanger[edge[t.v][i]] == 2) continue;
            q.push(Data(edge[t.v][i], t.cost));
        }
    }
}

signed main()
{
    cin >> N >> M >> K >> S >> P >> Q;
    for (int i = 0; i < K; i++)
    {
        cin >> C[i];
        C[i]--;
    }
    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        a--; b--;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }

    BFS();
    printf("%lld\n", Dijkstra());
    return 0;
}

6問目

bitDPを書こうとするとif文まみれになりそうで怖かったのでメモ化再帰で解きました。
8近傍全部の「屋台で買ったか」という情報を保存して、実際には 右上、上、今いる場所、左、左下 の5地点だけをメモすることで実装しやすくしました。(でも汚い)
しかしよく考えたら今いる場所は絶対買わなければいけないのでメモする必要がなかったです。
 2^5の定数がかかっていますが O(HW)です。

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

#define int long long

const int MAX_H = 1000, MAX_W = 1000;
const int INF = LLONG_MAX/2;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const int ex[5] = {1, 0, 1, 0, 2}, ey[5] = {1, 1, 0, 2, 0};

int H, W;
char fld[MAX_H][MAX_W];
int memo[MAX_H][MAX_W][1 << 5];

void Move(bool s[3][3], int dir)
{
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            int nx = j + dx[dir], ny = i + dy[dir];
            if (nx < 3 && ny < 3) s[i][j] = s[ny][nx];
            else s[i][j] = false;
        }
    }
}

int ToKey(bool s[3][3])
{
    int res = 0;
    for (int i = 0; i < 5; i++)
    {
        if (s[ey[i]][ex[i]]) res = res | (1 << i);
    }
    return res;
}

bool IsOutside(int x, int y)
{
    return x < 0 || W <= x || y < 0 || H <= y;
}

int DFS(int x, int y, bool s[3][3])
{
    int key = ToKey(s);
    if (memo[y][x][key] != INF) return memo[y][x][key];

    int c = 0;
    if (fld[y][x] != '.' && !s[1][1])
    {
        c = fld[y][x] - '0';
        s[1][1] = true;
    }

    vector<int> yatai;
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i], ny = y + dy[i];
        if (IsOutside(nx, ny)) continue;
        if (fld[ny][nx] == '.' || s[dy[i] + 1][dx[i] + 1]) continue;
        yatai.push_back(i);
    }

    for (int i = 0; i < max((unsigned)1, yatai.size()); i++)
    {
        int c_ = c;
        bool ns[3][3];
        memcpy((bool*)ns, (bool*)s, sizeof(bool)*3*3);
        for (int j = 0; j < yatai.size(); j++)
        {
            if (i == j) continue;
            ns[dy[yatai[j]] + 1][dx[yatai[j]] + 1] = true;
            c_ += fld[y + dy[yatai[j]]][x + dx[yatai[j]]] - '0';
        }
        if (x == W - 1 && y == H - 1) return c_;
        for (int j = 0; j < 2; j++)
        {
            int nx = x + dx[j], ny = y + dy[j];
            if (IsOutside(nx, ny)) continue;

            bool ns_[3][3] = {};
            memcpy((bool*)ns_, (bool*)ns, sizeof(bool)*3*3);
            Move(ns_, j);
            memo[y][x][key] = min(memo[y][x][key], DFS(nx, ny, ns_) + c_);
        }
    }
    return memo[y][x][key];
}

signed main()
{
    fill((int*)memo, (int*)memo + MAX_H*MAX_W*(1 << 5), INF);
    cin >> H >> W;
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            cin >> fld[i][j];
        }
    }

    bool s[3][3] = {};
    printf("%lld\n", DFS(0, 0, s));
    return 0;
}