C - Boats Competition

cpcodeforcesdiv3greedyexhaustive search

最終更新日

問題

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

問題文

nn 人の人がいて、それぞれの体重は wiw_i

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

最大で何ペア作れる?

制約

サンプル

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

考察

1win1 \le w_i \le n という制約に加えて、 nn が小さいことから、全探索してシミュレーションしても間に合う。
具体的には、 ss11 から 2n2 n まで全探索したときに、相異なる i,ji, j に対して ai+aj=sa_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;
}