Atcoder M-SOLUTIONS プロコンオープン 2020 Python (A~D)

総括

AとBしか解けず。
C,Dは次の日考えたら解けましたが、コンテスト中は一度詰まってしまうと発想を切り替えて解くことがなかなか難しいです。

問題

A. Kyu in AtCoder

回答

X = int(input())

if 400 <= X and X <= 599:
    print(8)
elif 600 <= X and X <= 799:
    print(7)
elif 800 <= X and X <= 999:
    print(6)
elif 1000 <= X and X <= 1199:
    print(5)
elif 1200 <= X and X <= 1399:
    print(4)
elif 1400 <= X and X <= 1599:
    print(3)
elif 1600 <= X and X <= 1799:
    print(2)
elif 1800 <= X and X <= 1999:
    print(1)
else:
    pass

ちょっと考えて解法が思いつかなかったので、愚直にif文を書きました。

200ずつの階層になっているので、200で割ってうまいこと書けば短いコードで書けそうです。
解説PDFでも1行で書かれていました。

B. Magic 2

回答

import itertools

def check(targets):
    if targets[1] > targets[0] and targets[2] > targets[1]:
        return True
    else:
        return False


if __name__ == "__main__":
    A, B, C = map(int, input().split())
    K = int(input())
    targets = [A, B, C]
    answer = 'No'

    cases = itertools.product([0, 1, 2], repeat=K)
    for case in cases:
        copy_targets = targets.copy()
        for i in case:
            copy_targets[i] = copy_targets[i] * 2
        if check(copy_targets):
            answer = 'Yes'
            break

    print(answer)

制約条件が緩いので愚直に全探索で行けそうです。

A, B, Cをリストのtargetsに格納し、それぞれに対応する添え字(0, 1, 2)とします。
また、魔術の成功条件をチェックする関数をcheck(targets)で作成します。

これにより問題文を下記のように言い換えます。
「添え字(0, 1, 2)から1つ選び2倍するという処理をK回行い、check(targets)がTrueとなった場合に'Yes'を表示する」

「添え字(0, 1, 2)から1つ選び2倍するという処理をK回行う」はitertools.productで生成できるので、あとは言い換えた処理をコードに落とすだけです。

C. Marks

コンテスト時には解けませんでした。

コンテスト時の回答

import numpy as np
N, K = map(int, input().split())
A = list(map(int, input().split()))
A = np.array(A)

scores = []

for i in range(0, N - K + 1):
    scores.append(A[i:i+K].prod())

for i in range(0, len(scores)-1):
    if scores[i] < scores[i+1]:
        print('Yes')
    else:
        print('No')

これでは通りません。
とりあえず問題文通りのコードを書きましたが、案の定TLEです。
毎回掛け算をしていると間に合いません。

翌日の回答

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

for i in range(K, N):
    if A[i-K] < A[i]:
        print('Yes')
    else:
        print('No')

掛け算を毎回行うと間に合わないので、掛け算をしないで題意を満たす方法を考えます。

問題文を読み返すと、「直近K回の点数を掛け算し、i学期の評点がi-1学期の評点より高いか否かを判定する」とありますので、
i学期とi-1学期の大小を比べるためには掛け算は必要なく、i-K学期のテストの点とi学期のテストの点を比べればそれで終わりです。

これに気づければコードを書くのは簡単です。

D. Road to Millionaire

こちらもコンテスト時には解けませんでした。
考え方はわかったものの、一部抜け漏れがありました。
また、そもそも問題を解くという点だけを考えると、下記に記載しているコードは助長で、より簡潔に解く方法があるようです。

コンテスト時回答

import numpy as np

N = int(input())
A = list(map(int, input().split()))
A = np.array(A)
have_money = 1000
have_stock = 0
have_stock_valuation = 0
call_status = True

def buy_stock(have_money, have_stock, have_stock_valuation, stock_price):
    stock_num = have_money // stock_price
    have_money -= stock_num * stock_price
    have_stock += stock_num
    have_stock_valuation += stock_num * stock_price

    return have_money, have_stock, have_stock_valuation

def sell_stock(have_money, have_stock, have_stock_valuation, stock_price):
    have_money += have_stock * stock_price
    have_stock = 0
    have_stock_valuation = 0

    return have_money, have_stock, have_stock_valuation

for i in range(N):
    if call_status:
        if A[i] < np.max(A[i:]):
            if A[i] > np.min(A[i:]) and np.argmin(A[i:]) < np.argmax(A[i:]):
                continue
            else:
                have_money, have_stock, have_stock_valuation = buy_stock(have_money, have_stock, have_stock_valuation, A[i])
                call_status = False
    else:
        if have_stock_valuation / have_stock < A[i]:
            if i == N -1:
                have_money, have_stock, have_stock_valuation = sell_stock(have_money, have_stock, have_stock_valuation,  A[i])
                break

            if A[i] < A[i+1]:
                continue
            else:
                have_money, have_stock, have_stock_valuation = sell_stock(have_money, have_stock, have_stock_valuation,  A[i])
                call_status = True

print(have_money)

これでは通りません。
「同日に売却と購入する」場合を反映しきれていないのでWAとなります。

翌日の回答

import numpy as np

def buy_stock(have_money, have_stock, have_stock_valuation, stock_price):
    stock_num = have_money // stock_price
    have_money -= stock_num * stock_price
    have_stock += stock_num
    have_stock_valuation += stock_num * stock_price

    return have_money, have_stock, have_stock_valuation

def sell_stock(have_money, have_stock, have_stock_valuation, stock_price):
    have_money += have_stock * stock_price
    have_stock = 0
    have_stock_valuation = 0

    return have_money, have_stock, have_stock_valuation

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    A = np.array(A)
    have_money = 1000
    have_stock = 0
    have_stock_valuation = 0
    call_status = True

    for i in range(N):

            if call_status:
                if i == N - 1:
                    continue
                if A[i] < A[i+1]:
                    have_money, have_stock, have_stock_valuation = buy_stock(have_money, have_stock, have_stock_valuation, A[i])
                    call_status = False
                if not call_status:
                    if have_stock_valuation / have_stock < A[i]:
                        have_money, have_stock, have_stock_valuation = sell_stock(have_money, have_stock, have_stock_valuation,  A[i])
                        call_status = True
            else:
                if have_stock_valuation / have_stock < A[i]:
                    have_money, have_stock, have_stock_valuation = sell_stock(have_money, have_stock, have_stock_valuation,  A[i])
                    call_status = True
                if call_status:
                    if i == N - 1:
                        continue
                    if A[i] < A[i+1] and call_status:
                        have_money, have_stock, have_stock_valuation = buy_stock(have_money, have_stock, have_stock_valuation, A[i])
                        call_status = False
            
    print(have_money)

これで通ります。

最適な売買方法は「適切なタイミング」で「買えるだけ買って全部売る」ことである、ということは考えてみるとわかります。

まずは「買えるだけ買って全部売る」を実装するために、buy_stockとsell_stockという関数を作成しました。

次に「適切なタイミング」を考えます。
何通りか実験をしてみると、適切なタイミングは下記であることが推測されます。

• 「買い」のタイミングは、「翌日に値上がりするタイミング」
• 「売り」のタイミングは、「保有株が値上がりしているタイミング」

これで準備はできたので、あとはコードに落としていきます。
注意点としては、買える状態（お金がある状態）と売れる状態（株を保有している状態）をcall_statusで保持しておき、上記に記載した「適切なタイミング」で、buy_stockとsell_stockを実行します。