競技プログラミング

AtCoder Beginner Contest 051: Candidates of No Shortest Paths

問題 問題文 https://atcoder.jp/contests/abc051/tasks/abc051_d 問題概要 頂点数 N, 辺の数 M の重み付き無向グラフが与えられる. ただし, このグラフは自己ループと二重辺をもたず, 連結であるものとする. 任意の 2頂点間のどの最短経路にも含まれない辺…

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度だけ通る経路は何通り…

AOJ 1625: Origami, or the art of folding paper

問題 問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1625&lang=jp 問題概要 幅 n, 高さ m の長方形の紙が与えられる. (n, m は32以下の正整数) 紙を t回折る操作をした後 p 回穴を開ける. (t, p は20 以下の正整数) t 組の d_i, c_i が…

AOJ1618: A Garden with Ponds

問題 問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1618&lang=jp 問題概要 面倒なので省略 解答例 指針 4重ループを回しすべての長方形について考える 解説 長方形の x の範囲 [lx, ry], y の範囲 [ly, ry] に関してループを回しすべて…

AOJ1617: Almost Identical Programs

問題 問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1617&lang=jp 問題概要 2つの文字列が与えられる. 2つが完全に等しければ, IDENTICAL と 2つのプログラム中の対応する文字列定数1つだけが異なるならば CLOSE と それ以外の場合,DIF…

AOJ DPL1: A - Coin Changing Problem

問題 問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_A 問題概要 額面が 円の m 種類の硬貨を使って n 円を支払うときの使用する硬貨の最小枚数を求めよ。 なお各額面のコインは何度でも使用できるものとし, 与えられるコインの額…

POJ1611: The Suspects

問題 問題文 http://poj.org/problem?id=1611 問題概要 n 人の学生とその学生からなる m 個のグループが与えられる。 全ての学生に 0 ~ n−1 の番号が振られており 0 番目の学生に SARS という病気の感染の疑いがある。感染の疑いのある学生と同じグループの…

ABC084: D - 2017-like Number

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

POJ3380: Bridges

問題 問題文 http://poj.org/problem?id=3380 問題概要 頂点数が n の重み付き無向グラフが与えられる。 各頂点は島を表しており, ある島から他の島までの経路は 1 通りしか存在しない。 各島には 1 つの町がある。 町には 1 から n まで番号がつけられてお…

ABC070: D - Transit Tree Path

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

AOJ0030: Sum of Integers

問題 問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0030&lang=jp 問題概要 0 から 9 までの数字から異なる n 個の数を取り出して和が s となる組み合わせの数を求めよ。 例 n = 3, s = 6 のとき 0 ~ 9 までの数字から異なる3個の数の和…