Fで詰んで萎えてたら書くの遅くなってしまった
32:04 5完 + 1ペナ 479位
A Saturday
Monday, Tuesday ... が問題文にあるので、これをコピペして配列にすると少しだけさぼれます
(AC 2:04)
B Split
そもそものスプリットってこういう定義なのかな？
それぞれのピンが何列目にあるかをあらかじめ求めておくと、「i列目に立っている数」を数えることで、条件をループでチェックする形に帰着できます
丁寧に確認して提出
(AC 9:48)
C Index x A (Continuous ver.)
普通にDレベルあるかと思ったけど、そんなこともないのか...
1つ区間を右にずらしたときにどうなるか考えます
今の区間が[l,r]でそれが[l+1,r+1]になったとします
Al x 1 + A(l+1) x 2 + ... Ar x K が Al x 0 + A(l+1) x 1 + ... Ar x (K-1) + A(r+1) x Kになるので、[l~r]でかけられる数が1ずつ減少します
つまり、Al ~ Arの和だけ減少するので、累積和でこれを管理すればいいです
(AC 15:11)
D Index x A (Not Continuous ver.)
DPとしてあまりに典型的すぎる、練習問題としてはいいですね
dp[i][j] := i番目までみてj個使った時の最大値
と定義してあげればよいです
一番よくみる形なので瞬殺
(AC 18:16)
E Erasing Vertices 2
コストが「各操作での最大値」なので、これを最小化するのは二分探索が有効そうです(いわゆる「最大値の最小化」)
各回のコストをK以下にできるか？という判定問題を考えます
どのように操作するのが最適でしょうか？
ある頂点に対する操作のコストは、操作を行うごとに増えることはなく、どこかのタイミングで減っていきます
なぜなら、削除される頂点が増えるのでその分だけコストが減少するからです
よって、「現時点でK以下ならそれを実施してよい」ことがわかります
それぞれの操作を実際に実行して、「頂点iを選んだときのコスト」がK以下に新しくなったのであれば、それも実行してしまえばよいです
これはqueueやstackで操作可能な頂点を管理することなどでシミュレーションできます
まあ、実は貪欲でいいんですけどね(本番は怖かったのでにぶたんした)
(AC 27:04)
F Exactly K Steps
ねえーーー、実装激重方針をとって死にました
＝＝＝ここからあんまりよくない方針＝＝＝
まず、簡単なケースを考えてみます
根からの距離がちょうどKはどうでしょうか？
これはあらかじめ木DPをしておくことで簡単に求められそうです
もう少し発展してみます
頂点uの部分木でuからの距離がちょうどKになるものはどうでしょうか？
もし存在するなら、オイラーツアーをして頂点に入る時間・出る時間を管理することで、にぶたんによって答えられます
より具体的には、オイラーツアーでの(入る時間,出る時間)をペアとして、頂点1からの距離ごとにvectorをつくります
その後、二分探索で部分木内にあるか確認することができます
さて、ここで残る問題は「親の方向に戻る」パターンになりました
単純に親方向に戻ればいいだけならどうでしょうか？
つまり、depth[i] >= Kの場合です
これは、LCAの要領でダブリングをすることで解けます
最後の問題として、「親の方向に戻るが、途中で枝分かれする」パターンが残ります
とりあえず、ちょうどKがわからずとも「最も遠い点はどこか？」という問いに答えられれば良いです
そうすれば、その途中に距離Kとなる点があるか判定できそうです
よって、木DPで
dp[i] := iから親方向に戻って枝分かれをするとして最適な頂点
を求めていきます
親とつながっている頂点の中で部分木の深さが最大のものが最適になるので、これを計算しながら進めていきます(実装がめんどくさすぎる)
こうして
1. 部分木にあるとき
2. 直接戻れるとき
3. 途中で枝分かれするとき
のすべてについて調査して見つかったら出力すればよいです
3が特にやばくてハマっていたら間に合わなかった...
実は直径のときに両端となるものが最遠点になるので、それを利用すると楽になるのか...
(AC 116:41)
総括
ABCもう一回勝つぞ！！
