Ccmmutty logo
Commutty IT
・0 pv・17 min read

青 (←水) 色コーダーが ABC 全問解説する【ABC286】

AtCoder競技プログラミングAtCoderBeginnerContest
https://cdn.magicode.io/media/notebox/6c9a0a53-42bb-4566-8ca6-8625fbd27a1d.jpeg

ウルシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 286)

F 抜き 6 完で初黄パフォ & 入青！
F 問題も解き方見えてたけど、インタラクティブだし、アルゴリズム持ってなかったしダメだった…(´・ω・｀)

A - Range Swap

(AP(A_P と AR),(AP+1A_R),(A_{P+1} と AR+1),⋯ ,(AQA_{R+1}), \cdots, (A_{Q} と AS)A_{S}) をそれぞれ入れ替える。
つまり、(AP(A_P と A(R−P)+P),(AP+1A_{(R-P)+P}),(A_{P+1} と A(R−P)+(P+1)),⋯ ,(AQA_{(R-P)+(P+1)}), \cdots, (A_{Q} と A(R−P)+(Q))A_{(R-P)+(Q)}) をそれぞれ入れ替える。
なので、P≤i≤QP \leq i \leq Q である ii それぞれで、AiA_i と A(R−P)+iA_{(R-P)+i} を入れ替えればいい。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, p, q, r, s;

    cin >> n >> p >> q >> r >> s;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    for (int i = p - 1; i < q; ++i) swap(a[i], a[r - p + i]);

    for (int i = 0; i < n; ++i) cout << a[i] << ' ';

    return 0;
}

B - Cat

SS の ii 文字目を SiS_i とおく。
i=1,2,⋯ ,Ni=1, 2, \cdots, N の順に SiS_i を出力していき、SiS_i = a かつ Si−1S_{i-1} = n のときのみ、SiS_i を出力する前に y を出力すれば OK。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    string s;

    cin >> n >> s;

    cout << s[0];
    for (int i = 1; i < n; ++i) {
        if (s[i] == 'a' && s[i - 1] == 'n') {
            cout << 'y';
        }
        cout << s[i];
    }

    return 0;
}

C - Rotate and Palindrome

SiS_i を置き換えてから、k(<N)k(<N) 回 SS の左端の文字を右端に移動することは、kk 回 SS の左端の文字を右端に移動してから、Si+kS_{i+k} を置き換える (i+k>Ni+k>N なら i+k−Ni+k-N を置き換える) ことと同じである。
つまり、AA 円払う操作を、BB 円払う操作より先に行ったとしても、必要な最低金額は変わらない。
なので、AA 円払う操作をすべて行った後に、BB 円払う操作を行うことを考える。
AA 円払う操作は NN 回でもとの文字列 SS に戻るので、最大でも N−1N-1 回行えばいい。
また、BB 円払う操作は、Si≠SN−i+1S_i \neq S_{N-i+1} である SiS_i にのみ行えばいい。
よって、SS に、AA 円払う操作を ii 回行った文字列 (0≤i<N0 \leq i <N) それぞれに対して、j<N−j+1j<N-j+1 の範囲で、Sj≠SN−j+1S_j \neq S_{N-j+1} である jj の数を数えればいい。
AA 円払う操作を ii 回行った文字列の、Sj≠SN−j+1S_j \neq S_{N-j+1} である jj の数を cnticnt_i とおくと、答えは、min⁡i(Ai+Bcnti)\displaystyle\min_{i} (Ai + B cnt_i)。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    int n;
    ll a, b;
    string s;
    ll ans = 1ll << 60;

    cin >> n >> a >> b >> s;

    for (int i = 0; i < n; ++i) {
        ll cost = i * a;
        for (int j = 0; j < n / 2; ++j) {
            if (s[j] != s[n - j - 1]) cost += b;
        }
        ans = min(ans, cost);
        s = s.substr(1, n - 1) + s[0];
    }

    cout << ans;

    return 0;
}

D - Money in Hand

「ちょうど ii 円支払えるか」を dp[i]dp[i] とおくと、dp[0]=truedp[0]=\text{true} で初期化すれば、ii ごとに、jj の降順に、
dp[j]={false(if    ∀k∈[0,Bi],dp[j−Aik]=false)true(otherwise)dp[j]= \begin{cases} \text{false}&(\text{if}\;\; \forall k \in [0,B_i], dp[j-A_i k] = \text{false}) \\ \text{true}&(\text{otherwise}) \end{cases}
で更新すればいい。答えは、dp[X]dp[X] で、オーダーは、O(NXB)O(NXB)。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, x;

    cin >> n >> x;

    vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i) cin >> a[i] >> b[i];

    vector<bool> dp(x + 1);
    dp[0] = true;

    for (int i = 0; i < n; ++i) {
        for (int j = x; j >= 0; --j) {
            for (int k = 0; k <= b[i] && j - a[i] * k >= 0; ++k) {
                if (dp[j - a[i] * k]) {
                    dp[j] = true;
                    break;
                }
            }
        }
    }

    cout << (dp[x] ? "Yes" : "No");

    return 0;
}

