全域最小木 プリム法またはクラスカル法が使える typedef double Weight; struct Edge { int src, dst; Weight weight; Edge(int src, int dst, Weight weight) : src(src), dst(dst), weight(weight) { } }; bool operator < (const Edge &e, const Edge &f…

最短経路の応用 エッジを更新するときにそれまでの最大容量と道の容量の高い方を伝搬する 上はダイクストラ法、下はワーシャルフロイド法の解答 struct Dic { map<string, int> m; int get(const string& s) { map<string, int>::iterator it = m.find(s); if (it != m.end()) { return</string,></string,>…

全点間最短距離 ダイクストラ法またはワーシャルフロイド法が使える static int g[128][128]; int main() { for (int N; cin >> N && N; ) { fill_n((int*)g, sizeof(g) / sizeof(g[0][0]), INT_MAX / 2); for (int n = 1; n <= N; ++n) { int M; cin >> M; …

シミュレーション 連想コンテナを使うのが定石 int main() { int n; cin >> n; string line; getline(cin, line); map<string, string> candidateToParty; for (int i = 0; i < n; ++i) { string candidate, party; getline(cin, candidate); getline(cin, party); candidate</string,>…

ダイクストラ法 一度訪れたintersectionは二度訪れる必要はない よって初めから行ける場所とそれ以外の場所でコストを変えてダイクストラをすれば良い int main() { for (int N, A, B; cin >> N >> A >> B; ) { int dp[128]; fill_n(dp, sizeof(dp) / sizeof…

動的計画法 Subset Sum Problemという有名問題らしい 横方向に桁数、縦方向にNの余剰を配置する REで通らなかったため、テーブルを埋め込んだ static const char* table[] = {"", "1", "10", "111", "100", "10", "1110", "1001", "1000", "111111111", "10"…

動的計画法 縦に車の数、横に2レーンのうち片方の車の総重量をとる DPが終わったらバックトラックして答えを求める static char dp[256][16 * 1024]; int main() { int length; cin >> length; length *= 100; vector<int> cars; dp[0][0] = -1; int bestCarIndex</int>…

並べかえられた文字列はソートして比較すると良い 短い文字列をソートしようとしてREをもらってしまった・・・ int main() { int n; cin >> n; for (int caseIndex = 1; caseIndex <= n; ++caseIndex) { map<string, int> dic; int m; cin >> m; for (int i = 0; i < m; +</string,>…

標準ライブラリと関数オブジェクトの使い方の練習問題として調度良いと思う データサイズの記述がないが、適当にやっても大丈夫だと思った const string toLower(const string& s) { string result; for (string::const_iterator it = s.begin(), itEnd = s.…

最悪ケースは下記のようなものだと思う ABCDEFGHIJKLMNOPQRST BCDEFGHIJKLMNOPQRSTU CDEFGHIJKLMNOPQRSTUV DEFGHIJKLMNOPQRSTUVW FGHIJKLMNOPQRSTUVWXY GHIJKLMNOPQRSTUVWXYZ HIJKLMNOPQRSTUVWXYZZ ... 2^26なので全探索しても通るはず static const int dx[…

最初に考えたときはナイーブな方法だと計算量が足りないなぁと延々と考えていた 繰り返される文字数kを全部回すとで通らない Nの約数の個数は個なので、Nの約数kだけ見ればとなり通る static char input[2 * 1024 * 1024]; int main() { while (scanf("%s", …

パスカルの三角形を書いたところ、REとなってしまった 入力が符号なし32ビット整数なのでintに入れたときに負の数になってしまったのだろう コンビネーションの式に変形して通した public class Main { public static void main(String[] args) { final Scan…

結局makeでコケた

cygwin + llvm-gccでSenna+MySQLを試そうとしている。Sennaのソースをダウンロードし./configureを使用としたところ、以下のようなエラーメッセージが出た。 configure: error: no acceptable ld found in $PATH適当にググッたところ、海外の掲示板でそれっ…

貪欲法 葉巻が作れなくなるまで順番に作っていく 一本ずつシミュレーションするとTLE public class Main { public static void main(String[] args) { final Scanner cin = new Scanner(System.in); while (cin.hasNextInt()) { long n = cin.nextLong(); fi…

作られる数の集合を見ていくとパターンがあることに気付く JavaとCで速度がだいぶ違うが、そういうものなのだと思う public class Main { public static void main(String[] args) { final Scanner scanner = new Scanner(System.in); final int S = scanner…

metaballの値を順に足していき、総和の半分と等しくなればそれが答え import java.util.Scanner; public class Main { public static void main(String[] args) { final Scanner cin = new Scanner(System.in); for (int N; (N = cin.nextInt()) != 0;) { fi…

時間制限が緩いので条件を丁寧に書けば通る static int type[256]; bool check(const string& s) { vector<int> types; for (string::const_iterator it = s.begin(), itEnd = s.end(); it != itEnd; ++it) { types.push_back(type[*it]); } if (find(types.begin</int>…

三次元の幅優先探索 広げる方向は6方向 static const int dx[] = {1, -1, 0, 0, 0, 0}; static const int dy[] = {0, 0, 1, -1, 0, 0}; static const int dz[] = {0, 0, 0, 0, 1, -1}; int main() { for (int X, Y, Z; cin >> X >> Y >> Z && (X || Y || Z);…

300x300なので幅優先探索で十分 広げる方向は8方向 static const int dx[] = {2, 2, 1, 1, -1, -1, -2, -2}; static const int dy[] = {1, -1, 2, -2, 2, -2, 1, -1}; int main() { int numberOfTests; cin >> numberOfTests; for (int testIndex = 0; testI…

幅優先探索 広げる方向は8方向 static const int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1}; static const int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1}; int main() { for (int height, width; cin >> height >> width && (height || width); ) { static char maze[1…

数列の公式を当てはめるだけ 正負で式が微妙に変わる点に注意する 正負で分けずに解く方法もあったはず・・・ ll myabs(ll i) { return i >= 0 ? i : -i; } ll calc(ll i) { const ll sign = i / myabs(i); i = myabs(i); const ll value = (i * (i + 1)) / …

動的計画法 横方向でここからここまでの和というテーブルを作り、 縦方向でそれらを足し合わせる O(N^4) int main() { int N; scanf("%d", &N); for (int row = 0; row < N; ++row) { for (int column = 0; column < N; ++column) { int value; scanf("%d", …

制限時間が緩いので全探索を定数レベルで高速化すれば通る bool compareByConditions(const string& lh, const string& rh) { return lh.size() != rh.size() ? lh.size() > rh.size() : lh > rh; } string toString(int value, int length) { char buffer[1…

左/右に降りる場合のビットの変換にパターンがある それをそのまま書けば良い ビット演算のみで一行で書くこともおそらく出来る int main() { int numberOfTestCases; cin >> numberOfTestCases; for (int caseIndex = 0; caseIndex < numberOfTestCases; ++…

動的計画法 パスカルの三角形を定義通り書けば良い int main() { ll dp[128][128]; memset(dp, 0, sizeof(dp)); dp[0][0] = 1; for (int n = 1; n < 128; ++n) { for (int m = 0; m < 128; ++m) { if (m) { dp[n][m] += dp[n - 1][m - 1]; } dp[n][m] += dp[…

動的計画法 直前のマスの最適解を用いて現在のマスの最適解を求める 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>…

素直に実装するのみ 問題文を読み間違えて1WA int main() { int caseIndex = 0; for (int S, T, M; cin >> S >> T >> M && (S || T || M); ) { int counter[128][3]; memset(counter, 0, sizeof(counter)); for (int s = 0; s < S; ++s) { int Id; cin >> Id…

2点をfor文で回す 対応する残り2点が存在するかどうかをlog(N)で調べる int main() { for (int n; cin >> n && n; ) { set<pair<int, int> > positionSet; vector<pair<int, int> > positions; for (int i = 0; i < n; ++i) { int x, y; cin >> x >> y; positions.push_back(make_pair(x, y</pair<int,></pair<int,>…

全部同じ高さになるように移動するのみ int main() { int caseIndex = 0; for (int n; cin >> n && n; ) { vector<int> heights; int sum = 0; for (int i = 0; i < n; ++i) { int height; cin >> height; heights.push_back(height); sum += height; } const int</int>…