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

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

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

# 3. 結果
|区分|結果|所要時間|実行時間|
|:--|:--|:--|:--|
|A問題|AC|10:44<br>(1NG,5:44+5min)|24ms|
|B問題|WA|-|-|
|C問題|TLE|-|2221ms|
|D問題|TLE|-|2206ms|

# 4. 解説

## 4-1. A問題

### 4-1-1. 問題文
> 長さ N の数列 A=(A<sub>1</sub>,A<sub>2</sub>,…,A<sub>N</sub>) が与えられます。
あなたは次の操作をちょうど K 回行います。
・A の先頭の要素を取り除き、A の末尾に 0 を挿入する。
操作を行った後の A の要素をすべて出力してください。

### 4-1-2. 入力形式
~~~
N K
A1 A2 ... AN
~~~

### 4-1-3. 解説
数列をリストに格納してから、愚直にK回操作を繰り返すよう実装します。
実際に提出したソースコードは以下ですが、最後の出力の箇所を、リストに対して*で展開することで、より単純に記述できます（リストのアンパックというみたいです）。

**[URL]**

https://note.nkmk.me/python-argument-expand/

https://qiita.com/tk226/items/73240c114020c22a850e#4-2-5-python%E6%96%87%E6%B3%95%E3%81%AE%E6%95%B4%E7%90%86

### 4-1-4. ソースコード
~~~python
n,k = map(int,input().split())
a = list(map(int,input().split()))
 
for i in range(k):
  a.pop(0)
  a.append(0)
 
for elem in a:
  print(elem, end=" ")
~~~

アンパックで記述した場合
~~~python
n,k = map(int,input().split())
a = list(map(int,input().split()))
 
for i in range(k):
  a.pop(0)
  a.append(0)
 
print(*a)
~~~


## 4-2. B問題

### 4-2-1. 問題文
> 高橋君は置き時計を買いました。
> この時計は、現在の時刻が 24 時制で AB 時 CD 分であるときに図 1 のように時刻を表します。
> 例えば図 2 では、時計は 7 時 58 分を示しています。
>> 時刻の表示方法をより形式的に説明すると次のようになります。
>> 現在の時刻が 24 時制で h 時 m 分であるとします。ここで 24 時制とは、時間を 0 以上 23 以下の整数で、分を 0 以上 59 以下の整数で表す時刻の表現方法を言います。
>> h の 10 の位を A, 1 の位を B, m の 10 の位を C, 1 の位を D とします。(ただし h,m が 1 桁である場合は先行ゼロを追加して考えます。)
>> このとき時計は左上に A を、左下に B を、右上に C を、右下に D を表示します。

> 高橋君は、次の条件を満たす時刻を 見間違えやすい時刻 と呼ぶことにしました。
時計の表示の右上と左下を入れ替えても、それに対応する 24 時制の時刻が存在する。
例えば 図 3 は 20 時 13 分を示していますが、時計の表示の右上と左下を入れ替えると 21 時 3 分を意味する表示になります。よって 20 時 13 分は見間違えやすい時刻です。
今、時計は H 時 M 分を示しています。
(現時点も含めて)以降はじめて訪れる見間違えやすい時刻を 24 時制で答えてください。

### 4-2-2. 入力形式
~~~
H M
~~~

### 4-2-3. 解説

**[筆者の考え]**
問題文を熟読して、キレイな法則性を導き出そうとしたことが良くなかったです。
結果として**WA**になったので。。。

時計に関する問題で、H≦24、M≦59の制約しかないので、計算量の検討は不要です。
そのような場合は、内容を愚直にコーディングするのが一番です。

### 4-2-4. ソースコード
~~~python
h,m = map(int,input().split())
 
h1 = 0
h2 = 0
m1 = 0
m2 = 0
 
if h < 10:
  h2 = h
else:
  h1 = h // 10
  h2 = h % 10

if m < 10:
  m2 = m
