2024年夏休み交流戦・練習編1

A - 🐓

AtCoder - abc079_d

問題文

各頂点のコストが与えられ、それを1に変換するのに必要な最小コストを求める。

解法

すべての数を1にするには、直接1に変換するか、別の数に変換してからさらに変換する方法がある。

これは$floyd$アルゴリズムによる最短経路探索と似ているため、$floyd$を適用できる。

コード

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

const int N = 2e2 + 10;
int cost[N][N], grid[N][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int h, w;
    cin >> h >> w;

    for (int i = 0; i < 10; i ++)
        for (int j = 0; j < 10; j ++)
            cin >> cost[i][j];

    for (int i = 1; i <= h; i ++)
        for (int j = 1; j <= w; j ++)
            cin >> grid[i][j];

    for (int k = 0; k < 10; k ++)
        for (int i = 0; i < 10; i ++)
            for (int j = 0; j < 10; j ++)
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);

    i64 total = 0;
    for (int i = 1; i <= h; i ++)
        for (int j = 1; j <= w; j ++)
            total += cost[grid[i][j]][1];

    cout << total << '\n';

    return 0;
}

B - 🐓🐓

AtCoder - arc100_a

問題文

n個の数列が与えられる。任意の数bを選択し、|A₁-(b+1)|+...+|Aᵢ-(b+i)|+...+|Aₙ-(b+n)|を最小化する。

解法

一般項は|Aᵢ-(b+i)|である。

この式は|(Aᵢ-i)-b|と書き換えられる。

この値を小さくするには、bを(Aᵢ-i)に近づける必要がある。

したがって、Aᵢ-iを計算し、ソートした後、中央値をbとして選ぶことで最小化できる。

コード

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    i64 result = 0;
    vector<i64> values(n + 1);
    for (int i = 1; i <= n; i ++) {
        cin >> values[i];
        values[i] -= i;
    }

    sort(values.begin() + 1, values.end());

    for (int i = 1; i <= n; i ++) {
        result += abs(values[i] - values[n / 2 + 1]);
    }

    cout << result << '\n';

    return 0;
}

C - 🐓🐓🐓

AtCoder - arc099_a

問題文

配列が与えられる。長さkの区間を一括で最小値に変更できる。配列全体が同じになるまで必要な操作回数を求める。

解法

kに関係なく、配列に1があれば、操作によりすべて1になる。

1のある位置からk個の区間を操作すると残り(n-k)個の要素が残る。

そのとき、1つだけ1を含み、残り(k-1)個は他の数を含む区間を操作することで、(k-1)個の数が1になる。

この操作回数は⌈(n-k)/(k-1)⌉であり、1回の操作を加えると⌈(n-1)/(k-1)⌉になる。

コード

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    int position;
    vector<i64> arr(n + 1);
    for (int i = 1; i <= n; i ++) {
        cin >> arr[i];
    }

    int answer = (n - 1 + (k - 2)) / (k - 1);

    cout << answer << '\n';

    return 0;
}

D - 🐓🐓🐓🐓

AtCoder - arc100_b

問題文

数列Aを連続する4つの部分に分割し、それぞれの和の差を最小化する。

解法

累積和を計算した上で、1〜n-1から3つの位置i,j,kを選ぶと、sᵢ,sⱼ-sᵢ,sₖ-sⱼ,sₙ-sₖの差を最小化できる。

jを固定し、iとkはそれぞれ1〜j-1とj+1〜nの分割点でバランスを取るように選択する。

このとき、iとkはそれぞれsⱼ-sᵢとsₙ-sₖの差を最小化するように選ぶ。

コード

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<i64> nums(n + 1), prefix(n + 1);
    for (int i = 1; i <= n; i ++) {
        cin >> nums[i];
        prefix[i] = prefix[i - 1] + nums[i];
    }

    i64 minimum = 1 << 30;

    i64 max_val, min_val, start1=1, start2=3;
    for (int i = 2; i < n; i ++) {
        while(start1 < i && abs(prefix[start1]-(prefix[i]-prefix[start1]))>abs(prefix[start1+1]-(prefix[i]-prefix[start1+1])))
            start1 ++;
        while(start2<n &&abs((prefix[start2]-prefix[i])-(prefix[n]-prefix[start2]))>abs((prefix[start2+1]-prefix[i])-(prefix[n]-prefix[start2+1])))
            start2 ++;
        max_val = max({prefix[start1], prefix[i] - prefix[start1], prefix[start2] - prefix[i], prefix[n] - prefix[start2]});
        min_val = min({prefix[start1], prefix[i] - prefix[start1], prefix[start2] - prefix[i], prefix[n] - prefix[start2]});
        minimum = min(minimum, max_val - min_val);

    }

    cout << minimum << '\n';

    return 0;
}

E - 🐓🐓🐓🐓🐓

CodeForces - 1808C

問題文

区間内の任意の数を選び、その数の最大桁と最小桁の差を最小にする。

解法

数位DPを使用する。

lとrの桁数が異なる場合、999...999（n-1桁）が答えになる。

同じ場合、数位DPで処理する。

dp[長さ][最大][最小][上限][下限]で状態を管理し、再帰的に計算する。

コード

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

i64 dp[25][20][20][2][2];
i64 numbers[25][20][20][2][2];

