ABC 288のA,B,C 問題を解くために考えたこと、ACできるPython3(PyPy3)コードを紹介します。
この記事は @u2dayo さんの記事を参考にしています。見たことのない方はそちらもご覧ください。とても勉強になります。
また、問題の難易度を表す指標を Atcoder Problems から引用しています。このサイトは勉強した問題を管理するのにとてもオススメです。
質問やご指摘はこちらまで
Twitter : Waaa1471
作者プロフィール
Atcoder ：緑 910
230204 現在
目次
はじめに
A.Many A+B Problems
B.Qualification Contest
C.Don’t be cycle
はじめに
特にC問題以降になると、競技プログラミングに典型的な前提知識、少し難しい数学的考察が必要になり始めます。
しかし、公式解説ではこの部分の解説があっさりしすぎていて競技プログラミング(Atcoder)を始めたばかりの人にはわかりにくい、難しいと感じるのではないでしょうか。
またC++がわからないと、コードの書き方を勉強することが難しいです。一応、参加者全員のコードを見ること自体は可能ですが、提出コードは必ずしも教育的ではありません(ここで紹介する記事も本番で提出したものとは全く異なります)。そんなものから初学者が解説もなしになにか得ることはとても難しいと思います。実際適当に何人かのコードをみたものの、意味がわからずに終わった経験があるのではないでしょうか。
この記事がそんな方々の勉強の助けになればよいなと思っています。
A.Many A+B Problems
難易度： 灰色 6
考察
適切に入力を受け取り、クエリごとに和をとるだけです。
コード
pypy3
93 ms /2000 ms
N=int(input())
for _ in range(N):
a,b=[int(ab) for ab in input().split()]
print(a+b)
補足
B.Qualification Contest
難易度：灰色 44
考察
1: 上位K人のハンドルネームの管理
2: ハンドルネームを辞書順に並び替え
以上 2つの処理を行えるか問われています。
上位K人のハンドルネームの管理
入力で K個までしか受け取らない方法もありますが、ここでは入力を順番にリストに格納した後、スライスして K番目以降を捨てることにします。
ハンドルネームを辞書順に並び替え
python では辞書順の並び替えは soretd() で簡単に実行できます。
コード
pypy3
63 ms /200 ms
N,K=[int(nk) for nk in input().split()]
S=[]
for _ in range(N):
s=input()
S.append(s)
for s in sorted(S[:K]):
print(s)
補足
-
sorted()
Pythonでリストをソートするsortとsortedの違い
C.Don’t be cycle
難易度 ： 茶色 436
考察
まず、グラフは破壊よりも構築する方が簡単です。
この事実に基づくと、閉路を持たないようにグラフを構築した場合に、いくつの辺を無視したか を求める問題であると解釈することができます。
閉路を検出しながらグラフを構築するには Union-Findが適しています。頂点 $Ai$ , $Bi$ を結ぶ前に、これらが既に同じ連結成分であればこの辺を採用すべきでない(無視する)と判断できます。もし採用してしまうと、閉路を成してしまうからです。
コード
pypy3
535 ms /2000 ms
メイン
ここに Union-Find クラスを書く
if __name__ =="__main__":
N,M=[int(nm) for nm in input().split()]
uf=UnionFind(N)
ans=0
for _ in range(M):
a,b=[int(ab)-1 for ab in input().split()]
# 閉路を成すか判定
if uf.same(a,b):
ans+=1
uf.union(a,b)
print(ans)
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 self.parents[x] > self.parents[y]:
x, y = y, x
self.parents[x] += self.parents[y]
self.parents[y] = x
def same(self,x,y):
return self.find(x) == self.find(y)
def roots(self):
return [i for i, x in enumerate(self.parents) if x < 0]
補足
-
Union-Find
PythonでのUnion-Find（素集合データ構造）の実装と使い方
コードの Union-Find クラスはほとんどこの記事をパクっています。解説もわかりやすいので、ご覧ください
B - Union Find
スライドがとても分かりやすいです。視覚的な理解ができるのでこちらも併せてオススメしています。
終わり
D 問題解けな過ぎワロタ