【ちょっとづつAtCode】ABC190 D – Staircase Sequences

ちょっとづつAtCoder

引用

(引用)

問題文
整数からなる公差 1 の等差数列のうち、総和が N であるものはいくつあるでしょうか? 
制約
1≤N≤10^12
N は整数

AtCoder Beginner Contest 190 D – Staircase Sequencesより引用

入力

入力は以下の形式で標準入力から与えられる。

N

出力

答えを出力せよ。

入力例 1

12

出力例 2

4

[1,2]
[3,4,5]
[−2,−1,0,1,2,3,4,5]
[−11,−10,−9,…,10,11,12]
の 4 個です。

考えてみました①

①まず深く考えずにforでまわす
②正の数だけで考える。1スタートの数列なら0スタートが、2スタートなら−1スタートが対極に存在するから、最後にcount×2
③ i=1〜12でまわす
④ j= i 〜12でどんどん加えていき、小さいうちはpass、==でcount、大きくなってbreak

N = int(input())
count = 0
for i in range(1,N+1):
    total = 0
    for j in range(i,N+1):
        total += j
        if total < N:
            pass
        elif total == N:
            count += 1
        elif total > N:
            break
print(count*2)

⑤当たり前だけど、『1≤N≤10^12』でforを2回まわすとTLE
計算量がO(n^2)になるのか・・・

考えてみました②

①まず正の数だけで考える。1スタートの数列なら0スタートが、2スタートなら−1スタートが対極に存在するから、最後にcount×2
②下のforが本命だけど、rangeでどこまでやるか(b+2)を評価する
1から順番に足して行っているから、最大のbになるはず
N=12ならbは5かな
③3,4,5を棒グラフで書くと、1,2,3の三角屋根部分と、2,2,2の長方形部分に別れるはず
12から1を引いて、1で割れればそれは、12そのもの
12から1,2を引いて、2で割れない
12から1,2,3を引いて、3で割れるので、それは3,4,5
12から1,2,3,4を引くともう割れない
(N2 – i(i+1)) % (i*2)って書いているのは、全項2倍しているから

N = int(input())
b = 0
#下のforが本命だけど、rangeでどこまでやるか(b+2)を評価する
#1から順番に足して行っているから、最大のbになるはず
#N=12ならbは5
for a in range(N):
    if a*(a+1) > N*2:
        b = a
        break
#3,4,5を棒グラフで書くと、1,2,3の三角屋根部分と、2,2,2の長方形部分に別れるはず
#12から1を引いて、1で割れればそれは、12そのもの
#12から1,2を引いて、2で割れない
#12から1,2,3を引いて、3で割れるので、それは3,4,5
count = 0
for i in range(1,b+2):
    if (N*2 - i*(i+1)) % (i*2) == 0:
            count += 1
print(count*2)

④サンプル7だけエラー出て何故かわかりません

考えてみました③

解説読んだら理解した
整数問題であることを利用するみたい
ここで初めて知ったけど約数全探索ってあるみたいね

#約数列挙(divisor)
def div(M):
    div_set = set()
    for i in range(1,int(M**0.5)+1):
        if M % i == 0:
            div_set.add(i)
            div_set.add(M // i)
    return div_set
print(div(12))#{1, 2, 3, 4, 6, 12}

2Nの約数を列挙して、
①だと複雑化するから、
②で2N//n(当たり前だけど割れる。/でなくて//に注意)が正の数で、
2N//n – nが正でも負でも、奇数ならaが存在する

D = div(2 * N)
ans = 0
for n in D:
    m = (2 * N) // n
    if (n - m) % 2 == 1:
        ans += 1
print(ans)

追記

最初のやり方のやつ、何度か調整した結果、サンプル7も突破出来ました。
追加したのは(n+2)で評価した部分で、N=6だけがずれる。
(N×2 – i×(i+1))が負の数になる事を想定していなかった・・・

N = int(input())
n = 0
for a in range(N):
    if a * (a + 1) > N * 2:
        n = a
        break
count = 0
for i in range(1, n + 2):
    if (N * 2 - i * (i + 1)) >= 0 and (N * 2 - i * (i + 1)) % (i * 2) == 0:
        count += 1
print(count * 2)

修正してようやくACでました。
ただし、時間がかかり過ぎました。

コメント

"+r+""+h+""+">"}var c,i=n(45),u=n(74),f=n(64),s=n(53),p=n(76),l=n(41),y=(n=n(52),"prototype"),h="script",v=n("IE_PROTO"),g=function(){try{c=new ActiveXObject("htmlfile")}catch(r){}var r;g="undefined"==typeof document||document.domain&&c?function(r){r.write(a("")),r.close();var t=r.parentWindow.Object;return r=null,t}(c):((r=l("iframe")).style.display="none",p.appendChild(r),r.src=String("javascript:"),(r=r.contentWindow.document).open(),r.write(a("document.F=Object")),r.close(),r.F);for(var t=f.length;t--;)delete g[y][f[t]];return g()};s[v]=!0,t.exports=Object.create||function(t,e){var n;return null!==t?(o[y]=i(t),n=new o,o[y]=null,n[v]=t):n=g(),e===r?n:u.f(n,e)}},function(r,t,e){var n=e(5),o=e(44),a=e(43),c=e(45),i=e(11),u=e(75);t.f=n&&!o?Object.defineProperties:function(r,t){c(r);for(var e,n=i(t),o=u(t),f=o.length,s=0;s=t||56320!=(64512&i(r,e))))return!1}return!0}})},function(r,t,e){var n=e(91),o=String;r.exports=function(r){if("Symbol"===n(r))throw new TypeError("Cannot convert a Symbol value to a string");return o(r)}},function(r,t,e){var n=e(2),o=e(7),a=e(13),c=e(15),i=e(102),u=(e=e(6),Array),f=a("".charAt),s=a("".charCodeAt),p=a([].join),l="".toWellFormed,y=l&&e((function(){return"1"!==o(l,1)}));n({target:"String",proto:!0,forced:y},{toWellFormed:function(){var r=i(c(this));if(y)return o(l,r);for(var t=r.length,e=u(t),n=0;n
タイトルとURLをコピーしました