この記事は公開されてから1年以上経過しています。情報が古い可能性がありますので、ご注意ください。
こんにちは、AWS事業本部コンサルティング部に所属している今泉(@bun76235104)です。
皆さんはアルゴリズムと数学に強くなりたいですか？
私はなりたいです。
時間を見つけては、ちょこまかとAtCoderという競技プログラミングのサイトの過去問を解いたり、実際にコンテストに参加したりしています。
今回も2022/8/27に開催された AtCoder Beginner Contest 266 というコンテストに参加してみたので、その時の記録や自分がどう考えてどのようなコードを出したのかなどをご紹介させていただきます。
前置き・事前知識
AtCoderとは何か・どのようにして問題を解くのかといったことに関しては、以下の記事をご参照ください。
※ 本記事はあくまで私がAtCoderに参加した結果を記載しており、会社全体が私と同じレベルということではありませんことご承知おきください。
想定される読者の方について
私自身は高校時代から所属も脳の構造もゴリゴリの文系であり、数学をとても苦手としています。
いつまでも苦手意識を持っているのも嫌で、時間を見つけて競技プログラミングの学習を通してアルゴリズムと数学の学習を行なっています。 (仕事・家庭・他の分野の学習の都合で競技プログラミングのみにフルコミットすることはできない状況です)
そんな私の現在のレベルは下図でいうところの灰コーダー(一度でもコンテストに参加したらなれる)の上位レベルです。
(画像はe869120様のレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編：競プロを始めよう】 - Qiitaより引用させていただいております)
以上を踏まえて、本記事を読んで何らかの学び・刺激を受けることができる方は以下に該当する方と思われます。
- これから競技プログラミングを始めようとしている・始めたばかり
- 数学やアルゴリズムが苦手
- 周りのレベルの高さに挫折した・挫折しかけている
- AtCoder Beginner ContestでC問題まで解くことを目標にしている
- PythonでAtCoderを始めた・始めている
- 個人的に筆者を知っている・応援している(!?)
それ以外の方には特に見るべきポイントも無いと思われますのでご了承ください。
コンテスト参加結果
毎回の目標としているC問題まで解くことができました。
レートも271 => 312 と上げることができました。
それぞれの問題の内容とコンテスト中のコードと何を考えていたかをまとめてみます。
A問題 Middle Letter
英小文字からなる長さが奇数の文字列 S が与えられます。S の中央の文字を出力してください。
私が提出したコードがこちらです(1分25秒程で提出)
S = input()
cent = len(S) // 2
print(S[cent])入力される文字列が奇数文字ということがわかっているので、頭の中で以下のように実際の文字を考えてみました
input: abc
output: b(2文字目。添字だと1)
input:abcde
output: c(3文字名。添字だと2)Pythonは // で除算結果を切り捨てた結果を計算してくれるので 3//2 だと 1 が、 5//2 だと 2 が返されます。
そのまま出力された数値を添字に使って出力すればOKでした。
B問題 Modulo Number
−10 ** 18 以上 10 ** 18以下の整数Nが与えられます。以下の条件を満たす 0 以上 998244353 未満の整数 x を求めてください。なお、答えが一意に定まることが証明できます。
N−x は 998244353 の倍数
私が提出したコードがこちらです(2分30秒程で提出)
N = int(input())
ans = (N % 998244353)
print(ans)答えを書くとこれだけなのですが、個人的にこれがパッと書けるようになっていることに少しばかりの成長を感じています。
以下のような考えをしていました
N-xが998244353の倍数になることがわかっているNから何を引いたら998244353の倍数になるかということかN - x = a * 998244353ということだよね(aは整数)- 余りを考えるだけじゃないだろうか
a * 998244353の部分は998244353で割ったら確実に余りが0になる- Nを
998244353で割ったあまりが出せれば、あまりの分だけ引き算をしてあげれば998244353の倍数になるはず N % 998244353を求めれば良いだけか
実際の入力例からも考えてみます
- 入力例1:
998244354 % 998244353は1になる。998244354-1が998244353の倍数になるのでOK - 入力例2:
-9982443534 % 998244353は998244349となる。-9982443534-998244349が998244353の倍数になるのでOK
解説 - AtCoder Beginner Contest 266を確認しましたが、考え方はこれで合っているようでした。
ちなみに私はゴリゴリの文系なので、AtCoderの学習を始める前であれば↓という考え方が出てこないか、時間がかかったと思います。
この問題で求められていることは、 N を 998244353 で割ったあまりを答えることです。
私の場合ですが こちらの「プログラマの数学 第2版」の第3章「第3章 剰余 ―― 周期性とグループ分け」を読むことで考え方が理解できるようになりましたので、解説を見てもピントこない方におすすめです!!
他にも余りの性質は面白く、よく出題されるているのを観測しています。
このような記事も見てみると面白いと思います。
C問題 Convex Quadrilateral
いやー・・・とても苦手な数学の問題ですね。
3回間違えましたが、何とか検索を駆使して答えを出すことができました。(出した答えは解説のやり方とは異なります)
四角形の各辺の角度を求めれば良いということで、それぞれの4点の座標の位置がわかっているのでベクトルか三角関数の問題かな？と思いました。
そうしたら以下のように2つのベクトルの成す角を求める参考記事が出てきたのでこちらを参考にいたしました
最終的に提出したコードがこちらです
import numpy as np
import math
A = np.array(list(map(int, input().split())))
B = np.array(list(map(int, input().split())))
C = np.array(list(map(int, input().split())))
D = np.array(list(map(int, input().split())))
def nasukaku(cent, left, right):
vec1 = [left[0]-cent[0], left[1]-cent[1]]
vec2 = [right[0]-cent[0], right[1]-cent[1]]
absvec1 = np.linalg.norm(vec1)
absvec2 = np.linalg.norm(vec2)
inner = np.inner(vec1, vec2)
cos_theta = inner/(absvec1*absvec2)
theta = np.degrees(np.arccos(cos_theta))
return theta
ABC = nasukaku(B, A, C)
BCD = nasukaku(C, B, D)
CDA = nasukaku(D, C, A)
DAB = nasukaku(A, D, B)
# print(ABC, BCD, CDA, DAB)
if ABC < 180 and BCD < 180 and CDA < 180 and DAB < 180:
if math.isclose(ABC+BCD+CDA+DAB, 360.0) is False:
print('No')
exit()
print('Yes')後で解説 - AtCoder Beginner Contest 266を見て気づいたのですが、ベクトルの外積を利用すればよかったようです。
これは、正直もっと数学自体の勉強と問題の数をこなさないとパッと出てこなさそうだなと感じました・・・
まとめ・感想
- B問題をサクッと解けたことにちょっとした成長を感じた
- C問題は「三角関数とかベクトルだ」と検索キーワードを導出できるだけマシになったかもしれない
- ともあれ、レートが上がってよかった
競プロは「自分のレベルの低さ」とか「周りの優秀さ」ばかりに着目してしまうと、嫌になってきてしまうと考えています。(それで挫折経験あり)
今回みたいに「勉強を始める前の自分」と比較して成長を喜びながら、緩やかに続けて行きたいと思います。