エクサウィザーズプログラミングコンテスト2021（AtCoder Beginner Contest 222） (ABC 222) に参加して，ABCDE 5完498位でした．参加記です．

問題へのリンク

A - Four Digits

文字列として読み込んで，(4 - 長さ) 個の 0 を出力した後に出力．

%04d という書式指定は浮かんだんですけど，printf の使い方に自信が持てず， 止めました．

B Failing Grade

言われたとおりに数えます．

C Swiss-System Tournament

シミュレーションします．

D Between Two Arrays

DPをします．

dp[i][j] = $c_i$ の値が $j$ 以下であって条件を満たす列 $(c_1, \ldots, c_i)$ の数．

E Red and Blue Tree

色の塗り方にかかわらず，各辺を通る回数は決まっているので，まず， この回数を求めます．2頂点を結ぶ最短経路は，LCA を使って求められます．

回数が決まったら，DPをします．

dp[e][k] = 辺 1, …, e を塗る方法で，そこまでの赤の回数と青の回数の 差が k であるような塗り方の数．

k の取り得る範囲は - (M * (N - 1)) 以上 (M * (N - 1)) 以下なので， 計算量は $O(MN^2)$ となります．危ないかな，と思いましたが 280ms でセーフ．

求める答は dp[N-1][K] なのですが，|K| が M * (N-1) より大きいときには 0 にすることが必要です．そういうサンプルを入れてくれてあったので 助かりました．全然気がついていなかったので，サンプルが無かったら 相当悩んだと思います．

G 222

Eまで49'11" で，私としては相当速く解けた感じです． もしGが解ければラッキー，と思って考え始めましたが， 歯が立ちませんでした．15分くらい考えて降参． この辺の判断が遅いんですよね．

F Expensive Expense

twitter で，みなさん，全方位木DP と言っています． チラッと考えはしたのですが，以下の方針で解ける，と思って実装を始めました． 結局間に合いませんでした．(コンテスト後に一応ACしました．) やっぱり全方位木DPで行くべきでしたでしょうか．

DFSの行きがけ順に街を並べて，$1 = s(1), \ldots, s(N)$ とします． 街 $i$ の子孫の s-添字は区間になります． つまり，$i$ の子孫は， $\{ s(j) \mid j \in [b(i), e(i)) \}$ と書くことができます．

最大値の問合せと和の更新ができる， ノード数 $N$ の遅延セグメント木を用意します． 初期状態では，ノード $i$ には，$E_{1, i}$ を設定しておきます． DFSで，セグメント木を更新していき，DFSで街$j$を見ているときには， ノード $i$ に $E_{j, i}$ が保持されるようにします．このためには， 木を$p$ から $q$ に下がるときに，

  • 全体に $C_r$ を加える．($r$ は，$p$ と $q$ を結ぶ道の番号)
  • $q$ の子孫には，$-2C_r$ を加える．(上と合わせて $C_r$ を減じたことになる)

を行います．ここで，

  • セグメント木のノード $q$ には $D_q$ が設定されているので， $-D_q$ を加えて 0 にする．
  • 全体の最大値を求める．

とすることで，$q$ における値が求められます．

$q$から$p$ に戻るときに，上の逆を行って， セグメント木の値を元に戻します．