競プロ日記#25/06/03 + #25/06/05

AtCoder

AtCoder Beginner Contest 393

C - Make it Simple

• 単純グラフの定義→自己ループと多重辺
• あとはシンプルにmapで数え上げ

AtCoder Beginner Contest 392

C - Bib

• mapをひたすら使って実装するだけ。
• 最初誰が誰を見ているかの関係をグラフで管理しようとしてしまったのと問題設定がややこしくて頭がこんがらがったが、一つ一つコメントアウトを活用して「何を管理しているmapか」という情報を整理すれば問題なく実装できた。

int main() {
    long long N;
    cin >> N;
    // vector<long long> G[100009];
    
    long long P[N + 1];
    long long Q[N + 1];
    P[0] = 0;
    Q[0] = 0;
    for (long long i = 1; i <= N; i++) {
        cin >> P[i];
    }
    for (long long i = 1; i <= N; i++) {
        cin >> Q[i];
    }
    map<long long, long long> H; // 人iがどのゼッケンをつけているか
    for (long long i = 1; i <= N; i++) {
        H[i] = Q[i];
    }

    map<long long, long long> R; // ゼッケンiをつけている人は誰か
    for (long long i = 1; i <= N; i++) {
        R[Q[i]] = H[i];
    }

    map<long long, long long> G; // 人iが見つめている人は誰か
    for (long long i = 1; i <= N; i++) {
        G[Q[i]] = P[i];
    }

    for (long long i = 1; i <= N; i++) {
        if (i > 1) {
            cout << " ";
        }
        cout << H[G[R[i]]]; // ゼッケンiを付けている人が見つめている人が付けているゼッケン
    }
}

• ちなみに解説では二行のfor文だけで答えを出していて草だった

AtCoder Beginner Contest 408

C - Not All Covered

• 記憶に新しいimos法
• 流石に解けた
• 問題には関係ないがやはり最新から近いコンテストだとaccのテストが機能していない可能性がある（仕方ないのでコードテストでテストした）

int main() {
    long long N,M;
    cin >> N >> M;
    long long dif[1000009];
    long long sum[1000009];
    dif[0] = 0;
    sum[0] = 0;
    for (long long i = 1;i <= M;i++){
        long long L,R;
        cin >> L >> R;
        dif[L]++;
        if (R < N) {
            dif[R + 1]--;
        }
    }

    long long min = LLONG_MAX;
    for (long long i = 1;i <= N;i++){
        sum[i] = sum[i - 1] + dif[i];
    }

    for (long long i = 1;i <= N;i++){
        if (sum[i] < min) {
            
            min = sum[i];
        }
    }
    if (min < 0) {
        cout << 0 << endl;
        return 0;
    }
    
    cout << min << endl;

}