else:
  m1 = m // 10
  m2 = m % 10

new_h = h1 * 10 + m1
new_m = h2 * 10 + m2
 
if h < 24 and m < 60 and new_h < 24 and new_m < 60:
  print(h, m)
else:
  while h > 23 or m > 59 or new_h > 23 or new_m > 59:
    if m == 59:
      m = 0
      if h == 23:
        h = 0
      else:
        h += 1
    else:
      m += 1
    
    if h < 10: 
      h2 = h
      h1 = 0
    else:
      h1 = h // 10
      h2 = h % 10
 
    if m < 10:
      m2 = m
      m1 = 0
    else:
      m1 = m // 10
      m2 = m % 10
    
    new_h = h1 * 10 + m1
    new_m = h2 * 10 + m2
    
  print(h, m)
~~~

## 4-3. C問題

### 4-3-1. 問題文
> 高橋君が運営する SNS「Twidai」にはユーザー 1 からユーザー N までの N 人のユーザーがいます。 Twidai では、ユーザーは別のユーザーをフォローすることや、フォローを解除することができます。
Twidai がサービスを開始してから、Q 回の操作が行われました。 i 回目 (1≤i≤Q) の操作は 3 つの整数T<sub>i</sub>,A<sub>i</sub>,B<sub>i</sub>で表され、それぞれ次のような操作を表します。
・T<sub>i</sub>=1 のとき：ユーザー A<sub>i</sub>がユーザー B<sub>i</sub>をフォローしたことを表す。この操作の時点でユーザーA<sub>i</sub>がユーザーB<sub>i</sub>をフォローしている場合、ユーザーのフォロー状況に変化はない。
・T<sub>i</sub>=2 のとき：ユーザー A<sub>i</sub>がユーザー B<sub>i</sub>のフォローを解除したことを表す。この操作の時点でユーザーA<sub>i</sub>がユーザー B<sub>i</sub>をフォローしていない場合、ユーザーのフォロー状況に変化はない。
・T<sub>i</sub>=3 のとき：ユーザー A<sub>i</sub>とユーザー B<sub>i</sub>が互いにフォローしているかをチェックすることを表す。この操作の時点でユーザー A<sub>i</sub>がユーザー B<sub>i</sub>をフォローしており、かつユーザー B<sub>i</sub>がユーザー A<sub>i</sub>をフォローしているとき、このチェックに対して Yes と答え、そうでないときこのチェックに対して No と答える必要がある。
サービス開始時には、どのユーザーも他のユーザーをフォローしていません。
すべての T<sub>i</sub>=3 であるような操作に対して、i が小さいほうから順番に正しい答えを出力してください。

### 4-3-2. 入力形式
~~~
N Q
T1 A1 B1
T2 A2 B2
...
TQ AQ BQ
~~~

### 4-3-3. 解説
フォロー状態の情報をどのように保持するかで、時間内に計算できるかが決まる問題でした。

**[筆者の考え]**
ユーザAがフォローしているユーザを状態を集合で管理、すなわちset()で管理しようと考えました。
なので、set()をユーザ数分用意して、listに格納する方法を取りました。
~~~
#ユーザ1がユーザ2とユーザ3をフォローしている場合
follows = [{2,3},{},{},...]
~~~

ただ、問題の制約を見ると、ユーザ数N ≦ 10<sup>9</sup>であり、操作の回数Q ≦ 10<sup>5</sup>なので、N×Qの計算が発生するとTLEとなります。
実際に提出したコードは以下です。

~~~python
n,q = map(int,input().split())
data = [set() for _ in range(n)]

for i in range(q):
  t,a,b = map(int,input().split())
  if t == 1:
    data[a-1].add(b)
  elif t == 2:
    data[a-1].discard(b)
  else:
    if data[a-1].issuperset({b}) and data[b-1].issuperset({a}):
      print("Yes")
    else:
      print("No")
~~~

