PAST12 (第12回アルゴリズム実技検定) 解説

アルゴリズム実技検定(PAST)の第12回の解法の紹介です

URL：https://atcoder.jp/contests/past202209-open

A - 信号機/Traffic Light
B - クレジット/Credits
C - 偏ったサイコロ/Biased Dice
D - 採点 / Marking
E - 棒倒しゲーム/Hitting Stick Game
F - 薬剤師 / Pharmacist
G - Wildcards
H - ３種の硬貨/Three Types of Coins
I - 毎日のリンゴ / Buying Apple Everyday
J - スプリンクラー/Sprinkler
K - 連結チェック/Checking Connectivity
L - 展覧会 / Exhibition
M - シリーズ / series
N - 上からと横から/From Above and From the Side
O - ２個のボール/Pick Two Numbers

A - 信号機/Traffic Light

問題文が読みにくいけど、頑張って読み解いて実装する

提出コード：https://atcoder.jp/contests/past202209-open/submissions/39327282

int main(){
  int x,y,z;
  cin >> x >> y >> z;
  cout << max(y, x + z) << "\n";
}

B - クレジット/Credits

$N$ が最大で500000桁くらいあるので、整数では受け取れない

100で割って切り捨て → 1,2桁を消すと同じなので文字列でそれを行う

サンプルのケースにもあるように1~2桁の時に0を出力しないといけないということに注意して実装する

提出コード：https://atcoder.jp/contests/past202209-open/submissions/39327302

int main(){
  string s;
  cin >> s;
  rep(i, 2) if(!s.empty()) s.pop_back();
  if(s.empty()) cout << "0\n";
  else cout << s << "\n";
}

C - 偏ったサイコロ/Biased Dice

サイコロを振る数が3回なのでfor3重ループで全探索できる

ans[i]=サイコロの目の合計がiの時の確率として答えを求めていけばよさそう

誤差が怖いので、整数で計算してから最後に $100^{3}$ で割ることにする

提出コード：https://atcoder.jp/contests/past202209-open/submissions/39327358

int main(){
  constexpr int n = 6;
  vvi p(3, vi(n));
  rep(i, 3) rep(j, n) cin >> p[i][j];
  vi ans(18 + 1);
  rep(i, n) rep(j, n) rep(k, n){
    ans[i+j+k+3] += p[0][i] * p[1][j] * p[2][k];
  }
  for(int i = 1; i <= 18; i++) printf("%.10lf\n", ans[i] / 1000000.0);
}

D - 採点 / Marking

多重辺があるか、自己ループがあるか、頂点の番号がおかしくないかを毎回確認すればいいので

自己ループ： $u,v$ が同じ値のものがあるかどうか
頂点の番号の確認： $u,v$ が $N$ を超えていないかどうか
多重辺：ほかに同じ $u,v(u\lt v)$ の辺が存在するかどうかをstd::setを使って確認

を辺を追加していくごとに確認していけばいい

提出コード：https://atcoder.jp/contests/past202209-open/submissions/39327394

void ng(){
  cout << "No\n";
  exit(0);
}
int main(){
  int n,m;
  cin >> n >> m;
  set<pair<int,int>> cnt;
  rep(i, m){
    int a,b;
    cin >> a >> b;
    a--; b--;
    if(a > b) swap(a, b);
    if(a >= n || b >= n || a == b || cnt.count({ a, b })) ng();
    cnt.insert({ a, b });
  }
  cout << "Yes\n";
}

E - 棒倒しゲーム/Hitting Stick Game

ラウンドが途中で終了するなら、合計が $N$ になっていなければいけない
$M$ 回行ってスコアが $N$ 以下であれば、そこでそのラウンドが終了する
合計で $R$ ラウンド行われている

の条件を満たしているかを調べればいい

最後、ゲームの途中で急に終わっていないかなどのチェックも忘れずにやる

提出コード：https://atcoder.jp/contests/past202209-open/submissions/39327487

void ng(){
  cout << "No\n";
  exit(0);
}
int main(){
  int r,n,m,l;
  cin >> r >> n >> m >> l;
  vector<int> s(l);
  rep(i, l) cin >> s[i];
  int tot = 0, num = 0, cnt = 0;
  rep(i, l){
    tot += s[i];
    cnt++;
    if(tot > n || cnt > m) ng();
    if(tot == n || cnt == m){
      tot = cnt = 0;
      num++;
    }
  }
  if(tot || cnt || num != r) ng();
  cout << "Yes\n";
}

F - 薬剤師 / Pharmacist

