AtCoder Beginner Contest(ABC) 283 - Pythonでリアルタイム参加結果と内容整理

1. 前書き

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

2. コンテスト内容

• コンテスト名
  • AtCoder Beginner Contest 283
• 開催日時
  • 2022/12/24(土) 21:00 - 22:40
• 実施区分
  • リアルタイム参加

3. 結果

区分	結果	所要時間	実行時間
A問題	AC	2:45	24ms
B問題	AC	8:10	463ms
C問題	AC	34:58(1)	202ms
D問題	AC	95:07(3)	159ms

4. 解説

4-1. A - Power

4-1-1. 問題文

整数 A,B が与えられます。 A^B の値を出力してください。

制約

• 1≤A,B≤9
• 入力はすべて整数

4-1-2. 入力形式

A B

4-1-3. 解説

pythonでは、累乗を計算する演算子「**」が用意されているので、それを利用するだけです。

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

a,b = map(int,input().split())

print(a ** b)

4-2. B - First Query Problem

4-2-1. 問題文

整数 N と長さ N の数列 A=(A₁,A₂,…,A_N) が与えられます。

クエリが Q 個与えられるので、与えられた順番に処理してください。 クエリは次の 2 種類のいずれかです。

• 1 k x : A_kの値を x に変更する。
• 2 k : A_kの値を出力する。

制約

• 1 ≤ N ≤ 10⁵
• 1 ≤ Q ≤ 10⁵
• 1 ≤ A_i ≤ 10⁹ (1 ≤ i ≤ N)
• どのクエリについても、1 ≤ k ≤ N
• 1番目の形式のクエリについて、0 ≤ x ≤ 10⁹
• 2番目の形式のクエリが1つ以上存在する
• 入力はすべて整数

4-2-2. 入力形式

N
A₁ A₂ ... A_N
Q
query₁
query₂
...
query_Q

ただし、query_iはi個目のクエリを表しており、次の形式のいずれかで与えられる。

1 k x

2 k

4-2-3. 解説

ABC278のD問題「All Assign Point Add」のように、いくつかの種類のクエリが与えられて、それを処理していく問題です。
ABC278-Dでは、数列の全要素について演算するクエリがあったため、愚直に実装するとTLEとなってしまいました。

ただし今回は、2種類どちらのクエリも、特定の1要素のみにアクセスするため、クエリの件数のみを考慮すれば良いです。
クエリの個数Qについては、1 ≤ Q ≤ 10⁵ であるため、そのまま実装しても十分に時間内に処理が完了できると推測されます。

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

n = int(input())
a = list(map(int, input().split()))
q = int(input())

for i in range(q):
  query = list(map(int,input().split()))
  if query[0] == 1:
  	a[query[1]-1] = query[2]
  else:
    print(a[query[1]-1])

公式解説の中で、クエリの内容を以下のようにスマートに変数に展開していました。
こちらの方が視認性が高いので、今後はこちらを使っていこうと思います。

query = [1, k, x]
type, k, x = query

4-3. C - Cash Register

4-3-1. 問題文

高橋君は、レジ打ちの仕事をしています。

レジの機械には 00, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 の 11 個のボタンがあります。 レジの機械には、はじめ 0 が表示されています。 ボタン 00 を押すと、表示されている数が 100 倍されます。 それ以外のボタンを押すと、表示されている数が 10 倍されたあとに、押されたボタンに書かれている数が加算されます。

高橋君は、レジに整数 S を表示させたいです。 レジに S が表示されている状態にするためには、少なくとも何回ボタンを押す必要があるか求めてください。

制約

• 1≤S≤10¹⁰⁰⁰⁰⁰
• S は整数

4-3-2. 入力形式

S

4-3-3. 解説

電卓に数字を打ち込んでいく場面を思い浮かべていけば、イメージが掴めると思います。
基本的には、桁数分の回数だけボタンを押す必要がありますが、整数Sの中に「00」が出現した場合、1回のボタンで2桁分の入力が可能になるため、「00」の出現回数分だけ、ボタンを押す回数を差し引けば良いということがわかります。

ただし、「000」のように3桁以上連続して0が出現した場合に、前方2つ（「000」）と後方2つ（「000」）をダブルカウントしないように注意。

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

s = int(input())

