1. 前書き

AtCoderBeginnerContest(ABC)の参加結果と内容の整理、および外部の解説記事を参考にした上で、自分なりに解法を整理していきます。
使用言語はPythonで行きます。本業ではJavaかRubyonRailsユーザーですが、計算速度の問題であったり、トレンドに乗っておくという意味でも（こちらが大きい）、Pythonに慣れていきたいと思います。

2. コンテスト内容

コンテスト名
- AtCoder Beginner Contest 275
開催日時
- 2022/11/12(土) 21:00 - 22:40
実施区分
- バーチャル参加
- 2022/11/13(日)

3. 結果

区分	結果	所要時間	実行時間
A問題	AC	4:02	22ms
B問題	AC	14:39	25ms
C問題	未提出	-	-

4. 解説

4-1. A問題

4-1-1. 問題文

(1,2,…,N) を並び替えた数列 P と整数 X が与えられます。数列 P の i 番目の項の値は P_iです。 P_k=X を満たす k を出力してください。

4-1-2. 入力形式

N X
P1 P2 ... PN

4-1-3. 解説

数列Pを配列に格納し、特定の値を検索して格納されているインデックスを出力する「index()」を利用するだけです。

4-1-4. ソースコード

n,x = map(int,input().split())
p = list(map(int, input().split()))
 
print(p.index(x)+1)

4-1-5. python文法の整理

配列内の特定の値を検索してインデックスを出力 index()

#使用法
[配列オブジェクト].index([検索値])

#使用例
array = ['apple', 'orange', 'peach']
print(array.index('apple')) -> 0

4-2. B問題

4-2-1. 問題文

英大文字および数字からなる 2 文字の文字列が N 個与えられます。i 個目の文字列は S_iです。
以下の 3 つの条件をすべて満たすか判定してください。
・すべての文字列に対して、1 文字目は H , D , C , S のどれかである。
・すべての文字列に対して、2 文字目は A , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , T , J , Q , K のどれかである。
・すべての文字列は相異なる。つまり、i≠j ならば S_i≠S_jである。

4-2-2. 入力形式

N
S1
S2
...
SN

4-2-3. 解説

各Siに対して以下を判定すれば良い。
各Siのうち1回でも合致したら、結果は「No」となり、全Siに合致しなかった場合のみ「Yes」となる。

Si[0]（1文字目）がH,D,C,Sに該当しない
Si[1]（2文字目）がA,2,3,4,5,6,7,8,9,T,J,Q,Kに該当しない
全Siを配列Sに格納し、S.count(Si) > 1となる

4-2-4. ソースコード

n = int(input())
s = []
for i in range(n):
  s.append(input())
 
cond1 = ["H","D","C","S"]
cond2 = ["A","2","3","4","5","6","7","8","9","T","J","Q","K"]
flg = True
for j in s:
  if j[0] not in cond1 or j[1] not in cond2 or s.count(j) > 1:
    flg = False
    break
 
if flg == True:
  print("Yes")
else:
  print("No")

4-2-5. python文法の整理

配列内の特定の要素数を検索 count()

#使用法
[配列オブジェクト].count([検索値])

#使用例
array = [1,4,2,6,2,3,5,1,3,2]
print(array.count(1)) -> 2
print(array.count(2)) -> 3
print(array.count(7)) -> 0

配列内に特定の値が含まれるかどうかの判定 in演算子

#使用法
[検索値] in [配列オブジェクト]

#使用例
array = [1,2,3,4]
print(1 in array) -> True
print(5 in array) -> False

配列オブジェクトの代わりに、集合オブジェクト（set())を使うことができる。
配列の場合は要素数に比例して処理時間が増えるが、集合の場合は要素数に依らず処理時間が変わらないため、基本的には集合オブジェクトを使う方が良い。
※特に競技プログラミングの場合は必須。

4-3. C問題

4-3-1. 問題文

