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 (1NG,5:44+5min)	24ms
B問題	WA	-	-
C問題	TLE	-	2221ms
D問題	TLE	-	2206ms

4. 解説

4-1. A問題

4-1-1. 問題文

長さ N の数列 A=(A₁,A₂,…,A_N) が与えられます。
あなたは次の操作をちょうど K 回行います。
・A の先頭の要素を取り除き、A の末尾に 0 を挿入する。
操作を行った後の A の要素をすべて出力してください。

4-1-2. 入力形式

N K
A1 A2 ... AN

4-1-3. 解説

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

[URL]

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

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=" ")

アンパックで記述した場合

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

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_i,A_i,B_iで表され、それぞれ次のような操作を表します。
・T_i=1 のとき：ユーザー A_iがユーザー B_iをフォローしたことを表す。この操作の時点でユーザーA_iがユーザーB_iをフォローしている場合、ユーザーのフォロー状況に変化はない。
・T_i=2 のとき：ユーザー A_iがユーザー B_iのフォローを解除したことを表す。この操作の時点でユーザーA_iがユーザー B_iをフォローしていない場合、ユーザーのフォロー状況に変化はない。
・T_i=3 のとき：ユーザー A_iとユーザー B_iが互いにフォローしているかをチェックすることを表す。この操作の時点でユーザー A_iがユーザー B_iをフォローしており、かつユーザー B_iがユーザー A_iをフォローしているとき、このチェックに対して Yes と答え、そうでないときこのチェックに対して No と答える必要がある。
サービス開始時には、どのユーザーも他のユーザーをフォローしていません。
すべての T_i=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⁹であり、操作の回数Q ≦ 10⁵なので、N×Qの計算が発生するとTLEとなります。
実際に提出したコードは以下です。

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を使用すると良いです。

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

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₁,A₂,…,A_N) が与えられます。
Q 個のクエリが与えられるので、順番にすべて処理してください。 q 番目 (1≤q≤Q) のクエリは以下の 3 つのいずれかの形式で、それぞれ次のようなクエリを表します。
・1 x_q：A のすべての要素に x_qを代入する。
・2 i_qx_q：A_{i_q}に x_qを加える。
・3 i_q：A_{i_q}の値を出力する。

4-3-2. 入力形式

N
A1 A2 ... AN
Q
query1
query2
...
queryQ

4-3-3. 解説

数列の長さがN ≦ 10⁵、クエリの個数Q ≦ 10⁵の制約があります。
なので、N×Qの処理を行うと≒10¹⁰となり、TLEとなります。

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

[筆者の考え]
コンテスト参加時は残り時間も少なかったので、愚直に実装しました。

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

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)

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

1. 前書き

2. コンテスト内容

3. 結果

4. 解説

4-1. A問題

4-1-1. 問題文

4-1-2. 入力形式

4-1-3. 解説

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

4-2. B問題

4-2-1. 問題文

4-2-2. 入力形式

4-2-3. 解説

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

4-3. C問題

4-3-1. 問題文

4-3-2. 入力形式

4-3-3. 解説

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

4-4. D問題

4-4-1. 問題文

4-3-2. 入力形式

4-3-3. 解説

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