さらっとだけ備忘録。 N以下の全ての素数を調べる。 その素数の累乗数表を持つ [2]のうち、N以下で最大のもの * 2を返す。 N以下の最大の素数の累乗数をxとする。 xの2倍がN以下であると仮定する。 ベルトラン＝チェビシェフの定理（今知った）より、 「自然…

#include <iostream> #include <string> using namespace std; int a[5] = {10, 20, 20, 40, 60}; int main() { cout << lower_bound(a, a + 5, 0) - a << endl; # 0 cout << lower_bound(a, a + 5, 20) - a << endl; # 1 cout << lower_bound(a, a + 5, 100) - a << endl; # 5</string></iostream>…

1が立ってる最も下のビットは x & -xでとれる

A: 深さ優先探索 - AtCoder Typical Contest 001 | AtCoder B: Union Find - AtCoder Typical Contest 001 | AtCoder C: 高速フーリエ変換 - AtCoder Typical Contest 001 | AtCoder Cの高速フーリエ変換だけ分からなかった。。高速フーリエ変換ちゃんと勉強…

初yukicoder参加。 No.221 犯罪都市 - yukicoder No.222 引き算と足し算 - yukicoder No.223 1マス指定の魔方陣 - yukicoder 1,2はただの実装。3は分からなくてそのまま時間切れとなってしまった。 犯罪都市 int main() { int N; cin >> N; N *= 100; double…

最長増加部分列 | 動的計画法 | Aizu Online Judge int a[1000*100+5] = {}; int main() { int n; cin >> n; fill(a, a + 1000*100+5, 1000*1000*1000*2); for (int i = 0; i < n; i++) { int t; cin >> t; *(lower_bound(a, a + 1000*100+5, t)) = t; } cou…

Knapsack Problem | Aizu Online Judge Combinatorial - 0-1 Knapsack Problem - アルゴリズムのメモ帳 とほぼ同じ問題。 続けて解いたので、ちょっとずるして上で解いたものを再利用した。 int main() { int N, W; cin >> N >> W; int v[105], w[105]; for …

ナップザック問題 | 動的計画法 | Aizu Online Judge シンプルなナップザック問題。 int main() { int N, W; cin >> N >> W; int v[105], w[105]; for (int i = 0; i < N; i++) cin >> v[i] >> w[i]; int dp[105][10005]; memset(dp, -1, sizeof(dp)); int r…

コイン問題 | 動的計画法 | Aizu Online Judge DPコースなるものを発見したので解いていこうと思う。 貪欲法でいける？と思ったが、コインの額面が半端なのでDPで解いていく。 int main() { int n, m; cin >> n >> m; int coins[25]; int dp[25][50005]; for…

Bingo | Aizu Online Judge 状態数をうまく削減しないといけない。 int N, M, S; int dp[50][3005]; int mod = 100000; int main() { while (1) { cin >> N >> M >> S; if (N == 0) break; memset(dp, 0, sizeof(dp)); N *= N; dp[0][0] = 1; for (int i = 1…

POJ 2441 : Arrange the Bulls 通ったんだけどこれでいいのかな。。 int N, M; int cows[30][30] = {}; int memo[(1 << 20) + 1] = {}; int solve(int i, int S) { if (memo[S] != -1) { return memo[S]; } if (i == N) return 1; int res = 0; for (int j =…