E - Souvenir

ii から jj への辺のコスト ci,jc_{i,j} を、ci,j={1,−Aj}c_{i,j}=\{1,-A_j\} とおいてワーシャルフロイドするだけ。
ワーシャルフロイドの解を d[i][j]={firsti,j,secondi,j}d[i][j]=\{first_{i,j},second_{i,j}\} とおくと、使用する直行便の本数は、firsti,jfirst_{i,j} で、お土産の価値の総和は、Ai−secondi,jA_i-second_{i,j}。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

class WarshallFloyd {
   public:
    using PAIR = pair<int, ll>;
    const PAIR INF = {1 << 20, 1ll << 60};

   private:
    int n;
    vector<vector<PAIR>> d;

   public:
    WarshallFloyd(int v) : n(v), d(v, vector<PAIR>(v, INF)) {
        for (int i = 0; i < n; i++) d[i][i] = {0, 0};
    }

    void edge(int from, int to, PAIR cost) {
        if (d[from][to] > cost) d[from][to] = cost;
    }

    void solve() {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                for (int k = 0; k < n; k++) {
                    PAIR comp = make_pair(d[j][i].first + d[i][k].first, d[j][i].second + d[i][k].second);
                    if (d[j][k] > comp) d[j][k] = comp;
                }
    }

    PAIR getD(int from, int to) { return d[from][to]; }
};

int main() {
    int n, q;

    cin >> n;

    vector<int> a(n);
    vector<string> s(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) cin >> s[i];

    WarshallFloyd w(n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (s[i][j] == 'Y') w.edge(i, j, make_pair(1, -a[j]));
        }
    }
    w.solve();

    cin >> q;

    for (int i = 0, u, v; i < q; ++i) {
        cin >> u >> v;
        --u; --v;

        WarshallFloyd::PAIR ans = w.getD(u, v);
        if (ans == w.INF) cout << "Impossible\n";
        else cout << ans.first << ' ' << a[u] - ans.second << '\n';
    }

    return 0;
}

F - Guess The Number 2

インタラクティブな問題で、改行の代わりに空白にしたり、空白の代わりに改行にしたりすると通らないことがあるのね…。
f(i)f(i) が kk 回で循環すれば、NN を kk で割った余りがわかる。なので、gcd(m1,m2,⋯ )=1\text{gcd}(m_1, m_2, \cdots) = 1 かつ ∑mi≤110\sum m_i \leq 110 かつ ∏mi≥109\prod m_i \geq {10}^9 である、(m1,m2,⋯ )(m_1, m_2, \cdots) を法とした中国剰余定理を用いれば OK。
例えば、(4,9,5,7,11,13,17,19,23)(4, 9, 5, 7, 11, 13, 17, 19, 23) を法とすればいい。このとき、AA は、
A=(2,3,4,1,6,7,8,9,10,11,12,13,5,⋯ )A=(2, 3, 4, 1, 6, 7, 8, 9, 10, 11, 12, 13, 5, \cdots)
((2,3,4,1)((2, 3, 4, 1) が 44 回で循環、(6,7,8,9,10,11,12,13,5)(6, 7, 8, 9, 10, 11, 12, 13, 5) が 99 回で循環、⋯ )\cdots)
など。
中国剰余定理を求める関数を持っていなかったので、ここを参考に実装。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

// 拡張 gcd (中国剰余定理用)
long long extGcd(long long a, long long b, long long &p, long long &q) {
    static auto swap = [](long long &a, long long &b) { a ^= b; b ^= a; a ^= b; };
    long long temp;
    long long x = 0, y = 1;
    p = 1, q = 0;
    while (b) {
        temp = a / b; a %= b;
        p -= x * temp; q -= y * temp;
        swap(a, b); swap(p, x); swap(q, y);
    }
    return a;
}

// 中国剰余定理
pair<long long, long long> CRT(long long b1, long long m1, long long b2, long long m2) {
    long long p, q;
    long long d = extGcd(m1, m2, p, q);
    if ((b2 - b1) % d) return {-1, -1};
    long long m = m1 / d * m2;
    long long r = b1 + m1 * ((b2 - b1) / d * p % (m2 / d));
    if (r < 0) r += m;
    return {r, m};
}

