AtCoder

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

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

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

\( N \) 個の整数が ‘pairwise coprime’ であれば ‘setwise coprime’ なので、’pairwise coprime’ ...

友達同士のグループの人数の最大値の分だけグループがあれば、「同じグループの中に友達がいない」という状況がつくれます。したがって、連結成分の最大値を求めます。これは、幅優先探索や Union-Find を使うことで求めることがで ...

与えられた式は、

\

となるので、\( B_i = A_1 + A_2 + \cdots + A_i \) とすると、

\

となります。よって、あらかじめ累積和を計算してから求め ...

行と列はそれぞれ独立に選ぶことができることに注目します。 \( i \) 行目にある爆弾の個数を \( R(i) \) とし、\( j \) 列目にある爆弾の個数を \( C(j) \) とします。マス \( (i, j ...

徒歩で行くことができるマスをグループ化し、IDを振ります。マス \( (i, j) \) の ID が \( 0\) であることを \( G(i, j) = 0 \) と表し、そのマスから徒歩でいけるマスの ID は ...

\( i \) 番目までで一番高い身長を \( h_i \) とすると、\( i + 1 \) 番目の人に必要な踏み台の高さは、

\

となります。\( h_0 = A_0 \) として、全探索します。

マス \( i \) を選択したとき、\( N \) 回以下の移動でマス \( i \) に戻ってくるので、\( K \) 回以下の移動で何周できるかを考えます。周回しない方が最適な場合もあることに注意します。マス \( i ...