s_str = str(s)
cnt = 0
flg = False
for char in s_str:
  if char == '0' and flg == True:
    cnt += 1
    flg = False
  elif char == '0' and flg == False:
    flg = True
  else:
    flg = False

print(len(s_str)-cnt)

上記の方法だと、ソースコードの量もそれなりのボリュームになってしまっていますが、スマートな解法を解説している方がいたので、紹介します。
「00」を別の1文字に置き換えると、完成した文字列の長さがそのまま答えになるというものでした。
※解説では「x」に置き換え

S=input()
SS=S.replace("00", "x")
print(len(SS))

4-4. D - Scope

4-4-1. 問題文

英小文字、「(」、「)」 からなる文字列のうち、以下の手順によって空文字列になるものを良い文字列と呼びます:

まず、英小文字をすべて削除する。
次に、連続する () が存在する限り、それを削除する。
例えば、((a)ba) は英小文字をすべて削除すると (()) となり、2 文字目と 3 文字目に連続する () を削除すると () となり、最終的に空文字列にすることができるので良い文字列です。

良い文字列 S が与えられます。 S の i 文字目を S_iで表します。

各英小文字 a , b , … , z に対して、その文字が書かれたボールが 1 つあります。 また、空の箱があります。

高橋君は i=1,2, … ,∣S∣ に対してこの順に気を失わない限り操作を行います。

• S_iが英小文字ならば、その英小文字が書かれたボールを箱に入れる。ただし、そのボールがすでに箱に入っている場合、高橋君は気を失う。
• S_iが 「(」 ならば、何もしない。
• S_iが 「)」 ならば、i 未満の整数 j であって、S の j 番目から i 番目までの文字からなる文字列が良い文字列となる最大の整数 j を取る。（このような整数 j は必ず存在することが証明できる。）j 番目から i 番目までの操作で箱に入れたボールをすべて、箱から取り出す。

高橋君が気を失わずに一連の操作を完了させられるか判定してください。

制約

• 1≤∣S∣≤3×10⁵
• S は良い文字列

4-4-2. 入力形式

S

4-4-3. 解説

問題文だけだと、S_iに対する処理の詳細がわかりにくいので、入出力例1を追ってみましょう。

入力例1

((a)ba)

1. 「(」　-> 何もしない
2. 「((」　-> 何もしない
3. 「((a」　-> 箱の中は空。「a」を箱の中に入れる
4. 「((a)」
   -> S₁〜S_iの文字列を対象に、右から見て最小桁数の良い文字列を抽出し、それに含まれる英小文字を箱から取り出す
   -> 良い文字列は「(a)」になるので、「a」を箱から取り出す
5. 「((a)b」　-> 箱の中は空。「b」を箱の中に入れる
6. 「((a)ba」　-> 箱の中は「b」。「a」を箱の中に入れる
7. 「((a)ba)」　-> 良い文字列は「((a)ba)」になるので、「a」と「b」を箱から取り出す

上記より、管理する必要がある情報を整理します。

1. 箱の中の英小文字
   -> 英小文字を引いた時、箱の中に同じ英小文字があるかどうかを判定する必要があるため、箱の中に入っている英小文字を格納します。
   検索する際の計算量を考慮して、集合set()で管理します。
2. ()の階層構造
   -> 今回の例で言うと、3文字目の「a」と5,6文字目の「b」、「a」では、何層の"()"に囲まれているかという観点で扱いが異なっています。
   3文字目の「a」は、良い文字列の最小単位が「(a)」となり、2層目の構造に含まれています。
   一方で、5,6文字目の「b」、「a」は、良い文字列の最小単位が「((a)ba)」となり、2層目を含んだ1層目の全体となります。

各階層を集合set()で定義して、リストに追加していくことにします。

• "("が出てきた時点で、新たな階層が形成されるため、新たな階層を集合set()で定義してリストに追加。
• 英小文字が出たら、現在の集合に要素を追加。
• ")"が出てきたら、現在の集合を削除。

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

s = input()

all = set()
data = []
data.append(set())
flg = True

for char in s:
  if char == '(':
    data.append(set())
  elif char == ')':
    tmp = all - data[len(data)-1]
    all = tmp
    data.pop()
  else:
    if char in all:
      print('No')
      flg = False
      break
    data[len(data)-1].add(char)
    all.add(char)

if flg == True:
  print('Yes')

5. さらに次の問題

E問題は動的計画法(DP)を使うとのこと。
勉強してから追記します！