AtCoder Beginner Contest 169 ／ Python

• 初学者です。（ 2019 / 9 ～ 現在９ヵ月目 ）
• AtCoder の問題に Python で取り組んでいます。
• ABC で４問目（茶か緑）まで解けることを目標にしています。

完全に独学なのでコードは酷いと思います。

AtCoder やってる方、お気軽にコメントください。

結果

４問目まで解いて緑、まあ良かったんじゃないでしょうか。

昨日の NOMURA のやつが出るんじゃなかった感があったので、

今日は挽回できて良かった。

問題と解答と勉強

atcoder.jp

提出したコード

A, B = map(int, input().split())
 
print(A*B)

atcoder.jp

提出したコード

N = input()
A = sorted(list(map(int, input().split())))
ans = 1
 
for i in A:
    if i == 0 or ans > 10**18: 
        ans = 0
        break
    else:
        ans *=i

if ans > 10**18:
    print(-1)
else:
    print(ans)

何かこれにスゴイ嵌まって時間を無駄にした挙句２回も間違えた。

これね、最初これを出したんよ。

import numpy as np
N = input()
A = list(map(int, input().split()))
ans = np.prod(np.array(A))
 
if ans > 10**18:
    print(-1)
else:
    print(ans)

何が違う？？部分的に不正解が出るんよね。謎い。

結局原因がわかっていない。numpy の何かだと思うんだけど。

前も言ってたけど numpy ちゃんと使えるようにならんとなぁ。



次に普通に for 文で書いたんだけど、全部計算させたら TLE に。

２問目だから正直言うと侮っていた、全部やらせりゃ良いだろと。

反省して 10の18乗 超えたら止めるようにしたら通った。



要らん時間の無駄をしてしまった感がある、勿体ない。

atcoder.jp

提出したコード

from decimal import *
 
A, B = input().split()
 
print(int(Decimal(A) * Decimal(B)))

これもね、１回ミスった。

いや、３問目だからタダの掛け算じゃないとは思ったんだけどね。

掛け算の時は十進浮動小数点ナンチャラは関係ないと思ってた。

割り算の時だけじゃないのねぇ、最初からデシマル君を呼べば良かった。



２問目と３問目で計15分もペナルティを喰らってしもうた。

くそぉぉぉ、もっと順位伸びたかもしらんのに。

atcoder.jp

提出したコード

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])
 
    if temp != 1:
        arr.append([temp, 1])
 
    if arr == []:
        arr.append([n, 1])
 
    return arr
 
import sys

N = int(input())
count = 0

if N == 1:
    print(count)
    sys.exit()
 
for i in factorization(N):
    a = 1
    while i[1] >= a*(a+1)/2:
        a += 1
        count += 1
        
print(count)

こいつが結構あっさり解けてしまってね、上機嫌。



こんな感じで、素因数分解して、ｚ に使える奴が何組入ってるか出す。

最初の素因数分解のコードは借り物だから若干ズルをしてるとも言える・・・。

指数の部分を 1+2+3+4+5+・・・ が何項まで入るかを求めるところは、

何かもっとスマートなやり方があるような気もする。

あとは、１を排除するのは忘れていたが、例に書いてあって助かった。

atcoder.jp

今回は珍しく、というか多分初めて５問目で時間が40分も残ってたんよ！

解けなかったけどね！！

A～B の範囲が被ってるところが中央値になり得る数字なんよね。

例えば N が３なら、２ヵ所以上の A～B に被って出てくる数字が答えのはず、

なんだけど、その何個被ってるかを求める方法がわからなかった。

全部に出てくるとかなら集合を使えば行けそうだけど、

２個だけに被るとかどうするん？？





と思ったんだけど、もっと簡単に求まるらしい。

arr = []
a,b = [],[]
for _ in range(int(input())):
    x,y = list(map(int,input().split()))
    a.append(x)
    b.append(y)
a.sort()
b.sort()
n = len(a)
if n%2!=0:
    x = n//2
    print(b[x]-a[x]+1)
else:
    x = n//2
    y = x-1
    a1 = (a[x]+a[y])/2
    b1 = (b[x]+b[y])/2
    ans = (b1-a1)/0.5
    print(int(ans)+1)

これは悔しい、数学で行けたんかぁ、５問目、数学で行けたかぁぁぁ。

atcoder.jp

相変わらずの６問目様だけれども。

import numpy as np
 
mod = 998244353
 
n, s = map(int, input().split())
A = list(map(int, input().split()))
DP = np.zeros(3005, dtype=np.int64)
 
for num, a in enumerate(A):
    double = DP * 2
    shift = np.hstack([np.zeros(a), DP[:-a]]).astype(np.int64)
    DP = double + shift
    DP[a] += pow(2, num, mod)
    DP %= mod
 
print(DP[s])

あれ、何かわかりそうじゃない？？

ちゃんと考えて無いけど、何かわかりそうな気配がある。

これは珍しい、後で考えてみる。