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

気づいたら月が替わっていました。もう半年なのですね…

競プロ典型 90 問
Codeforces Round #729 (Div. 2)
ABC208
- D - Shortest Path Queries 2
- E - Digit Products

競プロ典型 90 問

078 - Easy Graph Problem（★2）

グラフの基礎。隣接リストをループで見ればOKです。
初心者？が割と躓きやすい問題だと思います(僕が競プロを教えていた同期も、ここは躓きポイントだと言っていました)

079 - Two by Two（★3）

左上から貪欲に操作をしていけばOKです。
とりあえずできる操作をして、一番右と下の列は最後にチェックです。

がんばって包除をします。
包除が青ぐらい(ABCのE問題)で出るたびにびっくりしている記憶があります。

081 - Friendly Group（★5）

二次元累積和を取って $K \times K$ の正方形の総和の最大値を探します。

082 - Counting Numbers（★3）

~~おっと、書きそうになりました…(これいつかやらかしそうで危ないですね、本当に気を付けないといけません)~~

$10^{18}$ だけ場合分けして、あとは等差数列の総和の公式で桁ごとに計算します。

083 - Colorful Graph（★6）

クエリ平方分割で頑張りました。
setをunorderedにしたり、クエリの更新を必要最小限だけ実行するようにしたりと結構キツキツにつめて5ペナの末ACです。

Codeforces Round #729 (Div. 2)

unratedですが久々に出ました。

B. Plus and Multiply

$b$ をした後に $a$ 倍をする必要はありません( $a$ 回 $b$ を足せばよいです)。
なので、 $1$ を $a$ 倍することを繰り返した時に、残りの差分が $b$ の倍数かどうかで判定できます。
難しいです。

C. Strange Function

$1$ から $k$ までのLCMを計算し、その値で $N$ を割った値を答えに足す、ということを繰り返せばOKです。

D. Priority Queue

$i$ 番目が+のとき、その値の寄与を考えます。
それ以外の要素は、 $i$ 番目の要素より小さいかどうか、で01を振り分けることができます。
あとは、 $dp[j][k] = j$ 番目までのクエリのあるなしを決め終え、 $k$ 個、自分以下の要素が含まれている状態のパターン数
を計算すればＯＫです。
$i$ 番目のときだけ、遷移が少し特殊になります。

E1. Abnormal Permutation Pairs (easy version)

$i$ 番目までは一致していて、その次の値がことなるとしたとき、その異なる値による転倒数の寄与の差分は簡単に計算できます。
それより後ろの部分についても、挿入DPでどれくらいの転倒数になるかが計算できます。
$dp[i][j] =$ 小さい方から $i$ 個の要素を入れて、転倒数が $j$ になるような順列のパターン数
を計算できると、あとは最初の差分と合わせて気合で計算できます。

ABC208

D - Shortest Path Queries 2

僕はワーシャルフロイドを知りませんでした。
手元で再発明して同じ遷移まで出しておいて解けなかったの、悲しいですね
蟻本読んだはずなのですが…

E - Digit Products

DFSで解きました。桁DPでなくてDFS派はほとんどいないのですかね(たしかに桁DPの方が考えることは少ないかもしれません)
$N$ 以下が確定したタイミングでそれぞれDFSをスタートさせます。
0が含まれるパターンだけ面倒なので別枠で計算します(これは、0が含まれないパターンの総数を、全パターンから引けばよいので、10のべき乗から9のべき乗を引きます)。DFSは、数字を小さい順に使うと仮定して、総積が $K$ を超えない範囲で決めていき、最後に並べ替えのパターン数を計算します。余計なbreak文を入れていて1ペナしました。