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

気づいたらもう土曜日です。おかしいですね…

ARC121
ABC203
- D - Pond
- E - White Pawn

ARC121

橙パフォを1カ月ぶりに出しました。だんだん出るようにはなっている気がします。

A - 2nd Greatest Distance

X, Y座標それぞれで大きいものと小さいものを2つずつくらいとってきて、全探索すればOKです。
念のため余裕を持って4つずつくらいとりました。

B - RGB Matching

RGBの偶奇は、000か011を並び替えたものの2択です。
前者は明らかに答えが0です。
後者は、11の中で一番値が小さくなるペアを選びます。このパターンだけ考慮してペナを吐くまでが1セットです。
Rが0、GBが1としたとき、RGとRBでそれぞれペアを作るパターンも存在します。
例えば、Rが[1,10], Gが[1]、Bが[10]のときです。
このパターンでは、RGとGBそれぞれで、一番値が小さくなるようなペアを選べばよいです。
もしRが同じ犬🐶になった場合、GBペアを直接選んだ場合が最適解になるので、特に問題はありません。
値を $r,\ g,\ b$ とすると、 $g \lt r \lt b$ のときは最適解が同じになります。 $g \lt b \lt r$ の場合はGBペアを選んだ方が最適になります(逆サイドも同様)。

C - Odd Even Sort

転倒している部分で選べる箇所があればそれを選択、なければ $1,2$ のどちらかを適宜選択すれば間に合うらしいです。

E - Directed Tree

ある頂点 $v$ が違反するには、 $v$ の子の部分木の頂点とペアにする必要があります。
違反しない方を考えると、親だけでなく、別の枝についても考慮しないといけないため大変です。
$dp[v][i] = v$ を頂点とする部分木について考えた時、少なくとも $i$ 個違反する頂点があるような、違反するペアの選び方
とすると、これはNTTです(オーダーが悪くなりますが楽です)。
順列のパターン数にするには、木の根の部分の $dp$ を計算した後、残った個数分階乗をかければいいです。
あとは、 $i$ の個数で正負をわけ、包除原理に落とし込むと答えが求まります。

ABC203

Fみたいな問題に気づくのすごい苦手です…(今回は謎の嘘解法に走っていました、久々にやらかした気がします)

D - Pond

感覚がマヒしていますが、冷静になるとこの位置にある割に難しいですね。
中央値の最小値は、二分探索をすると見通しがよくなります。
ある $X$ 以下にできるかどうか、を考えると、 $A_{i,j}$ は $X$ 以下であるかどうか、0,1の二択にすることができます。
$K \times K$ の領域の中で、1の個数が半数以上になっていればいいです。
二次元累積和を頑張って書けばOKです。

E - White Pawn

$dp[i][j] = (i,j)$ にたどり着くことができるかどうか、を考えます。
すると、これはシンプルなDPで書くことができます。
遷移は、1つ前の行のみが必要なので、配列のサイズを $2 \times N$ に抑えることができます。
さらに、1行上の値から違う値に更新されうるのは、たかだか黒いポーンがある列と、その左右にです。なので、その部分だけ愚直に更新するようにすればいいです。これで、配列サイズを $N$ におさえて一次元で書けるようになりました。
今回、 $N$ は大きいので、mapなんかを用いた座標圧縮を行ってあげれば、サイズが $M$ に抑えられます。