精進メモ 2021/05/10~ - ツバサの備忘録

もう金曜日ですね。
ReoNaさんのニューシングルカップリング、いいです。

典型90 036 - Max Manhattan Distance（★5）

+-全探索です。
$|a|$ が $\max(a,-a)$ なので、 $\max(|a| + |b|)$ は $\max(a + b,a-b,-a+b,-a-b)$ になります。
あとはここに、 $x_{i} - x_{j}$ と $y_{i}-y_{j}$ を当てはめれば良いです。回転もいりません。最近ARCで見ました。

典型90 037 - Don't Leave the Spice（★5）

DPをセグ木で更新すれば良いです。
$dp[i][j] = i$ 番目の香辛料までみて、使った量が $j$ になるような組み合わせの中での価値最大、とします。
もらうDPを考えると、遷移元の量が $[j - r_{i},j - l_{i}]$ の区間になっているので、セグ木で最大値を取り出せばいいです。

典型90 039 - Tree Distance（★5）

寄与を考えるいつものです。頂点1を根とする木を考えます。
頂点 $v$ を根とする部分木のサイズを $s_{v}$ とすると、 $v$ とその親を繋ぐ辺が使われる回数は、 $s_{v} \times (n - s_{v})$ になります。
よって、木DPで部分木のサイズを求めれば答えを求めることができます。

典型90 040 - Get More Money（★7）

†燃やす埋める†

典型 041 - Piles in AtCoder Farm（★7）

凸包を作り、辺それぞれに対して、辺以下にある格子点をfloor_sumで計算し、上側の個数から下側の個数を引き、最後に下側の辺上の点を足します。
縦に直線になっているパターンに注意。

GCJ

ついにRound 2突破しました！！！！競プロを始めた時からの夢だったので、とても嬉しいです。その日は興奮してなかなか眠れませんでした。

f:id:emtubasa:20210517133558j:plain

A:ぐっとにらむと毎回全体の最小値選ぶだけ
B:最小でXを使うと、(N-X)/Xで同じ問題に帰着できる、初手だけ3以上なのが注意
C:セグ木 + コンビネーションで再帰的にやる
d:フロー
とツイートに書いてあります。内容はもう忘れました。
B,Cは面白かったという記憶だけ残っています。

ABC201

Eで苦しみました。

D - Game in Momotetsu World

MinMaxの素直なDPです。
頭がこんがらがりやすいので、丁寧にやりました。

E - Xor Distances

bitごとにやります。
木DPで、今見ている頂点からどこかの子へのパスと、子同士のパス、の2つに分けて数え上げていきます。
$dp[v][b] =$ 自身の子から $v$ へのパスで、今見ているbitのxorが $b$ になるようなもののパターン数
をがんばって数えます。
60回DFSをするとTLEしますが、頑張って定数倍高速化しました。

F - Insertion Sort

$B_{i},C_{i}$ については、 $A_{i}$ とのminを取ることで、右端と左端に送る操作をした時のコストが決まります。
( $B_{i}$ )(いじらない or $A_{i}$ 消費)( $C_{i}$ ) という3パターンに分かれます。
左右は累積和を取ることで簡単に求められます。
真ん中は、いじらないと決めた値 $X$ があったら、つぎにいじらない選択肢を選べる $Y$ は、元の順列で $X$ 以降にある値です。
ということで、
$dp[i][j] =$ 元の順列で $i$ 番目の値を最後にいじらないとしたとき、 $j$ 個の要素を並べ終えた段階におけるコストの最小値
とすると、 $i$ をインデックスにもつ遅延セグ木によって高速化できます。

ARC119

D,Eは難しくて現時点だと解ききるのが難しいです。

A - 119 × 2²³ + 1

$c$ については、 $a,b$ を決めた上で残った値を使えばいいので無視してかまいません。 $b$ を固定すると、これは60通りくらいにしかなりません。 $a$ が一番大きくなるには、 $N$ を $2^{b}$ で割り切り捨てた値を選べばいいです。
あとは、余った値を $c$ にして計算し、全探索します。

B - Electric Board

まずは問題文を丁寧に読みます。
0の個数は変化しないので、個数が違っていたらそもそも -1 です。
結局、0の位置は一回の操作で、"最も近い0を超えない範囲で"自由に入れ替えることができます。なので、一番左側から揃えていくしかありません。よって、 $s,t$ に含まれる $i$ 番目の0の位置が異なっているような $i$ の個数が答えになります。

C - ARC Wrecker 2

判定を一回行うだけなら、左側から貪欲に0になるよう調整していけば良いです。
このとき、 $S = A_{1} - A_{0}$ として、次に $A_{2} - S$ を計算し、次はこの値を $A_{3}$ から引き…
と、よく見ると毎回正負を入れ替えて引いていることになります。
この手の問題は、 $A_{i}$ を先に、+-+-...としてしまえば上手く計算できます。
ということで、奇数番目は $A_{i}$ 、偶数番目は $-A_{i}$ として累積和を取っていくと、累積和が0となるような区間の個数を求める問題になります。
これはzero sum rangesという問題で有名な解き方で、 $0$ からの累積和の値に対する個数をmapで管理し、現時点での累積和と同じ値のmapの要素を参照して答えに加算していけば良いです。