**[解説を踏まえて]**
フォロー状態を集合set()で扱うまではOKで、その複数のset()を辞書型で管理すると解決します。
以下でも使用した、defaultdictを使用すると良いです。

https://qiita.com/tk226/items/4291eaf9549d4d03b9cc#4-3-5-python%E6%96%87%E6%B3%95%E3%81%AE%E6%95%B4%E7%90%86

### 4-3-4. ソースコード
~~~python
from collections import defaultdict

n,q = map(int,input().split())
data = defaultdict(set)

for i in range(q):
  t,a,b = map(int,input().split())
  if t == 1:
    data[a].add(b)
  elif t == 2:
    data[a].discard(b)
  else:
    if data[a].issuperset({b}) and data[b].issuperset({a}):
      print("Yes")
    else:
      print("No")
~~~

## 4-4. D問題

### 4-4-1. 問題文
> 長さ N の数列 A=(A<sub>1</sub>,A<sub>2</sub>,…,A<sub>N</sub>) が与えられます。
Q 個のクエリが与えられるので、順番にすべて処理してください。 q 番目 (1≤q≤Q) のクエリは以下の 3 つのいずれかの形式で、それぞれ次のようなクエリを表します。
・1 x<sub>q</sub>：A のすべての要素に x<sub>q</sub>を代入する。
・2 i<sub>q</sub>x<sub>q</sub>：A<sub>i<sub>q</sub></sub>に x<sub>q</sub>を加える。
・3 i<sub>q</sub>：A<sub>i<sub>q</sub></sub>の値を出力する。

### 4-3-2. 入力形式
~~~
N
A1 A2 ... AN
Q
query1
query2
...
queryQ
~~~

### 4-3-3. 解説
数列の長さがN ≦ 10<sup>5</sup>、クエリの個数Q ≦ 10<sup>5</sup>の制約があります。
なので、N×Qの処理を行うと≒10<sup>10</sup>となり、TLEとなります。

今回の場合、クエリの種別1が、すべての要素に対して処理を行うため、この部分を工夫する必要があります。

**[筆者の考え]**
コンテスト参加時は残り時間も少なかったので、愚直に実装しました。
~~~python
n = int(input())
a = list(map(int,input().split()))
q = int(input())
 
for _ in range(q):
  Q = list(map(int,input().split()))
  if Q[0] == 1:
    a = [Q[1]] * n
  elif Q[0] == 2:
    a[Q[1]-1] += Q[2]
  else:
    print(a[Q[1]-1])
~~~

**[解説を踏まえて]**
クエリ1が発生した場合に、代入する値を保持しておき、クエリ3の出力時に条件分岐して処理することで間に合います。
条件としては、以下のようになります。

- クエリ1が出たら、変数xに代入値を保持
- クエリ2が出た場合、以下の処理をして、最後にインデックスを計算済み集合に追加
  - 変数xに値がある場合、かつ、インデックスが計算済集合に無い場合
    - 対象要素に(x+クエリの加算値)を代入
  - 上記以外（変数xに値が無い、または、インデックスが計算済集合にある場合）
    - 対象要素に加算値を加算
- クエリ3が出た場合、
  - 変数xに値がある場合、かつ、インデックスが計算済集合に無い場合
    - xを出力
  - 上記以外（変数xに値が無い、または、インデックスが計算済集合にある場合）
    - 対象要素を出力

### 4-3-4. ソースコード
~~~python
n = int(input())
a = list(map(int,input().split()))
q = int(input())

x1 = -1
values = set()
for _ in range(q):
  Q = list(map(int,input().split()))
  if Q[0] == 1:
    x1 = Q[1]
    values = set()
  elif Q[0] == 2:
    i = Q[1] - 1
    if i in values or x1 < 0:
      a[i] += Q[2]
    else:
      a[i] = x1 + Q[2]
    values.add(i)
  else:
    i = Q[1] - 1
    if i in values or x1 < 0:
      print(a[i])
    else:
      print(x1)
~~~