C - Boats Competition

問題

https://codeforces.com/contest/1399/problem/C (新しいタブで開く)

問題文

$n$ 人の人がいて、それぞれの体重は $w_i$ 。

ある $s$ に対して、 $a_i + a_j = s$ となるようにペアを作る。
ただし、 $i \ne j$ で、 1 人の人は 1 つのペアにしか入れない。

最大で何ペア作れる？

制約

• $1 \le t \le 1000$
• $1 \le n \le 50$
• $1 \le w_i \le n$

サンプル

5
5
1 2 3 4 5
8
6 6 6 6 6 6 8 8
8
1 2 2 1 2 1 1 2
3
1 3 3
6
1 1 3 4 2 2

2
3
4
1
2

考察

$1 \le w_i \le n$ という制約に加えて、 $n$ が小さいことから、全探索してシミュレーションしても間に合う。
具体的には、 $s$ を $1$ から $2 n$ まで全探索したときに、相異なる $i, j$ に対して $a_i + a_j = s$ となるペアがいくつ作れるかを数えればいい。

コード

https://codeforces.com/contest/1399/submission/126144846 (新しいタブで開く)

void solve() {
  int n;
  cin >> n;
  vector<int> w(n);
  rep(i, n) cin >> w[i];
  int ans = 0;
  rep(s, 2 * n) {
    int tmpa = 0;
    set<int> used;
    for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
        if (s + 1 == w[i] + w[j] && !used.count(i) && !used.count(j)) {
          tmpa++;
          used.insert(i);
          used.insert(j);
        }
      }
    }
    ans = max(ans, tmpa);
  }
  cout << ans << endl;
}