動的計画法 直前のマスの最適解を用いて現在のマスの最適解を求める int main() { int N; cin >> N; int first; cin >> first; vector<int> dp; dp.push_back(first); int bestAnswer = INT_MIN; for (int n = 2; n <= N; ++n) { vector<int> next; for (int i = 0; i </int></int>…

動的計画法 以下の三つのパターンを考えれば良い 一つ前から縦のタイルを置くパターン 二つ前から横のタイル二つを置くパターン 二つ前から正方形のタイルを置くパターン 組み合わせの数が膨大になるため多倍長整数が必要となる nが64ビットまでかつmod何と…

動的計画法 次に奇数の液体を飲む場合は偶数番目の液体を飲んだ後の力の最大値+strengthに更新する 次に偶数の液体を飲む場合は上記の逆 int main() { int odd = INT_MIN / 2; int even = 0; int P; cin >> P; for (int i = 0; i < P; ++i) { int strength; …

画像URLの中に"\"が含まれていた場合、ディレクトリの区切りではなく、エスケープされた文字として認識してしまうらしい。原因が分かったのでGreaseMonkeyで自動的に置換するようにしてみた。下記がそのスクリプト。 // ==UserScript== // @name Repair Imag…

カードの順番を逆にしてTrie木を作り、ノードの数を数えて終わりです メモリが足りなかったりTLEしたりで、何どもやり直しました int main() { const string firstLetters[] = {"A","2","3","4","5","6","7","8","9","10","J","Q","K"}; const string second…

フェリーには詰め込めるだけ詰め込めば良い 貪欲にシミュレーションするだけです int count(int l, const vector<int>& lengths) { int answer = 0; int sum = 0; for (vector<int>::const_iterator it = lengths.begin(); it != lengths.end(); ++it) { sum += *it; i</int></int>…

何日目にどの問題を解いているかというDPです この解答ではダイクストラ法チックに解いています int B[512]; int A[512]; int Bs[512][512]; int As[512][512]; int main() { int M, P; cin >> M >> P; for (int i = 0; i < P; ++i) { cin >> B[i] >> A[i]; …

最長部分繰り返し文字列という問題だと思います Spaghetti Sourceのライブラリをお借りしました #define SETNUM(rank, i,s) \ NUM[i] = make_pair(make_pair(rank[i], i+s

直接解をを求めようとすると難しいです ある値が与えられたとき、その値が解として正しいかどうかは線形時間で求めることができます コレを使って解を二分探索で求めることができます int pickupGreedy(const vector<int>& ds, int length) { int result = 0; int</int>…

k-th shortest pathという有名問題です Spaghetti Sourceのライブラリを使用しています static const int INF = INT_MAX / 2; #define REP(i,n) for(int i=0;i<(int)n;++i) #define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i) #def…

サイズが大きくないためDPで解けます 有るか無いかのビットフラグをキーにする典型的なDPです bool isValid(int value, int N) { bool last = false; for (int shift = 0; shift < N; ++shift) { if (last && (value & (1 << shift)) != 0) { return false; …

ハフマン木を作る要領で解けるようです 分割するのではなく、全部バラけた状態からくっつける方向で考えると解けるようです int main() { int N; cin >> N; priority_queue<ll, vector<ll>, greater<ll> > ls; for (int i = 0; i < N; ++i) { ll l; cin >> l; ls.push(l); } ll </ll></ll,>…

うまい解法が思いつかなかったためテーブル埋込みを使いました 2^20個を1セットとしてテーブルに持たせ、端数の部分を全探索しました int numofbits5(ulong bits) { bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555); bits = (bits & 0x33333333) + (…

主人公(?)の位置と正方形の一辺を表すベクトルで全探索です N int main() { static char farm[128][128]; static char firstLine[128]; gets(firstLine); const int N = atoi(firstLine); for (int x = 0; x < N; ++x) { gets(farm[x]); } int answer = 0; f…

スタックを使って高さを管理していけば解けるようです int main() { vector<int> stk; int N; cin >> N; ll sum = 0; for (int i = 0; i < N; ++i) { int h; cin >> h; while (!stk.empty() && stk.back() <= h) { stk.pop_back(); } sum += stk.size(); stk.push</int>…

各桁のビットに着目して解いていく 各桁ごとにビットが立つ確率を求め、それらを2^i倍して足していけば良い 答えが合わずに困ってたら、1〜nまでで考えていたのが原因だった。本当は0〜n-1 G++で提出したらWA、C++だとACだった。やっぱり納得が行かない。 in…

答えの値で二分探索を行った 初めkの値の意味を取り違えており、毎ターンk+1乾燥させるようにしていた。WA 入力の直後に--kしたら、0割りでRE k==1の場合は自然乾燥させる場合と等価になるので、max_elementを返せば良い static int a[128 * 1024]; bool che…

問題文を見て目を疑った どう切っても良いので、とりあえずスライスしてみた コンパイラにG++を選択するとWAでC++だとPE or ACという、ちょっと納得の行かない結果になった %.15lfだとOLE、%.10lfだとPE、%.9lfだとACというのも納得が行かなかった int main(…

Twitter上で@tozangezanさんがつぶやいていた問題 サイズが500000なのでO(N log N)のアルゴリズムまでなら通る可能性が高い この回答では最初に500000まで求めてから、最後に入力を処理している #include <iostream> #include <set> using namespace std; static int a[5000</set></iostream>…

丁寧にシミュレーションをすれば良い 左右に玉が転がる部分の判定ルーチンは使いまわせるように関数化した bool check(const string& s, int pos, int dir) { for (; 0 <= pos && pos < s.size(); pos += dir) { if (s[pos] == '.') { return true; } else i…

http://acm.pku.edu.cn/JudgeOnline/problem?id=3093 DP あかかじめ値段の昇順にソートしておく 安い店から順に辿っていき、買うか買わないかで分岐する 他の店で買えなくなるまで買うという条件を満たすため、自分が買わなかったマリゲータのうち最も安い物…

http://acm.pku.edu.cn/JudgeOnline/problem?id=3088 DP解法 やり方が何通りかあるらしい ある押すボタンの集合について、それらのボタンを使ったシーケンスが何通り作れるかを計算していく 最後に全てのパターンを足して出力 ll solve(int B) { static ll d…

http://acm.pku.edu.cn/JudgeOnline/problem?id=3087 データサイズた小さいため単純にシミュレーションをするだけで間に合う int main() { int N; cin >> N; for (int testCase = 1; testCase <= N; ++testCase) { int C; cin >> C; int permutation[256]; f…

http://acm.pku.edu.cn/JudgeOnline/problem?id=2386 典型的な幅優先探索 int main() { int N, M; cin >> N >> M; static bool wall[128][128]; memset(wall, -1, sizeof(wall)); for (int y = 1; y <= N; ++y) { for (int x = 1; x <= M; ++x) { char c; ci…