考え方 $S,T$の原点を重心に取り直す（座標全体を$N$倍すれば，座標変換後も整数座標になる） $S$の中で原点から最も離れている点$(x_{0}, y_{0})$を1つとる． $T$の中で，原点からの距離が$\sqrt{x_{0}^{2} + y_{0}^{2}}$に一致するものの偏角（$x$軸となす…

よく出る思考パターン・覚えておきたいアイディアをメモしておきます． 問題の分類にもなっています．参考になるコードのリンクをメモしている問題もあります．【2022.01追記】最近は，このページではなく，タグで分類するようにしています． 入力 出力 改行…

【類題】EDPC - D - Knapsack 1 - 競プロはじめました 考え方 DP - 「ぴったり」で考える方法 貰うDP 考え方まず，制約から何を変数に使えるか考える．D - Knapsack 1とは，制約のみ異なる．これにより，変数に$W$を使うことはできなくなる．代わりに，$v_{i…

【類題】EDPC - E - Knapsack 2 - 競プロはじめました 考え方②：「ぴったり」で考える方法 貰うDP 考え方①：「以下」で考える方法 貰うDP 考え方②：「ぴったり」で考える方法「$W$以下」ではなく，「$W$ぴったり」となるように考えるのがよくあるパターン．…

配るDPでないと，うまく書けない例？ 【類題】 ABC099C - Strange Bank - 競プロはじめました ナップサック問題に雰囲気が似ている：D - Knapsack 1 - 競プロはじめましたDP考え方$N$コの弁当からたこ焼き$X$コ・たい焼き$Y$コ（ぴったり）になるよう選ぶ方…

きっかけ：ABC219Dと次の記事． 貰う DP と配る DP、メモ化再帰、個数制限なしナップサック問題 - Qiita DP 考え方 貰うDP 配るDP メモ化再帰 DP考え方答えを$f(N)$とすると，$x = 0,1,...,N-1$に対して$f(x)$がわかっていれば$f(N)$が計算できる．よって，D…

考え方 回答例 考え方 辺を除かない状態で，最短距離dを求める．また，最短経路につかう辺の集合routeを求める． 辺を順に除いていき，その辺がrouteに含まれないならdが答え．routeに含まれるなら，もう一度最短距離を求める（※）． （※）routeの数≦$N-1$で…

クラスカル法クラスカル法．コストの小さい順に辺を見ていき，閉路・二重辺でなければ追加する．UnionFindを使う．バラバラの状態からはじめ，辺の頂点が同じグループに属していないなら追加すれば良い．UnionFindコストが負の辺は取り除く意味がない（すべ…

対角線上の2点を決める 対辺の数を求める 対角線上の2点を決める長方形は，対角線上の2点により一意に決まる．よって， 左上と右下の座標を決めたとき， 左下と右上の座標が集合に含まれるか判定する setのinなら$O(1)$で計算できるのがポイント．【参考】Su…

不要部分を削った行列が一致するか判定する numpyによる解法 numpyなし #の座標の集合で見る 不要部分を削った行列が一致するか判定する行列の不要な部分を削除した上で，片方の行列を回転させてもう一方と一致するかを調べれば良い．numpyによる解法ちょっ…

C++ ではこんなに簡単にかけるのに．．． Editorial - AtCoder Beginner Contest 217【追記（C++ の回答）】(C++) ABC217D - Cutting Woods - 競プロはじめました一般的な話は次が役立ちそう： std::setを使わない代替テクニック [いかたこのたこつぼ] 【Pyt…