[AtCoder] ABC136 E – Max GCD (500点)

問題へのリンク 問題概要 N 個の整数列 \(A_1, A_2, \cdots, A_N\) に、以下の操作をK回まで行う。これら全てはある数の倍数となるが、その数の最大値を求め...

AtCoder ABC 139 E – League

問題へのリンク 問題概要 N人の選手がいる。各選手は1日1試合のみできる。総当たり戦を行う時、最短で何日かかるか？ ただし、i 番目の選手は \(A_{i, 1}, A_{i, ...

AtCoder ABC 152 F – Tree and Constraints

問題へのリンク 問題概要 N頂点の木がある。辺を白か黒で塗るとき、以下のような制約をM個満たすような塗り方は何通りか？ 制約 i：頂点 \(u_i\) と頂点 \(v_i\) を...

AtCoder ABC 152 F – Tree and Constraints

問題へのリンク 問題概要 N頂点の木がある。辺を白か黒で塗るとき、以下のような制約をM個満たすような塗り方は何通りか？ 制約 i：頂点 \(u_i\) と頂点 \(v_i\) を...

動的計画法（Dynamic Programming）

動的計画法とは、小さい部分問題を計算して記録しておき、より大きい問題を計算する際に利用する手法のことです。 普通に計算すると同じ計算を何度も繰り返してしまい非効率であるようなアル...

AtCoder ABC152 D – Handstand 2

問題へのリンク 問題 N以下の整数の組（A, B）について、Aの先頭とBの末尾の数が等しく、Aの末尾とBの先頭の数が等しいのは何通りあるか？ 制約 $$1\leq N \leq ...

AtCoder ABC152 D – Handstand 2

問題へのリンク 問題 N以下の整数の組（A, B）について、Aの先頭とBの末尾の数が等しく、Aの末尾とBの先頭の数が等しいのは何通りあるか？ 制約 $$1\leq N \leq ...

貪欲なアルゴリズム（greedy）

貪欲なアルゴリズムとは以下のような性質を持つアルゴリズムのことを言います。 その場での最善の手を選ぶことを繰り返す 貪欲法を用いたアルゴリズムは、実装が簡単な上に応用範囲が広いの...

AtCoder キーエンスプログラミングコンテスト2020 D – Swap and Flip

問題へのリンク 問題 表が\(A_i\)、裏が\(B_i\)、と書かれた\(N\)枚のカードがある。「隣り合う2枚を選択して、入れ替えて裏返す」という操作をして、カードの並びが広...

互いに素な集合(Disjoint-set・Union-find)

2つの集合が共通する要素を持たない時に「互いに素」であると言い、このような集合の集まりを「素集合系」などと言います。 素集合系の例 素集合系は、いくつかの木構造を用いることで管理...

AtCoder ABC 135 D – Digits Parade

問題へのリンク 問題 一部が ? で与えられる数字の文字列 S について、13で割って5余る数で考えられる物は何通りあるか。 答えを 1e9+7 で割った余りで答えよ。 制約 $...