Subscribed unsubscribe Subscribe Subscribe

stkblog

白血病と関係ないことを書きます なにかあったら教えて下さい

Codeforces#333 Div.2 AとB やった

Codeforces python

まとめ

A はちょっと時間かかった。
B は死ぬほど時間かかった上に起きたら落ちてた。
Rating も下がった。
C ~ は実力とやる気が足りない

A. Two Bases

codeforces.com

入力の数が多くて怯んだ(雑魚

{ \displaystyle
101111_{(2)} = 1\cdot2^5 + 0\cdot2^4 + 1\cdot2^3 + 1\cdot2^2 + 1\cdot2^1 + 1\cdot2^0
= 47_{(10)}
}

みたいな感じで10進法に(じゃなくてもいいけど)揃えて比べればおk

提出(AC)

n, m = map(int, raw_input().split())
X = map(int, raw_input().split())

ans_x = 0
for i in xrange(n):
    ans_x += X[i] * m**(n-i-1)

n, m = map(int, raw_input().split())
X = map(int, raw_input().split())

ans_y = 0
for i in xrange(n):
    ans_y += X[i] * m**(n-i-1)

if ans_x > ans_y:
    print '>'
elif ans_x < ans_y:
    print '<'
else:
    print '='

最初Xをまずつなげてから整数になおして…とか考えてしまったので、10分もかかってしまった。

清書

def calc():
    n, m = map(int, raw_input().split())
    X = map(int, raw_input().split())
    ans = 0
    for i in xrange(n):
        ans += X[i] * m**(n-i-1)
    return ans

x = calc()
y = calc()

if x > y:
    print '>'
elif x < y:
    print '<'
else:
    print '='

2回繰り返してる部分ダサいかなと思ったので

B. Approximating a Constant Range

codeforces.com

与えられた数列の中で 最大と最小が1以内 になるような数列の長さ。

提出(TLE)

隣り合った数字2つとって順番にチェックすればわかるのではないだろうか → TLE
n * (M-m) 回(?)

n = input()
A = map(int, raw_input().split())

m, M = min(A), max(A)

longest = 1
cnt = 0
for i in xrange(M-m):
    l, r = m+i, m+i+1
    for a in A:
        if a in [l,r]:
            cnt += 1
        else:
            longest = max(longest, cnt)
            cnt = 0
    else:
        longest = max(longest, cnt)
        cnt = 0

print longest

提出(RE)

はじめて値が変わったポイント覚えておいて次回はそこからスタートすればよいのではないだろうか
プレテストこれで通ったので寝た。REて。

n = input()
A = map(int, raw_input().split())

l, r, cnt, ans = 0, 1, 0, 0
first = True
while r <= n:
    if first and A[l] != A[r]:
        first = False
        next = r
    else:
        if max(A[l:r]) - min(A[l:r]) < 2:
            r += 1
            cnt += 1
        else:
            ans = max(ans, cnt)
            l,r = next,next+1
            cnt = 0
            first = True
else:
    ans = max(ans, cnt)

print ans
3
1 1 1

r=3 になる → A[3] を見ようとする → IndexError


他の人のAC提出をカンニングしたりして(あんまりよくわからなかったけど)ごちゃごちゃやってたらうまくいった

AC

n = input()
A = map(int, raw_input().split())

l, c, cnt, ans = 0, 1, 0, 2
first = True
mx, mn = A[0], A[0]

while l+c <= n:
    if A[l] == A[min(n-1, l+c)]:      #右端の値が同じなら
        c += 1                      #もう1つ右をみる
    else:                                #ちがったら
        if first:                      #それがはじめてなら
            first = False
            next_l = l+c                     #つぎそこから始めるので覚えとく

        if A[l] < A[min(n-1, l+c)]:        #右に大きい値が出てきたなら
            mx = A[min(n-1, l+c)]       #それが今見てる数列の上の値
        elif A[l] > A[min(n-1, l+c)]:      #その逆
            mn = A[min(n-1, l+c)]

        if mx - mn >= 2:             #上の値と下の値が2離れたらおわり
            ans = max(ans, c)  
            c = 1
            l = next_l
            first = True
            mx = mn = A[l]
        else:                          #まだいけるなら
            c += 1                   #もう1つ右を見る
else:                                  #最後の1回
    ans = max(ans, c-1)     

print ans

あんまり解けたって感じしてない。
まあぼちぼちやっていきます

Div.2 で2完が当面の目標(低