CODE FESTIVAL 2016 Final: D - Pair Cards

,

http://cf16-final-open.contest.atcoder.jp/tasks/codefestival_2016_final_d

solution

$X_i \bmod M$で分類して$a + b \equiv 0 \pmod{M}$な類の対$(a,b)$ごとに見る。$O(N)$。

各$k$ ($0 \le k \lt M$)について、余りが$k$になる整数の数$a_k = |\{ i \mid k \equiv X_i \pmod{M} \}|$、同じ整数のペアで余りが$k$なものの数$b_k = \sum_{y \equiv k \pmod{M}} \lfloor \frac{|\{ i \mid X_i = y \}|}{2} \rfloor$を求める。 そのような対の組$(a_k, b_k), (a_{M-k}, b_{M-k})$を取ると、$c = \lfloor \frac{\min \{ a_k, a_{M-k} \}}{2} \rfloor$として$n = c + \max \{ 0, b_k - c \} + \max \{ b_{M-k} - c \}$個の$2$枚組が取れる。同じ整数同士の$2$枚組に使えない整数から使うべき、同じ整数同士の$2$枚組にできても足して$M$な組を作って損しないことから、正当性はある程度信じることができる。$k = M-k$な場合は例外なことに注意しつつ足し合わせる。

implementation

#include <iostream>
#include <vector>
#include <map>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
int main() {
    // input
    int n, m; cin >> n >> m;
    map<int,int> xs;
    repeat (i,n) {
        int x; cin >> x;
        xs[x] += 1;
    }
    // compute
    vector<int> cnt(m), pr(m);
    for (auto it : xs) {
        int x, k; tie(x, k) = it;
        cnt[x % m] += k;
        pr [x % m] += k / 2 * 2;
    }
    int ans = 0;
    repeat (i,m) {
        int j = (m - i) % m;
        if (i == j) {
            ans += cnt[i] / 2;
        } else if (i < j) {
            int k = min(cnt[i], cnt[j]);
            ans += k;
            ans += min(cnt[i] - k, pr[i]) / 2;
            ans += min(cnt[j] - k, pr[j]) / 2;
        }
    }
    // output
    cout << ans << endl;
    return 0;
}