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

もう6月です。気分はまだ2020年の春休み。

競プロ典型 90 問
ABC203 F - Weed
HUPC2016(RUPCセット)
典型90 053 - Discrete Dowsing（★7）
ABC204

競プロ典型 90 問

048 - I will not drop out（★3）

部分点と、満点部分を分解してソート、貪欲に取って終了です。

049 - Flip Digits 2（★6）

$L_{i}-1,R_{i}$ をコスト $C_{i}$ で結ぶ辺として最小全域木です。
難しいですね…

050 - Stair Jump（★3）

すなおにDPします。遷移は2パターンです。

051 - Typical Shop（★5）

半分全列挙して、候補を二分探索で求めていきます。

052 - Dice Product（★3）

式変形すると、それぞれのダイスの和を求め、その総積を計算すればOKです。

054 - Takahashi Number（★6）

論文から著者、著者から論文に辺を張ってBFSすればOKです。

055 - Select 5（★2）

枝刈りして全探索です。積を和だと思ってペナを出しました。

056 - Lucky Bag（★5）

頑張ってDPの復元をします。
$dp[i][j] = i$ 個福袋を買い終えて、総和が $j$ 円になるとき、最後に買った福袋の種類
と定義して遷移をしていけばOKです。

ABC203 F - Weed

提出
高橋君の操作が $\log A_{i}$ 回で収まるのがポイントでした。この手のポイントに気づくのが苦手です…

$dp[i][j] =$ 高橋君が $i$ 回操作をして、 $[1,j]$ までの草を抜き終えたとき、必要な青木君の操作回数

とすると、 $dp[i][n]$ が $K$ 以下になっているような $(i,dp[i][n])$ の最小値が答えです。
遷移は、青木君が操作をするのが
$dp[i][j] = dp[i][j-1] + 1$ です。
高橋君が操作をするのが、

$m_{j} = j$ 番目の草を抜いたときに同時に抜くことのできる草のidの最小値

として、
$dp[i][j] = dp[i-1][m_{j} - 1]$ です。

HUPC2016(RUPCセット)

チーム練でした。

C: 成長する点

点と直線、点と点の距離公式を使って頑張る問題です。
距離の最小値を配列でメモしておき、 $O(N)$ で候補を探せばよい…です。コンテスト中は見落としていました。
~~競プロを始めたばかりの後輩に押し付けて良い問題ではないです。~~

D: Complex Oracle

$[i,n]$ のクエリを $N-1$ 回飛ばすと、左側から順に値が確定していきます。
まだ選んでいない数の中で、転倒数の差分 + 1番目に小さいものになります。

E: Arai's

二部マッチングを素直にします。面談回数をコストにして辺を張り、容量を1ずつ流していきます。
$K$ を超えないコストの中で流せたフローが答えです。

F: きっちり

数列を半分で折りたたみ、差分を考えます。前半パートは正、後半パートは負として考えると、判定条件は、 $N/2$ の長さの数列について、全ての要素が0になっていることです。
区間加算を行い、セグ木で数列の最大と最小がどちらも0になっていればOKです。

G: 運命力

4秒前の状態まで持って、 $5N \times 5N$ の行列累乗です。
シャッフルの遷移3パターンは頑張ります。

典型90 053 - Discrete Dowsing（★7）

黄金分割探索です。
切り捨てる範囲を、...8,5,3,2,1とフィボナッチ数列にしていくように、数列の長さをうまく決めると良いらしいです。
これなら、誤差を気にする必要がありません(1500より大きい部分については適当に-1が入っていると考えればいいです)。

ABC204

Eの考察にハマりました。
もう少し早くできたと思います、悔しい。

C - Tour

CにBFS,DFSってありましたっけ…
驚きながら実装しました。

D - Cooking

オーブン1を使う料理を決めると、オーブン2を使う料理は自動的に決まります。総和から、オーブン1を使う料理分ひくだけです。
$dp[i][j] = i$ までの料理を決めて、片割れのグループの時間が $j$ となるようにできるかどうか
とすると、 $N$ まで決めて、 $j$ が作成できるとき、 $\max (j,\sum T_{i} - j)$ の最小値が答えです。

E - Rush Hour 2

想定解がわかりません。
$t$ 秒に $C,D$ の辺を通ると、 $t + C + D / (t + 1)$ 秒に目的地に着くのですから、これを微分してあげると、だいたい $t + 1 = \sqrt D$ になっていればいいことがわかるので、この周辺で辺の移動を開始するパターンを探索してあげます(すでに $t$ が大きければ、そのまま直で移動)。
あとはダイクストラです。