第11回の過去問題全部

第11回

第11回 E問題変わった数列(7点)

問題

E - 変わった数列

私の言語

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株式会社採用サイトよりご確認ください。

是非ともよろしくお願いいたします。