Atcoder解いてみた AtCoder Beginner Contest C - Reorder Cards

AtCoder Beginner Contest C - Reorder Cards

問題はこちら

回答

座標圧縮

#include <iostream>
#include <string>
#include <map>
#include <unordered_map>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <limits.h>
#include <bitset>
#include <list>
#include <set>
#include <numeric>
#include <tuple>
#include <iomanip>
#include <random>


long long H, W;
int N;
std::vector<std::pair<long long, int>> A;
std::vector<std::pair<long long, int>> B;

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

	std::cin >> H >> W >> N;

	for (int i = 0; i < N; i++) {
		long long a, b;
		std::cin >> a >> b;
		A.emplace_back(a, i);
		B.emplace_back(b, i);
	}

	std::sort(A.begin(), A.end());
	std::sort(B.begin(), B.end());

	// 階差の合計を求める
	std::vector<long long> diffAccumA(N+1);
	std::vector<long long> diffAccumB(N+1);

	long long tmpA;
	long long tmpB;

	tmpA = A[0].first - 0;
	tmpA--;
	diffAccumA[0] = tmpA;

	tmpB = B[0].first - 0;
	tmpB--;
	diffAccumB[0] = tmpB;


	for (int i = 1; i < N; i++) {
		long long tmpA = A[i].first - A[i - 1].first;

		if (tmpA > 0) {
			tmpA--;
		}

		diffAccumA[i] += (diffAccumA[i - 1] + tmpA);

		long long tmpB = B[i].first - B[i - 1].first;

		if (tmpB > 0) {
			tmpB--;
		}

		diffAccumB[i] += (diffAccumB[i - 1] + tmpB);
	}

	// 詰める
	std::vector<long long> ansA(N);
	std::vector<long long> ansB(N);

	for (int i = 0; i < N; i++) {
		ansA[A[i].second] = A[i].first - diffAccumA[i];
		ansB[B[i].second] = B[i].first - diffAccumB[i];
	}

	for (int i = 0; i < N; i++) {
		std::cout << ansA[i] << " " << ansB[i] << std::endl;
	}

	return 0;
}

以下、典型実装

パターン1 : std::unique + std::lower_bound（最も標準的な座標圧縮）

重複を削除した配列を作り、二分探索で「自分より小さい値が何種類あるか」を求める方法です。余計なソート用ペア構造体（std::pair）すら不要になります。

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    int H, W, N;
    std::cin >> H >> W >> N;

    std::vector<int> A(N), B(N);
    std::vector<int> valsA(N), valsB(N);

    for (int i = 0; i < N; i++) {
        std::cin >> A[i] >> B[i];
        valsA[i] = A[i];
        valsB[i] = B[i];
    }

    // 重複を削除して昇順に並べ替える
    std::sort(valsA.begin(), valsA.end());
    valsA.erase(std::unique(valsA.begin(), valsA.end()), valsA.end());

    std::sort(valsB.begin(), valsB.end());
    valsB.erase(std::unique(valsB.begin(), valsB.end()), valsB.end());

    // 各要素が何番目の値かを二分探索で求めて出力 (1-indexed なので + 1)
    for (int i = 0; i < N; i++) {
        int ansA = std::lower_bound(valsA.begin(), valsA.end(), A[i]) - valsA.begin() + 1;
        int ansB = std::lower_bound(valsB.begin(), valsB.end(), B[i]) - valsB.begin() + 1;
        std::cout << ansA << " " << ansB << "\n";
    }

    return 0;
}

補足
std::unique：重複要素を詰めて、不要になったエリアの先頭位置（イテレータ）を返す
valsA.erase：指定された不要エリアをメモリ上から実際に削除してサイズを縮小する

パターン2 : ソートして順に 1, 2, 3... と連番を振る

元コードの「ソートして処理する」という流れを汲みつつ、階差や引き算を使わずに「値が変わったらカウンターを +1 する」だけにしたシンプルな実装です。

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    int H, W, N;
    std::cin >> H >> W >> N;

    std::vector<std::pair<int, int>> A(N), B(N);
    for (int i = 0; i < N; i++) {
        std::cin >> A[i].first >> B[i].first;
        A[i].second = i;
        B[i].second = i;
    }

    std::sort(A.begin(), A.end());
    std::sort(B.begin(), B.end());

    std::vector<int> ansA(N), ansB(N);

    // 行方向の圧縮
    int rankA = 0;
    for (int i = 0; i < N; i++) {
        // 直前の値と異なるときだけランクを進める
        if (i == 0 || A[i].first != A[i - 1].first) {
            rankA++;
        }
        ansA[A[i].second] = rankA;
    }

    // 列方向の圧縮
    int rankB = 0;
    for (int i = 0; i < N; i++) {
        if (i == 0 || B[i].first != B[i - 1].first) {
            rankB++;
        }
        ansB[B[i].second] = rankB;
    }

    for (int i = 0; i < N; i++) {
        std::cout << ansA[i] << " " << ansB[i] << "\n";
    }

    return 0;
}