【AtCoder30週目】競プロ初心者が6ヶ月で水色コーダー目指す学習記（延長戦）

水色コーダーを目指す取り組みをしてきました。

悔しいので、3ヶ月の延長戦を設定して続けることにしました。

期間は2022年9月から、12月までの3ヶ月としました。

学習の方針

e869120さんの記事を参考に学習の方針を立てます。

レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】

上の記事によると、水色コーダー（レーティング1200）の条件はこんな感じのようです。

AtCoder で水色コーダー、つまりレーティング 1200 に到達するには、

• AtCoder Beginner Contest で確率 8 割以上で 4 問正解できる
• AtCoder Beginner Contest で確率 3-4 割で 5 問正解できる
• AtCoder Beginner Contest の問題をある程度早く解くことができる
  • 目安は、A 問題 1 分、B 問題 4 分、C 問題 10 分、D 問題 25 分

A~D問題を50分以内目安で解くことが必要とのことです。

B問題4分、C問題10分が次の壁となりそうです。

アルゴリズム学習

こちらの記事を見て、水色に到達するために何が必要か考えました。

レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】

解説されている基本アルゴリズム12個を学習します。

今週の学習内容はこちらです。

一通り学習したアルゴリズムは灰色、今週学習したものを太字にしています。

DP

DPはこちらの記事で学習し、問題を数問解いて感触を掴みました。

アルゴリズム学習

典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～

動的計画法超入門！ Educational DP Contest の A ～ E 問題の解説と類題集

問題演習（A~E）

Educational DP Contest / DP まとめコンテスト

データ構造学習

データ構造3つを学習します。

一通り学習した構造は灰色、今週学習したものを太字にしています。

筆者の学習歴

学習歴はこんな感じです。

みんなのPython Lightweight Language Python Definitive Guide / 柴田淳

posted with カエレバ

bookfanプレミアム

Yahooショッピング

Amazon

楽天市場

競プロではC++を使う方が多いかと思いますが、筆者はPythonのシンプルさに感動したためPythonで取り組みます。

毎週のAtCoder Beginner Contest（ABC）をペースメーカーにしていきます。

今週のコンテスト

ABC274

ABCに参加してきました。

ABC274

3問AC、茶色パフォーマンスでした。

結果

6分13秒時点（所要時間6分13秒）でACしました。
少数部を3桁並べる必要があるのが注意点です。

a,b=map(int,input().split())
s=b/a
print("{:,.3f}".format(s))

17分16秒時点（所要時間11分3秒）でACしました。
列を探索する処理方法に少してこづりました。
処理は、素直な全探索でOKです。

H,W=map(int,input().split())
a = [list(input()) for l in range(H)]
b=[0]*W
#print(a)
#print(a[0][1])

for i in range(W):
  for j in range(H):
    if a[j][i]=="#":
      b[i]+=1
      
print(*b)

37分36秒時点（所要時間20分30秒）でACしました。
i番目のアメーバは、2iと2i+1のアメーバになる条件で計算します。
アメーバの世代数を記録し、N回分遡る処理で計算しました。

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

B=[0]*(2*N+2)

for i in range(1,N+1):
  B[2*i]=B[A[i-1]]+1
  B[2*i+1]=B[2*i]
  
for i in range(1,len(B)):
  print(B[i])

60分ほど試行錯誤しましたが、ACできませんでした。
Nが1,000までありうるので、素直なbit全探索ではTLEすると考えました。
正負の値を集合に足していく処理で良かったようです。

def solve(n, x, y, a):
    for p, ds in [(x, a[1::2]), (y, a[0::2])]:
        #print(p,ds)
        que = [p]
        #print(que)
        for d in ds:
            S = set()
            for c in que:
                S.add(c + d)
                S.add(c - d)
            que = list(S)
            #print(que)
        if not 0 in que:
            return "No"
    return "Yes"

n, x, y = map(int, input().split())
a = list(map(int, input().split()))
x -= a[0]
a = a[1:]
print(solve(n, x, y, a))

次の目標

目標：緑色パフォーマンスを出せるようにする

緑色昇級のため、目標を整理しました。

安定して茶色パフォーマンスを出し、早いうちに緑色パフォーマンスを目指します。