AtCoder Beginner Contest 105 に参加しました(Python)

サイトへのURL

AtCoder Beginner Contest 105 - AtCoder

以下では,li_input()関数を用います.

def li_input():
    return [int(_) for _ in input().split()]

A問題

問題文

高橋君は N 枚の AtCoder せんべいを K 人の AtCoder 参加者になるべく公平に配ることにしました。 N 枚すべてのせんべいを配るとき、せんべいを最も多くもらった人と最も少なくもらった人のもらったせんべいの枚数の差(の絶対値)の最小値を求めてください。  

解法

せんべいN枚をK人に均等に分けられる時,答えは0です.
均等に分けられない時,答えは1です.

ソースコード

def main():
    N, K = li_input()

    if N % K == 0:
        print(0)
    else:
        print(1)


main()

B問題

問題文

ABC 洋菓子店では, 1 個 4 ドルのケーキと 1 個 7 ドルのドーナツが売られている. このとき, 合計金額が N ドルとなる買い方はあるか, 判定せよ. ただし, 同じ商品を二個以上買っても良く, 買わない商品があっても良いものとする.

解法

ケーキを買う個数をx,ドーナツを買う個数をyとします.
また,合計金額pp = 4x + 7yとします.

問題文の条件より,Nはたかだか100なので,
1 <= p <= 100となるようなxyを全探索によって求めれば良いです.

ソースコード

def main():
    l = []

    for i in range(100):
        for j in range(100):
            if i * 4 + j * 7 <= 100:
                l.append(i * 4 + j * 7)

    N = int(input())

    if N in l:
        print("Yes")
    else:
        print("No")

C問題

問題文

f:id:Szarny:20180812013256p:plain

解法

公式解法とは全く異なります

細かいところについては,ソース内に書いているので省きます.
通常の10進数>2進数変換の際と同じように考えました.

  1. 最上位ビットの位置を決める(上位から順に b_k b_{k-1} b_{k-2} ... b_1 b_0 とする 当然b_{k}1)
  2. 2.1. 各ビットの-2進数の位を c_k c_{k-1} c_{k-2} ... c_1 c_0 とする
    2.2. 現在の値を c_kの値とする
    2.3. i = k-1とする

  3.  c_{i}が正の数である場合は4へ 負の数である場合は5へ
  4. 4.1.  c_{j} (j < i) である全ての正の数の総和と現在までの値を足してNに届かなければ, b_{i}のビットを立てる
    4.2. 現在の値 = 現在の値 +  c_{i}とする.

  5. 5.1.  c_{j} (j < i) である全ての負の数の総和と現在までの値を足してNを上回れば, b_{i}のビットを立てる
    5.2. 現在の値 = 現在の値 +  c_{i}とする.

  6. iをデクリメントして3に戻る

のような感じです.

ソースコード

c = []


# (i < limit, c[i] > 0となるc[i]の数を足して行った結果) + 現在の値 が
# Nを下回ればc[limit]を足す必要がある
def is_lower(limit, c_value, N):
    add_value = 0
    for i in range(limit - 1, -1, -1):
        if c[i] > 0:
            add_value += c[i]

    return c_value + add_value < N


# (i < limit c[i] < 0となるc[idx]の数の総和) + 現在の値 が
# Nを上回ればc[limit]を引く必要がある
def is_over(limit, c_value, N):
    sub_value = 0
    for i in range(limit - 1, -1, -1):
        if c[i] < 0:
            sub_value += c[i]

    return c_value + sub_value > N


def main():
    global c

    N = int(input())
    c_value = None

    # コーナーケース
    if N == 0:
        print(0)
        return

    # 位を事前に計算
    for i in range(50):
        c.append((-2)**i)

    # NがPositiveの場合
    # (-2)**i (i=2k) の総和が目的の値を超えるところが最上位ビット
    if N > 0:
        tmpsum = 0
        for i in range(50):

            if c[i] > 0:
                tmpsum += c[i]

            if tmpsum >= N:
                idx = i
                c_value = c[i]
                break

    # NがNegativeの場合
    # (-2)**i (i=2k+1) の総和が目的の値を下回るところが最上位ビット
    else:
        tmpsub = 0
        for i in range(50):
            if c[i] < 0:
                tmpsub += c[i]

            if tmpsub <= N:
                idx = i
                c_value = c[i]
                break

    ans = "1"

    for c_idx in range(idx - 1, -1, -1):
        # c[c_idx]がNegativeのとき
        # c[c_idx]の値を加算しなければ
        # c_idx' < c_idx かつ c[c_idx']<0 となる任意のc[c_idx']の値を加算しても
        # 最終的な総和がNを上回ってしまうなら,c[c_idx]を加算する必要がある
        if c[c_idx] < 0:
            if is_over(c_idx, c_value, N):
                ans += "1"
                c_value += c[c_idx]
            else:
                ans += "0"

        # c[c_idx]がPositiveのとき
        # c[c_idx]の値を加算しなければ
        # c_idx' < c_idx かつ c[c_idx']>0 となる任意のc[c_idx']の値を加算しても
        # 最終的な総和がNを下回ってしまうなら,c[c_idx]を加算する必要がある
        else:
            if is_lower(c_idx, c_value, N):
                ans += "1"
                c_value += c[c_idx]
            else:
                ans += "0"

    print(ans)


main()

D問題

問題文

f:id:Szarny:20180812020237p:plain

解法

累積和を用います.
ただし,ここでは各累積和の Mの剰余が知れればいいので,計算時に Mの剰余のみを格納します.
つまり, A_{1}から A_{k}までの総和を Mで割った値を C_{k}とします.
(ただし, C_{0} = 0とする.)

ここで,条件を満たすような (l, r)の総数というのは, C_{l-1} = C_{r}となるような (l, r)において,それぞれの (l, r)の2つの組み合わせの個数の和のことです.
なぜなら, C_{l-1} = C_{r} ( C_{l-1} - C_{r} = 0)のとき, A_{l} A_{l+1} ... A_{r-1} A_{r}の総和は Mの倍数になるからです.
これを数え上げれば解くことができます.

ソースコード

import collections

def main():
    N, M = li_input()
    A = li_input()

    ans = 0
    d = collections.defaultdict(lambda: 0)

    cumsum = [0]
    c_sum = 0
    for a in A:
        c_sum = (c_sum + a) % M
        cumsum.append(c_sum)

    for c in cumsum:
        d[c] += 1

    for v in d.values():
        if v >= 2:
            ans += v * (v - 1) // 2

    print(ans)


main()