[AtCoder] ABC 177 E – Coprime
\( N \) 個の整数が ‘pairwise coprime’ であれば ‘setwise coprime’ なので、’pairwise coprime’ ...
[AtCoder] ABC 177 D – Friends
友達同士のグループの人数の最大値の分だけグループがあれば、「同じグループの中に友達がいない」という状況がつくれます。したがって、連結成分の最大値を求めます。これは、幅優先探索や Union-Find を使うことで求めることがで ...
[AtCoder] ABC 177 C – Sum of product of pairs
与えられた式は、
\
となるので、\( B_i = A_1 + A_2 + \cdots + A_i \) とすると、
\
となります。よって、あらかじめ累積和を計算してから求め ...
[AtCoder] ABC 176 E – Bomber
行と列はそれぞれ独立に選ぶことができることに注目します。 \( i \) 行目にある爆弾の個数を \( R(i) \) とし、\( j \) 列目にある爆弾の個数を \( C(j) \) とします。マス \( (i, j ...
[AtCoder] ABC 176 D – Wizard in Maze
徒歩で行くことができるマスをグループ化し、IDを振ります。マス \( (i, j) \) の ID が \( 0\) であることを \( G(i, j) = 0 \) と表し、そのマスから徒歩でいけるマスの ID は ...
[AtCoder] ABC 176 C – Step
\( i \) 番目までで一番高い身長を \( h_i \) とすると、\( i + 1 \) 番目の人に必要な踏み台の高さは、
\
となります。\( h_0 = A_0 \) として、全探索します。
[AtCoder] ABC 175 D – Moving Piece
マス \( i \) を選択したとき、\( N \) 回以下の移動でマス \( i \) に戻ってくるので、\( K \) 回以下の移動で何周できるかを考えます。周回しない方が最適な場合もあることに注意します。マス \( i ...
[AtCoder] ABC 175 C – Walking Takahashi
下記の問題と似ています。
まず初めに、\( K \) の値を無視して考えます。また、\( X = |X| \) としても一般性を失わないので、\( X = |X| \) とします。整数 \( t \) を
[AtCoder] ABC 174 E – Logs
\( K \) 回の操作後の最も長い丸太の長さを \( t \) とします。\( t \) を固定したとき、条件を満たすかどうかを二分探索によって求めます。丸太 \( i \) の長さを \( t \) 以下にするためには、
[AtCoder] ABC 174 D – Alter Altar
条件を満たす石の並びは、先頭から \( i (0 \leq i \leq N)\) 個目までが赤石で、以降は白石です。\( i = 0 \) のときは全てが赤石で、\( i = N \) のときは全てが白石です。し ...