A問題: 時間帯の重なり判定

この問題は、ある時間が指定された時間範囲に含まれるかを判定するものである。注意点として、時間帯が翌日にまたがるケースがある。これを処理するために、終了時刻が開始時刻より小さい場合は終了時刻に24を加算し、範囲を正しく表現する。

次に、基準となる時刻（国王が叫ぶ時刻）がその範囲内にあるか、または24時間を加えたバージョンが範囲内にあるかをチェックする。どちらにも該当しない場合のみ「Yes」を出力する。

#include <iostream>
using namespace std;

int main() {
    int start, call, end;
    cin >> start >> end >> call;
    
    if (end < start) end += 24;
    if ((start <= call && call <= end) || 
        (start <= call + 24 && call + 24 <= end)) {
        cout << "No\n";
    } else {
        cout << "Yes\n";
    }
    
    return 0;
}

B問題: 浮動小数点数の正規表示

標準入力で与えられた浮動小数点数をそのまま出力するだけの問題。C++のcoutは末尾の不要なゼロを自動的に削除してくれるため、特別なフォーマット処理は不要。

#include <iostream>
using namespace std;

int main() {
    double value;
    cin >> value;
    cout << value << endl;
    return 0;
}

C問題: 辞書順での組み合わせ探索

各桁について1から上限値までの数字を選択し、再帰的に全探索を行う。選択した数字の合計がKの倍数になる場合、その組み合わせを出力する。DFSによる深さ優先探索で、自然に辞書順の結果が得られる。

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

int N, K;
vector<int> limits, current;
int total = 0;

void search(int pos) {
    if (pos == N) {
        if (total % K == 0) {
            for (int num : current) cout << num << ' ';
            cout << '\n';
        }
        return;
    }
    
    for (int d = 1; d <= limits[pos]; ++d) {
        current[pos] = d;
        total += d;
        search(pos + 1);
        total -= d;
    }
}

int main() {
    cin >> N >> K;
    limits.resize(N);
    current.assign(N, 0);
    for (int i = 0; i < N; ++i) cin >> limits[i];
    
    search(0);
    return 0;
}

D問題: 円環上の区間和とモジュラスの活用

円環構造を扱うために、配列を2倍長に展開して線形化する手法を用いる。前半部分の累積和を計算し、後半部分に対して同じパターンを繰り返す。ここで、区間和がMの倍数となる条件は、累積和のモジュラスが等しいことと同値になる。

ハッシュテーブル（バケット）を使って、出現頻度を管理しながら走査。後ろから処理することで、自分自身との重複を避けつつ、対応するsの個数を効率的にカウントできる。

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

const int MAX = 200005;
long long A[2 * MAX], P[2 * MAX];
map<long long, int> bucket;
int N, M;

int main() {
    cin >> N >> M;
    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
        P[i] = (P[i-1] + A[i]) % M;
    }
    
    // 環状展開
    for (int i = N+1; i <= 2*N; ++i) {
        P[i] = (P[i-1] + A[i-N]) % M;
    }
    
    // 前半分の頻度を初期登録
    for (int i = 1; i <= N; ++i) {
        bucket[P[i]]++;
    }
    
    long long result = 0;
    for (int i = N+1; i <= 2*N; ++i) {
        bucket[P[i-N]]--;  // 古い要素を除外
        result += bucket[P[i]];  // 同じ余りを持つsの数を追加
        bucket[P[i]]++;  // 現在位置を登録
    }
    
    cout << result << endl;
    return 0;
}

E問題: パーミュテーションの倍増法によるシミュレーション

各位置に対する操作を2のべき乗回繰り返した結果を事前にテーブル化する。倍増法（ダブリング）によって、K回の操作をO(log K)でシミュレートできる。

具体的には、table[i][j] を位置iから2^j回操作後の位置として定義。クエリごとにKをビット分解し、立っているビットに対応する遷移を適用していく。

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

int main() {
    int n;
    long long k;
    cin >> n >> k;
    
    vector<vector<int>> jump(n+1, vector<int>(64));
    vector<int> values(n+1);
    
    for (int i = 1; i <= n; ++i) cin >> jump[i][0];
    for (int i = 1; i <= n; ++i) cin >> values[i];
    
    // 倍増テーブルの構築
    for (int b = 1; b < 64; ++b) {
        for (int i = 1; i <= n; ++i) {
            jump[i][b] = jump[jump[i][b-1]][b-1];
        }
    }
    
    // 各初期位置に対してk回操作後の値を求める
    for (int start = 1; start <= n; ++start) {
        int pos = start;
        for (int bit = 0; bit < 64; ++bit) {
            if (k & (1LL << bit)) {
                pos = jump[pos][bit];
            }
        }
        cout << values[pos] << ' ';
    }
    cout << endl;
    
    return 0;
}

F問題: 順列区間のハッシュによる一致判定

二つの配列の部分列が「同じ要素を持ち、順序も同一」かどうかを高速に判定する必要がある。単純な総和や二乗和では衝突が起きやすいので、ランダムな重み付けハッシュを用いる。

1〜Nの各整数をunsigned long long型の乱数にマッピングし、区間のハッシュ値としてその和と二乗和を保持。自然オーバーフローにより暗黙的に2^64で剰余を取ることで、効率的な計算が可能になる。

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

mt19937_64 rng(114514);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, q;
    cin >> n >> q;
    
    vector<unsigned long long> weight(n+1), 
                                hashA(n+1), sqA(n+1),
                                hashB(n+1), sqB(n+1);
    
    // ランダム重み生成
    for (int i = 1; i <= n; ++i) weight[i] = rng();
    
    // A配列の累積ハッシュ
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        hashA[i] = hashA[i-1] + weight[x];
        sqA[i] = sqA[i-1] + weight[x] * weight[x];
    }
    
    // B配列の累積ハッシュ
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        hashB[i] = hashB[i-1] + weight[x];
        sqB[i] = sqB[i-1] + weight[x] * weight[x];
    }
    
    while (q--) {
        int aL, aR, bL, bR;
        cin >> aL >> aR >> bL >> bR;
        
        bool same = (aR - aL == bR - bL) &&
                   (hashA[aR] - hashA[aL-1] == hashB[bR] - hashB[bL-1]) &&
                   (sqA[aR] - sqA[aL-1] == sqB[bR] - sqB[bL-1]);
                   
        cout << (same ? "Yes" : "No") << '\n';
    }
    
    return 0;
}