各人が持っているアレルギーの種類の合計は $2\times10^{5}$ 以下なので、 $N$ 個の薬それぞれについて $O(D_i)$ で薬を与えられるか判定すればいい

$N$ 個ある薬それぞれに、特定のアレルゲンが含まれているかどうかを $O(1)$ で管理できるようにすれば間に合いそう(提出コードのcntにあたる部分)

計算量は $O(\sum_i C_i + N\sum_i D_i)$

提出コード：https://atcoder.jp/contests/past202209-open/submissions/39327642

int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  vector<bitset<200010>> cnt(n);
  rep(i, n){
    int c; cin >> c;
    rep(j, c){
      int x; cin >> x;
      cnt[i][x] = 1;
    }
  }
  int q;
  cin >> q;
  rep(_, q){
    int d; cin >> d;
    vector<int> y(d);
    rep(i, d) cin >> y[i];
    int mx = 0, idx = -1-1;
    rep(i, n){
      bool ok = true;
      rep(j, d) if(cnt[i][y[j]]){
        ok = false; break;
      }
      if(ok && chmax(mx, a[i])) idx = i;
    }
    cout << idx+1 << "\n";
  }
}

G - Wildcards

制約的に?の位置は全探索できそう

bit全探索を使ってbitが1になっている数(popcount)が $K$ の時だけ調べるようにして、 $T$ を $N$ 個の文字のどれかにして全探索する

計算量は $O(_NC_KLN^{2})$ 。だいたい $2\times10^{9}$ になるけどたぶんC++だと間に合う(C++で提出すると642[ms]だった)

もう少し高速化を考えると、?になる部分を除いた文字列の中で一番多く重複している文字列の数を求めればいいのでmapを使えば $O(CLN\log N)$ で解ける。だいたい $2\times10^{7}$ くらい。公式解説に書かれている解法です

下のソースコードは遅いほうで書かれてます

提出コード：https://atcoder.jp/contests/past202209-open/submissions/39327743

int main(){
  int n,l,K;
  cin >> n >> l >> K;
  vector<string> s(n);
  rep(i, n) cin >> s[i];
  int ans = 0;
  rep(i, 1 << l) if(__builtin_popcount(i) == K){
    rep(j, n){
      int num = 0;
      rep(k, n){
        bool ok = true;
        rep(p, l) if(!(i >> p & 1) && s[j][p] != s[k][p]){
          ok = false; break;
        }
        num += ok;
      }
      chmax(ans, num);
    }
  }
  cout << ans << "\n";
}

H - ３種の硬貨/Three Types of Coins

銅貨より銀貨、銀貨よりも金貨の価値が飛びぬけて高いので、まず金貨を最大化していき、その次に銀貨をなるべく使わないようにするのが一番最適になりそう

袋と銅貨の枚数の2つの状態を持つ動的計画法を考えてみる

$dp[i][j] =$ 袋 $i$ まで見て、銅貨が残り $j$ 枚の時、金貨の枚数を最大化して銀貨をなるべく残したときの金貨,銀貨の枚数

std::pairを使うと比較したときにfirst, secondの順に優先的に並べられるのでこれを使ってfirstに金貨の枚数、secondに(-銀貨の枚数)を入れるといい感じにできる

初期状態は $dp[0][X]=\{0,0\}$ 、ほかはすべて $\{-\infty,-\infty\}$ にする

遷移は袋を買うか買わないかの2通りを考えればいい

下の実装では1次元配列にしてメモリの削減をしてます

提出コード：https://atcoder.jp/contests/past202209-open/submissions/39328031

int main(){
  int n,x;
  cin >> n >> x;
  vector<int> a(n), b(n), c(n);
  rep(i, n) cin >> a[i] >> b[i] >> c[i];
  // dp[i][j]: 袋iまで見て、銅貨が残りj枚の時の{金貨,銀貨}の枚数の最大値
  vector<pair<int,int>> dp(x + 1, { -mod, -mod });
  dp[x] = { 0, 0 };
  rep(i, n){
    auto nxt = dp;
    for(int j = x; j >= b[i]; j--){
      pair<int,int> v(dp[j].first + c[i], dp[j].second - a[i]);
      chmax(nxt[j - b[i]], v);
    }
    swap(dp, nxt);
  }
  int k = -1, g = mod, d = -1;
  rep(i, x+1){
    if(chmax(k, dp[i].first)){
      g = -dp[i].second;
      d = i;
    }else if(k == dp[i].first){
      if(chmin(g, -dp[i].second)){
        d = i;
      }else if(g == -dp[i].second){
        chmax(d, i);
      }
    }
  }
  cout << k << " " << 1000000000-g << " " << d << "\n";
}

