JOIレベル5解説 - Part 1 (品質検査～最高のピザ)

https://joi.goodbaton.com/ のレベル5です。演習時の参考にお使いください。なお、セミファイナルステージ(旧本選)、ファイナルステージ(旧春トレ)、オープンは除いています。

品質検査

問題概要

3つの部品の組について、「すべてが正常である」かどうかがN個与えられる。それぞれの部品が正常であるか、正常でないか、どちらであるともいえないかを判定せよ。

解法

まず合格であるパーツを絞り出す。次に、合格をO、不明を?として、OO?、O?O、?OOを探し、?をOにする。このとき、それぞれの不合格ケースは独立に処理できる。なぜなら、不明が1つしかない場合は不合格であるものが自明であることには変わりないし、不明が2つ以上の場合は「1つしか故障していない」わけではないから結局故障しているのかが不明であるからである。

コード例

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vl = vector<long long>;
#define rep(i,n) for(ll i=0;i<(n);++i)

int main() {
    ll a, b, c;
    cin >> a >> b >> c;

    ll N;
    cin >> N;

    // 0...x, 1...o, 2...?
    vl st(a+b+c, 2);

    queue<tuple<ll,ll,ll>> q;
    rep(_, N) {
        ll i, j, k, r;
        cin >> i >> j >> k >> r;
        --i, --j, --k;
        
        if (r == 1) { // テストが合格であるならばすべて合格
            st[i] = st[j] = st[k] = 1;
        } else { // 不合格なら合格をすべて参照する必要があるので後回し
            q.emplace(i, j, k);
        }
    }
    
    // 後回しにした不合格のケースについて処理する。
    while (!q.empty()) {
        auto [i, j, k] = q.front(); q.pop();
        bool I = st[i] == 1, J = st[j] == 1, K = st[k] == 1;
        if (I && J && !K) st[k] = 0;
        if (I && !J && K) st[j] = 0;
        if (!I && J && K) st[i] = 0;
    }

    // 範囲for文を使って結果を出力
    for (auto v:st) cout << v << endl;
}

星座探し

問題概要

たくさんの点の集合A,Bが与えられる。Aを平行移動してBに重ねるとき、平行移動する量を答えよ。ただし、Bには余分な点が含まれている可能性がある。

解法

星座の星0を実際の星$i$に当てはめて、あと残りが重なるかチェックする。

コード例

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long>;
template<typename T>istream&operator>>(istream&is,vector<T>&v){for(auto&in:v)is>>in;return is;}

int main() {
    ll n;
    cin >> n;
    vector<P> seiza(n);
    cin >> seiza;
    ll m;
    cin >> m;
    vector<P> photo(m);
    cin >> photo;
    sort(photo.begin(), photo.end());

    // seiza[0]を移動する先
    for (P move_target : photo) {
        ll dx = move_target.first - seiza[0].first;
        ll dy = move_target.second - seiza[0].second;
        bool ok = true;
        for(P star : seiza) {
            if (!binary_search(all(photo), make_pair(star.first+dx, star.second+dy))) {
                ok = false;
            }
        }
        if (ok) {
            cout << dx << " " << dy << endl;
            return 0;
        }
    }
}

船旅

問題概要

N頂点の無向グラフについて、特定の点の間の最短距離を求めよ。ただし、途中で辺が増えていく。また、辺の重みは0より大きい。

解法

クエリごとにdijkstraを繰り返して答えを求める。

コード例

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<long long, long long>;
#define rep(i,n) for(ll i=0;i<(n);++i)
ll INF = 2e15;

