水色コーダーを目指す取り組みをしてきました。
期間は2022年3月から、9月20日までの半年としてきました。
結果は407（茶色）で終わりました。
悔しいので、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) | ダイクストラ法 | ワーシャルフロイド法 | クラスカル法 |
| 高速な素数判定法 | べき乗を高速に計算する手法 | 逆元を計算する手法 | 累積和 |
二分探索に関しては、Pythonにライブラリがあります。
bisect、bisect_left、insortの使い方を確認したので、一旦よしとしました。
DFSは、けんちょんさんのこちらの記事の問題を解きました。
PythonでDFSを解くならこちらの問題が基準になるかと思います。
コードは模範解答です。
他のDFS問題でも使えそうなので、メモしておきます。
# おまじない
import sys
sys.setrecursionlimit(300000)
N=int(input())
G=[[] for i in range(N+1)]
for i in range(N-1):
a,b=map(int,input().split())
G[a].append(b)
G[b].append(a)
for i in range(N+1):G[i].sort()
ans=[]
def dfs(crr,pre):
ans.append(crr)
for nxt in G[crr]:
if nxt!=pre:
dfs(nxt,crr)
ans.append(crr)
dfs(1,-1)
print(*ans)
データ構造学習
データ構造3つを学習します。
一通り学習した構造は灰色、今週学習したものを太字にしています。
| グラフ | 木 | Union-Find |
筆者の学習歴
学習歴はこんな感じです。
・利用言語はPython3
・Pythonの利用は業務で少し
・学習は「みんなのPython」を読んだくらい
・ABCコンテストには数回参加した（解けるのは1〜2問）
競プロではC++を使う方が多いかと思いますが、筆者はPythonのシンプルさに感動したためPythonで取り組みます。
毎週のAtCoder Beginner Contest（ABC）をペースメーカーにしていきます。
今週のコンテスト
ABC270
ABCに参加してきました。
2問AC、茶色パフォーマンスでした。
C問題を解くことができませんでした。
AC：2問
パフォーマンス：586
レーティング：404→423（+19）
段級位：8級
結果
1-2-4 Test
配点が1点、2点、4点のテストがある。
すぬけくんは、高橋くん、青木くんの少なくともどちらか一方が正解した問題を正解する。
すぬけくんの得点を出力せよ。
10分8秒時点（所要時間10分8秒）でACしました。
BitのOR演算であることを理解するのに時間がかかり、分岐を書き出そうとしてしまいました。
a,b=map(int,input().split())
print(a | b)
Hammer
数直線上の迷路に、ゴール、壁、ハンマーの座標が与えられる。
ハンマーを取得した後なら壁を壊すことができる。
ゴールに到達できるか出力せよ
20分36秒時点（所要時間10分28秒）でACしました。
この問題は分岐を書き出せば良いと判断しました。
X×Yの正負で判断する処理で工夫しています。
import math
x,y,z=map(int,input().split())
if x*y<0:
print(abs(x))
elif abs(x)<abs(y):
print(abs(x))
else:
if z*y<0:
print(2*abs(z)+abs(x))
elif abs(z)<abs(y):
print(abs(x))
else:
print(-1)
Simple Path
木が与えられる。
頂点XからYへの単純経路を出力せよ
ACできませんでした。
DFSを使おうと思いましたが、最短経路出力の処理が分かりませんでした。
こんなコードでACしている解答もあったので、記憶しておきたいです。
（networkxは計算時間がかかりますがギリギリACできるようです）
import networkx as nx
g=nx.Graph()
n,x,y=map(int,input().split())
for i in range(n-1):
u,v=map(int,input().split())
g.add_edge(u,v)
print(*list(nx.shortest_path(g,x,y))) 次の目標
目標：緑色パフォーマンスを出せるようにする
緑色昇級のため、目標を整理しました。
・A・B問題を高速で解く（理想5〜10分以内）
・C・D問題をどちらかあるいは両方解く
安定して茶色パフォーマンスを出し、できれば緑色パフォーマンスを目指します。
