---
# System prepended metadata

title: '**[2021/01/19 TPC](https://codeforces.com/group/9f55GySeDA/contest/312924)**'

---

# **[2021/01/19 TPC](https://codeforces.com/group/9f55GySeDA/contest/312924)**
# **A. Hongcow Learns the Cyclic Shift**

問題文通りにシフトを全探索して, setで管理するだけ.

```cpp
set<string> T;
string S;
cin >> S;
rep(i, len(S)) {
    T.insert(S);
    S = S.substr(1, len(S) - 1) + S[0];
}
cout << len(T) << rt;
```

# **B. Hongcow Solves A Puzzle**

ごちゃごちゃ書いてあるけど結局長方形かどうか判定するだけ.

```cpp
ll N, M, l = INF, r = -1, u = -1, d = INF;
cin >> N >> M;
string S[N];
rep(i, N) cin >> S[i];
rep(i, N) rep(j, M) {
    if (S[i][j] == 'X') {
        chmin(d, i);
        chmax(u, i);
        chmin(l, j);
        chmax(r, j);
    }
}
inc(i, d, u) inc(j, l, r) if (S[i][j] != 'X') return puts("NO") & 0;
puts("YES");
```

# **C. Hongcow Builds A Nation**

連結成分をクリークにするだけ. 浮いている頂点は一番大きいところにまとめる.

```cpp
ll N, M, K, A, B;
cin >> N >> M >> K;
ll C[K];
UFS uf(N);
rep(i, K) cin >> C[i], C[i]--;
rep(i, M) cin >> A >> B, uf.unite(A - 1, B - 1);
ll res = 0, used[N], mx = -1, cnt = 0;
rep(i, N) used[i] = 0;
rep(i, K) {
    chmax(mx, uf.size(C[i]));
    res += uf.size(C[i]) * (uf.size(C[i]) - 1) / 2;
    used[uf.root(C[i])] = 1;
}
rep(i, N) if (used[uf.root(i)] != 1) cnt++;
cout << res + (mx + cnt) * (mx + cnt - 1) / 2 - mx * (mx - 1) / 2 - M << rt;
```

# **D. Hongcow's Game**

パズルゲー. $2^k$ の縦格子を作ると, いい感じに exclude j を計算できる.

```cpp
ll N;
cin >> N;

ll res1[10][1000], res2[10][1000], pw[10];
rep(i, 10) pw[i] = pow(2, i);
rep(i, 10) rep(j, N) res1[i][j] = res2[i][j] = INF;
vector<ll> A[10], B[10];
rep(i, 10) {
	rep(j, N) {
        if (j % (pw[i] * 2) < pw[i]) {
            A[i].pb(j + 1);
        } else {
            B[i].pb(j + 1);
        }
    }

    if (len(A[i])) {
        cout << len(A[i]) << endl;
    rep(j, len(A[i])) {
        cout << A[i][j];
        if (j == len(A[i]) - 1) cout << endl;
        else
            cout << sp;
        }
        rep(j, N) cin >> res1[i][j];
    }

    if (len(B[i])) {
    cout << len(B[i]) << endl;
    rep(j, len(B[i])) {
        cout << B[i][j];
        if (j == len(B[i]) - 1) cout << endl;
        else
        	cout << sp;
    }
    	rep(j, N) cin >> res2[i][j];
    }
}

ll res[N];
rep(i, N) res[i] = INF;
rep(i, N) {
	rep(j, 10) {
        ll f = 1;
        each(k, A[j]) if (k == i + 1) f = 0;
        if (f) chmin(res[i], res1[j][i]);
    }
    rep(j, 10) {
        ll f = 1;
        each(k, B[j]) if (k == i + 1) f = 0;
        if (f) chmin(res[i], res2[j][i]);
    }
}
cout << -1 << rt;
rep(i, N) {
    cout << res[i];
    if (i == N - 1) cout << endl;
    else
    	cout << sp;
}
```

# **E. Hongcow Buys a Deck of Cards**

BitDPできそうな形をしているが, よく見ると $10^7$ オーダーのコストをキーに持たないといけない. 或いはうまく半分前列挙できればそこそこ速いがそれでも定数倍の重い $10^9$ 程度の計算回数になってしまう. (ここまでコンテスト中の考察, 以降検索して出てきた中国語の解説ページを読んで) よく見ると, コストの改善分をキーにするとこれが $O(n^2)$ で全体で $O(2^nn^3)$ になり間に合う.