int main() {
    ll N, K;
    cin >> N >> K;
    vector<vector<P>> nexts(N); // cost, arrive_at
    rep(i, K) {
        ll kind;
        cin >> kind;
        switch (kind) {
            case 0: {
                ll a, b;
                cin >> a >> b; --a, --b;
                // do dijkstra
                priority_queue<P, vector<P>, greater<>> q; // cost, arrive_at
                q.emplace(0, a);

                vector<ll> costs(N, INF);
                costs[a] = 0;
                while (!q.empty()) {
                    auto [_, now] = q.top(); q.pop();

                    for (auto [cost, next] : nexts[now]) {
                        if (costs[next] > costs[now] + cost) {
                            costs[next] = costs[now] + cost;
                            q.emplace(costs[next], next);
                        }
                    }
                }

                if (costs[b] == INF) {
                    cout << -1 << endl;
                } else {
                    cout << costs[b] << endl;
                }
                break;
            }
            case 1: {
                ll c, d, e;
                cin >> c >> d >> e; --c, --d;
                nexts[c].emplace_back(e,d);
                nexts[d].emplace_back(e,c);
                break;
            }
        }
    }
}

薄氷渡り

問題概要

M×Nのグリッドが与えられる。グリッドの各点は、0回もしくは1回通過することができる。好きな点から始め、できるだけ多くの点を通るとき、その数の最大値を求めよ。

解法

再帰を用いてDFS(深さ優先探索)をする。これは、移動方法が20万通り=$2*10^5$を超えないことから間に合うといえる。

コード例

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(ll i=0;i<(n);i++)
template<typename T>istream&operator>>(istream&is,vector<T>&v){for(auto&in:v)is>>in;return is;}

vector<vector<ll>> mp;
vector<vector<bool>> seen;
ll res = 0;
ll m, n;

void dfs(ll x, ll y, ll depth) {
    chmax(res, depth);
    seen[x][y] = true;
    rep(i, 4) {
        ll next_x = x + dx[i], next_y = y + dy[i];
        if (0 <= next_x && next_x < n && 0 <= next_y && next_y < m && !seen[next_x][next_y] && mp[next_x][next_y]==1){
            dfs(next_x, next_y, depth+1);
        }
    }
    seen[x][y] = false;
}

int main() {
    cin >> m >> n;
    mp = vector<vector<ll>>(n, vl(m));
    cin >> mp;
    rep(i, n) {
        rep(j, m) {
            if (mp[i][j] == 0) continue;
            seen = vc(n, vb(m, false));
            dfs(i,j,1);
        }
    }

    cout << res << endl;
}

カード並べ

問題概要

数列Aが与えられる。k個選んでそれを横に並べ1つの数として見るとき、その種類数を求めよ。

解法

すべてのカードの組み合わせについて、最初に文字列としてカードを結合し、それを数値に変換し、重複を許さないデータ構造であるsetに追加していく。

コード例

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(ll i=0;i<(n);i++)
template<typename T>istream&operator>>(istream&is,vector<T>&v){for(auto&in:v)is>>in;return is;}

int main() {
    ll N, K;
    cin >> N >> K;
    vector<string> cards(N);
    cin >> cards;

    set<ll> vals;
    if (K == 2) {
        rep(i, N) {
            rep(j, N) {
                if (i == j) continue;
                vals.insert(stoll(cards[i]+cards[j]));
            }
        }
    } else if (K == 3) {
        rep(i, N) {
            rep(j, N) {
                rep(k, N) {
                    if (i == j || j == k || k == i) continue;
                    vals.insert(stoll(cards[i]+cards[j]+cards[k]));
                }
            }
        }
    } else if (K == 4) {
        rep(i, N) {
            rep(j, N) {
                rep(k, N) {
                    rep(l, N) {
                        if (i == j || i == k || i == l || j == k || j == l || k == l) continue;
                        vals.insert(stoll(cards[i]+cards[j]+cards[k]+cards[l]));
                    }
                }
            }
        }
    }

    cout << vals.size() << endl;
}

1年生

問題概要

数列が与えられる。数列の要素の間に$+$もしくは$-$の符号を入れ(最後は$=$)、等式を成り立たせよ。ただし、左から演算していくときに、20を超えたり、0を切ったりしてはならない。

