【AtCoder17週目】競プロ初心者が6ヶ月で水色コーダー目指す学習記

期間は6ヶ月(25週間)とし、水色コーダーを目指します。

最近のC、D問題攻略のためアルゴリズム別学習を進めています。

筆者の学習歴

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

筆者の競技プログラミング歴

・利用言語はPython3

・Pythonの利用は業務で少し

・学習は「みんなのPython」を読んだくらい

・ABCコンテストには数回参加した(解けるのは1〜2問)

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

今日が2022年7月9日(土)で、9月20日までの半年の期間で学習を進めます。

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

今週学習したこと

今週からABC Problemsで過去問に取り組み始めました。

B問題を解くのと、アルゴリズムの分野別学習を進めます。

atcProblems0702

学習内容

ABC ProblemsでB問題を30問

さらに@e869120さんの記事で分野別学習を始めました。

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

基本アルゴリズム12個を学ぶと良いようです。

各記事ボリュームがありますが、まずは12個基本を押さえます。

全探索 二分探索 深さ優先探索 (DFS) 幅優先探索 (BFS)
動的計画法 (DP) ダイクストラ法 ワーシャルフロイド法 クラスカル法
高速な素数判定法 べき乗を高速に計算する手法 逆元を計算する手法 累積和

今週はキュー、DFS、二分探索を学習しました。

 

キューの問題

D. LR insertion

C. pushpush

 

精選100問

次の目標

前回のコンテストで茶色パフォーマンス(500)は出せました。

この調子でパフォーマンスを出せれば茶色(400)に昇級できそうです。

目標を更新しました。

目標:茶色パフォーマンスを継続して出せるようにする

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

学習内容

・A・B問題を高速で解く(理想5〜10分以内)

・C・D問題をどちらかあるいは両方解く

まずはA・B問題を確実に解けるようにします。

C、D問題については簡単な場合両方、難しい場合はどちらかを解きます。

これで緑色パフォーマンスを取れる可能性があります。

今週のABC

ABCに参加してきました。

abc259

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

B問題が解けなかったのが痛かったです。

abc259

ABC結果

AC:2問

パフォーマンス:500

レーティング:289→304(+20)

段級位:9級

結果

A問題

Growth Record

高橋くんの今の年齢と身長が与えられる。M歳の時の身長を出力せよ。

問題はわかりやすいですが、条件が少し多いです。

4分でACしました。

n,m,x,t,d=map(int,input().split())
if m>=x:
print(t)
else:
print(t-(x-m)*d)
B問題

Counterclockwise Rotation

xy平面上の座標を反時計回りにt度回転した座標を求めよ。

問題はシンプルですが、実装方法を調べるのに時間がかかりました。

Numpyでの実装を考えましたが、回答の式を直接実装するのが速いと判断。

import math  
a,b,t=map(int,input().split())
theta=t*math.pi/180
c=a*math.cos(theta)-b*math.sin(theta)
d=a*math.sin(theta)+b*math.cos(theta)
print(c,d)
C問題

XX to XXX

文字列S、Tが与えられる。

Sのうち、同じ文字が連続している箇所の間に同じ文字を追加する操作を任意回数繰り返す。

SをTにできるか判定せよ。

残り時間はこの問題に取り組みました。

Tを見て同じ文字が3つ連続している箇所から1つを取り除く操作を繰り返していきできそうな気がしました。

しかし実装方法が浮かばず時間ぎれ。

感想

A、B問題しかACできませんでした。

C問題は解きたかったので反省です。

来週学習すること

C、D問題以降も勝負できる様にするため、まずはAtCoder ProblemsでB問題を解いていきます。

その後は、BFS、DPなどのアルゴリズムの学習をします。

・AtCoder Problems

コメントを残す

メールアドレスが公開されることはありません。

CAPTCHA