💻

AtCoder Beginner Contest 304に参加したので冒頭3問を振り返ります

2023/06/04に公開

競技プログラミング

AtCoder

tech

こんにちは。

ダイの大冒険という漫画のガチ勢のbun913といいます。

皆さんはAtCoderという競技プログラミングを楽しめるサービスをご存知でしょうか？

https://atcoder.jp/?lang=ja

私は半年位前までコンテストに参加していたのですが、そこから他のことにリソースを使うべく、ぱったりと参加することをやめていました。（以下は茶色コーダーという脱初心者的なことを達成した時の記事となります）

最近いくつか考えることがあり、先日の2023年6月3日（土）に開催された東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 304） - AtCoderからエンジョイ勢として競プロに復帰することにしました！

その辺の経緯などはポエミーになりそうであるため、本記事では特に触れないことにします！

今回はA問題、B問題、C問題を正解することができたので正解に至った思考の整理や類似の問題なんかを軽く紹介いたします。

解いた問題と正解に至るまで

A - First Player

以下みたいにN人（以下図では3人）の人が円卓に座っています

abc304a

年齢が最も小さい人を起点として時計回りで i 番目の位置に座っている人の名前を出力せよ

という問題です。以下の図で言えば、2歳の子から順番に名前を出力すればよいということですね（2歳が大人しく一人で座っているのが偉いんですが）

abc304a2

やることとしては、以下の2点だと考えました。

円卓に座っている人で年齢が最も低い人を見つける
繰り返し
- その人から順に年齢を出力する

例えば以下のように2歳の人が配列の真ん中にいる場合は、単純にfor文で回してはまずいですよね。

# 年齢を格納している配列
A = [33,2,5]
S = ["pop", "gome", "dai"]
# 年齢が一番低い人のインデックスを取得(1になる)
min_index = A.index(min(A))
# 2歳の子からN人(3人)分時計回りに年齢を出力しないといけない
for i in range(min_index, min_index+N):
  # これだと"gome","dai"のあとにインデックスが配列の長さを超えてエラーになる
  print(S[i])

ということで、このような時に剰余（あまり）を使うことでif文などを書かずに、また最初のインデックスに戻ることができて非常に便利です。

for文で1からN人分繰り返し
- index:1 % N(3) = 1
  - S[1] => "gome"
- index:2 % N(3) = 2
  - S[2] => "dai"
- index:3 % N(3) = 0
  - S[0] => "pop"

ということで以下のようなコードを提出することで正解となりました。

N = int(input())
S = []
A = []

for i in range(N):
    sa = input()
    s, a = sa.split()
    S.append(s)
    A.append(int(a))
# Aのいちばん小さい人のindexを取得
min_index = A.index(min(A))
# min_indexからN人分の名前を出力（あまりをとって円卓を回す)
for i in range(min_index, min_index+N):
    print(S[i % N])

B - Subscribers

解説には以下のように記載されています。

解説 - 東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 304）

N を文字列と捉え、4 文字目以降をすべて 0 に置き換える

確かにこのように実装できたと思うのですが、「B問題で愚直に実装しても問題なさそうだし、書かれた通りに実装しよう」と思って最終的に以下のようなコードを出力しました。

N = int(input())
if N <= 10**3 - 1:
    print(N)
    exit()
