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つ どの状態においても、そのノードより下…