I - 毎日のリンゴ / Buying Apple Everyday

商品券の枚数 $k$ は $\mathrm{ceil}\left(\frac{Ai}{M}\right) = \mathrm{floor}\left(\frac{Ai+M-1}{M}\right)$ で表せる

$N$ 日間リンゴを買うのは確定しているので商品券の部分だけを考えると、 $\sum_{i=1}^N {\mathrm{floor}\left(\frac{Ai+M-1}{M}\right)}$ を求めたい

これはfloor sumを使えば高速に解ける

floor sum：https://judge.yosupo.jp/problem/sum_of_floor_of_linear
- この問題でいう $N,M,A,B$ を $N+1, M, A, M-1$ にすればいい

提出コード：https://atcoder.jp/contests/past202209-open/submissions/39328179

void solve(){
  int n,a,m;
  cin >> n >> a >> m;
  // sum M*((Ai+M-1)/M)-Ai
  ll v = (ll)n * (n+1) / 2 * a;
  ll vv = floor_sum(n+1, m, a, m-1) - floor_sum(1, m, a, m-1);
  cout << vv*m - v << "\n";
}
int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int t;
  cin >> t;
  rep(i, t) solve();
}

J - スプリンクラー/Sprinkler

幾何は苦手なのでライブラリに頼ります(https://ei1333.github.io/luzhiled/snippets/geometry/template.html)
- ここの関数Real area(const Polygon &p, const Circle &c)を使うと楽に解ける

円の中心を長方形の中心に置いたときが一番大きい面積になるので、ライブラリの円と多角形の共通部分の面積を求めるものを使うと解ける

提出コード：https://atcoder.jp/contests/past202209-open/submissions/39350450

int main(){
  double h,w,d;
  cin >> h >> w >> d;
  Polygon p{ {0,0}, {w,0}, {w,h}, {0,h} };
  Circle c({ w/2, h/2 }, d);
  printf("%.10lf\n", area(p, c) / h / w);
}

K - 連結チェック/Checking Connectivity

連結判定の問題 → UnionFindを使う

UnionFindは追加が得意で消去は苦手なのに対して、今回の問題は辺の追加クエリが少なく(最大で10個)、辺の消去クエリが多い

クエリを逆向きに処理するということを考えるとUnionFindが得意な形に持っていくことができる

クエリを逆で見たとき、UnionFindでの消去は高々10回しか実行しないので、消去したい辺以外をもう一度すべて結び直せばいい

クエリの最後から始めるのでどの辺が張られていて張られていないのかを気を付けて確認しながら実装する

実装で辺の管理はstd::setを使った

提出コード：https://atcoder.jp/contests/past202209-open/submissions/39328625

int main(){
  int n,m;
  cin >> n >> m;
  set<pair<int,int>> cnt;
  rep(i, m){
    int a,b;
    cin >> a >> b;
    a--; b--;
    cnt.insert({ a, b });
  }
  vector<int> use(m);
  int q;
  cin >> q;
  vector<int> t(q), x(q), y(q);
  rep(i, q){
    cin >> t[i] >> x[i] >> y[i];
    x[i]--; y[i]--;
    if(t[i] == 1) cnt.insert({ x[i], y[i] });
    if(t[i] == 2) cnt.erase({ x[i], y[i] });
  }
  UnionFind tree(n);
  for(const auto &x : cnt){
    tree.unite(x.first, x.second);
  }
  vector<int> ans;
  per(i, q){
    if(t[i] == 1){
      tree = UnionFind(n);
      cnt.erase({ x[i], y[i] });
      for(const auto &x : cnt){
        tree.unite(x.first, x.second);
      }
    }else if(t[i] == 2){
      cnt.insert({ x[i], y[i] });
      tree.unite(x[i], y[i]);
    }else{
      ans.push_back(tree.same(x[i], y[i]));
    }
  }
  reverse(all(ans));
  for(const int x : ans){
    if(x) cout << "Yes\n";
    else cout << "No\n";
  }
}

L - 展覧会 / Exhibition

なんか難しそう...

未満以上の基準となる $Q_j$ がバラバラだと判定しずらいので、 $Q_j$ の値をindexにして $P_j,L_j,R_j$ を管理しておくことにする

動的計画法で考えてみる、現在の位置と左右に何個あるのかが必要そうなのでとりあえず、

$dp[i][j][k]=i$ まで見て、 $i$ から左は $j$ 個展示されており、 $i$ より右には $k$ 個展示されているときの点数の最大値

としてみる。が、これだと状態数が $N^{3}$ になってしまい、TLE、MLEになってしまう

ここで、問題の定数倍部分に注目してみると、左右に何個展示されているのかという情報は3で割ったあまりで判定できることがわかるので

$dp[i][j][k]=i$ まで見て、( $i$ から左に展示されている数)%3が $j$ 、( $i$ より右に展示されている数)%3が $k$ ときの点数の最大値

としてみると。うまくできそう

初期化は、左には何もないので0として、右は何個展示されているかは初めの状態では未定なので $k=0,1,2$ について、 $dp[0][0][k]=0$ としておく (この時、 $Q_j=1$ の中で条件を満たすものがあればスコアを加算する)

答えを求めるときは初期化と同じように右はわかっていて左側の展示数は

遷移は $i$ 番目の絵を選ぶ/選ばないの2通りある

選ばないとき：この時 $i+1$ の左右にある絵の数は変わらないので $dp[i+1][j][k] \leftarrow dp[i][j][k]+S$ ( $S$ は $i+1$ の時に加算されるスコア)
選ぶとき：番号 $i$ にあたる絵が展示されるため、 $i$ のときに右側にあった $i$ の番号の絵が $i\rightarrow i+1$ になったときに左側に移る。そのため $dp[i+1][(j+1)\%3][(k-1)\%3] \leftarrow dp[i][j][k]+S$ となる

3は定数倍なので計算量は $O(N+M)$ になる

提出コード：https://atcoder.jp/contests/past202209-open/submissions/39328958

int main(){
  int n,m;
  cin >> n >> m;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  vector<vector<int>> p(n+1), l(n+1), r(n+1);
  vector<int> len(n+1);
  rep(i, m){
    int v,q,a,b;
    cin >> v >> q >> a >> b;
    q--;
    p[q].push_back(v);
    l[q].push_back(a);
    r[q].push_back(b);
    len[q]++;
  }
  // dp[i][j][k]: iまで見て、iまでで選んだ数%3==j, iより後で選ぶ数%3==kの時の点数の最大値
  vector<vector<vector<ll>>> dp(n + 1, vector<vector<ll>>(3, vector<ll>(3, -1e18)));
  rep(i, 3){
    dp[0][0][i] = 0;
    rep(j, len[0]){
      if(l[0][j] == 0 && r[0][j] == i) dp[0][0][i] += p[0][j];
    }
  }
  rep(i, n){
    rep(j, 3) rep(k, 3){
      // select
      ll v = dp[i][j][k] + a[i];
      const int nxt_l = (j+1) % 3, nxt_r = (k-1+3) % 3;
      rep(pos, len[i+1]){
        if(l[i+1][pos] == nxt_l && r[i+1][pos] == nxt_r) v += p[i+1][pos];
      }
      chmax(dp[i+1][nxt_l][nxt_r], v);
      // not select
      v = dp[i][j][k];
      rep(pos, len[i+1]){
        if(l[i+1][pos] == j && r[i+1][pos] == k) v += p[i+1][pos];
      }
      chmax(dp[i+1][j][k], v);
    }
  }
  ll ans = 0;
  rep(i, 3) chmax(ans, dp[n][i][0]);
  cout << ans << "\n";
}

M - シリーズ / series

DPで解けそう

$dp[i] = i$ 巻目まですべて買ったときにかかる最小コスト

とする。

今回はdpの遷移がちょっと難しい

L~Rの区間で購入するとき、 $dp[R] \leftarrow dp[L] + B$ をするといけそうだけどちょっと怪しい...

区間の本を購入したときのDPの更新を2回行ったとき、共通部分ができていても互いに更新されないようになってるのでこれじゃダメだとわかる( $L={1,3}, R={4,6}$ の時とか)

同じシリーズの本を複数購入しても問題はないので、L~Rを買うときは $dp[R+1] \leftarrow \min_{i=L,...,R} {(dp[i])} + B$ とすればいい

1点更新、区間最小値のセグ木を使うと $O((N+M)\log N)$ で解ける

下のコードのSegmentTreeは1点chmin更新、区間最小値取得のセグ木です

提出コード：https://atcoder.jp/contests/past202209-open/submissions/39329860

int main(){
  int n,m;
  cin >> n >> m;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  vector<vector<pair<int,int>>> v(n);
  rep(i, m){
    int b,l,r;
    cin >> b >> l >> r;
    l--; r--;
    v[r].emplace_back(b, l);
  }
  SegmentTree<ll, min> dp(n + 1);
  dp.update(0, 0);
  rep(i, n){
    for(const auto &x : v[i]){
      int val,l;
      tie(val,l) = x;
      dp.update(i+1, dp.query(l, i+1) + val);
    }
    dp.update(i+1, dp.get(i) + a[i]);
  }
  cout << dp.get(n) << "\n";
}

N - 上からと横から/From Above and From the Side

$H,W\leq2\times10^{5}$ かつ $HW\leq2\times10^{5}$ なので、 $\min(H,W)\leq\sqrt{2\times10^{5}}$ となる

横向き(T=1)の場合、dequeを使うと末尾削除と先頭追加のクエリが $O(1)$ でできるので高速に答えられる

縦向き(T=2)の場合、愚直に操作を行って $O(H)$ かかってしまうことになる

$\min(H,W)\leq\sqrt{2\times10^{5}}$ というのを使うと、 $H>W$ の時、縦横をすべて入れ替えてクエリを処理すると、T=2のクエリが最遅でも $\sqrt{2\times10^{5}}$ で答えることができる

そうすると全体で計算量 $O(Q\sqrt{2\times10^{5}})$ でできる

提出コード：https://atcoder.jp/contests/past202209-open/submissions/39330394

int main(){
  int h,w,q;
  cin >> h >> w >> q;
  const bool flip = h > w;
  vector<string> s(h);
  rep(i, h) cin >> s[i];
  vector<deque<char>> d;
  if(flip){
    d.resize(w, deque<char>(h));
    rep(i, h) rep(j, w) d[j][i] = s[i][j];
    swap(h, w);
  }else{
    d.resize(h, deque<char>(w));
    rep(i, h) rep(j, w) d[i][j] = s[i][j];
  }
  string ans;
  rep(_, q){
    int t,p; char c;
    cin >> t >> p >> c;
    p--;
    if(!((t - 1) ^ flip)){
      d[p].push_front(d[p].back());
      d[p].pop_back();
      ans += d[p][0];
      d[p][0] = c;
    }else{
      ans += d[h-1][p];
      per(i, h-1) d[i+1][p] = d[i][p];
      d[0][p] = c;
    }
  }
  cout << ans << "\n";
}

O - ２個のボール/Pick Two Numbers

$x = a|b, y = \mathrm{popcount}(a)+\mathrm{popcount}(b)$ と書いてあって複雑なので、とりあえず $x = a|b$ が与えられた時を考えてみる

$a|b = x$ となるすべての $(a,b)$ について $A_a \times B_b$ の合計 $f(x)$ を求めたい。式で表すと $f(x) = \sum_{(i|j) = x} {A_i B_j}$ となる

これはBitwiset Or Convolutionを使うと $O(N2^{N})$ で $f(0),f(1),\cdots,f(2^{N}-1)$ を求めることができる

Bitwiset And Convolution：https://judge.yosupo.jp/problem/bitwise_and_convolution

あとはpopcountをどうすればいいかを考える

$a,b$ でそれぞれpopcountをある値に固定してあげるとOrの畳み込みを使っていい感じに解けそう

-> popcount=0~Nでそれぞれ固定して、それに合ったindexの値だけを使って(それ以外をすべて0にして)Orの畳み込みをして答えを求めていくとできそう

計算量は $O(N^{3} 2^{N} + Q)$ 。ちょっと厳しいかもしれないけど、TLが4[s]でC++であれば何とかなるはず(実際に提出してみると実行時間は1983[ms]でした。提出コード：https://atcoder.jp/contests/past202209-open/submissions/39342834)

高速ゼータ変換したときに、popcountの部分もついでに計算してから戻すというようにすると $O(N^{2} 2^{N} + Q)$ が実現できる。これで提出すると305[ms]になった

提出コード：https://atcoder.jp/contests/past202209-open/submissions/39342872

int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n,q;
  cin >> n >> q;
  vector<vector<mint>> a(n+1, vector<mint>(1 << n)), b(n+1, vector<mint>(1 << n));
  rep(i, 1 << n){
    int x; cin >> x;
    a[__builtin_popcount(i)][i] = x;
  }
  rep(i, 1 << n){
    int x; cin >> x;
    b[__builtin_popcount(i)][i] = x;
  }
  // bitwise or convolution
  rep(i, n+1){
    fzt(a[i]);
    fzt(b[i]);
  }
  vector<vector<mint>> v(n*2+1, vector<mint>(1 << n));
  rep(i, n+1){
    rep(j, n+1){
      rep(k, 1 << n){
        v[i+j][k] += a[i][k] * b[j][k];
      }
    }
  }
  rep(i, n*2+1) fmt(v[i]);
  rep(i, q){
    int x,y;
    cin >> x >> y;
    cout << v[y][x] << "\n";
  }
}

US_cube’s blog