参加日記: AtCoder ABC 245 AからF(Python)

A - Good morning

１日を86400秒とした時の比較とすると単純です。秒数はh時m分の入力があった時、$60h + m$で求められます。青木くんは1秒後ということで+1して比較すれば良いです。

時間・空間計算量はO(1)です。

実装(Python)

a,b,c,d = map(int, input().split())
x = a*60 + b
y = c*60 + d + 1
if x < y: print("Takahashi")
else: print("Aoki")

B - Mex

多少問題を言い換えると以下のようになります。

• 0,1,2...と数字を見ていき、Aに含まれない最初の数を答えてください

実装としては以下の２つが考えられます。

• 1: Aをリストとして扱い、存在を確認します。リストへの検索は各存在確認に対して$O(N)$です。全体で$O(N^2)$でTLに対して十分に動きます。
  • extraな空間計算量は$O(1)$です。
• 2: Aを辞書として扱います。辞書への追加と存在確認は$O(1)$のため全体で$O(N)$です。
  • なお、C++でsetを用いると$O(logN)$です。
  • extraな空間計算量は$O(N)$です。

時間、空間共に最悪のケースはNが2000であることからAが$0,1,2,..,1998,1999$の時で、答えが2000の時です。

実装(Python)

n = int(input())
dat = set(map(int, input().split()))
i = 0
while i in dat: i += 1
print(i)

C - Choose Elements

この問題は解説以上に書くことがないので省略します。

私は値をとりうるか？の代わりに、None or 値が入っている場合は何が入っているか？という管理にしましたが、この問題の場合どちらでも良いでしょう。

時間空間計算量は$O(N)$です。

実装(Python)

n, k = map(int, input().split())
data = list(map(int, input().split()))
datb = list(map(int, input().split()))
dp = [[None] * 2 for _ in range(n)]
dp[0][0] = data[0]
dp[0][1] = datb[0]

for ind in range(1, n):
    if dp[ind - 1][0] is not None:
        if abs(data[ind] - dp[ind - 1][0]) <= k: dp[ind][0] = data[ind]
        if abs(datb[ind] - dp[ind - 1][0]) <= k: dp[ind][1] = datb[ind]
    if dp[ind - 1][1] is not None:
        if abs(data[ind] - dp[ind - 1][1]) <= k: dp[ind][0] = data[ind]
        if abs(datb[ind] - dp[ind - 1][1]) <= k: dp[ind][1] = datb[ind]

if dp[n - 1][0] is not None: print("Yes")
elif dp[n - 1][1] is not None: print("Yes")
else: print("No")

D - Polynomial division

Python(numpy)すごいなー...

E(別記事)

F(別記事)