AtCoderBeginnerContest274 に参加しました

数学苦手エンジニアがキーエンスプログラミングコンテスト2022（AtCoder Beginner Contest 274）に参加してみました！問題の意味がわからない時には、雰囲気で理解した気にならずに納得するまで、コードに手をつけるべきではないという学びを得ました。

#AtCoder

#Python

#競技プログラミング

今泉大樹

2022.10.23

この記事は公開されてから1年以上経過しています。情報が古い可能性がありますので、ご注意ください。

こんにちは、AWS 事業本部コンサルティング部に所属している今泉（@bun76235104）です。

私は以前より AtCoder のコンテストに参加しており、先日茶色コーダーといわれるレート帯に入ることができました。

現在は自分のできるペースで緑コーダーというレート帯を目指して、ゆっくり精進しています。

今回も 2022/10/22（土）に開催されたキーエンスプログラミングコンテスト 2022（AtCoder Beginner Contest 274）に参加してきました！

AtCoder のレートと筆者のレベル感について

以下表および画像は e869120 様のレッドコーダーが教える、競プロ・AtCoder 上達のガイドライン【初級編：競プロを始めよう】 - Qiitaより引用させていただいています。

レーティング	色	相対的な位置	絶対的な位置
2800+	赤	上位 0.2%
2400-2799	橙	上位 0.6%
2000-2399	黄	上位 2%	アルゴリズムの研究職・研究開発で重宝されるレベル
1600-1999	青	上位 5%	ほとんどの IT 企業でアルゴリズム能力がカンストする
1200-1599	水	上位 10%	半数以上の IT 企業でアルゴリズム能力がカンストする
800-1199	緑	上位 20%	エンジニアとしてかなり優秀
400-799	茶	上位 35%	学生なら優秀
1-399	灰	上位 100%

atcoder_colors

私は上記の茶色の下位に位置しており、一つ上の緑を目指しています。

AtCoder の問題を解くのは楽しいのですが、私の現在の職務上のロールではプログラムを直接自分で書くことは少なく、競技プログラミングにリソースの全てを投じることはできない状況です。

BeginnerContest と冠するコンテストでは毎回 B 問題までは絶対解いて、C 問題までを 100 分以内に解くことを目標にしています。

筆者の結果について

abc274_bun913_result

コンテストは 10/22 の21:00 ~ 22:40 までの開催でした。

私の提出履歴がこちらです。

提出日時	問題	結果
2022-10-22 22:19:23	C - Ameba	AC（正解）
2022-10-22 21:46:56	C - Ameba	WA（不正解）
2022-10-22 21:12:00	B - Line Sensor	AC（正解）
2022-10-22 21:03:14	A - Batting Average	AC(正解)

今回目標としている C 問題まで解くことができましたが、後に紹介する C 問題を難しく考えすぎて、1 回不正解を出してしまったことに加えて、正解の提出自体も遅い時間となってしまいました。

A - Batting Average

整数 A,B が与えられるので B / A を小数点第 4 位で四捨五入した値を表示する問題となっています。

ただし、プログラムにおいて小数の計算をする時には誤差へ注意が必要です。

私は誤差を恐れて、Python の decimal モジュールを利用して解くというある意味力技解法を用いました。

from decimal import Decimal, ROUND_HALF_UP

A, B = list(map(int, input().split()))
f = B / A
ans = Decimal(str(f)).quantize(Decimal("0.001"), rounding=ROUND_HALF_UP)
print(ans)

公式の解説を見て勉強になったのですが、少数ではなく整数で取り扱うテクニックがあるようです。

このような解法を一瞬で思いつくようになれば、とてもカッコ良いですね。

B - Line Sensor

問題を見た瞬間「ん？」と思いましたが、以下解説を見て納得しました。

j 列目に置かれている箱の個数。言い換えると、Cij が # であるような整数 i の個数。

これは実際に私がコンテスト中に整理のために書いた図ですが、以下のように列ごとに#が何個あるか数えて、列数分出力すれば良いだけです。

abc274_b_step1

色々とやり方はあるかと思いますが、コンテスト中には表の列と行を転置して、for 文で列ごとの#の数を数えています。

H, W = list(map(int, input().split()))
C = [list(input()) for _ in range(H)]
# ↓列と行を入れ替え
cd = [list(x) for x in zip(*C)]
ans = []
for c in cd:
    # 列ごとに#の数を数える
    t = c.count("#")
    ans.append(t)
print(*ans, sep=" ")

C - Ameba

abc274_c_question_description

はい。これだけ見てもよくわかりませんでした。

今回意味を理解することに時間をかけてしまった問題です。

さらに悪いことに問題を雰囲気で理解した気になり、手を動かし始めてしまったのが反省点です。

要点を整理するとこんな形です。

最初はアメーバが1匹
各アメーバは分裂して消滅し、新たに2匹のアメーバが生まれる
A[i]のアメーバが分裂すると,2iと2i+1という番号をつけたアメーバが生まれる
1匹のアメーバから始まって、N回の分裂があるので、消滅するアメーバも含めて全体として2N+1のアメーバがいる
2N+1のアメーバについて親から何世代離れているかを考える

これでもわかりにくいので、私が70分経過後くらいに再度整理するために書いた図がこちらになります。

余談ですが、自分のコードの汚さだけでなく字の汚さも晒しているのには驚きですが、コンテスト中の切羽詰まったリアルさがあって味があると思いたいです。

abc274_c_matome1_tegaki

ここまで分かってしまえば、各ノード（アメーバ）の親がわかるので、自分から親までの世代数をメモしていけばOKです。

木構造を再現する必要もありませんでした。

from collections import defaultdict

N = int(input())
A = list(map(int, input().split()))
# アメーバの番号: 親からの世代数 をメモする辞書
memo = defaultdict(int)

for i, a in enumerate(A):
    n = i + 1
    parent = a
    l = 2 * n
    r = 2 * n + 1
    # 親の世代数+1して辞書にメモ
    memo[l] = memo[parent] + 1
    memo[r] = memo[parent] + 1

for k in range(2 * N + 1):
    n = k + 1
    print(memo[n])