ABC 412
Table of Contents
https://atcoder.jp/contests/abc412
A. Task Failed Successfully
https://atcoder.jp/contests/abc412/tasks/abc412_a
B. Precondition
https://atcoder.jp/contests/abc412/tasks/abc412_b
C. Giant Domino
https://atcoder.jp/contests/abc412/tasks/abc412_c
できるだけ大きいドミノを選ぶのが最適。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
auto cal = []() -> void {
int N;
cin >> N;
vll S(N);
rep(i, N) cin >> S[i];
ll st = S[0], fin = S[N - 1];
S.erase(S.begin(), S.begin() + 1);
S.pop_back();
sort(all(S));
S.push_back(INF);
ll ans = 2;
ll pr = st;
rep(i, (ll)S.size() - 1) {
if (S[i] <= pr) continue;
if (fin <= pr * 2) break;
if (S[i] <= pr * 2 && S[i + 1] > pr * 2) {
pr = S[i];
ans++;
}
}
if (fin > pr * 2) ans = -1;
cout << ans << '\n';
};
int T;
cin >> T;
rep(i, T) {
cal();
}
}
upper_bound を使うバージョン
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
auto cal = []() -> void {
int N;
cin >> N;
vll S(N);
rep(i, N) cin >> S[i];
ll st = S[0], fin = S[N - 1];
if (fin <= st * 2) {
cout << 2 << endl;
return;
}
vll ssub;
rep2(i, 1, N - 1) {
ssub.push_back(S[i]);
}
sort(all(ssub));
ll ans = 2;
ll pr = st;
while (true) {
if (fin <= pr * 2) break;
auto it = upper_bound(all(ssub), pr * 2);
if (it == ssub.begin()) break;
it = prev(it);
if (*it <= pr) break;
if (*it <= pr * 2) {
pr = *it;
ans++;
} else {
break;
}
}
if (fin > pr * 2) ans = -1;
cout << ans << endl;
};
int T;
cin >> T;
rep(i, T) {
cal();
}
}
D. Make 2-Regular Graph
https://atcoder.jp/contests/abc412/tasks/abc412_d
全ての頂点の次数が2であるようなグラフを全探索して、そのグラフにするために必要なコストを計算し、そのうち最小となるものを求める。 問題は条件を満たすグラフを全列挙する部分だが $1, 2, \cdots, N$ の順列を $P_1, P_2, \cdots, P_N$ としたとき、 $i, P_i$ 間に無向辺を張れば頂点の次数をたかだか 2 にすることができることに気づいた。 ただし $i = P_i$ の場合は次数 1 の頂点ができてしまうのでそのような場合は除外する。 $N \leq 8$ より全探索しても $8! = 40,320$ 通りしかないので十分に間に合う。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N, M;
cin >> N >> M;
vvint grid(N, vint(N));
rep(i, M) {
int a, b;
cin >> a >> b;
a--, b--;
grid[a][b] = grid[b][a] = 1;
}
ll ans = INF;
vint v(N);
iota(all(v), 0);
do {
vector<set<int>> graph(N);
rep(i, N) {
graph[i].insert(v[i]);
graph[v[i]].insert(i);
}
int ok = 1;
rep(i, N) {
if (graph[i].size() != 2) ok = 0;
}
if (!ok) continue;
vvint tmp(N, vint(N));
rep(i, N) {
for (int nx : graph[i]) {
tmp[i][nx] = 1;
}
}
ll cnt = 0;
rep(i, N) rep2(j, i + 1, N) {
if (grid[i][j] != tmp[i][j]) cnt++;
}
chmin(ans, cnt);
} while (next_permutation(all(v)));
cout << ans << endl;
}
解説読んで理解した別解。全ての頂点の次数が2であるとき、グラフはいくつかのサイクルに分解される。 このとき、連結成分の数に関わらず辺の数は $N$ である。 単純グラフにおける辺の数は最大で $N(N-1)/2$ であり、この後 $N$ 本を選んでくれば条件を満たすグラフの候補を全て列挙できる。 この中にサイクルにならないものもあるがそれは無視する。 $N(N-1)/2$ 本から $N$ 本を選ぶ組み合わせは $\binom{N(N-1)/2}{N}$ 通りである。 今回の問題では $N \leq 8$ なので最大でも $\binom{8\cdot7/2}{8} = \binom{28}{8} = 3,108,105$ 通りであり、十分に間に合う。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N, M;
cin >> N >> M;
vvint grid(N, vint(N));
rep(i, M) {
int a, b;
cin >> a >> b;
a--, b--;
grid[a][b] = grid[b][a] = 1;
}
using P = pair<int, int>;
vector<P> es;
rep(i, N) rep2(j, i + 1, N) es.push_back({i, j});
ll ans = INF;
int m = N * (N - 1) / 2;
auto judge = [&](int used) -> void {
vector<P> edges;
rep(i, m) {
if (used >> i & 1) edges.push_back(es[i]);
}
vector tmp(N, vint(N));
for (auto [u, v] : edges) {
tmp[u][v] = 1;
tmp[v][u] = 1;
}
// 全ての頂点の次数が 2 であるか確認
rep(i, N) {
ll deg = 0;
rep(j, N) {
deg += tmp[i][j];
}
if (deg != 2) return;
}
ll sum = 0;
rep(i, N) rep2(j, i + 1, N) {
if (grid[i][j] != tmp[i][j]) sum++;
}
chmin(ans, sum);
return;
};
// N(N-1)/2 本の辺から N 本を選ぶ組み合わせを全探索
auto dfs = [&](auto dfs, int used) -> void {
if (__builtin_popcount(used) == N) {
judge(used);
return;
}
int s = -1;
rep(i, m) {
if (used >> i & 1) s = i;
}
s++;
rep2(i, s, m) {
dfs(dfs, used | (1 << i));
}
};
dfs(dfs, 0);
cout << ans << endl;
}
E. LCM Sequence
https://atcoder.jp/contests/abc412/tasks/abc412_e
解説 AC.
種類が増えるのは素冪(単一の素数の冪)のときである。よって $L+1 \sim R$ に含まれる素冪の個数 +1 (+1 は L 分) を求めれば良い。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll L, R;
cin >> L >> R;
// L+1 ~ R にある素冪の個数を数える
L++;
ll W = R - L + 1;
vll x(W), cnt(W);
rep(i, W) {
x[i] = L + i;
}
int M = 1e7;
vector<bool> isprime(M, true);
isprime[0] = isprime[1] = false;
rep2(i, 2, M) {
if (!isprime[i]) continue;
for (int j = i + i; j < M; j += i) {
isprime[j] = false;
}
// (L+i-1)/i * i = (L を超える最小の i の倍数)
for (ll j = (L + i - 1) / i * i; j <= R; j += i) {
while (x[j - L] % i == 0) x[j - L] /= i;
cnt[j - L]++; // j の値が何個の素数で構成されるかカウント
}
}
ll ans = 1; // L 分を含むので初期値は 1
// L+1 ~ R の素冪の個数を数える
rep(i, W) {
if (x[i] != 1) cnt[i]++; // x[i] = 1 => x[i] は素数
if (cnt[i] == 1) ans++; // 1種類の素数だけからなる => 素冪
}
cout << ans << endl;
}
F. Socks 4
https://atcoder.jp/contests/abc412/tasks/abc412_f