競プロで解いた問題が最近1000問を超えたみたいですが、未だに苦手が大量にあるので。 知らない or 実装したことがない or 苦手 実装 あまりできるようにならない 幾何 全部 DP 本質的に難しい問題が多い 木 Segment Tree 遅延 永続 SttarySkyTree 2D 平衡二…

解法 cuteでソートするとDPできて、cuteの最大値が定数で、dp[鍋の種類][重さ] := max{cuteの最小値}となるようなテーブルがO(NW)で作れる。 できたテーブルは尺取法でO(W)で走査できる。全体で、O(NW) #include <iostream> #include <algorithm> #include <map> #include <cstring> using names</cstring></map></algorithm></iostream>…

解法 dp[index][分割する個数] := min{右端に来る数} とするとO(N^3)でDPできるが、これでは間に合わないので、工夫して dp[index][右端に来る数] := max{分割する個数} として、j #include <iostream> #include <cstdio> #include <vector> #include <map> #include <algorithm> using namespace std; </algorithm></map></vector></cstdio></iostream>…

考察要素が大きく、実装パートも面白いので良問だと思う。 解法 完全グラフK_nのときは、自明 そうでないとき、他の全ての点と接続しているような点が存在しているから、その点を取り除く。 #include <cstdio> #include <algorithm> #include <vector> using namespace std; typedef lon</vector></algorithm></cstdio>…