D - へんてこ辞書 概要 N頂点N辺の有効グラフとN項の数列bが与えられる。各頂点から出る辺は1本であり、b[i]は頂点iから出ている辺を表す。 頂点aからスタートし、k回移動した後にいる頂点番号を答えよ。 制約 2 ≦ N ≦ 10^5 1 ≦ k ≦ 10^100000 共通方針 この…

D - Flipping Signs 概要 N項の数列Aが与えられる。「1からN-1までの番号iを選び、A[i-1]とA[i]に-1を乗算する」という操作を好きなだけ行う。操作終了後の数列をBとするとき、Bの和の最大値を求めよ。 制約 2 ≦ N ≦ 10^5 -10^9 ≦ A[i] ≦ 10^9 方針① いろい…

C - GCD on Blackboard 概要 N項の数列Aが与えられる。この数列のうち1項を好きな数字に変えて数列全体のGCDを計算する（数字を変えなくてもよい。）。GCDの最大値を求めよ。 制約 1 ≦ N ≦ 2*10^5 1 ≦ A[i] ≦ 10^9 全体の方針 数字を変更する項を固定する。 …

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 方針 最終的に、奇数長の経…

D - Handstand 方針 反転する区間は0が続いている区間のみを考えてよい。 すると問題は、0が続いている区間をK区間ずつ1に反転していって、1が連続する区間が最大になるものを求めればよい。これは尺取り法でO(N+K)で求めることが出来る。 感想 下記ブログを…

B - 花束 概要 赤い花がR本、青い花がB本ある。次の2種類の花束を好きなだけ作るとき、2種類の花束の合計の個数の最大値を求めよ。 赤い花がx本、青い花が1本の花束 赤い花が1本、青い花がy本の花束 制約 1 ≦ R, B ≦ 10^18 2 ≦ x, y ≦ 10^9 方針 2分探索を使…

D - Cake 123 概要 X項の数列A、Y項の数列B、Z項の数列Cがある。 A、B、Cからそれぞれ1項ずつ取り出して和を求めるとき、その和が大きい順にK個出力せよ。 制約 1 ≦ X, Y, Z ≦ 1000 1 ≦ K ≦ min(3000, X * Y * Z) 1 ≦ Ai, Bi, Ci ≦ 10^10 方針 Ai + Bj + Ck…

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…

D - Modulo Operations 概要 N項の数列Sと整数Xが与えられる。Xは黒板に書いてある。 N!通りあるSの順列のそれぞれについて、黒板に書いてある数をmod S[i] して黒板に書き直すことを繰り返してゆき、最後に黒板に残った数字を足してゆく。合計を求めよ。 (m…