アルゴリズム忘備録

競技プログラミングとかデータ分析とか

AGC015 B - Evilator

agc015.contest.atcoder.jp

 

各階に上または下のボタンしかないエレベーターがある。最上階は下、1階は上であるときに、i階からj階に移動する全組み合わせについて移動の最低回数の合計値を求めよ。

 

移動の最低回数は多くても2回。なので、すべての組み合わせ N * (N - 1) に2回の移動が必要な組み合わせの数を足せばよい。移動に2回必要な移動というのはi階において上ボタンしかない場合は1~i-1階まで、下ボタンしかない場合はi+1~N階までであり、各階が上か下かによって、i-1 または N-i を足していけばよい。O(N)。