ABC 295 のA,B,C,D問題を解くために考えたこと、ACできるPython3(PyPy3)コードを紹介します。
この記事は @u2dayo さんの記事を参考にしています。見たことのない方はそちらもご覧ください。とても勉強になります。
また、問題の難易度を表す指標を Atcoder Problems から引用しています。このサイトは勉強した問題を管理するのにとてもオススメです。
質問やご指摘はこちらまで
Twitter : Waaa1471
作者プロフィール
Atcoder ：緑色 979
230326 現在
目次
はじめに
A.Probably English
B.Bombs
C.Socks
D.Three Days Ago
はじめに
特にC問題以降になると、競技プログラミングに典型的な前提知識、少し難しい数学的考察が必要になり始めます。
しかし、公式解説ではこの部分の解説があっさりしすぎていて競技プログラミング(Atcoder)を始めたばかりの人にはわかりにくい、難しいと感じるのではないでしょうか。
またC++がわからないと、コードの書き方を勉強することが難しいです。一応、参加者全員のコードを見ること自体は可能ですが、提出コードは必ずしも教育的ではありません(ここで紹介する記事も本番で提出したものとは全く異なります)。そんなものから初学者が解説もなしになにか得ることはとても難しいと思います。実際適当に何人かのコードをみたものの、意味がわからずに終わった経験があるのではないでしょうか。
この記事がそんな方々の勉強の助けになればよいなと思っています。
A.Probably English
難易度： 灰色 15
考察
入力した N 個の文字列を要素とする長さ N のリスト W を作成し、特定単語が W の要素として含まれているか判定すればよいです。
コード
pypy3
60 ms/2000 ms
N=int(input())
W=input().split()
if "and" in W or "not" in W or "that" in W or "the" in W or "you" in W:
print("Yes")
exit()
print("No")
補足
# 入力を文字列で受け取る場合
if "and" in "andor notnot thisthat athe youi":
# "Yes"
# 入力をリストで受け取る場合
if "and" in ["andor","notnot","thatthis","athe","youi"]:
# "No"
このように、文字列検索では一致判定ではなく包含判定となるため注意が必要です。
- 計算量 ～ リスト vs 集合 ～
集合でデータを管理することで、リストの場合よりも高速に要素検索が行えます。
この問題では管理すべきデータが非常に少ないのでリストで管理しても全く問題ないのですが、この差でリストの場合のみ TLE することはよくあるので絶対に覚えておきましょう。
・Pythonistaなら知っておきたい計算量のはなし
・Pythonで"in list"から"in set"に変えただけで爆速になった件とその理由
B.Bombs
難易度： 灰色 153
考察
マスを全探索し、そのマスに爆弾があればさらにそこから破壊できる範囲のマスを全部調べれば、最終状態を求められそうです。
破壊範囲を 20^2 と大雑把に見積もっても計算量は O(RC × 20^2) ⇒ O(20^4) で十分高速です。
(修正時、図で表現したい)
コード
pypy3
96 ms/2000 ms
R,C=[int(rc) for rc in input().split()]
RC=[]
for _ in range(R):
# マスの更新に備えてリストで各マスを管理する(文字列内更新はできない)
B=[b for b in input()]
RC.append(B)
for r in range(R):
for c in range(C):
if RC[r][c]=="." or RC[r][c]=="#":
continue
b=int(RC[r][c])
# 以降壁のみ破壊するので、ここで現在位置を破壊しておく
RC[r][c]="."
for x in range(-b,b+1):
for y in range(-b,b+1):
# マンハッタン距離 b 以下
if abs(x)+abs(y)>b:
continue
cand_r=r+x
cand_c=c+y
# 破壊対象マスが盤面内かつ壁なら破壊
if 0<=cand_r<R and 0<=cand_c<C and RC[cand_r][cand_c]=="#":
RC[cand_r][cand_c]="."
for i in range(R):
print("".join(RC[i]))
補足
なし
C.Socks
難易度 ： 灰色 122
考察
同じ色の靴下の枚数を管理することができれば、ペアを作るための操作回数が求められます。
ここでは、defaultdict で色と枚数を紐づけることにします。(色を全て管理することはできないので、リストはNG)
コード
pypy3
276 ms/2000 ms
from collections import defaultdict
N=int(input())
A=[int(a) for a in input().split()]
D=defaultdict(int)
for a in A:
D[a]+=1
ans=0
for a in D:
ans+=D[a]//2
print(ans)
補足
- defaultdict
・公式ドキュメント
要素として、リストや集合などのデータ構造をもつことができる辞書。この問題のように非連続な要素を管理する場合でよく利用する。
なおこの問題のような個数管理問題では、同じ collections ライブラリに搭載されている Counter クラスでデータを管理することもできる。
・PythonのCounterでリストの各要素の出現個数をカウント
D.Three Days Ago
難易度： 緑色 939
考察
嬉しい列となるためには、[l,r] の区間に含まれる 1 ～ 9 の各要素の個数偶数である必要がある。
ただし、[l,r] 区間は N^2 オーダーなので全部考えることができない。
そこで、[l,r]が嬉しい列の場合、[0,r] と [0,l-1] の各要素の偶奇が一致することに注目。⇒ [0,0]の部分列から順に、各要素の偶奇を調べて同じ偶奇を持つ連続列の総数を管理する。なお、ここでは 10桁の 2進数で各要素の偶奇を表現することにする。例えば 0,2,4,6,8 が奇数回登場したことを 1010101010(2) で表現する。
コード
pypy3
291 ms/2000 ms
S=input()
table=[0 for _ in range(2**10)]
table[0]=1
bit=0
for i in range(len(S)):
s=int(S[i])
# ここまでの 0～9 までの偶奇を bit で表現
bit^=2**s
table[bit]+=1
ans=0
# 同じ偶奇を持つ個数の組み合わせを計上
for t in table:
ans+=t*(t-1)//2
print(ans)
補足
- 類題
問題ページ
ネタバレ回避で abc 160 ～ 165 , c ～ e と記載
終わり
0328
たくさんの閲覧、反応感謝しております。
考察項目は通常クオリティ(abc293 以前)まで修正するつもりです。時間ができ次第、になってしまいますが、コードは分かりやすい(はず)なのでしばらく勘弁して下さい。
修正後は twitter でアナウンスいたします。