ABC 289のA,B,C,D 問題を解くために考えたこと、ACできるPython3(PyPy3)コードを紹介します。
この記事は @u2dayo さんの記事を参考にしています。見たことのない方はそちらもご覧ください。とても勉強になります。
また、問題の難易度を表す指標を Atcoder Problems から引用しています。このサイトは勉強した問題を管理するのにとてもオススメです。
質問やご指摘はこちらまで
Twitter : Waaa1471
作者プロフィール
Atcoder ：緑 886
230211 現在
目次
はじめに
A.flip
B.レ/V
C.Coverage
D.Step Up Robot
はじめに
特にC問題以降になると、競技プログラミングに典型的な前提知識、少し難しい数学的考察が必要になり始めます。
しかし、公式解説ではこの部分の解説があっさりしすぎていて競技プログラミング(Atcoder)を始めたばかりの人にはわかりにくい、難しいと感じるのではないでしょうか。
またC++がわからないと、コードの書き方を勉強することが難しいです。一応、参加者全員のコードを見ること自体は可能ですが、提出コードは必ずしも教育的ではありません(ここで紹介する記事も本番で提出したものとは全く異なります)。そんなものから初学者が解説もなしになにか得ることはとても難しいと思います。実際適当に何人かのコードをみたものの、意味がわからずに終わった経験があるのではないでしょうか。
この記事がそんな方々の勉強の助けになればよいなと思っています。
A.flip
難易度：14
考察
python では文字列の置き換えを replace() 関数 で実行できます。
注意点として、素直に 0 を 1 に置き換え、その後 1 を 0 に置き換えてしまうと全て 0 に置き換わってしまいます。
そこで、最初の置き換えを 次の置き換えに影響されない 仮の値 への置き換えに変更し、次の置き換えが終わった後それを真の値に置き換えることにします。
コード
pypy3
109 ms /2000 ms
S=input()
# 仮の値で置き換え
S=S.replace("1", "2")
S=S.replace("0", "1")
# 真の値で置き換え
S=S.replace("2", "0")
print(S)
補足
B.レ/V
難易度：225
考察
問題文が非常に長いですが、つまりは 1 ～ N までの整数列 を レ点のルール に従って読む場合の順番を求める問題です。
このような例では、1 → 6 → 5 → ... 2 → 7 と読むことになります。
必要な情報
基本的には前から順に読んでいくので、整数列を前から見て順番を決定する方針をたてます。このとき、前から $i$ 番目の整数を読む前に読むべきであって $i$ より後ろにある最大の整数 $S_i\ $ があらかじめ分かっていればうれしいです。( 例では $S_2 = 6$ )
$S_i$ が求められれば $S_i$ → $S_i -1$ → ... $i+1$ → $i$ , と $S_i$ から $i$ まで降順に読んでいけばよいと分かるからです。
戦略
$S_i$ とは、整数 $i$ から レ点でつながっている最も大きな整数 です。これを求めるために、ここでは Union-Find でレ点でつながる整数のグループを作成することにします。
Union-Find ではグループ内のどの値からでもアクセス可能な 代表値 (親) を設定することができます。$i$ から $S_i$ を求めたい現状にピッタリです。
注意点
$S_i > i+1$ の場合、$i+1$ を見ることになった際、既に $i+1$ は読み終わっている状態です。$S_i$ → $S_i -1$ → ... $i+1$ まで再読してはいけないので、一度読んだ整数を管理しこれを防ぎます。
実装でのポイント
グループを形成する際、結合する値 と 現在の代表値 のより大きな方で代表値を更新することにします。これによって結合する順番によらず、代表値がグループ内での最大値である状態を保つことができます。
コード
pypy3
62 ms/ 200 ms
メイン
ここに Union-Find クラスを書く
if __name__ =="__main__":
N,M=[int(nm) for nm in input().split()]
A=[int(a) for a in input().split()]
uf=UnionFind(N)
# レ点でつながるグループを作成
for a in A:
uf.union(a-1, a)
# 読まれる順番を保存
order=[]
# 前から i 番目 の整数が読まれているか、いないかの状態を管理
ok=[False for _ in range(N)]
for i in range(N):
# 既に読まれていればスキップ
if ok[i]:
continue
# レ が後になければそのまま読む
if uf.parents[i]==-1:
order.append(i+1)
else:
# ここより後ろにある位置で、最初に読まなければいけない位置
x=uf.find(i)
# この位置から i まで逆順に読む
for j in range(x,i-1,-1):
order.append(j+1)
# 読まれた状態へ更新
ok[j]=True
print(*order)
Union-Find クラス
class UnionFind():
def __init__(self,n):
self.n = n
self.parents = [-1] * n
# 代表値検索
def find(self,x):
if self.parents[x] < 0:
return x
else:
self.parents[x] = self.find(self.parents[x])
return self.parents[x]
# グループ化
def union(self,x,y):
x = self.find(x)
y = self.find(y)
if x == y:
return
# 同じグループのうち、最も右側の位置を代表値(親)にする
if y>x:
x,y=y,x
self.parents[x] += self.parents[y]
self.parents[y] = x
補足
- Union-Find
PythonでのUnion-Find（素集合データ構造）の実装と使い方
Union-Find クラス実装のための解説がとても分かりやすく記載されています。必読です。
B - Union Find
スライドがとても分かりやすく、視覚的に操作を理解することができると思います。 - 出力形式
競技プログラミングにおける Python での標準入出力のまとめ
こちらに分かりやすくまとめられているので、出力形式に躓いた方はご覧ください
C.Coverage
難易度 ： 396
考察
基本的に忠実に !! 全探索
親切に集合を選ぶ方法が $2^M-1$ 通りであることが問題文中で示されていて、また $1≦ M ≦10$ であることから 選ぶ方法を全探索して、その選び方が条件を満たすか判断することができます。
選び方は $i$ 桁目で $S_i$ を選んでいるかを表す、$M$ 桁の 2進数で表現することにします。いわゆる bit 全探索 と呼ばれる戦略で、$i$ 桁目が 1なら $S_i$ を選んでいる、0なら選んでいない 選び方を表現します。
また選び方を決定し、そこから $S_i$ の状態を復元するために、bit演算 で $i$ 桁目が 0 か 1 か を調べています。
こうしてこの選び方で含まれる整数を全て調べ、条件を満たすか判定すればよいです。
コード
pypy3
267 ms/2000 ms
N,M=[int(nm) for nm in input().split()]
ok=[[] for _ in range(N+1)]
S=[]
for i in range(M):
C=int(input())
A=[int(a) for a in input().split()]
S.append(set(A))
ans=0
# 選び方全探索
for bit in range(2**M):
# 個の選び方で x が含まれるか管理
ok=[False for _ in range(N+1)]
for i in range(M):
# Si を選んでいるか
if bit>>i & 1:
for s in S[i]:
ok[s]=True
# 1～N まで全てあれば条件を満たす選び方として計上
if all(ok[1:]):
ans+=1
print(ans)
補足
-
all()
Pythonではリストやタプルなどが保持している要素を、一括で真偽判定（TrueかFalseか）することができるall関数、any関数があります。
全ての or どれかひとつの 要素で条件判定したい場合に便利な関数です。
D.Step Up Robot
難易度： 551
考察
問題文に記載されている通り、$i$ 段目に到達可能であれば $i+A_1$ 段目 ... $i+A_N$ 段目 までのモチが置かれていない段にも到達可能です。
したがって 0 段目から到達可能な段を求め、さらにそれらからも到達可能な段を求めていく。これを $X$ 段目まで繰り返すことで、$X$ 段目に到達可能か求めることができそうです。
このような状態の遷移に忠実に状態を更新していくことは 動的計画法 (DP) で行います。
この問題ではシンプルに $\ dp[i]\ $ で $i$ 段目に到達可能かを管理すればよいでしょう。
コード
pypy3
90 ms/ 2000 ms
N=int(input())
A=[int(a) for a in input().split()]
M=int(input())
B=[int(b) for b in input().split()]
X=int(input())
# もちの存在を管理
ok=[True for _ in range(10**5+10)]
for b in B:
ok[b]=False
dp=[False for _ in range(X+1)]
dp[0]=True
for i in range(X):
# i段目に到達可能なら
if dp[i]:
for a in A:
# もちがなければ遷移可能
if i+a<=X and ok[i+a]:
dp[i+a]=True
if dp[-1]:
print("Yes")
else:
print("No")
補足
- 動的計画法
・動的計画法ってなに？ (導入)
・典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～
こちらで動的計画法の概念を勉強することができます。
分かるようになったら、アルゴ式 1～2章で練習してみましょう
動的計画法 (DP)
終わり
来週も見てくれよな!