競技プログラミング初心者が6ヶ月で水色コーダー目指す学習記【AtCoder-3週目】

Atcoderでもっと多くの問題を解きたい!と言うことで学習していきます。

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

筆者の学習歴

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

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

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

・利用言語はPython3

・Pythonの利用は業務で少し

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

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

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

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

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

今週学習したこと

今週3月26日(土)〜4月2日(土)は、DPの学習をしていました。

競プロの時間があまり取れず、DPの練習だけしました。

こちらEducational DP ContestのページでA-D問題を解きました。

今週のABC

ABCに参加してきました。

abc246

結果はこんな感じでした。

abc246

ABC結果

AC:2問

パフォーマンス:310

レーティング:93→111

段級位:11級

結果

A問題

xy平面上に長方形がある。

3点の座標が与えられるとき、4つ目の座標を出力せよ。

特に問題はないですね。

コードは冗長ですが、場合分けして解きました。

a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
d = list(range(2))

if a[0] == b[0]:
    d[0]=c[0]
elif b[0] == c[0]:
    d[0]=a[0]
else:
    d[0]=b[0]

if a[1] == b[1]:
    d[1]=c[1]
elif b[1] == c[1]:
    d[1]=a[1]
else:
    d[1]=b[1]

print(str(d[0])+" "+str(d[1])) 
B問題

(0,0)から、点(A,B)に向かって距離1だけ進むとき、進んだ先の座標を出力せよ。

int、floatに気をつけて出力すればOKです。

import math
a,b=map(int, input().split())
c=math.sqrt(a*a+b*b)

x=float(a)/c
y=float(b)/c
print(str(x)+" "+str(y)) 
C問題

N個の商品があり、それぞれの値段は数列Aである。

K枚のクーポンがあり、クーポンを使うと商品をmax{a-KX,0}の値段で買うことができる。

最も安くN個の商品が買えるようクーポンを使うとき、N個の商品を買うのに必要な金額を出力せよ。

普通にKのループを組めば解けると考え、一度提出しました。

ですが、Kが10*9までと大きいためTLEしてしまいます。

n, k, x=map(int, input().split())
a = list(map(int, input().split()))
a.sort()

while k>0:
    a[n-1] -= x
    a.sort()
    k-=1

for i in range(n):
    if a[i]<0:
        a[i]=0

print(sum(a)) 

続いて、DPで解くことを考えましたが、dp[i]の更新の数式が立てられず断念。

感想

2問目までは安定して解ける様になってきました。

2問目まで25分前後かかっているので、速度をあげたいですね。

レーティングは少しずつ(20ずつくらい)上がっていますが、ペースが遅いので練習を積む必要があります。

来週学習すること

D問題以降も勝負できる様にするため、グラフの学習をします。

DPの練習も進めます。

Educationl DP Contest / DPまとめコンテスト