# AtCoder Beginner Contest 383 参加記
## 概要
2024/12/07 21:00 ~ 22:40 の AtCoder Beginner Contest 383 に参加した。
結果はノーペナ 6 完で、全体 347 位・国内 153 位（Rated 内 209 位・Rated 国内 60 位）だった。
## A - Humidifier 1 (150 点)
問題文の仰せのままに実装をする。$1$ 番目の例外処理を考えるのは嫌なので、$(T_0, V_0) = (0, 0)$ のような番兵を追加しておくと実装が多少楽になる。
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
int N; cin >> N;
vector<int> T(N + 1, 0), V(N + 1, 0);
for(int i = 1; i <= N; ++i){
cin >> T[i] >> V[i];
}
// 加湿器に残っている水の量
int water = 0;
for(int i = 1; i <= N; ++i){
// 前回水を入れた時刻からの経過時間だけ加湿器の水を減らす
// 水の量が負になることはないことに注意
water -= T[i] - T[i - 1];
if(water < 0){
water = 0;
}
// 加湿器に水を入れる
water += V[i];
}
cout << water << endl;
}
```
## B - Humidifier 2 (250 点)
制約が $H, W \le 10$ と非常に小さいので、何やっても許されそうな見た目をしている。
「加湿器を置く床の $2$ マス」を全探索する方針が考えられる。
この方針は「$1$ つ目の加湿器をどの床に置くか」 「$2$ つ目の加湿器をどの床に置くか」 「$2$ つの加湿器によって加湿される床は何マスあるか」という $3$ つをすべて探索する $\textrm{O}(H^3W^3)$ 方針だが、前述の通り制約が非常に小さいので $H^3W^3 \le 10^6$ となり余裕で間に合う。
本来は置く床 $2$ マスが同じマスの場合を弾くべきだが、同じマスに加湿器を置いた場合がただ一つの最適となるケースは存在しないので、実はそのような処理を書く必要はない。
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
int H, W, D; cin >> H >> W >> D;
vector<string> S(H);
for(int i = 0; i < H; ++i){
cin >> S[i];
}
// 加湿されたマスの最大値
int answer = 0;
for(int y1 = 0; y1 < H; ++y1){
for(int x1 = 0; x1 < W; ++x1){
// 1 つ目の加湿器を置く場所を全探索
if(S[y1][x1] == '#') continue;
for(int y2 = 0; y2 < H; ++y2){
for(int x2 = 0; x2 < W; ++x2){
// 2 つ目の加湿器を置く場所を全探索
if(S[y2][x2] == '#') continue;
// 加湿器を置いたときに加湿されたマスの数
int humidified = 0;
for(int i = 0; i < H; ++i){
for(int j = 0; j < W; ++j){
if(S[i][j] == '#') continue;
// 加湿される条件はマンハッタン距離が D 以下であること
if(abs(i - y1) + abs(j - x1) <= D or
abs(i - y2) + abs(j - x2) <= D){
++humidified;
}
}
}
// 答えの更新
if(humidified > answer){
answer = humidified;
}
}
}
}
}
cout << answer << endl;
}
```
## C - Humidifier 3 (350 点)
私は嘘解法で通しましたの札
## D - 9 Divisors (400 点)
約数の個数と書いてあるので、約数の個数の公式を思い浮かべると、$N$ 以下の正整数 $X$ が正の約数を $9$ 個もつことは、異なる素数 $p, q$ を用いて $X = p^8$ あるいは $X = p^2 q^2$ と表されることが分かる。
$p^2 q^2$ のケースについて考える。ここで $p < q$ として一般性を失わない。$N \le 4 \times 10^{12}$ より、$q^2 < 10^{12}$ となるから $q < 10^6$ である。従って、$10^6$ 以下の素数をすべて列挙しておけばよさそうである。これはエラトステネスの篩を用いることで $\textrm{O}(n \log \log n)$ で列挙することが可能である。
さらに、$p^2 q^2 \le N$ ということは $\displaystyle p^2 \le \left\lfloor \frac{N}{q^2} \right\rfloor$ である。これと $2 \le p < q < \sqrt{N}$ から $4 \le p^2 < q^2 < N$ と合わせることにより、列挙した素数の昇順に二分探索していけばある素数 $q$ に対して $p^2 q^2 \le N$ を満たす素数 $p < q$ の個数を求めることが出来そうである。
$p^8$ のケースについては、先に列挙した素数に対して実際に計算して確かめればよい。$N \le 4 \times 10^{12}$ より、$p < 100$ という適当な範囲のみ調べれば十分である。（この範囲であれば 64 bit 整数を用いることでオーバーフローを考慮する必要もない）
以上より前計算 $\textrm{O}(\sqrt{N} \log \log N)$ で素数を列挙し、素数の個数が $\displaystyle M := \textrm{O}\left( \frac{N}{\log N} \right)$ 個であることから二分探索パートが $\textrm{O}\left(M \log M\right)$ で終わる。
```cpp=
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
ll N; cin >> N;
// エラトステネスの篩を用いて P = 10^6 以下の素数を列挙(少しゆとりを持たせている)
const ll P = 1000010;
vector<bool> sieve(P, true);
sieve[0] = sieve[1] = false;
// 素数の二乗値の配列
vector<ll> prime;
ll answer = 0;
for(ll q = 2; q < P; ++q){
if(!sieve[q]) continue;
// 二分探索を用いて p^2 q^2 > N を満たす最小の p^2 を求める。
// 実際には配列の先頭からの距離が条件を満たす p の個数なので、それを足す。
ll p = N / (q * q);
answer += distance(prime.begin(), upper_bound(prime.begin(), prime.end(), p));
// q が小さいとき、8 乗の値が N 以下であるかも調べる。
if(q < 100 and q * q * q * q * q * q * q * q <= N){
answer += 1;
}
// 篩と素数の二乗値の配列の更新
prime.push_back(q * q);
for(ll r = q + q; r < P; r += q){
sieve[r] = false;
}
}
cout << answer << endl;
}
```
## E - Sum of Max Matching (500 点)
パスの重み、および $f(x, y)$ について観察すると、「ある頂点 $x, y$ に対して $f(x, y) = w$ である」ということは「ある頂点 $x, y$ は重み $w$ **以下**の辺から成る部分グラフでは連結だが、重み $w$ **未満**の辺から成る部分グラフでは連結ではない」と言い換えることができる。さらにこれは「ある頂点 $x, y$ は重み $w$ **未満**の辺から成る部分グラフに重み $w$ の辺を加えたとき初めて連結になる」と言い換えることができ、ここまで言い換えると最小全域木を求めるクラスカル法の考えが応用できそうだと考えることができる。
この問題は頂点集合 $A$ に対して頂点集合 $B$ を自由に対応させて、$\displaystyle \sum_{i = 1}^K f(A_i, B_i)$ の値を最小化することが目的であった。ここで、ある $2$ つの連結成分 $X, Y$ があり、頂点 $a \in A$ が $X$ に、頂点 $b \in B$ が $Y$ に属していると仮定する。今、$X, Y$ が重み $w$ の辺によって連結となったとき、頂点 $a, b$ はマッチングさせるべきかを考えると、これは貪欲にマッチングさせるべきだということが分かる。仮にマッチングさせず、頂点 $a, b$ をそれぞれある連結成分 $Z$ とそこに属する頂点 $a^\prime \in A, b^\prime \in B$ と重み $w^\prime \ge w$ の辺を加えた際にマッチングさせたとしても $\displaystyle \sum_{i = 1}^K f(A_i, B_i)$ の値は減ることがないからである。
結局、この問題は次の処理を行うことで解くことができる。
1. Union Find を用いて $N$ 頂点 $0$ 辺の無向グラフを用意する。
2. $w_i$ の昇順に次の一連の処理を行う。
1. $u_i$ と $v_i$ が属する連結成分を求め、それらが同一の連結成分に属する場合は何もしない。
2. 連結成分 $X$ に含まれる頂点 $a \in A, b \in B$ の数をそれぞれ $A(X), B(X)$ と置く。このとき頂点 $u_i, v_i$ が属している連結成分 $U, V$ を併合したときに新たに作れるマッチングの個数は $M = \min (A(U) + A(V), B(U) + B(V))$ である。
3. $M \times w_i$ を答えに加算し、$U, V$ を併合させる。
```cpp=
#include <bits/stdc++.h>
using namespace std;
#include <atcoder/dsu>
using namespace atcoder;
using ll = long long;
int main(){
int N, M, K; cin >> N >> M >> K;
vector<tuple<ll, int, int>> edge(M);
for(int i = 0; i < M; ++i){
ll u, v, w; cin >> u >> v >> w;
edge[i] = {w, u, v};
}
sort(edge.begin(), edge.end());
vector<ll> cnt_A(N + 1, 0), cnt_B(N + 1, 0);
for(int i = 0; i < K; ++i){
int A; cin >> A;
++cnt_A[A];
}
for(int i = 0; i < K; ++i){
int B; cin >> B;
++cnt_B[B];
}
dsu uf(N + 1);
ll answer = 0;
for(auto [w, u, v] : edge){
// 頂点 u, v が属する連結成分を求める。
u = uf.leader(u), v = uf.leader(v);
if(u == v) continue;
// マッチングを作れるだけ作る
ll ua = cnt_A[u], ub = cnt_B[u];
ll va = cnt_A[v], vb = cnt_B[v];
ll M = min(ua + va, ub + vb);
answer += w * M;
// 併合してできた新しい連結成分に情報をマージする
int t = uf.merge(u, v);
cnt_A[t] = ua + va - M;
cnt_B[t] = ub + vb - M;
}
cout << answer << endl;
}
```
## F - Diversity (525 点)
色に関する条件がない場合、これは典型的な 0-1 ナップザック問題になる。というわけで、これを応用させることを考える。
次のような素直な DP を考えてみる。
$\textrm{DP}(i, j, k) := i$ 番目までの品物のうち、$j$ 色の品物を買って、合計金額が $k$ 円となるような買い方のうち、最も大きな満足度の値（不可能なら $-\infty$ ）
これをそのまま実装しても $\textrm{O}(N^2X)$ となるので、実行時間制限に間に合わせることができない。そのため、添え字を削ることを考える。この中で削れそうなのは $j$ なので、詳しく考察してみる。
品物を色ごとにまとめてみる。すると、同じ色の中では単純なナップザック問題を解いておき、それを基に DP をすればよいということが浮かぶ。実際この方法は上手くいって、詳しくは実装例参考（書くの疲れた）
```cpp=
#line 1 "code.cpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
ll N, X, K; cin >> N >> X >> K;
// 色ごとにまとめた商品の (価格, 効用) のリスト
vector<vector<pair<int, ll>>> color(N + 1);
for(int i = 0; i < N; ++i){
ll P, U, C; cin >> P >> U >> C;
color[C].push_back({P, U});
}
ll inf = -1;
// dp[f][j] := 色 i の品物を買った/買っていない(f)とき、
// 価格が j 円となるような買い方の満足度の最大値
vector dp(2, vector(X + 1, inf));
dp[0][0] = 0;
for(int i = 1; i <= N; ++i){
if(color[i].empty()) continue;
fill(dp[1].begin(), dp[1].end(), inf);
for(auto [P, U] : color[i]){
for(int j = X; j >= P; --j){
if(dp[0][j - P] != inf){
dp[1][j] = max(dp[1][j], dp[0][j - P] + U + K);
}
if(dp[1][j - P] != inf){
dp[1][j] = max(dp[1][j], dp[1][j - P] + U);
}
}
}
for(int j = 0; j <= X; ++j){
dp[0][j] = max(dp[0][j], dp[1][j]);
}
}
cout << *max_element(dp[0].begin(), dp[0].end()) << endl;
}
```
Sign in with Wallet
Connect another wallet