問題 Problem - E - CodeforcesN 枚のコインと K が与えられるので、Kを作れるコインの集合で作れる数字を列挙しろ。 解法 DP コード import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintWriter; i…

問題 Contest Page | CodeChef頂点数 N のツリーが与えられる。 K 個のギャングがいて、各ギャングはツリー上のある頂点集合を支配している。 クエリが Q 個くる。各クエリはある頂点 v と、ギャングのリストが含まれている。 リスト中のギャングが支配して…

解法 最小費用流そのものやんけ！！！！ コード import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; import java.util.PriorityQueue; public class BiconnectedDiv1 { public int minimize(int[] w1, int[] w2) { int V =…

問題 Problem - 686D - Codeforces頂点数 N の木が与えられる。頂点 v を根とする部分木を考えた時、その部分木に含まれる頂点の u うち、u を消去してできる残りの部分木が、いずれも元の部分木の半分以下のサイズになるような u を「v の centroid である…

問題 Problem - C - Codeforces 解法 よく考えると状態はくらいしかない。 コード import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.NoSuchE…

問題 Contest Page | CodeChefN 個の空文字列と M 個の単語が与えられる。Q 個のクエリに応答せよ。クエリは以下の 3 種類からなる。 文字列 X の先頭に文字 C を挿入する。 L〜R 番目の文字列の中で単語 P を含むものがいくつあるか出力する。 L〜R 番目の…

問題 Problem - E - Codeforces平面上に、点がN個あり、どの3点を選んでも三角形を作っても面積がSを超えないように配置されている。このとき、N個の点とは別に3点選び、平面上に配置された全ての点を包含して、かつ、面積が4Sを超えないような三角形を作れ…

問題 Problem - D - Codeforces 解法 あるノード cur について考える。 cur および cur の子孫のうち、まだプレゼントを渡していない人がいるとする。この、「まだプレゼントを渡していない人」の中で cur に渡す人がいるなら、他の「まだプレゼントを渡して…

問題 2016/Practice/模擬国内予選B/問題文とデータセット - ACM-ICPC Japanese Alumni Group 解法 強連結成分分解して、最上流の強連結成分の中で誰かが起きれば、強連結成分内の人も、その下流の人も起きる。 コード #include <bits/stdc++.h> using namespace std; int N;</bits/stdc++.h>…

問題 2016/Practice/模擬国内予選B/問題文とデータセット - ACM-ICPC Japanese Alumni Group 解法 使われているお布団の組み合わせが bitmask とする。この組み合わせでできる最小のコストを dp[bitmask] とする。ここに新しくお布団 i を下に差し込んでコス…

解法 二分探索+全探索+BFS コード #include <bits/stdc++.h> using namespace std; class HardProof { int N; bool check(const vector<int> &D, int minCost, int maxCost) { vector<vector<bool>> g(N, vector<bool>(N, false)); for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { g[i</bool></vector<bool></int></bits/stdc++.h>…

問題 Problem - E - Codeforces 解法 潰す範囲の正方形を愚直に全部試す。この時、正方形内部の管理を愚直にやると遅くなるので、しゃくとり法の要領で1列ずつやる。 コード #include <bits/stdc++.h> using namespace std; const int DX[] = {0, 0, 1, -1}; const int DY[]</bits/stdc++.h>…

問題 Contest Page | CodeChef100 以下の自然数を使ってLISがちょうどK個存在する数列を作れ。同じ数字は1度しか使えない。 解法 MAKELIS - Editorial - CodeChef Discuss{ 2 1 4 3 }で 2*2 通りのLISが含まれる数列を作れる。ここの左側に {5 6} をつけると…

問題 Contest Page | CodeChefツリーが与えられる。1本辺を足して閉路を作るとき、直径を小さくすることが可能か判定せよ。 解法 MAXDIST - Editorial - CodeChef Discussツリーの直径を求める。ツリーの直径が偶数の時、中心となる頂点は1つだけである。中…

問題 B: せんべい - AtCoder Regular Contest 055 | AtCoder 解法 dp[n][k] := n 枚のうち k 枚食べることができる場合のNのせんべいを得られる確率、とおく。 食べるかどうか悩むのは、今までに出てきたせんべいより大きい場合だけで良い。よって残りn枚の…

問題 C: ABCAC - AtCoder Regular Contest 055 | AtCoder 解法 ABCACの5つの区間に分けるとき、末尾のA+Cの部分の長さ s を全探索する。1 つめの A の始点と、2つめの C の終点は決まっているが、A+Cの長さを定めることで、2つめの A の始点と 1 つめの C の…

問題 Problem - D - Codeforces 解法 Codeforces Round #355 (Div. 2) Editorial - Codeforcesダイクストラと全列挙を使い分ける。 コード #include <bits/stdc++.h> using namespace std; typedef pair<int, int> P; typedef tuple<int, int, int> E; template <class T, class U> void chmin(T &t, U f) { if (t > f) </class></int,></int,></bits/stdc++.h>…

問題 Dashboard - Round 2 2016 - Google Code Jam 解法 Bは K-1 個選んだ状態でもう一つの確率を p とすると答えは p の一次式だから端っこで最大になるはずで、だから両端から見れば良い、と思って書いて、あとになって示せてない気がしたけどやっぱり示せ…

問題 https://www.codechef.com/SNCKQL16/problems/FDIVGAME 解法 grundy 数に規則性がある (のを uwi さんに教えてもらった) ので、それを先に作っておいて、参照しながら求めると良い。 コード #include <bits/stdc++.h> using namespace std; int main() { cin.tie(0); i</bits/stdc++.h>…