図解解説シリーズ
競技プログラミングを始めたばかりでAtCoderの解説やJOIの解説ではいまいちピンと来ない…という人向けに、図解を用いて解説を行います。
問題文
情報オリンピック日本委員会に掲載されている問題
AtCoderに掲載されている問題
入出力など実際に確認して自分の作成したプログラムを採点することができます。
図解解説
今年度の本選のA問題は、以下のスキルを確認する問題になっています。
１．累積和
２．二分探索
問題文を整理するために、まずはカステラの切り方について考えてみます。
上記手続きに従って、カステラの切り方についてプログラムを作成し、実行してみます。変数cntは、カステラの個数を管理するための変数として定義しています。
N = int(input())
for i in range(N):
a = int(input())
#奇数になるまでカステラを2で割っていき
#長さと個数がいくつになるか計算を行う
cnt = 1
while a%2==0:
a = a//2
cnt = cnt*2
print(a,cnt)
入力例１を使用して実行結果を確認すると、以下のようになります。
7 2
9 1
1 8
3 4
入力例３を使用して実行結果を確認すると、以下のようになります。
1 536870912
3 134217728
1 536870912
1 536870912
1 134217728
1 536870912
5 134217728
1 536870912
1 536870912
1 536870912
7 134217728
3 268435456
1 536870912
57 16777216
1 536870912
1 536870912
入力例３の結果からもわかる通り、多くの個数に分かれることになります。そのため、X番目のピースの長さを求めるには、何かしらの工夫が必要になります。
そこで、X番目を探す方法について整理してみます。
上記スライドのようにどの位置に該当するか探し出すことができれば、先頭からX番目のカステラの長さを求めることができます。高速に位置を特定する方法として、二分探索が使用できますのでそのための準備を行っていきます。そのために、切り分けた個数を利用して累積和を求めます。
今回、○～×番目の×番目に相当する値を使っていきます。カステラの長さを管理するためのリストnagasaとカステラの個数を管理するためのリストkosuuを作成し、カステラの長さを求めた変数aの値と、カステラの個数を求めた変数cntの値をそれぞれ順番に格納しておきます。その後、リストkosuuの値を更新することで累積和を求めます。
N = int(input())
nagasa = []
kosuu = []
for i in range(N):
a = int(input())
#奇数になるまでカステラを2で割っていき
#長さと個数がいくつになるか計算を行う
cnt = 1
while a%2==0:
a = a//2
cnt = cnt*2
nagasa.append(a)
kosuu.append(cnt)
#個数の累積和を計算する処理
for i in range(N-1):
kosuu[i+1] += kosuu[i]
print(kosuu)
次に、二分探索について考えます。Pythonでは二分探索を行うためのbisectライブラリが提供されていますので、今回はライブラリを使用します。ライブラリの使用方法に関しては、Web上に多くの有用な記事がありますので詳細についてはそちらを参照してください。
今回の入力例１を使って、二分探索の動きを確認してみます。
上記スライドのようにbisect_leftを使用すると、検索値がリストkosuuのどこに入るか要素番号を確認することができます。一致する値が見つかった場合は、左側の要素番号を確認することができます。なお、bisect_right（bisect）を使用すると、一致する値が見つかった場合は、右側の要素番号を確認することができます。左側の要素番号を利用すれば、求めたいカステラの長さがリストnagasaの要素番号と一致するため効率よくプログラムを作成することができます。以上を踏まえて以下のような解答になります。
解答例
import bisect
N = int(input())
nagasa = []
kosuu = []
for i in range(N):
a = int(input())
#奇数になるまでカステラを2で割っていき
#長さと個数がいくつになるか計算を行う
cnt = 1
while a%2==0:
a = a//2
cnt = cnt*2
nagasa.append(a)
kosuu.append(cnt)
#個数の累積和を計算する処理
for i in range(N-1):
kosuu[i+1] += kosuu[i]
#二分探索を使ってx番目のカステラの長さを求める
Q = int(input())
for i in range(Q):
x = int(input())
j = bisect.bisect_left(kosuu,x)
print(nagasa[j])
イラスト
スライド内で使用しているイラストはすべて「いらすとや」の素材を利用しています。