解法

DPをする。
$dp_{i,j}$ : i番目の数値まで考えたときにそこまでの合計値でjを達成する方法が何通りあるか

コード例

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0; i<(n); i++)
using ll = long long;
template<typename T>istream&operator>>(istream&is,vector<T>&v){for(auto&in:v)is>>in;return is;}

int main() {
    ll n;
    cin >> n;
    vector<ll> ints(n);
    cin >> ints;

    vector<vector<ll>> dp(n-1, vl(21, 0)); // dp[i][j]...i番目の合計値をjにする方法の数
    dp[0][ints[0]]=1;
    rep(i, n-2) {
        rep(j, 21) {
            if (j + ints[i+1] <= 20) {
                dp[i+1][j+ints[i+1]]+=dp[i][j];
            }
            if (j - ints[i+1] >= 0) {
                dp[i+1][j-ints[i+1]]+=dp[i][j];
            }
        }
    }
    cout << dp.back()[ints.back()] << endl;
}

チーズ

問題概要

通れない点を0個以上含むグリッドが与えられる。与えられる点について、順番に巡るときの最短距離を求めよ。

解法

便宜上、スタートを工場0とする。
BFSをN回繰り返す。i回目($0\leq i < N$)のBFSは、i番目の工場からi+1番目の工場に行く最短距離を求める。

コード例

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(ll i=0; i<(n); i++)
template<typename T>istream&operator>>(istream&is,vector<T>&v){for(auto&in:v)is>>in;return is;}

int main() {
    ll h, w, n;
    cin>>h>>w>>n;
    vector<string> field(h);
    cin >> field;

    vector<pair<ll,ll>> p(n+1);

    rep(i,h) rep(j,w) {
        if(field[i][j]=='S')p[0]=make_pair(i,j);
        if('0'<field[i][j]&&field[i][j]<='9')p[field[i][j]-'0']=make_pair(i,j);
    }

    ll res = 0;
    rep(i,n) {
        vector<vector<ll>> dist(h,vector<ll>(w,INF));
        dist[p[i].first][p[i].second] = 0;
        
        queue<P> q;
        q.push(p[i]);

        while (!q.empty()) {
            auto [x,y] = q.front(); q.pop();
            rep(i,4){
                ll nx=x+dx[i], ny=y+dy[i];
                if(0<=nx&&nx<h&&0<=ny&&ny<w&&field[nx][ny]!='X'&&dist[nx][ny]>dist[x][y]+1){
                    dist[nx][ny]=dist[x][y]+1;
                    q.emplace(nx,ny);
                }
            }
        }
        res+=dist[p[i+1].first][p[i+1].second];
    }
    cout<<res<<endl;
}

最高のピザ

問題概要

ピザに全部同じ価格のトッピングをそれぞれ0個か1個載せていくとき、「カロリー数の総和を価格で割った値」を最大化せよ。トッピングのカロリー数は等しいとは限らない。

解法

カロリー効率を毎回計算しながら、一番カロリー効率の良いトッピングから順に見ていき、貪欲法で追加するか判定する。この際、少数を表現できる型を使用する必要があることに注意。(doubleなど)

コード例

#include <bits/stdc++.h>
using namespace std;using ll=long long;
#define rep(i,n) for(ll i=0; i<(n); i++)

int main() {
    ll N, A, B, C;
    cin >> N >> A >> B >> C;
    vl D(N);
    rep(i, N) cin >> D[i];
    sort(D.rbegin(), D.rend());

    ll price = A, calorie = C;

    rep(i, N) {
        double now_cal_kouritu = double(calorie) / double(price);
        ll d = D[i];

        double next_cal_kouritu = double(calorie+d) / double(price+B);
        if (next_cal_kouritu > now_cal_kouritu) {
            price += B;
            calorie += d;
        }
    }

    cout << calorie/price << endl;
}