参考にしたのは以下の@rng_58さんによるツイートです 導出が自明ではないのでメモ（少なくとも僕にとっては）ideone.com/SOygoW これで 1 から N までの逆元が O(N) でもとまります— rng_2さん (@rng_58) 2013年3月15日 @komaki__ i * (MOD/i) = MOD - MOD%i…

AOJで他の解法投げると見れなくなると思うので，とりあえずコード貼っておきます 解法 直方体とその領域で重なっている数を持っておく． ソースコード struct Rect { int v[3][2]; ll calc_area() const { ll res = 1; rep(d, 3) res *= v[d][1] - v[d][0]; …

まだジャッジが終わっていないので、間違っていたらごめんなさい Beautiful strings 解法 ソートするだけ ソースコード どっかいった Balanced Smileys 解法 適当に探索。メモ化してやると、状態数はO(|s|^2)なので余裕で間に合う ソースコード map<string, bool> dp; bool</string,>…

解法 あるフェンスが利用可能である条件は、フェンスを張ったときに左右のどちらか一方のみにペンギンが存在するような場合である。（ここでは、反時計回りにフェンスを張っていくので、左側に全てのペンギンがいる場合に利用可能とする。）利用可能であるフ…

解法 区間dp dp[i][j] = [i, j]の最大マッチング ソースコード int n; string c; int dp[55][55]; int dfs(int l, int r) { if (l >= r) return 0; else if (dp[l][r] != -1) return dp[l][r]; int res = 0; for (int i = l + 1; i <= r; ++i) if (c[l] == c…

解法 右下にある場合0 一番下の行 or 一番右の列にある場合1 それ以外の場合は1回の操作で↑の状態にできるので2 ソースコード int PenguinTiles::minMoves(vector <string> tiles) { int h = tiles.size(), w = tiles[0].size(); if (tiles[h - 1][w - 1] == '.') re</string>…

ハル研究所プログラミングコンテスト2012に参加しました。 応募締め切り時は総合9位でした。（最後に最適解が出ないコードを出してしまって少し不安、最大スコアのコードで順位付けてくれるんだろうか）どのような方針を取ったか書いていきます。まず、問題…

ソースコード int main() { int pf[22222]; CL(pf, -1); for (int i = 2; i <= 20000; ++i) if (pf[i] == -1) for (int j = i; j <= 20000; j += i) pf[j] = i; int res = 1; int n; scanf("%d", &n); while (n--) { int a; scanf("%d", &a); if (pf[a] > pf…

ソースコード int main() { int n, s; scanf("%d%d", &n, &s); int a[33][33]; rep(j, n) erep(i, j) { a[i][j] = s; if (++s == 10) s = 1; } rep(i, n) { rep(j, i) printf(" "); for (int j = i; j < n; ++j) printf("%d%c", a[i][j], j + 1 == n ? '\n' …

ソースコード int w, h; char c[1024][100]; int dfs(int x, int y) { if (!in_rect(x, y, w, h) || c[y][x] != '*') return 0; c[y][x] = '.'; int s = 1; rep(i, 4) s += dfs(x + dx[i], y + dy[i]); return s; } int main() { cin >> w >> h; rep(i, h) c…

大きい桁からその桁が必要かを上限下限から判断する方法でやろうとした が、n進数(n > 1)とほとんど同じやり方でできるみたいなのでそうした 参考: wikipedia:en:Negative_base ソースコード vector<int> to_negabase(ll n, int base) { vector<int> res; if (n == 0) </int></int>…

解法 Dはスペースの個数 / 牛の間隔の個数で求められる Dの計算時の余りはD + 1にできる回数。問題に明記されてない気がするが、この回数分D + 1を使う必要がある最小コストの計算はdpをする dp[i][j] = 牛iを位置(i + D * i + j)に置いたときの最小コストそ…

解法 凸 or 平になっている箇所を爆破する ソースコード int main() { const int M = 5 * ten(5) + 10; int n, h[M]; scanf("%d", &n); rep(i, n) scanf("%d", h + i + 1); h[0] = h[n + 1] = 0; for (int i = 1; i <= n; ++i) if (h[i - 1] <= h[i] && h[i]…

解法 greedy 左端をflipするかの2通りを試す 位置iが1である場合、iをひっくり返すにはi, i + 1, i + 2をひっくり返す必要があるのでgreedyにやる別解 反転パターンを全探索。bit + 無駄な探索しない高速化をしないとTLEする ソースコード greedy int main()…

解法 月の出費の上限で二分探索 ソースコード int n, m; int money[ten(5) + 100]; bool ok(int month_spend) { int months = 1, spend = 0; rep(i, n) { if (spend + money[i] > month_spend) { ++months; spend = 0; } spend += money[i]; } return months …

問題の意味がなかなかわからなかった 問題概要 ノード数nのDAGが与えられる。入力次数が0のノードからnへのパスを全て列挙する。各辺ごとにいくつのパスに含まれているかを数えたとき、最大のパス数はいくつか。 解法 辺i -> jを含むパス数は、(入力次数0の…

解法 区間dp dp[i][j] = [i, j)をpalindromeにする最小コスト ソースコード int main() { int m, n; string s; cin >> n >> m >> s; const int inf = ten(8); int cost[256]; fill(cost, cost + 256, inf); while (n--) { char c; int add, del; cin >> c >>…

解法 一番上の行のflipの仕方を決めると、flipの仕方は一意に決まるので、一番上の行のflipパターンを全て試す。 蟻本に載ってる問題です ソースコード int h, w, tile[22][22]; int work[22][22], pos[22][22]; int f; void flip(int x, int y) { work[y][x…

解法 まずは、座標圧縮する ビルの開始点、終了点に高さをメモする 座標の小さい点から走査していき、ビルの開始点ではそのビルの高さを集合に加え、終了点では集合から削除する 高さの集合の管理には追加、削除が高速にできるものを使うと良い 追加、削除が…

解法 bfs ソースコード int main() { int n, k; scanf("%d%d", &n, &k); const int inf = ten(7); int d[2 * ten(5) + 100]; fill(d, d + 2 * ten(5), inf); queue<int> q; d[n] = 0; q.push(n); while (!q.empty()) { int p = q.front(); q.pop(); int nd = d[p]</int>…

ソースコード int main() { int n, k, p; scanf("%d%d%d", &n, &k, &p); int m = k / n; vector<int> res; queue<int> deck; rep(i, k) deck.push(i + 1); for (int i = 0; !deck.empty(); ++i %= n) { if (i == n - 1) res.pb(deck.front()); deck.pop(); rep(j, p) {</int></int>…

ソースコード int main() { int n, b, h[2 * ten(4)]; scanf("%d%d", &n, &b); rep(i, n) scanf("%d", h + i); int res = ten(9); rep(s, bin(n)) { int sum = 0; rep(i, n) if (s >> i & 1) sum += h[i]; if (sum >= b) chmin(res, sum - b); } printf("%d\…

ソースコード int main() { int n, b, h[2 * ten(4)]; scanf("%d%d", &n, &b); rep(i, n) scanf("%d", h + i); sort(h, h + n, greater<int>()); int i = 0, sum = 0; while (sum < b) { sum += h[i]; ++i; } printf("%d\n", i); }</int>

解法 SegTree。区間は以下の3つの情報を持つ必要がある。 区間内で最大の連続した空きスペース 区間の左端から連続した空きスペース 区間の右端から連続した空きスペース （実装では、その区間は完全に空きであるか(empty)を持っているが補助的なもの。）こ…

解法 aを昇順にするコストをdpで求める。hはaを昇順にsortしたものとする dp[i + 1][j] = iをh[j]としたときの最小コスト iをh[j]とするためには、i - 1はh[k] (k dp[i + 1][j] = min{dp[i][k] (k aを降順にするコストはaを反転して同じ処理を使うと楽 ソー…

解法 greedy 前1文字しか見ないgreedyでは、BCABのようなケースで、BBACと出力してしまう可能性がある(正しくはBABC) 出力形式にも注意。80文字ごとに改行を入れる必要がある。 ソースコード int main() { int n; string s; scanf("%d", &n); rep(i, n) { ch…

ソースコード int main() { typedef pair<pint, int> P; int n, m, r; static vector<pint> g[ten(6) + 10]; // [start] => (end + r, efficiency) scanf("%d%d%d", &n, &m, &r); rep(i, m) { int s, e, ef; scanf("%d%d%d", &s, &e, &ef); if (e <= n) g[s].pb(pint(min(n, e</pint></pint,>…

ワーシャルフロイド ソースコード int main() { int n, m, t; scanf("%d%d%d", &n, &m, &t); const int inf = ten(8); int w[303][303]; rep(i, n) rep(j, n) w[i][j] = i == j ? 0 : inf; while (m--) { int s, e, h; scanf("%d%d%d", &s, &e, &h); --s, --…

ソースコード bool lake[128][128]; int dfs(int x, int y) { if (!lake[y][x]) return 0; lake[y][x] = false; int res = 1; rep(i, 4) res += dfs(x + dx[i], y + dy[i]); return res; } int main() { int h, w, k; scanf("%d%d%d", &h, &w, &k); while (k…

ソースコード int main() { int k, n; scanf("%d%d", &n, &k); rep(i, k) { int s, t, r; scanf("%d%d%d", &s, &t, &r); int read_minutes = (n + (s - 1)) / s; int rest_times = (read_minutes - 1) / t; printf("%d\n", read_minutes + rest_times * r); }…