int main() {
    vector<int> m({4, 9, 5, 7, 11, 13, 17, 19, 23});
    const int mSize = m.size();
    const int sumSize = mSize + 1;
    vector<int> sum(sumSize);
    sum[0] = 0;
    for (int i = 1; i < sumSize; ++i) sum[i] = sum[i - 1] + m[i - 1];

    // A を出力
    const int aSize = sum.back();
    cout << aSize << endl;
    for (int i = 0; i < mSize; ++i) {
        for (int j = 2; j <= m[i]; ++j) {
            cout << j + sum[i] << ' ';
        }
        cout << 1 + sum[i] << ' ';
    }
    cout << endl;

    vector<int> input(aSize);
    for (int i = 0; i < aSize; ++i) {
        cin >> input[i];
    }

    // 中国剰余定理を用いて N を求める
    int r = input[0] - 1, mod = m[0];
    for (int i = 1; i < mSize; ++i) {
        tie(r, mod) = CRT(r, mod, input[sum[i]] - sum[i] - 1, m[i]);
    }
    cout << r << endl;

    return 0;
}

G - Unique Walk

SS に含まれない辺で結ばれている 22 頂点間は、自由に移動できる。そのため、SS に含まれない辺を削除し、その辺で結ばれている 22 頂点を 11 点に圧縮しても問題ない。
SS に含まれないすべての辺に対して、上記の操作を行ったグラフを G′G' とおく。
すると、この問題は、G′G' 上の歩道のうち、G′G' 上のすべての辺をちょうど 11 回ずつ通るようなものが存在するか判定する問題と同値となる。
この問題は、一筆書きが可能 (オイラー路というらしい) かどうかの判定問題に他ならない。つまり、
  • G′G' が連結
  • 張られている辺の本数が奇数である頂点の数が 22 個以下
の 22 つを満たせばいい。制約から GG は連結なので、G′G' も連結である。なので、「張られている辺の本数が奇数である頂点の数」を数えるだけで OK。オーダー O(N)O(N) で判定できる。
G′G' の作成は、Union-Find を用いれば、オーダー O(Mα(N))O(M \alpha(N)) でできる。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

class UnionFind {
    vector<int> p;

   public:
    UnionFind(int n) : p(n, -1) {}

    void unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return;

        if (p[x] < p[y]) {
            p[x] += p[y];
            p[y] = x;
        } else {
            p[y] += p[x];
            p[x] = y;
        }
        return;
    }

    int find(int x) {
        if (p[x] < 0) return x;
        while (p[p[x]] >= 0) {
            p[x] = p[p[x]];
            x = p[x];
            if (p[x] < 0) return x;
        }
        return p[x];
    }
};

int main() {
    int n, m, k;

    cin >> n >> m;

    vector<pair<int, int>> e(m);  // 辺
    for (int i = 0, u, v; i < m; ++i) {
        cin >> u >> v;
        --u, --v;
        e[i] = {u, v};
    }

    cin >> k;
    vector<bool> inS(m);  // S に含まれるか
    for (int i = 0, x; i < k; ++i) {
        cin >> x;
        inS[x - 1] = true;
    }

    // S に含まれない辺で結ばれた 2 頂点を圧縮
    UnionFind uni(n);
    for (int i = 0; i < m; ++i) {
        if (!inS[i]) uni.unite(e[i].first, e[i].second);
    }

    // press[i] = (圧縮後の i の頂点番号)
    vector<int> press(n);
    for (int i = 0; i < n; ++i) {
        press[i] = uni.find(i);
    }

    // G' の作成
    vector<vector<int>> g(n);
    for (int i = 0; i < m; ++i) {
        if (inS[i]) {
            auto [u, v] = e[i];
            g[press[u]].push_back(press[v]);
            g[press[v]].push_back(press[u]);
        }
    }

    // 張られている辺の本数が奇数である頂点の数をカウント
    int odd = 0;
    for (int i = 0; i < n; ++i) {
        if (g[i].size() & 1) ++odd;
    }

    cout << (odd <= 2 ? "Yes" : "No");

    return 0;
}

Ex - Don't Swim

解説見ずに Ex 問題 AC したけど、その解法、コーナーケースあった…ので、もう 11 つ思いついていたパターンで AC 取り直した…(´・ω・｀)
凸包をとるアルゴリズムが典型っぽいので、それを持ってるなら公式解説のほうが実装楽そうだけど…。ちなみに、凸包をとるアルゴリズムは、「競プロ典型 90 問」のこの問題の解説で紹介されています。公式解説では O(N)O(N) って書いてあったけど、ソートに O(Nlog⁡N)O(N \log N) かかります…。
私の解法が O(N)O(N) なので、それを解説します。
頂点 x,yx,y の候補して、できる限りぎりぎりのところのみを考えるという考え方は、公式解説と同じ。 つまり、

