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

Atcoderに最近ハマっています。

パズル感覚で問題を解くのと、レーティングが数値で出るのが面白いですね。

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

A問題を高速で解く感覚と、C問題も方針が分かるようになってきました。

筆者の学習歴

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

まだまだ入門と言う感じですね。

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

・利用言語はPython3

・Pythonの利用は業務で少し

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

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

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

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

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

今週学習したこと

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

ABC ProblemsでA、B問題を中心に50問ほど解きました。

A問題はサクサクと進めるので、まずはA問題を全部解ききるように進めます。

学習内容

ABC ProblemsでA、B問題を80問(A:40問、B:10問)

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

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

 

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

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

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

 

今週は全探索を学習しました。

たのしい探索アルゴリズムの世界【前編:全探索、bit全探索から半分全列挙まで】

 

次の目標

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

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

茶色への昇級は見えてきたので、目標を更新しました。

目標:緑色パフォーマンス(800以上)を出す

緑色パフォーマンス獲得のため、目標を整理しました。

学習内容

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

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

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

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

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

今週のABC

ABCに参加してきました。

abc258

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

前回よりパフォーマンスは下がってしまったので、次回はリベンジしたいですね。

abc258

ABC結果

AC:2問

パフォーマンス:381

レーティング:280→289(+9)

段級位:9級

結果

A問題

A to Z String2

N,Xが与えられる。AをN個、BをN個、….ZをN個繋げてできる文字列の先頭からX番目の文字を出力せよ。

ASCIIコードで大文字を出力できれば良いです。

問題の条件の理解に手こずってしまいました。

7分かかりましたがAC。

import math
n,x=list(map(int,input().split()))
y=math.ceil(x/n)
print(chr(65+y-1))
B問題

1D Pawn

左右一列に並ぶN個のマスに、K個のコマが配置されている。

K個のコマはAiに置かれており、以下の操作をQ回行う。

・左からLi番目のコマが右端にあれば操作しない

・左からLi番目のコマの右にコマがなければ右に1マス移動させる

Q回の操作の後のコマの並びを出力せよ。

問題の制約から、Q×Nのループで実装すればいけそうと判断。

処理を整理するのに手こずりました。

30分ほどかかってAC

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

S=[0]*(N+1)
for i in A:
  S[i]+=1
#print(S)

for i in range(Q):
  cnt=0
  for j in range(N):
    if S[j]==1:
      cnt+=1
      if cnt==L[i]:
        if S[j+1]!=1:
          S[j+1]=1
          S[j]=0
        else:
          continue
        
#print(S)
#ary1 = np.array(S)
T=[i for i in range(N+1) if S[i]==1]
print(*T)
C問題

Robot Takahashi

N人の人がいて、N人は子供か大人である。

閾値Xを指定して、子供か大人を判断する時、正しく判断した人数をf(X)とする。

f(X)の最大値を求めよ

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

素直に全探索すると、TLEするので検索条件を絞る必要があります。

N*2となるループ以外に思いつかず、1時間近く考えましたがACできず無念。

感想

A,B問題をACすることができました。

2ACでパフォーマンスが381だったので、次回は茶色パフォーマンス以上を取ります。

来週学習すること

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

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

・AtCoder Problems

 

コメントを残す

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

CAPTCHA