u++の備忘録

AtCoder Beginner Contest 118をPythonで解く

python 競プロ

「AtCoder Beginner Contest 118」に出て、3完でした。

atcoder.jp

Cは実装に確証が持てておらず、かつコードも汚いので解説などで勉強します。Dは方針が立ちそうでしたが「ちょうどN本のマッチ棒を使って」という条件で分からなくなりました。

f:id:upura:20190216223457p:plain

A - B +/- A（100点）

  • 要件通りに実装
A, B = list(map(int, input().split()))

if (B % A == 0):
    print(A + B)
else:
    print(B - A)

B - Foods Loved by Everyone（200点）

  • 「好き」で挙げられたindexを一つのlistに格納
  • collectionsで集計
import collections

N, M = list(map(int, input().split()))

a = []
for i in range(N):
    tmp = list(map(int, input().split()))
    a += tmp[1:]

c = collections.Counter(a)
ans = 0
for val in c.values():
    if val == N:
        ans += 1

print(ans)

C - Monsters Battle Royale（300点）

  • 実装に確証がないまま通した
  • 最初に、一番小さい数字で、その他全てに可能な限り攻撃
  • その状態でソート
  • 小さい数字2種類を取り出し、互いに攻撃させ合った結果を答えとする
  • 数字が1種類しかない場合の処理も書く
N = int(input())
A = list(map(int, input().split()))

As = sorted(A)
As = [a%As[0] if a%As[0] != 0 else As[0] for a in As]
As = sorted(As)

def judge(tmp_one, tmp_two):
    flg = 1

    while flg:
        if tmp_two%tmp_one == 0:
            tmp_two = tmp_one
        else:
            tmp_two = tmp_two%tmp_one

        if tmp_one%tmp_two == 0:
            tmp_one = tmp_two
        else:
            tmp_one = tmp_one%tmp_two
        if tmp_one == tmp_two:
            flg = 0

    return tmp_one

tmp_one = As[0]
for i in range(1, N):
    if i == N - 1:
        tmp_two = As[i]
    elif As[i] != As[0]:
        tmp_two = As[i]
        break

ans = judge(tmp_one, tmp_two)
print(ans)

D - Match Matching（400点）

  • 桁数を増やすのを最優先で、マッチ棒の消費が小さい数字を積極的に作っていく？
  • 「ちょうど」使い切る組み合わせの探索が必要そうで、方針が分からなくなった
import numpy as np

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
A = sorted(A)

cost = [2, 5, 5, 4, 5, 6, 3, 7, 6]
candidate = []

for i in range(len(A)):
    candidate.append(cost[A[i]-1])

A = np.array(A)
candidate = np.array(candidate)

sort_index = candidate.argsort()
candidate = candidate[sort_index]
A = A[sort_index]

ans = ""
for _ in range(N//candidate[0]-1):
    ans += str(A[0])

rest = N%candidate[0] + candidate[0]
print(rest)
print(ans)

復習[追記: 20190217]

B

setにして積集合を取るのが簡単でした

note.nkmk.me


C

単純に最大公約数で良かったです。詳しくは公式解説を参照。

import fractions


N = int(input())
A = list(map(int, input().split()))

 
ans = fractions.gcd(A[0], A[1])

for i in range(2, N):
    ans = fractions.gcd(ans, A[i])

print(ans)

D

「ちょうどN本」の類いは、動的計画法（DP）の頻出問題のようですね。精進します。

qiita.com