このような、赤か緑の距離を考えればいい。
そのような頂点の見つけ方を考える。
図のように、

できる限りぎりぎりの頂点は、それぞれ S,TS,T を原点としたときの角度が最小 (または最大) の頂点である。なので、それを求めればいい。O(N)O(N) で求められる。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

// ユークリッド距離
double eucD(double x1, double y1, double x2, double y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

// 角度を [-PI, PI] -> [0, PI * 2] へ変換
void fromZero(double &th) {
    static const double PI = 3.141592653589793;
    if (th < 0) th += PI * 2;
}

int main() {
    int n;
    double sx, sy, tx, ty;
    const double PI = 3.141592653589793;

    cin >> n;

    vector<double> x(n), y(n);
    for (int i = 0; i < n; ++i) cin >> x[i] >> y[i];

    cin >> sx >> sy >> tx >> ty;

    // s を原点とした角度、t を原点とした角度を求める
    vector<double> sTheta(n), tTheta(n);
    for (int i = 0; i < n; ++i) {
        sTheta[i] = atan2(y[i] - sy, x[i] - sx);
        tTheta[i] = atan2(y[i] - ty, x[i] - tx);
    }
    double stTheta = atan2(ty - sy, tx - sx);
    double tsTheta = atan2(sy - ty, sx - tx);

    // 最小、最大の角度を求める
    auto [sMinTheta, sMaxTheta] = minmax_element(sTheta.begin(), sTheta.end());
    auto [tMinTheta, tMaxTheta] = minmax_element(tTheta.begin(), tTheta.end());

    // 最大の角度と最小の角度の差が PI 以上なら
    // できる限りぎりぎりの頂点の角度の差が PI 以上なのはおかしいので、
    // 角度の範囲を [-PI, PI] から [0, PI * 2] に変更して再計算
    if (*sMaxTheta - *sMinTheta >= PI) {
        for (int i = 0; i < n; ++i) fromZero(sTheta[i]);
        fromZero(stTheta);
        tie(sMinTheta, sMaxTheta) = minmax_element(sTheta.begin(), sTheta.end());
    }
    if (*tMaxTheta - *tMinTheta >= PI) {
        for (int i = 0; i < n; ++i) fromZero(tTheta[i]);
        fromZero(tsTheta);
        tie(tMinTheta, tMaxTheta) = minmax_element(tTheta.begin(), tTheta.end());
    }

    // 線分 st が多角形と交わらないなら s と t の距離が答え
    if (stTheta < *sMinTheta || *sMaxTheta < stTheta ||
        tsTheta < *tMinTheta || *tMaxTheta < tsTheta) {
        printf("%.10lf", eucD(sx, sy, tx, ty));
        return 0;
    }

    // d[i] は、頂点 0, 頂点 1, …, 頂点 i の順に移動したときの距離
    vector<double> d(n);
    for (int i = 1; i < n; ++i) {
        d[i] = d[i - 1] + eucD(x[i], y[i], x[i - 1], y[i - 1]);
    }
    double polygonD = d[n - 1] + eucD(x[0], y[0], x[n - 1], y[n - 1]);

    // 角度が最小、最大になる頂点の番号
    int sMinIdx = sMinTheta - sTheta.begin(), sMaxIdx = sMaxTheta - sTheta.begin();
    int tMinIdx = tMinTheta - tTheta.begin(), tMaxIdx = tMaxTheta - tTheta.begin();
    // その頂点との距離
    double sMinD = eucD(x[sMinIdx], y[sMinIdx], sx, sy),
           sMaxD = eucD(x[sMaxIdx], y[sMaxIdx], sx, sy);
    double tMinD = eucD(x[tMinIdx], y[tMinIdx], tx, ty),
           tMaxD = eucD(x[tMaxIdx], y[tMaxIdx], tx, ty);

    double polygonD0 = abs(d[sMinIdx] - d[tMaxIdx]);
    double d0 = min(polygonD0, polygonD - polygonD0) + sMinD + tMaxD;
    double polygonD1 = abs(d[sMaxIdx] - d[tMinIdx]);
    double d1 = min(polygonD1, polygonD - polygonD1) + sMaxD + tMinD;

    printf("%.10lf", min(d0, d1));

    return 0;
}

Discussion

コメントにはログインが必要です。