void solve() {

    i64 left, right;
    cin >> left >> right;

    vector<int> upper(20, -1), lower(20, -1);
    lower[1] = left % 10;
    i64 len_left = 1, offset = 1, temp = left / 10, len_right = 1;
    while (temp) {
        offset *= 10;
        lower[++len_left] = temp % 10;
        temp /= 10;
    }

    temp = right / 10, upper[1] = right % 10;
    while (temp) {
        upper[++len_right] = temp % 10;
        temp /= 10;
    }

    if (len_left != len_right) {
        cout << string(len_right - 1, '9') << '\n';
        return ;
    }

    reverse(lower.begin() + 1, lower.begin() + len_left + 1);
    reverse(upper.begin() + 1, upper.begin() + len_right + 1);
    memset(dp, -1, sizeof dp);
    memset(numbers,0,sizeof numbers);

    auto dfs = [&](auto & self, int length, i64 current, int max_digit, int min_digit, bool limit_up, bool limit_down)->i64 {
        if (length == len_right + 1) return max_digit - min_digit;
        if (~dp[length][max_digit][min_digit][limit_up][limit_down])
            return dp[length][max_digit][min_digit][limit_up][limit_down];

        i64 best = 10;
        for (int digit = (limit_down ? lower[length] : 0); digit <= (limit_up ? upper[length] : 9); digit ++) {
            i64 res = self(self, length + 1, current / 10, max(max_digit, digit), min(min_digit, digit), limit_up & (digit == upper[length]), limit_down & (digit == lower[length]));
            i64 value = numbers[length + 1][max(max_digit, digit)][min(min_digit, digit)][limit_up & (digit == upper[length])][limit_down & (digit == lower[length])];
            if (res < best) {
                best = res;
                numbers[length][max_digit][min_digit][limit_up][limit_down] = digit * current + value;
            }
        }

        return dp[length][max_digit][min_digit][limit_up][limit_down] = best;
    };

    dfs(dfs, 1, offset, 0, 10, 1, 1);

    cout << numbers[1][0][10][1][1] << '\n';

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int test_cases;
    cin >> test_cases;
    while (test_cases--)
        solve();

    return 0;
}

F - 🐓🐓🐓🐓🐓🐓

CodeForces - 1547E

問題文

n個のマスとk個のエアコンがある。エアコンの位置には初期温度があり、エアコンは両方向に温度を影響させ、同じマスに複数の影響がある場合は最小値を取る。

解法

温度ポインタを保持し、左右からそれぞれ走査し、最小温度を更新しながら各マスの温度を計算する。

コード

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

void solve() {

    int n, k;
    cin >> n >> k;

    vector<int> temperatures(n + 1, 1 << 30), ac_positions(k + 1), ac_temps(k + 1);
    for (int i = 1; i <= k; i ++)
        cin >> ac_positions[i];
    for (int i = 1; i <= k; i ++) {
        cin >> ac_temps[i];
        temperatures[ac_positions[i]] = ac_temps[i];
    }

    int current = 1 << 30;
    for (int i = 1; i <= n; i ++) {
        current = min(++current, temperatures[i]);
        temperatures[i] = min(current, temperatures[i]);        
    }
    
    current = 1 << 30;
    for (int i = n; i >= 1; i --) {
        current = min(++current, temperatures[i]);
        temperatures[i] = min(current, temperatures[i]);
    }

    for (int i = 1; i <= n; i ++)
        cout << temperatures[i] << " \n"[i == n];

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int test_cases;
    cin >> test_cases;
    while (test_cases--)
        solve();

    return 0;
}

G - 🐓🐓🐓🐓🐓🐓🐓

CodeForces - 1107C

問題文

文字ボタンの入力順序が与えられる。それぞれのボタンはAᵢのダメージを与えるが、同一ボタンはk回以上押せない。最大ダメージを達成するためにスキップするボタンの順序を求める。

解法

ボタンの順序を走査し、同じボタンの場合はヒープに保存する。異なるボタンに到達または最後に到達した際、ヒープからk個取り出して合計を加算する。

コード

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    vector<i64> damage(n);
    for (int i = 0; i < n; i ++) {
        cin >> damage[i];
    }

    string sequence;
    cin >> sequence;

    priority_queue<i64> heap;

    i64 total_damage = 0;
    for (int i = 0; i < n; i ++) {
        heap.push(damage[i]);
        if (i == n - 1 || i < n - 1 && sequence[i] != sequence[i + 1]) {
            int count = 0;
            while (count++ < k && heap.size()) {
                total_damage += heap.top();
                heap.pop();
            }
            while (heap.size()) heap.pop();
        }
    }

    cout << total_damage << '\n';

    return 0;
}

H - 🐓🐓🐓🐓🐓🐓🐓🐓

AtCoder - arc102_b

問題文

数Lが与えられる。1からnまでの有向グラフを構築し、1からnへのパス数をLとする。

解法

Lをビット表現に分解し、最も高いビットをkとする。1からkの間でi→i+1の辺を追加し、重みを0と2^(i-1)にする。これにより[0,2^k-1]のパス数を生成できる。Lの他のビットが1の場合は、iからnに重みを設定する。

コード

#include

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int bit_length = 0, L;
    cin >> L;

    while ((1