SoundHound Inc. Programming Contest 2018 -Masters Tournament- D - Saving Snuuk(400) D - Saving Snuuk 概要 n頂点m辺の連結無向グラフが与えられ、各辺には2種類のコスト（コストA, コストBと分類）が与えられる。 頂点sから頂点tに移動するコストを考…

CODE FESTIVAL 2017 qualB C - 3 Steps(500) C - 3 Steps 概要 N頂点M辺の連結無向グラフに、「長さがちょうど3の経路をもつ2頂点間に辺を追加する」ということを繰り返す。追加できる辺の最大値を答えよ。 制約 2 ≦ N, M ≦ 10^5 方針 最終的に、奇数長の経…

Union-Find木に関する問題集です。 ATC001 B - Union Find B: Union Find - AtCoder Typical Contest 001 | AtCoder 概要 (Union-Find木そのまま) 解答 Submission #4827269 - AtCoder Typical Contest 001 | AtCoder #include <bits/stdc++.h> #define rep(i,n) for(int i=</bits/stdc++.h>…

ABC085 B - Kagami Mochi (200) B - Kagami Mochi 概要 N項の数列dが与えられ、数列dは鏡餅の直径を表している。 鏡餅iと鏡餅jはdi 鏡餅は何段でも重ねられるものとする。 重ねられる鏡餅の枚数の最大値を答えよ。 制約 1 ≦ N ≦ 100 1 ≦ di ≦ 100 方針 diをs…

CODE THANKS FESTIVAL 2017 C - Factory (300) C: Factory - CODE THANKS FESTIVAL 2017(Parallel) | AtCoder 概要 項の数列が与えられる。から数を回選んでその合計を求めることを考える。ただし、各は一度選ばれるごとにが加算されるものとする。 数を回選…

ABC032 D - ナップサック問題 D - ナップサック問題 概要 0/1ナップサック 制約が3種類 制約 ① ② ③ 方針 実質３問。 ① いわゆる半分全列挙。 荷物を前半分、後半分の２つに分け、それぞれですべての荷物の入れ方で重さの合計、価値の合計のペアをベクトルに…

AOJ DPL1_C ナップザック問題 概要 重さ、価値の荷物が個ある。 重さの合計が以内になるように荷物を選んだ時、荷物の価値の合計の最大値を求めよ。 ただし、同じ荷物を何度選んでもよい。 制約 方針 番目までの荷物を使い、重さが以内であるときの価値の最…

AOJ DPL_1_B 0-1 ナップザック問題 ナップザック問題 | 動的計画法 | Aizu Online Judge 概要 重さ、価値の荷物が個ある。 重さの合計が以内になるように荷物を選んだ時、荷物の価値の合計の最大値を求めよ。 制約 方針 番目までの荷物を使い、重さが以内で…

KUPC2015 A - 東京都 A - 東京都 概要 英小文字からなる文字列を任意の文字間で任意回区切り、 tokyoという文字列とkyotoという文字列を作るとき、合わせて最大で何個作れるか出力せよ。 制約 方針 文字列の前からtokyo、kyotoそれぞれでマッチングしていく…

AOJ 0521 おつり おつり | Aizu Online Judge 概要 1000円以下の買い物金額に対し、1000円支払ったとき お釣りの硬貨の最小枚数を答えよ。 制約 問題のとおり。 方針 金額が大きい硬貨から使ってゆく。 解答 #include <bits/stdc++.h> #define FOR(i,a,b) for(int i=(a);i<(</bits/stdc++.h>…

ABC054 C - One-stroke Path C - One-stroke Path 概要 与えられた自己ループと二重辺を含まない 頂点辺の重み無し無向グラフについて、 頂点1から始めて全ての頂点を1度だけ訪れるパスは何通りあるかを出力せよ。 制約 方針 訪れる頂点の順番を順列で与え、…

ABC007 C - 幅優先探索 C - 幅優先探索 概要 縦マス、横マスの迷路が与えられる。 この迷路の始点から終点までの最短移動数を答えよ。 制約 方針 BFSで計算する。 解答 Submission #3858461 - AtCoder Beginner Contest 007 #include <bits/stdc++.h> #define FOR(i,a,b) fo</bits/stdc++.h>…

ATC001 A - 深さ優先探索 A: 深さ優先探索 - AtCoder Typical Contest 001 | AtCoder 概要 縦、横の迷路が与えられる。始点から終点まで到達できるかを判定せよ。 制約 方針 DFSで行けるマスの記録をつけながら、行けるマスにひたすら行く。 ヒューリスティ…

ARC061 C - たくさんの数式 / Many Formulas (300) C: たくさんの数式 / Many Formulas - AtCoder Regular Contest 061 | AtCoder 概要 数字のからよりなる文字列が与えられる。 この文字列の文字間に好きなだけの記号を挿入した算式を作成し、その和を計算…

1-1 くじ引き JOI 2007 本選 C ダーツ http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0529 概要 数列から重複を許して多くとも4つの項を取り出すとき、 取り出した項の和の最大値を答えよ。 ただし、最大値はを超えてはならない。 制約 方針 、…