解法 固有値が2の時の固有ベクトルを求めて、適当にグラフを作ると、後ろから辿ることで状態を復元できる #include <iostream> #include <string> #include <map> #include <algorithm> using namespace std; typedef pair<char, int> State; map<pair<State, int>, State> f; map<pair<State, char>, pair<State, int> > g; #define M 9 int deg[M] = {3, </state,></pair<state,></pair<state,></char,></algorithm></map></string></iostream>…

LPであることと、フローっぽいことはなんとなく分かるけど、最小費用流のLP双対の形にするのが少し難しいので、1100妥当だと思う。 解法 最小費用流の双対なので、変形してから流す。 ネットワークが少し特殊な形をしてるけど、蟻本とかで調べるとやり方が書…

解法 木のサイズに関する自明な枝刈りをすると計算量が落ちるから、頑張って実装する。 木を作ったり判定したりするのが大変なので工夫すると比較的楽に実装できる。 判定するときは、queueを3つくらい使うと綺麗に実装できる。 #include <iostream> #include <string> #includ</string></iostream>…

解法 包除原理+DP包除原理に気づかずbitDPしようとしたら複雑すぎて無理だった(解説スライド見ても解けるとしか書いてなかった) あと、解説スライド見ると包除原理だけで良いらしい(ちょっと読んでもよく分からなかった) #include <cstdio> #include <cstring> #include <algorithm> #inc</algorithm></cstring></cstdio>…

競プロで解いた問題が最近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>…

解法 sort+累積和+setで解こうとするとsetのメモリの定数倍が大きくMLEするので、 尺取法みたいな感じ(？)で次数を1つずつ順に見ながら、最小カットを考えるとO(n)で解けて、メモリも足りる。 #include <iostream> using namespace std; typedef long ll; #define N 25</iostream>…

解法 想定解は、後ろからUnionFindらしい。賢い。この問題は(実装が重くなるが)平方分割でも解けて、 MクエリがB回来るたびにO(N)で全部の頂点を更新すると、Qクエリをダブリングを用いてO(BlogN)で処理でき、全体でO(Q*(N+BlogN))となるので B = √(NlogN)程…

解法 SRM607Med CombinationLockDiv1と同じように考えると、直ぐ解ける。 まず、to - from を計算して、回転数を求めて、差分を求めることができる。 「(複数の)ダイアルを1回回す」 ⇔ 「差分を任意に2つ選び、それぞれ +x, -x する」 であるから、差分を総…

解法 直近の順列に着目して、DPする #include <iostream> #include <vector> #include <map> #include <algorithm> using namespace std; #define chmax(X,Y) X=max(X,Y) #define N 200 map<vector<int>, int> dp[N]; int main(){ int n; cin>>n; vector<int> d(n), a(n); for(int i = 0; i < n; i++) cin>>d[i];</int></vector<int></algorithm></map></vector></iostream>…