競技プログラミング

AOJ2502: B: VOCAL ANDROID

問題 https://onlinejudge.u-aizu.ac.jp/problems/2502 解答例 解説 重さが可変 () の品物から重さがちょうど になるときの価値の総和の最大値を求めると考えれば, 個数制限なしナップザック問題とほとんど同じ問題とみなすことができる. ここでナップザック…

AtCoder Beginner Contest 049: D - 連結

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

Educational Codeforces Round 83: E. Array Shrinking

問題 問題文 https://codeforces.com/contest/1312/problem/E 問題概要 項数 の数列 が与えられる. を満たす組を選び, に置き換えるという操作をできるだけした際, 最終的な数列の長さとして考えられるもののうち最小のものを答えよ. 例 4 3 2 2 3 -> 4 3 3 …

Educational Codeforces Round 83: D. Count the Arrays

問題 問題文 https://codeforces.com/contest/1312/problem/D 問題概要 要素数 の数列 を考える. 各要素は を満たす. 各数列について, 等しい値をもつ要素が, ちょうど1組存在する. 各数列 について, 以下を満たす インデックス が存在する. i番目の前の数列…

AOJ 1180: 繰り返す10進数 / Recurring Decimals

問題 問題文 https://onlinejudge.u-aizu.ac.jp/problems/1180 問題概要 非負の整数 と桁数 が与えられる. 以下の規則を適用し, から をつくる. 整数 を 10進表記し, 桁が足りない場合は上位の桁を0埋めする. 各桁の数字を並び替えてできる数字のうち, 最大…

AOJ 1166: 迷図と命ず / Amazing Mazes

問題 https://onlinejudge.u-aizu.ac.jp/problems/1166 問題文 問題概要 迷路を表すデータが与えられる. 入口から出口までの最短経路の長さを求めよ. 制約 データセット数 : 解答例 指針 BFS 解説 二次元グリッド上の最短経路問題なので幅優先探索(Breadth F…

AOJ 1173: 世界の天秤 / The Balance of the World

問題 問題文 https://onlinejudge.u-aizu.ac.jp/problems/1173 問題概要 丸括弧と角括弧の二種類の括弧を含む文字列が与えられる. 括弧列が整合しているか判定せよ. ただしここで, 括弧列が整合しているとは以下を満たしていることを言う. すべての左丸括弧…

ABC052/ARC067: C - Factors of Factorial

問題 問題文 https://atcoder.jp/contests/abc052/tasks/arc067_a https://atcoder.jp/contests/arc067/tasks/arc067_a 問題概要 整数 N が与えらる. の正の約数の個数を 割った余りを求めよ. 制約 解答例 指針 とすると, 解説 と素因数分解すると, となる. …

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個の数の和…