AtCoder

AtCoder Beginner Contest 049: D - 連結

問題 問題文 https://atcoder.jp/contests/abc049/tasks/arc065_b 問題概要 頂点数が n の無向グラフが与えられる. 2つの種類の辺があり, それぞれ M本の辺, L本の辺がある. 1種類のみの辺を使ったとき, 各頂点からいずれの種類の辺のみを使ってもたどり着け…

AtCoder Beginner Contest 098: D - Xor Sum 2

問題 問題文 https://atcoder.jp/contests/abc098/tasks/arc098_b 問題概要 長さ N の整数列 A が与えられる. 次の条件を満たす整数 l, r (1 <= l <= r <= N) の組の個数を求めよ. 制約 入力は整数 解答例 指針 尺取法 解説 条件を満たすのはどのようなとき…

AtCoder Grand Contest 023: A - Zero-Sum Ranges

問題 問題文 https://atcoder.jp/contests/agc023/tasks/agc023_a 問題概要 長さ N の整数列 A が与えられる. A の空でない連続する部分列のうち, 総和が 0 となるものの個数を求めよ. 制約 解答例 指針 連続する部分列の総和 => 累積和 解説 初項を 0 とし,…

AtCoder Beginner Contest 107: D - Median of Medians

問題 問題文 https://atcoder.jp/contests/abc107/tasks/arc101_b 問題概要 長さ N の数列 a が与えられる. 区間 [l, r] (1≤l≤r≤N) について, a のすべての連続部分列の中央値を各々求め, その中央値を並べ新たに数列 m を作る. このとき m の中央値を求めよ…

AtCoder Beginner Contest 108: D - All Your Paths are Different Lengths

問題 問題文 https://atcoder.jp/contests/abc108/tasks/arc102_b 問題概要 整数 が与えられる. 以下の条件を満たす有向グラフをひとつ構成せよ. グラフは多重辺を含んでもよい. 条件を満たす有向グラフの存在は保証されている. 頂点数 が 20 以下で全ての頂…

AtCoder Beginner Contest 109: D - Make Them Even

問題 問題文 https://atcoder.jp/contests/abc109/tasks/abc109_d 問題概要 縦 H, 横 W のマス目がある. マス (i, j) には 枚のコインがある. コイン 1 枚を上下左右のいずれかに移動するという操作を各マスについて 1 回以下行って偶数枚のコインが置かれて…

AtCoder Beginner Contest 110: D - Factorizatiom

問題 問題文 https://atcoder.jp/contests/abc110/tasks/abc110_d 問題概要 正整数 N, M が与えられる. となるような正整数からなる長さ N の数列 a が何通りあるかを 109+7 で割った剰余の形で答えよ. 制約 解答例 指針 重複組合せ 解説 まず M がある素数 …

AtCoder Beginner Contest 111: D - Robot Arms

問題 問題文 https://atcoder.jp/contests/abc111/tasks/arc103_b 問題概要 N 個座標 (X_i, Y_i) が与えられる. 正整数 d_1, d_2, d_3, .. d_m を用意し, それぞれに対して (d_i, 0) (-d_i, 0) (0, d_i) (0, -d_i) のいずれかを加算することで, (X_i, Y_i) …

AtCoder Beginner Contest 112: D - Partition

問題 問題文 https://atcoder.jp/contests/abc112/tasks/abc112_d 問題概要 整数 N, M が与えられる. 各項の和が M となる 長さ N の数列 a のうち, a の最大公約数の最大値を求めよ. 解答例 指針 M の約数を考える 解説 の最大公約数を とすると, 数列 の各…

AtCoder Beginner Contest 113: D - Number of Amidakuji

問題 問題文 https://atcoder.jp/contests/abc113/tasks/abc113_d 問題概要 あみだくじを作る. まず W 本の平行な縦線を引き, 次にそれらを繋ぐ横線を引いていく. それぞれの縦棒の長さは H + 1 であり, 横線の端点となれるのは上から 1, 2, 3 ... H の位置…

AtCoder Beginner Contest 114: D - 756

問題 問題文 https://atcoder.jp/contests/abc114/tasks/abc114_d 問題概要 整数 が与えられる. の約数のうち, 約数がちょうど 75 個となる数はいくつあるか. 解答例 指針 N! を素因数分解する 解説 約数がちょうど 75個となる整数とは より p, q, r を異な…

AtCoder Beginner Contest 115: D - Christmas

問題 問題文 https://beta.atcoder.jp/contests/abc115/tasks/abc115_d 問題概要 多次元バーガーを作る事を考える. 多次元バーガにはレベルがあり, レベル L バーガー (Lは 0 以上の整数) は以下のように定義される. L = 0 : パティ 1 枚のみで構成される. L…

ABC054: C - One-stroke Path

問題 問題文 https://beta.atcoder.jp/contests/abc054/tasks/abc054_c 問題概要 頂点数: N , 辺の数: M の重みなし無向グラフが与えられる. ただし, このグラフは自己ループや二重辺を持たない. 頂点 1 を始点として, 全ての頂点を1度だけ通る経路は何通り…

ABC084: D - 2017-like Number

問題 問題文 https://abc084.contest.atcoder.jp/tasks/abc084_d 問題概要 N も (N+1) / 2 も素数であるという条件を満たす奇数 N を 2017に似た数 とする。 個のクエリが与えられ, 各クエリでは奇数 が与えられる。 区間 で 2017に似た数となる奇数の個数を…

ABC070: D - Transit Tree Path

問題 問題文 https://beta.atcoder.jp/contests/abc070/tasks/abc070_d 問題概要 頂点数が N の重み付き無向グラフが与えられる。 与えられるグラフは辺の数が N−1 本で閉路のない連結グラフ, すなわち木構造となっている。 頂点 から 頂点 K を経由しつつ, …