(ABC304)A-C問題のpythonでの解法

こんにちは、こんぶちゃ(茶コーダー)です！

初心者視点から競プロAtCoderのABC304のA問題〜C問題の自身の解答と解答説明をしていきます。

こんな人にオススメしたい

競技プログラミング初心者で、問題の解き方がわからない方
AtCoderの公式解説は読んだが、内容が理解できなかった方
Pythonでの解法を知りたい方

まだまだ学習の身ですので、最適コードではない部分も多々あるかと思いますが、その部分は同じ学習者として温かい気持ちで応援＆ご助言頂けば嬉しいです。

では早速行ってみましょう！

今回使用している機能・アルゴリズム

roll関数(行列シフト(スクロール))　　　　　　　　　・・・　問題A

今回の参加コンテスト(ABC304)
感想

今回の参加コンテスト(ABC304)

AtCoder Beginner Contest 304

A問題：First Player

A – First Player

問題(要約)

順番に番号が付けられたN人が、順番に円卓に座っている。年齢が最も若い人から時計回りの順番に名前を出力する

解答

# 番号1
import numpy as np

# 番号2
n=int(input())
S=[]
minA=float("inf")
num=-1

# 番号3
for i in range(n):
    s,a = input().split()
    S.append(s)
    a=int(a)
    # 番号3-1
    if minA > a:
        minA = a
        num=i

for s in np.roll(S,-num):
    print(s)

考え方 (下の番号は、コード内のコメント番号と連携している)

最も若い人が何番目化を確認し、numpyのroll関数を順番を入れ替えて出力する

roll関数を用いるためnumpyをimportする
入力nを受け取り、変数設定を行う
- 名前を配列で保持するため、空配列Sを定義する
- 年齢の最小値を保持するためにminAを設定する。初期値は無限大(float(“inf”))で定義する
- 最も年齢が若い人の配列を記憶するためのnum変数を定義する。初期値は念の為配列外に設定している
名前と年齢を受け取り、名前は配列に登録していく
- 最小年齢を探すために、minAと比較して小さければ、minAと配列番号のnumを更新する
numpyのroll関数を用いて、num分を配列を回転させ(マイナスが必要)、名前を順番に出力する
＊Numpyのroll関数の振る舞いは下記参照

補足：roll関数

roll関数は第1引数に配列、第2引数にシフト量を記載する。シフトの仕方は下記の表を参照

第1引数(初期配列)	第2引数	シフト後の配列
[1, 2, 3, 4, 5]	0	[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]	1	[5, 1, 2, 3, 4]
[1, 2, 3, 4, 5]	2	[4, 5, 1, 2, 3]
[1, 2, 3, 4, 5]	3	[3, 4, 5, 1, 2]
[1, 2, 3, 4, 5]	-1	[2, 3, 4, 5, 1]
[1, 2, 3, 4, 5]	-2	[3, 4, 5, 1, 2]
[1, 2, 3, 4, 5]	-3	[4, 5, 1, 2, 3]

＊chatGPTを用いて表を作成

B問題：Subscribers

B – Subscribers

問題(要約)

正数Nが与えられており、先頭3桁以降を切り捨てた数を表示する
＊この問題文の要約がポイントだと思います

解答

# 番号1
N=input()

# 番号2
for i in range(len(N)):
    if i < 3:
        print(N[i],end="")
    else:
        print(0,end="")
# 番号3
print()

考え方(下の番号は、コード内のコメント番号と連携している)

問題文を上記のように要約することにより、文字列で正数Nを取扱い、先頭3文字とそれ以外で出力変える

Nを取り込む。ただし、文字列型のままにする
文字列の長さ分 for文を繰り返す
- i < 3、つまり先頭3文字はそのまま出力する
- 残り部分は、0を出力する
- print文にend=””を入力することにより、改行せずに出力可能
atCoderの出力は、最後に改行が必要なため、改行だけを行っている
itertoolsのcombinationsを用いて想定される組み合わせパターンを全て列挙する。また、配列でなく、集合(set)にすることにより、後のif文の検索スピードを向上させている

C問題：Virus

C – Virus

問題(要約)

二次元平面にN人の人がおり、人_iの座標は(x_i,y_i)で表される。人1が感染した。距離D以内にいる人が感染する。時間が十分経った後に、それぞれの人が感染しているかどうかを判断する。

解答

# 番号1
import math

# 番号2
n,d=map(int,input().split())
xy=[]
for _ in range(n):
    x,y=map(int,input().split())
    xy.append((x,y))

# 番号3
infected=[0]
non_infected=[x for x in range(1,n)]

# 番号4
for i in infected:
    xi,yi = xy[i]
    # 番号4-1
    for p in non_infected:
        x,y=xy[p]
        # 番号4-2
        dist=math.sqrt((xi-x)**2 + (yi-y)**2)
        if dist <= d:
            infected.append(p)
            non_infected.remove(p)

# 番号5
infected=set(infected)

# 番号6
for i in range(n):
    if i in infected:
        print("Yes")
    else:
        print("No")

考え方(下の番号は、コード内のコメント番号と連携している)

感染した人達の配列と感染していない人達の配列に分け、それぞれの感染した人に対して感染していない人を確認していく。for文に用いている変数を動的に変更していく

ユークリッド距離で平方根を用いるため、mathモジュールをインポートしておく
入力を受け取る
- 人の座標は、配列xyにタプル型で追加していく
感染者リストと非感染者リストを準備する
- 感染者リスト(infected)には人1、配列番号0を登録する
- 非感染者リスト(non_infected)には、人1以外の人を登録する
感染者リストから番号を一つづつ取り出していく。感染者が見つかった場合、infectedに追加されるため、for文の回数は動的に変化する
1. 非感染者リストの人を確認していく。この非感染者リストに関しても、感染した場合はリストから削除され、感染者リストに追加されるため、for文の回数も動的に変化していく
2. 取り出した感染者リストの番号と選んだ非感染者リストのユークリッド距離を求め、距離がD以下かどうかを確認する
  - 距離D以下の場合は、感染者リストに選んだ非感染者を追加する
  - 非感染者リストから、選んだ非感染者を削除する
検索の高速化のため、感染者リストを集合に変換する
感染者リストに番号がある場合は”Yes”を出力し、それ以外の場合は、”No”を出力する