10⁹階建てのビルがあり、N 本のはしごがかかっています。
ビルの 1 階にいる高橋君ははしごを繰り返し使って（0 回でもよい）できるだけ高い階へ上りたいと考えています。
はしごには 1 から N までの番号がついており、はしご i は A_i階と B_i階を結んでいます。はしご i を利用すると A_i階から B_i階へ、または B_i階から A_i階へ双方向に移動することができますが、それ以外の階の間の移動は行うことはできません。
また、高橋君は同じ階での移動は自由に行うことができますが、はしご以外の方法で他の階へ移動することはできません。
高橋君は最高で何階へ上ることができますか？

4-3-2. 入力形式

N
A1 B1
A2 B2
...
AN BN

4-3-3. 解説

バーチャル参加時は全く歯が立ちませんでしたので、解説を読みました。

今回の設問のような状況は、「グラフ」という図で表すことができます。
入力例1である以下の場合、グラフは次のような図になります。

このグラフについて全探索したい場合、「幅優先探索（BFS：Breadth First Search）」というアルゴリズムを使用します。

[BFSの考え方]
準備

訪問予定の点の情報を格納する「キュー」を用意する。
探索を開始する点（今回の場合は「1」）をキューに格納する。
各階がつながっている先の情報を、連想配列形式で保存する。入力値を順に処理すると以下のようになる。

1 4 -> {1:[4],4:[1]}
4 3 -> {1:[4],4:[1,3],3:[4]}
4 10 -> {1:[4],4:[1,3,10],3:[4],10:[4]}
8 3 -> {1:[4],4:[1,3,10],3:[4,8],10:[4],8:[3]}

訪問済かどうかの情報を、連想配列形式で保存する。ただし、0：未訪問、1：訪問済とする。

探索の手順

キューの先頭を取り出し、その点を訪問する。今回の場合は①に訪問する。訪問済み用連想配列は「{1:1}」となる。
訪問した点から接続している点で、かつ未訪問の点をキューに格納する。今回の場合は④をキューに格納する。
現時点での最高階数を上回っていれば、答えを更新する。

上記を繰り返します。

[参考URL]

4-3-4. ソースコード

from collections import defaultdict, deque
 
#はしごの数
n = int(input())
 
#つながっている階数の情報を連想配列で保存
connect = defaultdict(list)
 
for _ in range(n):
  a,b = map(int, input().split())
  connect[a].append(b)
  connect[b].append(a)
 
#答えの階数
#初期位置である1階をセット
ans = 1
 
#キューを定義
que = deque()
 
#訪問済チェックを連想配列で保存
#0:未訪問、1:訪問済
visited = defaultdict(int)
 
#初期位置を1階とするため、queに1をセット
que.append(1)
 
#1階を訪問済とする
visited[1] = 1
 
#キューが空になるまでループ
while 0 < len(que):
  #キューの先頭を取り出し、現在位置にセット
  now = que.popleft()
  
  #現時点での最高階数と現在位置をうち、大きい方を答えにセット
  ans = max(ans,now)
  
  #現在位置とつながっている階を全てでループ
  for to in connect[now]:
    
    #現在位置が未訪問の場合のみ、後続処理を実行
    if visited[to] == 0:
      #現在位置を訪問済みに変更
      visited[to] = 1
      #現在位置をキューへ追加
      que.append(to)
 
print(ans)

4-3-5. python文法の整理

連想配列 collections.defaultdict()
辞書型dictを利用する際は、キーが存在しない場合を考慮して、しっかりハンドリングする必要がある。そんな時に、defaultdictを使うと、キーが存在しない場合でも初期値を設定してくれる。

from collections import defaultdict

dd = defaultdict(int)
print(dd[1]) -> 0

キューを扱う collections.deque()
dequeは先頭/末尾から要素を取り出す操作を高速に行うことができる。配列の場合、先頭要素に対する操作は、要素数が大きくなるほど、比例して時間がかかる。

#使用例
from collections import deque

d = deque()
d.append(1) -> deque([1])
d.appendleft(2) -> deque([2,1])
d.pop() -> deque([2])
d.popleft() -> deque([])