B. Hyperset (Codeforces Round #612 Div. 2)

問題

https://codeforces.com/contest/1287/problem/B

問題概要

'S', 'E', 'T' で構成された長さkの文字列がn個与えられる。

n個のうち3個を取ってきた時、1番目からk番目の文字すべてについて以下のいずれかの条件を満たす組み合わせはいくつあるか？

• 3文字とも同じである
• 3文字とも異なる

解説

2つ目までの文字列を確定させると、3つ目の文字列は一意に定まります。2つの文字が同じである場合、3つ目の文字も同じでなければならず、2つの文字が異なる場合、3つ目の文字はまだ現れていないもう一種の文字でなければならないからです。

ここで、3重ループで全探索するとTLEしてしまいます。なので、各文字列が何度現れるかをあらかじめmapで保持しておいて、2重ループで2つ目までの文字列を全探索し、そこから一意に定まる文字列がいくつあるかをmapから検索すれば計算量を落とすことができます。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n, k;
    cin >> n >> k;
    vector<string> s(n);
    map<string, int> mp;
    for (int i = 0; i < n; i++) {
        cin >> s[i];
        mp[s[i]]++;
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            string t;
            for (int l = 0; l < k; l++) {
                if (s[i][l] == s[j][l]) {
                    t += s[i][l];
                } else if (s[i][l] != 'S' && s[j][l] != 'S') {
                    t += 'S';
                } else if (s[i][l] != 'E' && s[j][l] != 'E') {
                    t += 'E';
                } else if (s[i][l] != 'T' && s[j][l] != 'T') {
                    t += 'T';
                }
            }
            ans += mp[t];
        }
    }
    cout << ans / 3 << endl; 
}

別解（私の実戦解）

mapに個数を保持する方針は変わらないのですが、2つ目までを全探索、ではなく、重複を省いてmapに保持されている文字列の個数分だけループを回し、それぞれの個数を掛け算します。

この方がループ回数が少なくなるのですが、一つ問題があって、同じ文字列が3個以上ある時に、その組み合わせを拾うことができないため、別途数え上げをする必要が生じます。 このケースでは、同じ文字列がx (x >= 3)ある時、x個の中から3つを選択する組み合わせでxCx-3個となります。組み合わせの計算は、制約が小さいのでパスカルの三角形で求めてかまいません。

Submission #68264262 - Codeforces