問題概要 N頂点のDAGが与えられる(多重辺アリ).入次数0のノードからN番目のノードまでの全てのパスを考える. それらのなかに最も多く含まれている辺の、含まれている回数を求めよ 辺a->bが含まれる回数は(始点からaまでのパスの総数)*(bから終点までのパスの…

問題概要 [Start,Finish]で、二進数で表記した時に0の数が1の数以上になるような数の個数を求めよ桁DP。やるだけ。なんでこれが8なんだろう(この前8のad-hocが自力で解けなかった) dp[i][j][k][l]:=今上からi桁目で、0の個数-1の個数がjでkはずっと上限でき…

クリスマスですね。日本語の解説記事がなかったので。 まずは普通に dp[i][j]:=i番目のポールを高さjにする時のそこまでのペナルティの合計の最小値 (不可能なときはINF)として漸化式をたててみると dp[i][j] = min{dp[i-1][k]+abs(k-j)*C | 0 となりますが…

ソースは全部 okuraofvegetable/PKU · GitHub にあげてます。 2247 全部列挙 2371 やるだけ 1007 適当に数えてペアでソート 1008 めんどくさいだけ 1013 全探索 1046 三平方で全部しらべる 1050 2次元imosしてあとは全部調べる 2840 やるだけ 2182 後ろの牛…

貪欲。valueの条件から価値の低いコインをたくさん使うより高いコインを1枚つかうほうが後で小回りが効くのでよい。最初、Cを超えないように大きい方から取っていって、それでもCより少なかったら価値の小さいほうからC以上になるまで取っていった。 なるべ…

LCA求めて距離出すだけ。 最初Navigation Nightmareのinputの形式と同じなのでマンハッタン距離かなぁと思っていたけど入力の方角関係ないらしい。意味不明。 最初ダブリングでやったらなぜかTLEが取れなかったのでeuler tour+RMQで書きなおしたら通った。 …

やるだけ。実装が重い(?)せいかなぜか非公式難易度表では8。 あらゆるテストが迫っているので今日はコレだけ。 int N,M,K; struct edge{int to,dir,cost;}; struct query{int from,to,turn;}; vector<edge> G[40010]; P dist[40010];//fi:East sec:North query Q[4</edge>…

問題としてはクソ簡単なのですが時間制限がキツい。 mapでは間に合わないのでロリハかTrieでやらないとダメだと書いていた人がいましたが、mapで通りました。 #include <string> #include <sstream> #include <iostream> #include <map> using namespace std; map<string,string> ma; int main() { string s;</string,string></map></iostream></sstream></string>…

segtreeがやたら書きたくなったのでPKU漁ったら出てきた問題。 解法 区間の最大値と最小値の差を出力する問題。普通に2つのsegtreeで区間の最大値、最小値を求めて引き算しました。 ソースコード #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <complex> #includ</complex></cmath></cstdlib></cstring></cstdio>…

この問題、多分今まで5,6回は説いている気がします（笑） なぜかというと、Union-Findの実装忘れたな〜と思うたびに解いてるからです。 今回はさすがに1発AC。Union-Findはとても大事なデータ構造なので素早く実装できないとダメなんじゃないかなと自分の中…

解法 暇つぶし（暇じゃないのに）やったやるだけ問題。 シミュレートするだけ。が、しかしstringのsubstr()つかってやって2TLE出しました…。 こういう問題で手こずるとJOI予選落ちるんじゃないかって気がしてとても焦ります…。自分が経験して困ったことなの…