さらっとだけ備忘録。 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 =…

Block | Aizu Online Judge 特に難しいことはないけど、入力ケースが多いので少しめんどくさい。 int mp[105][105]; bool visited[105][105]; int w, h; int xs, ys; int xg, yg; int n; int col; int dx[]={-1,1,0,0}; int dy[]={0,0,1,-1}; void solve(int…

島の数 | Aizu Online Judge 教科書的なDFSの問題なんだが、入力ケースの終わりがちょっと特殊だった。 Patisserie | Aizu Online Judgeを彷彿とさせる。。 bool visited[13][13]; string mp[13]; int dx[]={0,0,1,-1}; int dy[]={1,-1,0,0}; void solve(int…

整数の和 | Aizu Online Judge こちらも玉に引き続き、シンプルに全通り試してみる。 int n, s; int solve(int now, int left, int sum) { if (left == 0) { return sum == s; } if (now > 9) return 0; int res = 0; res+=solve(now+1, left-1, sum+now); r…

玉 | Aizu Online Judge シンプルな深さ優先探索。全通り試してOK。 int tama[11]; bool solve(int i, int n) { if (i == 10) { int al=-1, bl=-1; for (int j = 0; j < 10; j++) { if ((1<

ほぼ1ヶ月ぶりの更新か...。久しぶりすぎてTopCoderの提出法忘れていた...。 BITかなと一瞬思ったが、リンゴを1とおくと簡単にサブリストのリンゴの数を計算できるので、事前に合計を計算してから単純に左端、右端を引いたり足したりしていくことにした。 cl…

Lupin The 4th | Aizu Online Judge 巡回セールスマン問題。経路復元が必要。 経路復元は、それ用に配列をもう一つ用意しておいて、最短の移動順序を記録しておく。 double dp[100000][20]; int pos[100000][20]; int n; int kura[20], d[20], sen[20]; doub…

Patisserie | Aizu Online Judge 巡回セールスマン問題。 dp[すでに並べたケーキの集合][最後に置いたケーキ]としてメモ化再帰で解く。 グラフはG[ケーキv][ケーキu]として、ケーキvの次にケーキuを置く時、どれほど長さが増えるかで事前に作っておく。 同じ…

Russian Dolls DP。最長増加部分列。 int main() { while (1) { vector< pair<int, int> > vp; int dp[205]; int n; cin >> n; if (n == 0) break; for (int i = 0; i < n; i++) { int h, r; cin >> h >> r; vp.push_back(pair<int, int>(h, r)); } int m; cin >> m; for (int i </int,></int,>…

At Boss's Expense 一発で書けた。素数とナップザック問題。 bool dp[35][1000005]; bool pt[1000005]; int main() { memset(pt, 1, sizeof(pt)); pt[0] = 0; pt[1] = 0; for (int i = 2; i * i < 1000005; i++) { if (pt[i]) { for (int j = i*2; j < 10000…

泥棒 | Aizu Online Judge int main() { int cas = 1; while (1) { int N, W; int v[1005], w[1005], dp[1005][1005]; cin >> W; if (!W) break; cin >> N; for (int i = 0; i < N; i++) { char c; cin >> v[i] >> c >> w[i]; } memset(dp, -1, sizeof(dp));…