if N <= 10**4 - 1:
    # 1の位を切り捨てて出力
    print(N // 10 * 10)
    exit()
if N <= 10**5 - 1:
    # 10の位を切り捨てて出力
    print(N // 100 * 100)
    exit()
if N <= 10**6 - 1:
    # 100の位を切り捨てて出力
    print(N // 1000 * 1000)
    exit()
if N <= 10**7 - 1:
    # 1000の位を切り捨てて出力
    print(N // 10000 * 10000)
    exit()
if N <= 10**8 - 1:
    # 10000の位を切り捨てて出力
    print(N // 100000 * 100000)
    exit()
if N <= 10**9 - 1:
    # 100000の位を切り捨てて出力
    print(N // 1000000 * 1000000)
    exit()

わぁ。愚直ですね。

本当に愚直なので特に解説する部分もないのですが、「⚪の位を切り捨てて出力」という処理は以下のような計算方法を利用しています。

# 13について1の位を切りすてて出力する方法
a = 13 // 10 # 1になる
ans = a * 10 # 10となる（求めたい出力）

# 138について10の位を切り捨てて出力する方法
a = 138 // 100 #1になる
ans = a * 100 #100となる(求めたい出力)

C - Virus

例えば以下のようなA,B,Cが2次元座標上に存在するとします
- 画像はDesmos | グラフ計算機から出力させていただきました

abc304c

ウイルスに感染する距離Dを3とすると
- AB間のユークリッド距離が $\sqrt{5}$ であるためAを媒介にBが感染する
- AC間のユークリッド距離が $\sqrt{18}$ であるためAを媒介に感染しない
- BC間のユークリッド距離が $\sqrt{5}$ であるためBを媒介にCが感染する

ということをプログラム上で考えていくことになると思います。

この時以下のように考えました。

「特に座標上で考える必要はなく、大事なのは人と人との距離だよな」
- 現実でも人との距離感は大事ですよね
「ウイルスを感染する人や間接的に感染することになる人との関係や繋がりを示せれば良いよな」
「そういえば今学習しなおしている書籍で関係を考えるにあたってグラフが考えやすいっていう問題を解いたな」
- 078 - Difference Optimization 1
「人を頂点としてユークリッド距離がD以内である人同士で、辺を張る（つなげる）。ってことをすれば間接的に感染する人も全て関係が整理できるな」
あとは頂点となっている人を「Yes」と答えてあげればよさそう
- ※ 頂点となっている人は幅優先探索でマークしてやればよさそう
- BFS (幅優先探索) 超入門！〜キューを鮮やかに使いこなす〜 - Qiita

abc304_c2

このような形で思考から「2次元座標」という概念を取り除いで問題をシンプルにしてみました。

最終的に提出したコードは以下のような形となりました。

from collections import deque

N, D = list(map(int, input().split()))
XY = [list(map(int, input().split())) for _ in range(N)]
# 2次元配列でグラフを表現する
# [
#  [2],  #0番目の人がつながっている頂点（人）を保持
#  [], #1番目の人がつながっている頂点(人)を保持
#  [0] #2番目の人がつながっている頂点（人）を保持
# ]
G = [[] for _ in range(N)]
for i in range(N):
    for j in range(i+1, N):
        x1, y1 = XY[i]
        x2, y2 = XY[j]
        if (x1-x2)**2 + (y1-y2)**2 <= D**2:
            G[i].append(j)
            G[j].append(i)
# 答えをBFSで求める
# 0,1,...,N-1番目の人が感染しているか（頂点になっているか）を保持する配列
ans = [False] * N
# 0番目の人は絶対感染しているからTrueにする
ans[0] = True
# 次に走査する頂点をキューに入れていく（最初は０番目の人）
q = deque([0])
while q:
    v = q.popleft()
    # vが繋がりを持っている頂点(人)を探してまだ走査していない頂点なら次走査するキューに入れる
    for nv in G[v]:
        if ans[nv]:
            continue
        ans[nv] = True
        q.append(nv)
# 答えを出力する
for b in ans:
    if b is True:
        print("Yes")
    else:
        print("No")

さいごに

最後までお読みいただきありがとうございました。

今現在私は「緑コーダーになる」という目標ではなく「ABCのC問題の過去問を全て解く」というような定量的な目標を立ててゆるふわに学習しています。

以前「茶コーダーになるぞ〜」と考えていた際は、コンテストの結果で一喜一憂することが多かったのですが、今は趣味でやっており、「C問題までをほぼ確実に解ける人になりたい」というモチベーションで続けています。

まずは、C問題の過去問の前に問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本をしっかり2周時終わることを目標にしています。(現在の進捗は1週目の65%ほど)

日々の学習の中で役に立ったことなどを紹介できればと思います。

以上bun913でした。

最後まで読んでいただき、ありがとうございました。

GitHubで編集を提案