AtCoder Beginner Contest(ABC) 276 - Pythonでのバーチャル参加結果と内容整理

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

# 2. コンテスト内容
- コンテスト名
    - AtCoder Beginner Contest 276
- 開催日時
    - 2022/11/5(土) 21:00 - 22:40
- 実施区分
    - バーチャル参加
    - 2022/11/7(月)

# 3. 結果
|区分|結果|所要時間|実行時間|
|:--|:--|:--|:--|
|A問題|AC|11:05|25ms|
|B問題|TLE|-|2208ms|
|C問題|未提出|-|-|

# 4. 解説

## 4-1. A問題

### 4-1-1. 問題文
> 英小文字からなる文字列 S が与えられます。
S に a が現れるならば最後に現れるのが何文字目かを出力し、現れないならば −1 を出力してください。

### 4-1-2. 入力形式
~~~
S
~~~

### 4-1-3. 解説
文字列に対してfind関数を使って、特定の部分文字列が出現するindexを求めることを考えました。
ただ、find関数は最小のindexを求めるものなので、入力文字列を反転してからfind関数を適用することにしました。

### 4-1-4. ソースコード
~~~python
s = input()
sr = s[::-1]
l = len(s)
if sr.find('a') == -1:
  print(-1)
else:
  print(l - sr.find('a'))
~~~

### 4-1-5. python文法の整理
**文字列中の出現する特定の文字列のindexを出力 find()**

~~~python
#使用法
[被検索文字列].find([検索文字列])

#使用例
str = 'abcba'
print(str.find('b')) -> 1
~~~

## 4-2. B問題

### 4-2-1. 問題文
> 1,…,N と番号付けられた N 個の都市と、都市間を結ぶ M 本の道路があります。
i(1≤i≤M) 番目の道路は都市A<sub>i</sub>と都市B<sub>i</sub>を結んでいます。
以下の指示に従い、N 行にわたって出力してください。
・都市 i(1≤i≤N) と道路で直接結ばれた都市が d<sub>i</sub>個あるとし、それらを昇順に都市a<sub>i,1</sub>,…,a<sub>i,d<sub>i</sub></sub>とおく。
・i(1≤i≤N) 行目には、d<sub>i</sub>+1 個の整数d<sub>i</sub>,a<sub>i,1</sub>,…,a<sub>i,d<sub>i</sub></sub>を、この順番で空白区切りで出力せよ。

### 4-2-2. 入力形式
~~~
N M
A1 B1
...
AM BM
~~~

### 4-2-3. 解説
**[筆者の思考]**
全体の処理フローを以下のように考えました。
1. 入力値で与えられる道路で結ばれた2都市の情報を、配列[A<sub>n</sub>, B<sub>n</sub>]の形式で整形し、道路の数M本分を2次元配列の形で格納する。　-> [[A<sub>1</sub>, B<sub>2</sub>], [A<sub>2</sub>, B<sub>2</sub>], ..., [A<sub>M</sub>, B<sub>M</sub>]]
1. 都市番号nとして1~Nでループし、1で生成した配列要素を捜査して都市番号nの対となる都市番号を、回答出力用の配列に格納する。
1. 回答出力用の配列要素を、昇順にソートする。

ただし、問題の制約として、N,M ≦ 10<sup>5</sup>であることに注意が必要でした。
上記の2で、N,Mの二重ループが発生しているため、N×M = 10<sup>5</sup>×10<sup>5</sup> = 10<sup>10</sup>となり、このままだと**TLE**となってしまいます。

以下が実際に書いたソースコードです。無駄が多すぎですね。。。
~~~python
import copy
 
n,m = map(int, input().split())
l = []
for i in range(m):
  l.append(list(map(int, input().split())))
  
for k in range(1,n+1):
  tmp = []
  tmp2 = []
  l2 = copy.deepcopy(l)
  for j in l2:
    if (k in j) == True:
      j.remove(k)
      tmp.append(j.pop())
  tmp2 = sorted(tmp)
 
  print(len(tmp2), end=' ')
  for elem in tmp2:
    print(elem, end=' ')
  print()
import copy

n,m = map(int, input().split())
l = []
for i in range(m):
  l.append(list(map(int, input().split())))
  
for k in range(1,n+1):
  tmp = []
  tmp2 = []
  l2 = copy.deepcopy(l)
  for j in l2:
    if (k in j) == True:
      j.remove(k)
      tmp.append(j.pop())
  tmp2 = sorted(tmp)

  print(len(tmp2), end=' ')
  for elem in tmp2:
    print(elem, end=' ')
  print()
~~~

**[他解説記事における解法]**
入力におけるM本の道路情報を取得する際に、事前に用意していた2次元配列に情報を格納するようにすれば良いだけでした。

ちなみに、このように辺で結ばれている頂点のリストを管理する手法は **「隣接リスト」** と呼ばれているようで、競技プログラミングでは頻出問題のようです。

**[参考URL]**

https://atcoder.jp/contests/abc276/editorial/5159

https://qiita.com/MoroeTachibana-oh/items/7083f8bd2634d70846da

### 4-2-4. ソースコード
~~~python
n,m = map(int, input().split())
l = [[] for _ in range(n)]
for i in range(m):
  a,b = map(int, input().split())
  l[a-1].append(b)
  l[b-1].append(a)
  
for elem in l:
  print(len(elem), *sorted(elem))
~~~

### 4-2-5. python文法の整理
**配列に要素追加 append()**
配列の末尾に要素を追加します。

~~~python
#使用法
[配列オブジェクト].append([追加要素])

#使用例
array = [1,2,3]
array.append(4)
print(array) -> [1,2,3,4]
~~~

**配列のソート sort(), sorted()**
- sort()：リスト型のメソッドで、配列オブジェクト自体をソートする破壊的処理。
- sorted()：組み込み関数で、引数に与えられたオブジェクトをソートし、新しいオブジェクトを生成する非破壊的処理。組み込み関数なので、配列以外にも文字列やタプルなど他の型にも使用できる。

~~~python
#使用法
[配列オブジェクト].sort()
sorted([配列オブジェクト])

#使用例
array = [4,2,3,1]
array.sort()
print(array) -> [1,2,3,4]

array = [4,2,3,1]
new_array = sorted(array)
print(array) -> [4,2,3,1]
print(new_array) -> [1,2,3,4]
~~~

**配列要素を全て出力する 「*」演算子**
配列要素の前に「*」を付けることで、各要素を1行に並べて、各要素間にスペースを挟むことができます。

~~~python
#使用法
*[配列オブジェクト]

#使用例
array = [1,2,3,4]
print(*array) -> 1 2 3 4
~~~