AtCoder Beginner Contest 210~212(灰色問題)

#はじめに
なんとかAtCoder Beginner Selectionを終わらせてABCに挑んだけど全く歯が立たなかったので過去問をやって行きます。
https://kenkoooo.com/atcoder/#/table/
まずAtCoder Problemで灰色の問題をやっていきます。
#Cabbage(210-A)
NがAを超えるかどうかで判定。

N,A,X,Y = map(int,input().split())

if N <= A:
    print(N * X)
else:
    print(A*X + (N-A) * Y)

#Blood Pressure(211-A)
式が問題に書かれているのでそれをプログラミングで再現するだけ。

A,B = map(int,input().split())

print((A + B * 2) / 3)

#Alloy(212-A)
0<A+B なのでA,Bがそれぞれ0か判定すれば良い。

A,B = map(int,input().split())

if A==0:
    print("Silver")
elif B==0:
    print("Gold")
else:
    print("Alloy")

#Bouzu Mekuri(210-B)
最初の"1"に当たるまでループを回していって、インデックスの偶奇を判定する。

N = input()
A = list(input())

for i in range(int(N)):
    if A[i] == "1":
        if i % 2 == 0:
            print("Takahashi")
        else:
            print("Aoki")
        break

#Cycle Hit(211-B)
入力した文字列をソートして一致するか確認。
回答ではどれか2つが被ったらNoと判断するという

S = []
for i in range(4):
    S.append(input())

if sorted(S) == ['2B','3B','H','HR']:
    print("Yes")
else:
    print("No")

#Weak Password(212-B)
全部の桁が同じか判定して、そのあと連続か判定する。
配列使わなくてもうまく書けばできそう(X[i]+1)%10 = X[i+1]とか。

X = list(map(int,list(input())))

next = [1,2,3,4,5,6,7,8,9,0]

if all([xi == X[0] for xi in X[1:]]):
    print("Weak")
elif all([next[X[i]]==X[i+1] for i in range(3)]):
    print("Weak")
else:
    print("Strong")

#Colorful Candies(210-C)
###1回目(コンテスト中)
とりあえず長さKの配列を作って異なる要素の数を調べれば良いんでしょと思って書いた。
テストも3件とも正しく答えが出たので意気揚々と提出するとTLEがでた。。。
答えが出れば良いっていうわけじゃなくて実行時間の制約も意識して解かないといけないC問題難しい。。。

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

candyNums = []

for i in range(N-K+1):
    work = C[i:K+i]
    candyNums.append(len(set(work)))

print(max(candyNums))

###2回目(コンテスト後)
全く思いつかなかったので解答を見た。
考え方としてi番目からi+K-1番目までの連続したK個のキャンディの中に色ごとに何が何個入っているかを情報として持っておいて、1つずらしたi+1番目からi+K番目になった時にi番目の色の個数が0かどうか、i+K番目の色の個数が1かどうか判定する、という風にする。

以下のデータを例に挙げて手順を書いていく。

5 3
1 2 2 3 4

1)　c0,c1,c2を確認し、色1が1つ、色2が2つあることを情報として持っておき、数が1以上の色の種類数を暫定の答えとして持っておく。
色1 : 個数1
色2 : 個数2
色の種類数 : 2
暫定の答え : 2

2)　c1,c2,c3を確認するときに、c0,c1,c2との差異としてc0の色の個数を1つ減らす。このとき、c0の色(色1)の個数が0になれば色の種類数を1減らす。
色1 : 個数0
色2 : 個数2
色の種類数　: 1
暫定の答え　: 2

1. 2)とは逆にc3の色(色3)の個数を1つ足す。このとき、c3の色(色3)の個数が1になれば色の種類数を1増やす。(元々の個数が0だったため、色の種類数が増えている)
   色1 : 個数0
   色2 : 個数2
   色3 : 個数1
   色の種類数　: 2
   暫定の答え　: 2

4)　次のc2,c3,c4についても2),3)と同様の処理を行う。このとき、色の種類数が暫定の答えより大きくなれば暫定の答えを更新する。
色1 : 個数0
色2 : 個数1
色3 : 個数1
色4 : 個数1
色の種類数　: 3
暫定の答え　: 3

5)　N個のキャンディまで調べ終わったときに暫定の答えを出力する。
出力　: 3

なかなか理解するのに時間がかかってしまったが、とりあえず一歩前進できたという実感がある。
これを実際のコンテストで書けと言われるとやはり時間がかかってしまいそうなので要練習。

import collections as cl

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

work =  cl.Counter(C[:K])
candyNum  = len(work)
wcandyNum = candyNum

for i in range(N-K):
    work[C[i]] -= 1
    if work[C[i]] == 0:
        wcandyNum -= 1
    
    work[C[i+K]] += 1
    if work[C[i+K]] == 1:
        wcandyNum += 1

    if wcandyNum > candyNum:
        candyNum = wcandyNum
        
print(candyNum)

#Min Difference(212-C)
###1回目(コンテスト中)
安定の全探索(使い方あってるのかな)でTLE。
今回はイメージとして、「AとBをソートして、先頭から順に差が小さいところだけを調べていく」というようなものが浮かんだが、実際にコードを書く際のイメージが浮かばず苦戦することになりそう。

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

A = list(map(int,input().split()))
B = list(map(int,input().split()))
mins=[]
Work = []
j=0
for i in range(N):
    if j == 0 and  A[i] - B[j] >= 0:
        Work.append(A[i] - B[j])
    else:
        while (A[i] - B[j]) < 0:
            if j==M:
                break
            j += 1

        Work.append(A[i] - B[j])
        Work.append(A[i] - B[j-1])

print(min(Work))

###2回目(コンテスト後)

最終的にだいぶ短いコードに収まった。
以下試して間違えたこと。

• B_j < A_i < B_j＋1の時に | A_i - B_j | と | A_i - B_j+1 |の両方を調べないといけないと思っていた。
  • B_j < A_i < A_i+1 < B_j＋1の時に | A_i - B_j+1 | と | A_i+1 - B_j |は調べる必要がない(下のコードでは前から順番に見ていくため、どうしても| A_i - B_j+1 |は調べないといけない。)
• for i in range(N)とfor j in range(M)の2重ループにしてしまった。
  • 内側のループを抜けると再度同じループがj=0から始まってしまうのでうまくいかなかった。
  • 2つの変数を0から順番に調べていく場合は2重ループと思い込んでいてそれでうまくいかないと気づくのに時間がかかり過ぎてしまった。
    　

コードを書いている途中で条件分岐がかなり多くなってしまって、方針が違うことに気づき最終的にほぼ解答と同じようにかなりスッキリまとまった。もう少し早めに気づけるように演習が必要と思った。

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

diff = []
i = 0
j = 0

while i < N and j < M:
    diff.append(abs(A[i]-B[j]))
    if A[i] < B[j]:
        i += 1
    else:
        j += 1
print(min(diff))

##まとめ
A,B問題は見たまま書けば正解できる問題ばかりで、これまでのコンテストでも正解できていたが、C問題から処理速度も考えないといけなくて、その考え方を知らなかったため苦戦していた。
とりあえず速く処理する方法をいくつか学んだが、もう少し本格的にアルゴリズムなどの勉強をする必要があると思った。
Atcoderやアルゴリズムなどの記事を読んで考え方の引き出しを増やしていきたい。