水色コーダーを目指す取り組みをしてきました。
悔しいので、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個を学習します。
今週の学習内容はこちらです。
一通り学習したアルゴリズムは灰色、今週学習したものを太字にしています。
| 全探索 | 二分探索 | 深さ優先探索 (DFS) | 幅優先探索 (BFS) |
| 動的計画法 (DP) | ダイクストラ法 | ワーシャルフロイド法 | クラスカル法 |
| 高速な素数判定法 | べき乗を高速に計算する手法 | 逆元を計算する手法 | 累積和 |
DP
DPはこちらの記事で学習し、問題を数問解いて感触を掴みました。
アルゴリズム学習
典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～
動的計画法超入門！ Educational DP Contest の A ～ E 問題の解説と類題集
問題演習（A~E）
Educational DP Contest / DP まとめコンテスト
データ構造学習
データ構造3つを学習します。
一通り学習した構造は灰色、今週学習したものを太字にしています。
| グラフ | 木 | Union-Find |
筆者の学習歴
学習歴はこんな感じです。
・利用言語はPython3
・Pythonの利用は業務で少し
・学習は「みんなのPython」を読んだくらい
・ABCコンテストには数回参加した（解けるのは1〜2問）
競プロではC++を使う方が多いかと思いますが、筆者はPythonのシンプルさに感動したためPythonで取り組みます。
毎週のAtCoder Beginner Contest（ABC）をペースメーカーにしていきます。
今週のコンテスト
ARC151
ABCに参加してきました。
0問AC、灰色パフォーマンスでした。
問題を解くことができませんでした。
AC：2問
パフォーマンス：168
レーティング：421→389（-32）
段級位：9級
結果
Equal Hamming Distances
2つの文字列S、Tが与えられる。
S、Tとハミング距離が等しいUで辞書順で最も小さいものを出力せよ。
ACできませんでした。
d(S,U)-d(T,U)を調べる発想が必要でした
N=int(input())
S=input()
T=input()
W=max(S,T)
x=list(S)
y=list(T)
z=W.count('1')
count=0
for i in range(N):
if x[i]!=y[i]:
count+=1
if count%2==1:
print(-1)
exit()
else:
count=count//2
K=str(W)
if count<=z:
U=K.replace('1','0',count)
else:
U=K.replace('1','0',z)
U=U[::-1]
U=U.relace('0','1',count-z)
U=U[::-1]
print(U)
次の目標
目標：緑色パフォーマンスを出せるようにする
緑色昇級のため、目標を整理しました。
・A・B問題を高速で解く（理想5〜10分以内）
・C・D問題をどちらかあるいは両方解く
安定して茶色パフォーマンスを出し、できれば緑色パフォーマンスを目指します。
