SupershipでVPoEしている名畑です。
「アルゴリズム実技検定(PAST)について 並びに 第11回A〜C問題 Python解答例」と「アルゴリズム実技検定(PAST) 第11回 D問題 Python解答例(Union-Find使用と不使用)」の続きとして、アルゴリズム実技検定(PAST)第11回のE問題の私の解答例(Python3)を公開します。
第11回の過去問題全部
第11回 E問題 変わった数列(7点)
問題
私の言語
- Python (3.8.2)
解答例
まず、この「変わった数列」がどんなものかイメージしやすくするため、iが1〜5のときの諸々を箇条書きにしてみます。
- i = 1
- 末尾に追加される数列 (1)
- 項数 1
- ここまでの累計項数 1
- i = 2
- 末尾に追加される数列 (2, 1, 2)
- 項数 3
- ここまでの累計項数 4
- i = 3
- 末尾に追加される数列 (3, 2, 1, 2, 3)
- 項数 5
- ここまでの累計項数 9
- i = 4
- 末尾に追加される数列 (4, 3, 2, 1, 2, 3, 4)
- 項数 7
- ここまでの累計項数 16
- i = 5
- 末尾に追加される数列 (5, 4, 3, 2, 1, 2, 3, 4, 5)
- 項数 9
- ここまでの累計項数 25
これを見ると、i^2がそこまでの累計の項数だとわかります（等差数列の公式から求められる)。
また、末尾に追加される数列の値は中心が1、両端がiであることもわかります。つまり末尾に追加される数列の各項の値は、追加される数列の中央からの距離と比例します。
なので、N項の値は
- N項はiがいくつのときに登場するか
- N項は求められたiで追加される数列の中でどこに位置するか
で求められます。
N = int(input())
# 累計桁数がNに近いiを見つけるために二分探索
i = 1
low = 1
high = 10 ** 100 # iの最大値が10^100のため
while i > 0:
i = (low + high) // 2
digit = i ** 2 # 累計の項数
if digit < N:
if low == i:
break
low = i
else:
if high == i:
break
high = i
# 項数に1を足す
if i ** 2 < N:
i += 1
num = N - (i - 1) ** 2 # iで追加される数列中の何番目にNがあるか
group_diff = abs(num - i) # 中心からの距離
print(group_diff + 1)
二分探索についてはネット上にたくさん情報ありますので、もしも初見の場合は調べてみていただければと思います。
最後に宣伝
SupershipのQiita Organizationを合わせてご覧いただけますと嬉しいです。他のメンバーの記事も多数あります。
Supershipではプロダクト開発やサービス開発に関わる方を絶賛募集しております。
興味がある方はSupership株式会社 採用サイトよりご確認ください。
是非ともよろしくお願いいたします。