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

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

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

筆者の学習歴

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

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

・利用言語はPython3

・Pythonの利用は業務で少し

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

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

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

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

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

今週学習したこと

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

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

学習内容

ABC ProblemsでB問題を30問

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

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

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

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

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

今週は勉強があまりできませんでした。

abc-problems-0717

次の目標

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

最近茶色パフォーマンスが安定していないので、まずは茶色パフォーマンスを安定させたいです。

目標を更新しました。

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

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

学習内容

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

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

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

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

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

今週のABC

ABCに参加してきました。

abc260

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

C問題以降が解けなかったのが痛かったです。

abc260

ABC結果

AC:2問

パフォーマンス:329

レーティング:304→307(+3)

段級位:9級

結果

A問題

Unique Letter

長さ3の文字列Sが与えられる。

Sに1文字だけ含まれる文字列を出力せよ。

問題はわかりやすいですが、方針を決めるのに手間取りました。

9分でACしました。

s=list(input())
flag=False
for i in range(3):
  if s.count(s[i])==1:
    print(s[i])
    flag=True
    exit()
    
print(-1)
B問題

Better Students are Needed

N人の学生がいて、数学の点数がA点、英語の点数がB点です。

数学の高い人X人、英語の点が高い人Y人、合計点が高い人Z人の順に合格とする時、合格者の番号を出力せよ。

ただし、同点であった場合は番号の若い方から合格とする。

問題の入出力と、TLEしないような処理に苦労しました。

N<=1000で3重ループを使ってしまうと時間が怪しくなるので、dequeを使うことにしました。

1時間ほどかかってなんとかAC

from collections import deque
n,x,y,z=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))

query=[]
ans=set()

for i in range(n):
	query.append([A[i],-1*(i+1),B[i],A[i]+B[i]])
query.sort(reverse=True)
#print(query)  

for _ in range(x):
	ans.add(-1*query[0][1])
	del query[0]
#print(ans)
    
query.sort(reverse=True, key=lambda x:(x[2],x[1]))
#print(query)
for _ in range(y):
	ans.add(-1*query[0][1])
	del query[0]
    
query.sort(reverse=True, key=lambda x:(x[3],x[1]))
#print(query)
for _ in range(z):
	ans.add(-1*query[0][1])
	del query[0]
    
Ans=list(ans)
Ans.sort()
for l in Ans:
	print(l)
C問題

Changing Jewels

高橋くんはレベルNの宝石を1つ持っている。

2つの処理を行い、宝石を変換することができる。

レベル1の青い宝石を最大でいくつ獲得できるか出力せよ。

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

問題は取り掛かりやすいですが、実装方法が浮かばず時間ぎれ。

感想

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

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

来週学習すること

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

またAtCoder Problemsで、B、C問題の過去問にも手を出していきたいです。

コメントを残す

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

CAPTCHA