2020年1月26日AtCoder操作, 最大公約数, 不変量, 最大値, 500点, 約数

問題へのリンク

問題概要

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

操作:\(A_1, A_2, ...

2020年1月25日AtCoder有向グラフ, 閉路, DAG, 有向非巡回グラフ, 半順序, 500点

問題へのリンク

問題概要

N人の選手がいる。各選手は1日1試合のみできる。総当たり戦を行う時、最短で何日かかるか?

ただし、i 番目の選手は \(A_{i, 1}, A_{i, 2}, \ldots, A_{i, ...

2020年1月25日AtCoderbit演算, bit全探索, 包除原理, , 余事象, 制約, 600点

問題へのリンク

問題概要

N頂点の木がある。辺を白か黒で塗るとき、以下のような制約をM個満たすような塗り方は何通りか?

制約 i:頂点 \(u_i\) と頂点 \(v_i\) を繋ぐパス上に、黒く塗られた辺が1つ ...

2020年1月19日AtCoder数え上げ, 桁の数が等しい, 400点

問題へのリンク

問題

N以下の整数の組(A, B)について、Aの先頭とBの末尾の数が等しく、Aの末尾とBの先頭の数が等しいのは何通りあるか?

制約

$$1\leq N \leq 2 \times 10^5$$

2020年1月19日AtCoder動的計画法, bit全探索, BIT, bitDP, パリティ, 最小回数, 操作, 700点

問題へのリンク

問題

表が\(A_i\)、裏が\(B_i\)、と書かれた\(N\)枚のカードがある。「隣り合う2枚を選択して、入れ替えて裏返す」という操作をして、カードの並びが広義単調増加になる最小回数を求めよ。

制約 ...

2020年1月17日AtCoder剰余, 動的計画法, 400点, 数字の文字列, 桁ごと

問題へのリンク

問題

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

制約\(1 \leq |S| \leq ...

2019年12月3日AtCoder順列, 全探索, 300点

問題

平面上でN個の座標が与えられる。全ての点を1回ずつ通るような動き方は\(N!\)通りあるが、これらの総移動距離の平均を求めよ。

元の問題: C – Average Length

解き方

二通りの方 ...

2019年11月30日AtCoderグラフ, , 400点, BFS, 辺彩色

問題

木構造について、頂点から見た時に自身から伸びる枝に重複が無いように色を塗る。使う色の数の最小値はいくつか?

問題:D – Coloring Edges on Tree

(木構造はグラフの一種と捉 ...