牛客週間コンテスト 第5回

A-游游の文字変換

#include <iostream>
#include <string>
using namespace std;

int main() {
    string input;
    cin >> input;
    
    for (size_t i = 0; i < input.length(); ++i) {
        char current = input[i];
        if (current >= 'A' && current < 'Z') {
            input[i] = current + 1;
        } else if (current > 'a' && current <= 'z') {
            input[i] = current - 1;
        } else if (current == 'Z') {
            input[i] = 'A';
        } else if (current == 'a') {
            input[i] = 'z';
        }
    }
    
    cout << input << endl;
    return 0;
}

B-游游の順列構築

i番目の要素が前i個の要素の中で最大値となるようにするには、最初に(n-k+1)番目の大きな要素を配置し、その後、2つずつ配置しながら1ずつ増やしていくと、k-1まで続き、kが0になると条件を満たす列が構成されます。

#include <iostream>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    
    int current = 1;
    for (int i = 1; i <= n; ++i) {
        if (k > 0 && i % 2 == 1) {
            cout << n - k + 1 << " ";
            k--;
        } else {
            cout << current++ << " ";
        }
    }
    
    return 0;
}

C-游游の二分木探索

nが1から10^3の範囲にある場合、直接全探索を行います。最初は01文字列を数値に変換して条件を満たしているかどうかを判断しようとしましたが、最終的に80ptしか得られませんでした。他の人のコードを見て、実際には左シフトするだけでよいことが分かりました。

#include <iostream>
#include <vector>
using namespace std;

void dfs(int node, int parent, int value, int length, const vector<vector<int>>& tree, const string& values, int& count, int L, int R) {
    if (value > R) return;
    
    if (value >= L && value <= R && length > 1) {
        count++;
    }
    
    for (int neighbor : tree[node]) {
        if (neighbor == parent) continue;
        dfs(neighbor, node, (value << 1) + (values[neighbor] - '0'), length + 1, tree, values, count, L, R);
    }
}

int main() {
    int n, L, R;
    cin >> n >> L >> R;
    string values;
    cin >> values;
    
    vector<vector<int>> tree(n + 1);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    
    int result = 0;
    for (int i = 1; i <= n; ++i) {
        dfs(i, 0, values[i-1] - '0', 1, tree, values, result, L, R);
    }
    
    cout << result << endl;
    return 0;
}

D-游游の行列統計

上層のk個の要素と下層のk個の要素が異なる場合、ちょうどk-1種類の異なる要素を持つ2×2の部分行列の数が存在します。

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main() {
    int n, m1, m2;
    cin >> n >> m1 >> m2;
    
    vector<pair<int, int>> upper(m1), lower(m2);
    for (auto& p : upper) cin >> p.first >> p.second;
    for (auto& p : lower) cin >> p.first >> p.second;
    
    map<int, int> freq;
    int i = 0, j = 0, answer = 0;
    
    while (i < m1 || j < m2) {
        freq[upper[i].first]++;
        freq[lower[j].first]++;
        
        if ((i != 0 || j != 0) && freq.size() == 2) {
            answer++;
        }
        
        if (upper[i].first != lower[j].first) {
            int k = min(upper[i].second, lower[j].second);
            upper[i].second -= k;
            lower[j].second -= k;
            answer += k - 1;
        } else {
            int k = min(upper[i].second, lower[j].second);
            upper[i].second -= k;
            lower[j].second -= k;
        }
        
        freq.clear();
        freq[upper[i].first]++;
        freq[lower[j].first]++;
        
        if (upper[i].second == 0) i++;
        if (lower[j].second == 0) j++;
    }
    
    cout << answer << endl;
    return 0;
}

E-小紅の木構造

すべての点の値の積を最小にするには、パスが最短である必要があります。菊花グラフが最適です。

したがって、2-2/3-3、2-3/3-2、2-2-2/3-3-3、2-2-3/2-3-2/3-2-2、3-2-3/2-3-3というパスがあります。

2-2/3-3と2-2-2/3-3-3を一緒にする理由は、それらの積の因数数が同じだからです。他のものは位置が異なるだけで、パスの結果は同じです。

また、3と2を単独で組み合わせる因数数は、それらを混合して組み合わせる因数数よりも小さいため、菊花グラフの中心に数量が最も多い2または3を配置する必要があります。

#include <iostream>
using namespace std;

long long fast_pow(long long base, long long exponent, long long mod) {
    long long result = 1;
    while (exponent > 0) {
        if (exponent % 2 == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exponent /= 2;
    }
    return result;
}

int main() {
    int n, k;
    cin >> n >> k;
    n -= k;
    if (n > k) swap(n, k);
    
    const long long MOD = 1e9 + 7;
    long long answer = 1;
    
    answer = fast_pow(3, k - 1, MOD);
    answer = (answer * fast_pow(4, n, MOD)) % MOD;
    answer = (answer * fast_pow(4, (k - 1) * (k - 2) / 2, MOD)) % MOD;
    answer = (answer * fast_pow(6, (k - 1) * n, MOD)) % MOD;
    answer = (answer * fast_pow(6, n * (n - 1) / 2, MOD)) % MOD;
    
    cout << answer << endl;
    return 0;
}