AtCoder最大値, 二分探索, 最小値

問題概要

問題へのリンク

風船に 1 から N までの番号が付けられていて、風船 i (1≦i≦N) は競技開始時に高度 \(H_i\) のところにあり、1 秒経過するにつれて高度が \(S_i\) だけ増加する。

AtCoder400点, 二分探索, K番目, 2つの積

ARC037 億マス計算 の上位問題です。

問題概要

問題へのリンク

N個の整数 \(A_1, A_2, A_3, \cdots, A_n\) がある。
2つを選んでその積を \(\frac{N(N-1 ...

AtCoderDP, 500点, 桁ごと, お釣り, 硬貨

問題へのリンク

問題概要

\(1, 10, 10^2, 10^3, \dots, 10^{(10^{100})}\) の紙幣で金銭のやり取りをする。

N 円払う時、支払うのに使う紙幣の枚数と、お釣りでもらう紙幣の ...

AtCoder二項係数, 600点, 二次元, 区間和

問題へのリンク

問題概要

2次元の平面上で、以下のように関数 f(r,c) を定義する。

f(r,c) := (0,0)から(r,c)までの経路の個数

この時、以下を計算せよ。ただし、\(10^9+7 ...

AtCoder動的計画法, 数え上げ, DP, 500点, 桁DP, 場合分け

問題へのリンク

問題概要

1 以上 N 以下の整数で、0 でない数字がちょうど K 個あるものの個数を求めよ。

制約

\begin{align}
&1 \leq N \leq 10^{100} \\ ...

AtCoder操作, 最大公約数, gcd, 不変量, 最大値, 500点, 約数

問題へのリンク

問題概要

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

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

AtCoder有向グラフ, 閉路, DAG, 有向非巡回グラフ, 半順序, 500点

問題へのリンク

問題概要

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

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

AtCoderbit演算, bit全探索, 包除原理, , 余事象, 制約, 600点

問題へのリンク

問題概要

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

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

AtCoder数え上げ, 桁の数が等しい, 400点

問題へのリンク

問題

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

制約

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

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

問題へのリンク

問題

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

制約 ...