ソースコード int main() { int t, n; scanf("%d%d", &t, &n); set<int> pos; rep(i, n) { int x; scanf("%d", &x); pos.insert(x); } const int inf = ten(9) + 100; pos.insert(-inf); pos.insert(inf); int res = 0, p = 0; ll past = 0; for (;;) { set<int>::iter</int></int>…

解法 状態が(場所, 最後に使ったカード)のdp ソースコード int min_ascending(const int* c, int n) { const int inf = ten(8); int dp[3 * ten(4) + 100][3]; // (pos, last card) erep(i, n) rep(j, 3) dp[i][j] = inf; dp[0][0] = 0; rep(i, n) rep(j, 3)…

bfs ソースコード int main() { int m; scanf("%d", &m); const int inf = ten(4); int dest_time[333][333]; const int w = 333, h = 333; rep(i, h) rep(j, w) dest_time[i][j] = inf; while (m--) { int x, y, t; scanf("%d%d%d", &x, &y, &t); chmin(des…

全ての組みを全探索 ソースコード int main() { int n, x[222], y[222]; scanf("%d", &n); rep(i, n) scanf("%d%d", x + i, y + i); set<pint> slope; rep(i, n) rep(j, i) { int dx = x[i] - x[j], dy = y[i] - y[j]; int g = __gcd(dx, dy); dx /= g, dy /= g; s</pint>…

解法 簡単のために与えられる区間[s, e]で重なっているものは1つの区間とします (s, e)にはスプリンクラーの範囲の端は置けませんまず始めに思いつく解法は以下のようなdpです [0, i]までスプリンクラーでカバーするときの最小値 dp[i] = min{dp[j] + 1 ; i …

はるだけ int main() { int n, m; while (~scanf("%d%d", &n, &m)) { Dinic<int> d(m); while (n--) { int s, e, c; scanf("%d%d%d", &s, &e, &c); --s, --e; d.add_edge(s, e, c); } printf("%d\n", d.max_flow(0, m - 1)); } }</int>

ライブラリ貼るだけ マルチテストケースという罠 int main() { int n, m; while (~scanf("%d%d", &n, &m)) { BipatiteGraph g(n, m); rep(i, n) { int s; scanf("%d", &s); while (s--) { int a; scanf("%d", &a); --a; g.add_edge(i, a); } } printf("%d\n"…

vector<int> arr() { int a; scanf("%d", &a); vector<int> res; while (a > 0) res.pb(a % 10), a /= 10; return res; } int main() { vector<int> a = arr(), b = arr(); int res = 0; rep(i, a.size()) rep(j, b.size()) res += a[i] * b[j]; printf("%d\n", res); }</int></int></int>

書くだけ int main() { int m, t, c[3]; scanf("%d%d", &m, &t); rep(i, 3) scanf("%d", c + i); int cost[3] = { c[0] + c[2], 2 * c[1], c[2] + c[0] }; const char* in = "ufd"; int dis = 0; int res = 0; rep(i, t) { char c[33]; scanf("%s", c); dis …

解法 1と2の境界を全探索 変更する必要があるカードは累積和を取ってO(1)で計算 ソースコード int main() { int n; int d[3 * ten(4)]; scanf("%d", &n); rep(i, n) scanf("%d", d + i); int one[3 * ten(4) + 100], two[3 * ten(4) + 100]; two[0] = 0; rep…

解法 次数が1のノードから見ていき、まだ条件を満たしていない場合は隣接ノードに基地局を設置していく ソースコード int main() { const int M = ten(5) + 100; static vector<int> e[M]; static int degree[M]; int n; scanf("%d", &n); if (n == 1) { puts("1"</int>…

解法 適当なノードをルートにして、tree dp 各ノードが取る状態はinstall(基地局が設置されている), ok(子のノードの少なくとも1つに基地局が設定されている), ng(子のノードに基地局が設定されているものがない)の3つ どの状態においても、そのノードより下…

解法 二分探索 + bfs 自分で支払う上限で二分探索する 判定方法は上限より大きい辺のコストを1、上限以下の辺のコストを0としたグラフ上でbfs コストk以下で到達できればok const int inf = ten(9); int n, p, k; vector<pint> e[1024]; bool bfs(int pay_upper) {</pint>…

状態が(経過時間, exaustion)のdp int main() { int n, m; int d[ten(4)]; scanf("%d%d", &n, &m); rep(i, n) scanf("%d", d + i); static int dp[ten(4) + 1000][512]; rep(i, n) { erep(j, m) { // run chmax(dp[i + 1][j + 1], dp[i][j] + d[i]); // rest…

解法 入力から有向グラフを作る。AがBに勝ったという情報からA -> Bに辺を張る このグラフ上でiからjに到達可能ならば、iはjに勝てるn cows中でiがkthの時、iは(n - k)cowsにwin and iは(k - 1)cowsにlose 順位が決定できる場合、win + lose == (n - k) + (k…

問題の解釈をがんばる int main() { int n, t; scanf("%d%d", &n, &t); if (n == 1) { while (t--) puts("1"); return 0; } pint song[2000]; rep(i, n) { song[i].second = -(i + 1); scanf("%d", &song[i].first); } while (t--) { sort(song, song + n, g…

やるだけ int main() { int n, k; scanf("%d%d", &n, &k); pint a[5 * ten(4)], b[5 * ten(4)]; rep(i, n) { scanf("%d%d", &a[i].first, &b[i].first); a[i].second = b[i].second = i + 1; } sort(a, a + n, greater<pint>()); sort(b, b + n, greater<pint>()); bool </pint></pint>…

二分探索する int main() { int n, s; scanf("%d%d", &n, &s); int l[2 * ten(4)]; rep(i, n) scanf("%d", l + i); sort(l, l + n); int res = 0; rep(i, n) res += upper_bound(l, l + i, s - l[i]) - l; printf("%d\n", res); }

本番の結果 xoo--- 249位 1808 -> 1758 Aにハマったまま終了(´・ω・`) A Cinema 解法 各映画のfavorite actorsの上限と下限を求めて、後は題意通りに実装 ソースコード int main() { #ifdef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output…

解けるまで 2^25のdp(char dp[1 枝狩り + unordered_mapなどゴリ押ししようとするがMLE取れず 2^25以上の配列を確保して通っている人がいるのに謎実は工夫すれば2^25の状態のdpで通せる 求めたい最大の答えは16未満なので、1つの状態に対して4bitあれば十分 …

Easy GreatFairyWar やるだけ int GreatFairyWar::minHP(vector <int> dps, vector <int> hp) { int dame = 0; for (int i = 0, t = 0; i < dps.size(); ++i) { t += hp[i]; dame += dps[i] * t; } return dame; } Medium IncubatorEasy n int IncubatorEasy::maxMagic</int></int>…

とりあえず作って長い間放置してました コード貼っつけるだけでもがんばって書いていきたい

TopCoder, Codeforces, AOJなどで解いた問題の解法を書いていく予定