ABC 283のA,B,C,D 問題を解くために考えたこと、ACできるPython3(PyPy3)コードを紹介します。
この記事は @u2dayo さんの記事を参考にしています。見たことのない方はそちらもご覧ください。とても勉強になります。
また、問題の難易度を表す指標を Atcoder Problems から引用しています。このサイトは勉強した問題を管理するのにとてもオススメです。
質問やご指摘はこちらまで
Twitter : Waaa1471
作者プロフィール
Atcoder ：緑 882
20221225 現在
目次
はじめに
A.Power
B.First Query Problem
C.Cash Register
D.Scope
はじめに
特にC問題以降になると、競技プログラミングに典型的な前提知識、少し難しい数学的考察が必要になり始めます。
しかし、公式解説ではこの部分の解説があっさりしすぎていて競技プログラミング(Atcoder)を始めたばかりの人にはわかりにくい、難しいと感じるのではないでしょうか。
またC++がわからないと、コードの書き方を勉強することが難しいです。一応、参加者全員のコードを見ること自体は可能ですが、提出コードは必ずしも教育的ではありません(ここで紹介する記事も本番で提出したものとは全く異なります)。そんなものから初学者が解説もなしになにか得ることはとても難しいと思います。実際適当に何人かのコードをみたものの、意味がわからずに終わった経験があるのではないでしょうか。
この記事がそんな方々の勉強の助けになればよいなと思っています。
A.Power
難易度： 灰色 8
考察
言われた通り、$ A^{B}$ を出力するだけです。
コード
pypy3
A,B=[int(ab) for ab in input().split()]
print(A**B)
補足
なし
B.First Query Problem
難易度： 灰色 35
考察
数列 A をリストで管理すると、要素の変更、出力ともに計算量 $O(1)$ で実行できるので、クエリを順番に見て、各操作に対応する処理を行えばよいです。
なお、数列の番号 kは 1始まりなのに対して、python におけるリストの index 番号は 0始まりです。これを調整する必要があります。
コード
pypy3
N=int(input())
A=[int(a) for a in input().split()]
Q=int(input())
for _ in range(Q):
query=[int(q) for q in input().split()]
if query[0]==1:
A[query[1]-1]=query[2]
else:
print(A[query[1]-1])
補足
-
計算量
その処理を実行するための 目安の計算回数 を表します。
問題が定める制限時間に間に合うような処理かどうか判断するために必要な概念です。
特に C 問題以降を解くためには必須なので、わからなければ こちら A 問題 補足をご覧ください。 -
リストの各操作における計算量
Pythonistaなら知っておきたい計算量のはなし
C.Cash Register
難易度 ： 灰色 88
考察
00 を含む数と含まない数を例に状況を整理してみます
1225 という数字を最小回数で作るには、1,2,2,5 と順にボタンを押すのが最適です。つまり、各桁の数字を順に押せばよいので、桁数 回必要ということになります。
しかし、2000 という数字を作るために 4回ボタンを押す必要はありません。0,0 と2回押すことは、00 を1回押すことで代わりがきくためです。
したがって、連続する 00 を x と置き換えた文字列の 桁数が最小回数に一致すると分かります。
replace("00","x") で置き換えることもできるし、頑張って、連続する 00 を検出してもいいです。
コード
pypy3
S=input()
SS=S.replace("00", "x")
print(len(SS))
00 を検出
S=input()
# 直前が 0 であることを示すflag
flag=False
ans=len(S)
for s in S:
if s=="0":
if flag:
ans-=1
# 二文字続いたらもとに戻す
flag=False
else:
flag=True
else:
flag=False
print(ans)
補足
- replace(A,B)
Pythonで文字列を置換（replace, translate, re.sub, re.subn）
D.Scope
難易度： 茶色 453
追記 20221227
after contest まで通っています。
考察
文字列を前から探索する場合に、各操作を実行するためにはどんな情報が必要になりそうか考えてみます。
- $S_i$ が英小文字ならば、その英小文字が書かれたボールを箱に入れる。ただし、そのボールがすでに箱に入っている場合、高橋君は気を失う。
⇒ 一度登場した英子文字を管理したいです。
集合 : set あるいは、辞書(連想配列) : dict,defaultdict で O(1) の要素検索が可能なのでどちらかで管理します。
- $S_i$ が ( ならば、何もしない。$S_i$ が ) ならば、i 未満の整数 j であって、S の j 番目から i 番目までの文字からなる文字列が良い文字列となる最大の整数 j を取る。（このような整数 j は必ず存在することが証明できる。）j 番目から i 番目までの操作で箱に入れたボールをすべて、箱から取り出す。
⇒ 今見ている ( ) の中身を管理したいです。
また、( ) が何重にもなっている場合、現在の ( ) の処理を中断し、新しい ( ) の処理に移らなくてはいけません。したがって、( ) 自体も管理する必要があります。
ただし図のように、内側の ( ) が閉じると、最後 に中断した ( ) を現在の ( ) に更新する ( 戻す ) 必要があります。
つまり、( ) は「 順番 」つきで管理する必要があるということです。リスト は順番つきでデータを管理でき、かつ 後ろからの操作を得意にしています。一つ外側の ( ) を取り出す(戻る) ためにはピッタリです。
ここまでで 何を、どうやって、管理すればよいかわかりました。
ここで、S の 各英子文字に対して
➀ 登場済か判定し
➁ 登場済でなければ、登場済に変更
③ () が閉じたので 未登場に変更
の３つの操作を行う可能性がありますが、これらは適切なデータ構造で管理していれば全て $O(1)$ で 実現できるので、計算量は全体で $O( |S|) $ となり十分高速です。
したがって、単純にシミレーションすればこの問題を解くことができるとわかりました。
コード
pypy3
from collections import defaultdict
S=input()
# 中断した () を管理するリスト
X=[]
# a ～ z がすでに箱に入っているか管理
Y=defaultdict(int)
# 今見ている () の中身を管理
now=set()
for s in S:
# 新しい () の登場にあわせて、今見ている () を X に格納
if s=="(":
X.append(now)
now=set()
continue
if s==")":
# 今見ている () の中身をキーに X を初期化
for t in now:
Y[t]=0
# 直前の () を取り出す
now=X.pop()
continue
# 被りを検出したら終了
if Y[s]!=0:
print("No")
exit()
# s を使用済みに変更
Y[s]=1
# 今見ている () に s が存在することを記録
now.add(s)
print("Yes")
補足
- 各データ構造計算量
・Pythonistaなら知っておきたい計算量のはなし
・Pythonで"in list"から"in set"に変えただけで爆速になった件とその理由
絶対に覚えてください
終わり
D 問題の after_contest も無事通りました。