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. ソースコード

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()

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

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

4-2. B問題

4-2-1. 問題文

1,…,N と番号付けられた N 個の都市と、都市間を結ぶ M 本の道路があります。
i(1≤i≤M) 番目の道路は都市A_iと都市B_iを結んでいます。
以下の指示に従い、N 行にわたって出力してください。
・都市 i(1≤i≤N) と道路で直接結ばれた都市が d_i個あるとし、それらを昇順に都市a_i,1,…,a_i,diとおく。
・i(1≤i≤N) 行目には、d_i+1 個の整数d_i,a_i,1,…,a_i,diを、この順番で空白区切りで出力せよ。

4-2-2. 入力形式

N M
A1 B1
...
AM BM

4-2-3. 解説

[筆者の思考]
全体の処理フローを以下のように考えました。

1. 入力値で与えられる道路で結ばれた2都市の情報を、配列[A_n, B_n]の形式で整形し、道路の数M本分を2次元配列の形で格納する。　-> [[A₁, B₂], [A₂, B₂], ..., [A_M, B_M]]
2. 都市番号nとして1~Nでループし、1で生成した配列要素を捜査して都市番号nの対となる都市番号を、回答出力用の配列に格納する。
3. 回答出力用の配列要素を、昇順にソートする。

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

以下が実際に書いたソースコードです。無駄が多すぎですね。。。

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]

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

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()
配列の末尾に要素を追加します。

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

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

配列のソート sort(), sorted()

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

#使用法
[配列オブジェクト].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行に並べて、各要素間にスペースを挟むことができます。

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

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