精進メモ 2021/06/21~ - ツバサの備忘録

CTFとの両立難しいですね。

典型90
ABC207
AGC054

典型90

072 - Loop Railway Plan（★4）

DFSを頑張ります。

073 - We Need Both a and b（★5）

木DPです。部分木について辺の有無を決め終え、今見ている頂点を含む連結成分の"ab"の状態が何か、を添え字に持ちます。

074 - ABC String 2（★6）

c があるとき、一番左側の c を選ぶようにしておけば、回数を最大化できます。
$dp[i] = i$ 番目を1回操作したときに行える、操作の回数の最大値とすると、
$\displaystyle dp[i] = \sum_{j = 1}^{i-1} dp[j] + 1$
となります。
あとは、cを2、bを1、aを0として、 $\sum_{i} dp[i] \times S_{i}$ を計算すれば良いです。

075 - Magic For Balls（★3）

素因数分解をし、含まれている素数を数えます。
$2^{i}$ が、その個数を超える最小の $i$ が答えです。

076 - Cake Cut（★3）

総和が10の倍数でなければまず答えはありません。
10の倍数のとき、しゃくとり法で答えがあるかを探せばOKです。

077 - Planes on a 2D Plane（★7）

二部マッチングです。飛行機と、到着地点をマッチングさせます。
復元はいつもの残余グラフを見るやつです。
実行時間が864msになっていて、Dinicの実装見直さないといけないパターンかもしれません…

ABC207

D問題が難しすぎました。

C - Many Segments

共通区間を抜き取るのは、 $\max(l_{i},l_{j}),\,min(r_{i},r_{j})$ を計算するいつものでOKです。
あとは開区間閉区間の細かい部分ですが、 $l \neq r$ であれば答えはすぐに決まります。そうでない場合は頑張ります(ただ、そこまでひどくなりません、if文2つでOKです)。
区間を2倍するテク、完全に失念していました。

D - Congruence Points

重心からのベクトル集合を作ります。
それを原点中心で回転させて、2つを一致させることができればOKです。ベクトルをそれぞれの集合から1つ選び、x軸に一致するようにして判定しました。
コーナーケースは、重心部分に丁度点があったとき、そのベクトルをx軸に揃えようとするとバグることです。

E - Mod i

$dp[i][j] = i$ 個の数列を決め終えた状態で、 $\sum_{k}A_{k} \mod (i + 1) \equiv j$ となっているようなもののパターン数
とすると解けます。
DPに、zero sum rangesを組み込む形で面白いです。まぁmodで状態をまとめているだけと言われればそうなのですが。

F - Tree Patrolling

$dp[i][j][k] =$ 今見ている頂点を根とする部分木について、監視されている頂点が $k$ 個、今見ている頂点に高橋君を配置したか( $i$ )、今見ている頂点は監視されているか( $j$ )
としてDPの遷移を組み立てます。
二乗の木DPです。

AGC054

A - Remove Substrings

先頭と末尾が異なる場合、明らかに答えは1です。
それ以外の場合、2つ連続して、先頭と異なる文字がある場所を探します。あれば、明らかに答えは2です。
それ以外の場合、連続するどの2点を選んでも、必ず1つは先頭と一致してしまいます。そのため、どのように削除しても空文字列にすることはできません。

B - Greedy Division

高橋君と青木君が選ぶミカンの集合を決め、それぞれ適当な順番で並べます。すると、それに対する順列は1通りに決まります。
この決め方でできる順列は重複しないので、丁度総和が半分ずつになる集合を選び、 $i, n-i$ 個だったとすると、 $i! \times (n-i)!$ を答えに加算すれば良いです。
あとは $i$ 個選んで総和を全体の半分にする集合の決め方を数えられればよく、これは

$dp[i][j] = i$ 個選んで総和が $j$ になるようなパターン数

として遷移をすると間に合います。

C - Roughly Sorted

まず、ある順列が与えられたときに、問題の条件を満たすような最小の操作を探します。
これは、自分より左側にある、自身より大きい数の個数が $K$ を超えているインデックスのうち、一番左側にあるものを、より左側に動かす、という操作を繰り返せばよいです。
$K$ を超えているものを左側に動かしても、swapされて右側にきたものが新しく $K$ を超えることはありません。
ということで、この操作を逆順に見ます。
すると、今自分より大きい数が左側に $K$ 個あり、自分の1つ右隣も自分より大きいものについて、元々の順列の位置は、今いる位置、もしくはそれより右側であれば何でも条件を満たします。
これは、順列の数字それぞれ独立に考えることができ、最終的には

上記の条件を満たす $i$ について、 $N- i$ (0-indexed)の総積を計算したもの

が答えになります。