Codeforces, 文字列

問題方針

k-balanced な文字列は次の条件を満たします。\( s_i = 0 \) のとき、\(a_i = -1 \) とし、\(s_i = 1 \) のとき、\(a_i = 1 \) とすると、

\begin{eq ...

Codeforces, 貪欲法

問題方針

\( i < j \) のとき、\( a_i \leftarrow a_i – 1 \)、\( a_j \leftarrow a_j + 1\) という操作は \( 0 \) コストでできますが、\( i & ...

Codeforces, 実装

問題方針

順列 \( p \) と異なる順列 \( p^{\prime} \) が \( F(p) = F(p^{\prime}) \) となるような \( p^{\prime} \) を見つけます。

\( F(p) \) ...

AtCoder, 実装

問題方針

敷き詰めパズルのような問題ですが、実際はもっと簡単です。一番左上の行から右に向かって色 \( i \) を \( a_1 \) 個塗っていき、\( W \) 個塗ったあとは、下の行の右端から左に向かって塗っていきます。つまり、 ...

AtCoder, 貪欲法

問題方針

\( p_i = i \) となる \( i \) に対して、\( (p_i, p_{i+1}) = (p_{i+1}, p_i)\) と交換します。このとき、\( p_{i+1} = i \) となるので、交換によるロスはあ ...

Codeforces, 数学

問題方針

\( a_i + (n – 1)a_i = na_i \) となることを利用して、\( 1 \leq i \leq n – 1 \) となる \( i\) について、\( (n-1)a_i \) を加算 ...

Codeforces, 全探索, 数学

問題方針

配列 \( a \) を昇順に並び替えて考えます。自然数 \( x \) を選んだ時のコストを \( f(x) \) とすると、

\

となります。ここで、\( x = (f(1) + a_{n-1})^ ...

Codeforces, 文字列, 貪欲法

問題方針

文字列 \( w \) と自然数 \( x \) が与えられたとき次の条件を満たす文字列 \( w \) を答えます。

\( i – x \geq 0 \wedge w_{i-x} = 1 \) ならば \( ...

AtCoder, 動的計画法

問題方針

マス \( (i, j)\) にあるアイテムの価値を \( g(i, j) \) とします。アイテムがない場合は \( 0 \) とします。次に、マス \( (i, j)\) において \( i \) 行目のアイテムを \( ...

Codeforces, 全探索, 数学, 貪欲法

問題問題の解釈

許容重量 \( p \) のリュック1と許容重量 \( f \) のリュック2があります。重さが \( s \) と \( w \) のモノがそれぞれ \( a \) 個と \( b \) 個あるとき、二つのリュックに入 ...