数学超苦手な文系エンジニアがAtCoder Beginner Contest 267に参加してみました
こんにちは、AWS事業本部コンサルティング部に所属している今泉(@bun76235104)です。
皆さんはアルゴリズムと数学に強くなりたいですか？
私はなりたいです。
私は以前よりAtCoderという競技プログラミングのサービスで毎週コンテストに出て学習をしております。(前回のコンテストの出場の際に書いた記事はこちらです)
今回も 9/3に開催された NECプログラミングコンテスト2022 (AtCoder Beginner Contest 267)に参加させて頂きましたので、自身の学んだことも含めてアウトプットさせていただきます。
前置き・事前知識
こちらの記事の前置き・事前知識をご参照ください。(見ていただきたい内容が増えたらこちらを更新させていただきます)
想定される読者の方について
こちらも、前回の記事の段階から変わっておりませんのでご参照ください。 (競プロ中級者以上の方であれば、特に学べることも刺激を受けられることも無いかもしれませんのでご了承ください)
コンテスト参加結果
以下のように目標を設定しておりますが、今回は最低目標の2問を解くことまでしかできませんでした。
- 最低目標: A・Bの2問を解く
- チャレンジ目標: C問題(もしくはD問題)を解く
ただB問題も前回などと比べると少し複雑だったためか、レート自体は下がることなく上昇させることができました。
今回はC問題を解ききることができなかったのですが、コンテスト終了後に解説を見て回答することができました。
後に記載しますが、数学的な要素だけでなくアルゴリズム的にも工夫のいる面白い問題でした!
A問題 Saturday
ある日、学校へ行くのに疲れてしまった高橋くんは、土曜日まであと何日あるかを知りたくなりました。その日は平日で、曜日を英語で表すと S だったことが分かっています。その日より後の直近の土曜日は何日後かを求めてください。
制約を見てみましょう。
S は Monday, Tuesday, Wednesday, Thursday, Friday のいずれかである
この制約から入力値はこの5種類だけ考えれば良いということになりますね。
if 文で分岐しても良いのですが、今回のように入力値があらかじめ決まっている場合はPythonならdict型で実装してしまうのがシンプルだと思います。
この際面倒ですが、与えられる入力値は間違えないようにコピペで記載するようにしています。
以下が私が提出したコードです(1分50秒ほどで提出)
memo = {"Monday": 5, "Tuesday": 4, "Wednesday": 3, "Thursday": 2, "Friday": 1}
S = input()
print(memo[S])
B問題 Split?
みんな大好きボーリングでスプリットの判定をするという問題ですね。楽しいですね。
ただ私は混乱して無駄に複雑なデータ構造を用意してしまったので、コンテスト中はあまり楽しくなかったです
コンテスト中は以下のようなことを考えていました(後から考えてもよく無い方法だったと思います)
- 1のピンが倒れているのは大前提だから、それを満たしているかは最初に確認した方が良いな
- 7つの列に対して最大でも2ピンしか並んでいないから各列のピンの立っている・立っていないの状況を
[[7つの要素(前列のピンの状況)],[7つの要素(後列のピンの状況)]]と二次元配列で考えれば良いかな(!?)
正直お見せするのも恥ずかしいのですが、一応正解できたコードがこちらです。(31分程で提出)
S = list(map(int, list(input())))
pins = [[-1, -1, 2, 1, 3, -1, -1], [7, 4, 8, 5, 9, 6, 10]]
# ピン1が倒れていないのは早めにアウトにする
if S[0] == 1:
print("No")
exit()
# 倒しているピンのメモ
for i, s in enumerate(S):
pin = i + 1
is_layed = True if s == 0 else False
for j in range(7):
cand1 = pins[0][j]
cand2 = pins[1][j]
if is_layed is False:
continue
if cand1 == pin:
pins[0][j] = 0
if cand2 == pin:
pins[1][j] = 0
standed = []
all_layed = []
for i in range(7):
col1 = pins[0][i]
col2 = pins[1][i]
# 立っているピンがあるか調べる
if col1 not in (0, -1) or col2 not in (0, -1):
standed.append(i)
# 全て倒れている列か調べる
if col1 in (0, -1) and col2 in (0, -1):
all_layed.append(i)
if len(standed) < 2:
print("No")
exit()
if len(all_layed) <= 0:
print("No")
exit()
_min = min(standed)
_max = max(standed)
for i in all_layed:
if i > _min and i < _max:
print("Yes")
exit()
print("No")
こんな良くわからない実装をしてしまうのがコンテストの怖いところです。
結局各列にピンが1本でも立っているか・1本もピンが立っていないかだけを管理すれば良いので [1列目にピンが立っているか,2列目にピンが立っているか..,7列目にピンが立っているか] という風に1次元のリストで管理した方がまだ良いですね。
そのようにリファクタすると以下のようになります(まだこっちの方がわかりやすい気がします)
S = list(map(int, list(input())))
# 各列でピンが1つでも立っているか、立っていないかを判定するためのリスト
# 1が列に立っているピンがある・0が立っているピンが無い状態を表す(最初は全て立っている)
cols = [1 for _ in range(7)]
# 1番目のピンが立っているか判定
if S[0] == 1:
print("No")
exit()
# 同じ列に立っているピンの組と何列目かをタプルで表現 (前のピン番号, 後ろのピン番号, 列番号)
combi_list = [(2, 8, 3), (1, 5, 4), (3, 9, 5)]
for combi in combi_list:
front, back, col_num = combi
if S[front - 1] == 0 and S[back - 1] == 0:
cols[col_num - 1] = 0
continue
cols[col_num] = 1
# ピン番号: 列番号の対応表
pin_col_map = {7: 1, 4: 2, 6: 6, 10: 7}
for i, v in enumerate(S):
# 2ピンある列は上で確認済みなので飛ばす
if i + 1 in set([2, 8, 1, 5, 3, 9]):
continue
col_num = pin_col_map[i + 1]
bcols[col_num - 1] = v
stand_cols, down_cols = ([], [])
for i, v in enumerate(cols):
if v == 1:
stand_cols.append(i)
continue
down_cols.append(i)
if len(stand_cols) < 2 or len(down_cols) <= 0:
print("No")
exit()
# 立っているピンがある列の最小値・最大値を算出
_min_stand = min(stand_cols)
_max_stand = max(stand_cols)
# 立っているピンとピンの間に全て倒れている列があればスプリット状態
for down_col in down_cols:
if down_col > _min_stand and down_col < _max_stand:
print("Yes")
exit()
print("No")
解説のように素直に書いた方がよかったかもしれません。
C問題 Index × A(Continuous ver.)
C問題については、とても良い問題だと個人的に感じております。
自分の理解促進のためにも複数ステップで考えてみました。(公式の解説動画でとてもわかりやすく教えてくださったので、自分でも考え直しました)
問題のサンプルを見て内容を理解できました。
ここだけ見ると「なーんだ。ただ言われた通りに左から順にM字を取り出して計算していくだけじゃん」と思うかもしれません。
以下のようなコードで確かにサンプルを通すことができますが、TLE (Time Limit Exceeded) となり、制限時間内にプログラムを終了させることができません。
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
ans = -(10**17)
for i in range(N):
# オーバーするなら終わり
if i + M - 1 > N - 1:
break
tmp = A[i : i + M]
s = 0
for i, v in enumerate(tmp):
s += (i + 1) * v
ans = max(ans, s)
print(ans)
EX21 - 計算量の見積もりのとおり、AtCoderでは1秒あたり10の8乗程度の計算が可能とのことです。
今回の問題の制約を見てみると 「NとMが最大で(10の5乗)」 という制約があります。
つまり N = 2 * (10の5乗) かつ M = 2 * (10の5乗) の時には上のような2重ループの書き方であれば 10の10乗 を超える計算量となってしまうため、間に合わないということになります。
この辺りについては、公式の解説動画でも分かりやすく触れてくださっています。
C問題の工夫1 式変形
公式の解説動画でホワイトボードに記載いただいているように、以下のステップで気付けを得ることができそうです。
まず例を考えてみましょう
ここで S1 と S2 をもう少し近づけて考えてみると
4と-1にかける数が違うだけで3つのうち2つ同じ項目を利用しています。
ここから 何とかして前の結果(S1)から次の結果(S2)を求めることができないだろうか という考え方にいたりました。
(なお私はここで具体的に解決策が思い浮かばずコンテスト終了しています)
ここでS1の方が 4*2 -1 * 3 を持っていて、S2の方が 4 * 1 -1 * 2 を持っていてかける数が1つずつ小さいので S1 - S2 を計算してみます。
すると以下のように式が立てられることに気づきます。
更に式を変形していくと以下のようにS1を利用してS2を導くための式が見えてきそうです
【余談】まずこんな式の変形をする発想がないんだがという方へ
※ C問題の解説を見てご理解いただける方は以下を見る必要はないかと思います。
私のように数学が苦手な文系の方はこう思われる方もいらっしゃるかもしれません。
なんでS1からS2を引くという発想に至るんだ。その発想がまず出てこないよ。
そんな方は是非一度この書籍を読まれてみてください。
この書籍の中の「等比数列の和の公式」の解説で今回の式変形に似た考え方が出てきます。
私はこのような体験をするうちに、「あ。数学が得意な人が問題を一般化していくのに、パターンみたいなものがあるんだな。全くの0からこれを思いつく天才ばかりでは無いのかもしれない」と思うようになりました。
数学が得意な方はこのような経験を早くから繰り返しているので、私も自分のペースで体験を積み重ねるしかないのかな。と考えております。
実際私はこのC問題を解説見るまで解けなかったわけですし
更に計算量を一工夫(累積和という考え方)
ここまでは数学的な考察が主という感じでしたね。
これで式を一般化できたのでコードに落とし込んでみましょう。
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
# 前の答えを利用するので最初の答えだけ手で出しておく
s1 = 0
for i, v in enumerate(A[:M]):
s1 += (i + 1) * v
bef_ans = s1
ans = bef_ans
for i in range(1, N + 1):
# M先まで見れなくなったら終了
if i + M > N:
break
# A[i-1]からA[i-1+M-1]までの和を求める
tmp_list = A[i - 1 : i - 1 + M]
total = sum(tmp_list)
# 式に当てはめる
cur_ans = bef_ans + (A[i + M - 1] * M) - total
bef_ans = cur_ans
ans = max(ans, cur_ans)
print(ans)
実際に提出すると、これでもTLEになります。
15行目から16行目の部分で、結局total を算出するために AからM文字分の文字を切り取って合計値を算出しており、計算量が N * Mとなっているためです。
tmp_list = A[i - 1 : i - 1 + M] total = sum(tmp_list)
特定の区間から特定の区間までの合計値を少ない計算量で算出する必要があります。
ここで利用できるのが累積和というテクニックです。
以下の記事が非常に分かりやすいので是非ご参照ください。
この累積和を利用して書き直したのが以下のコードとなります。
from itertools import accumulate
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
# N項までの累積和を用意(Pythonの標準ライブラリを利用)
T = [0] + list(accumulate(A))
# 前の答えを利用するので最初の答えだけ手で出しておく
s1 = 0
for i, v in enumerate(A[:M]):
s1 += (i + 1) * v
ans, bef_ans = s1,s1
for i in range(1, N + 1):
# M先まで見れなくなったら終了
if i + M > N:
break
# A[i-1]からA[i-1+M-1]までの和を求める
total = T[i + M - 1] - T[i - 1]
cur_ans = bef_ans + (A[i + M - 1] * M) - total
ans = max(ans, cur_ans)
bef_ans = cur_ans
print(ans)
このように累積和を利用して、特定の区間の和を少ない計算量で算出することで無事正解コードになりました。
以上が筆者の現段階の力で理解できる範疇で書いたコードになりますが、AtCoderは他の方の提出したコードを眺めて勉強するのも醍醐味の一つですので、ぜひ調べてみてください!!
まとめ・感想
- B問題も前回より難しかった
- C問題が数学的考察だけではなく、そこからアルゴリズム的に一工夫必要なのが面白い
- (個人的に)レートが下がらないでよかった
まずはレート400以上でなれる茶色コーダーを目指して、可能な限り毎週コンテストに参加していこうと思います!! (他の学習もあるので競プロフルコミットはできないですが・・・)
私のような数学本気で苦手勢の方にも、何かしらの刺激になれば幸いです。
