初心者のためのAtCoder解説【ABC190】

AtCoderのABC190を題材にAtCoder初級者の私の回答と考えていたことを説明します。

この記事シリーズは「こんなレベルでも大丈夫なのか」と皆さんにぜひ思っていただくのが目的なので1つの参考になれば嬉しいです。

ABC190の問題

全体について

今回の問題のdifficultyはこんな感じです。difficultyの数値はその値のAtCoderのレートの人が50%正答できるという基準です。私の目線でざっくりとした難易度に翻訳したものを真ん中の列に書きました。

今回もD問題まで紹介します。

A問題

お互いに1個ずつアメを食べるので、基本的に最初に持っているアメの数が大きいほうが勝ちます。

もし最初のアメの数が同数だった場合は先手のほうが先にアメがなくなるので後手の勝利となります。この2点をコードに起こします。

A, B, C = map(int, input().split())
if A > B:
    print('Takahashi')
elif A == B:
    if C == 0:
        print('Aoki')
    else:
        print('Takahashi')
else:
    print('Aoki')

なお公式の回答例ではCの値を最初のアメの数に含めて考えてA+CとBの大小を比べてコードを簡略化していますね。

B問題

高橋くんが魔物にダメージを与えられるのは、N種類の呪文の中にS秒以内の詠唱かつD以上の威力を持つものがある場合です。なのでN種類の中から条件に合致する呪文があるかを判定すればOKです。

N, S, D = map(int, input().split())

attack = 'No'

for _ in range(N):
    x, y = map(int, input().split())
    if x < S and y > D:
        attack = 'Yes'
print(attack)

C問題

K人の人が更にボールを置く置き方は全部で$2^{16}=65536$通りです。なので今回はすべての場合を調べても時間内に計算を終わらせられると思ったので愚直に全ての場合を調べます。

各ボールの配置が決まったらM個の条件がそれぞれ満たされているかどうかを1つずつチェックし、条件を最も多く満たす場合のときの条件の個数を求めればOKです。

私はボールの置き方の組み合わせの求め方がわからなかったので、0から65535の数をK桁の2進数で表して、0と1で皿の上のボールの有無を表現しました。そのためコードは読みづらくなっています。

N, M = map(int, input().split())
cond = []
for _ in range(M):
    cond.append(list(map(int, input().split())))
K = int(input())
cases = []
for _ in range(K):
    cases.append(list(map(int, input().split())))

maximumCnt = 0
for i in range(2 ** K):
    case = list(map(int, format(i, 'b').zfill(K)))
    ballsOnDish = set()
    for j in range(K):
        ballsOnDish.add(cases[j][case[j]])
    cnt = 0
    for j in range(M):
      if cond[j][0] in ballsOnDish and cond[j][1] in ballsOnDish:
        cnt += 1

    if cnt > maximumCnt:
        maximumCnt = cnt
print(maximumCnt)

公式の回答ではitertools.product()を利用して全ての組み合わせを求めています。便利そうなライブラリなのでぜひこちらも見てください。

D問題

初項a、項数n、交差dの等差数列の和Nは以下の数式で表すことができます。

$$N = \frac{n}{2}(2a-(n-1)d)$$

今回d=1なので上の式は次のように変換することができます。

$$2N = n(2a-n+1)$$

aとnは自由に決めることができるので、2Nを約数の積での表し方と考えることができます。

ただしここで注意しないといけないのは数の偶奇です。左辺は偶数なので当然右辺も偶数とならければいけません。するとnとaの一方が偶数の場合、他方は奇数でなければならないことがわかります。その点だけ注意します。

約数の積での表し方は2Nを素因数分解したときに、素因数を2つに分ける組み合わせを求めれば大丈夫です。ただし上で言ったようにaとnは互いに偶数ではいけないので、素因数の2だけはaかnのどちらかに全てを振り分けなくてはいけません。

その点に注意してコードに起こすと以下のようになります。関数の定義部分では素因数分解の関数を作っています。

N = int(input())

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

l = factorization(2 * N)

combination = 1
for i in range(len(l)):
    factor = l[i][0]
    if factor == 2:
        num = 2
    else:
        l[i][1] + 1
    combination *= num
    
print(combination)

最後に

回答は全て私のgitHubに載せてありますので必要があればご覧ください。