【Python】Atcoder Beginner Contest177を解く

競技プログラミング

競技プログラミングの記事を書くのはいつ以来でしょうか、なんだかんだたまにやると面白いのでやってます。相変わらずがっつりやるわけでもなくチビチビとやっていましたが、茶色になりました。

仕事柄pythonを使うことが多くなったのでこの記事からpythonで書いていきたいと思います。今回の177は時間内ではなく後日解いたものです。自分用なのでメモとコードは殴り書きです。ご容赦を

今回解いたものはこちらにあげています。

Build software better, together
GitHub is where people build software. More than 100 million people use GitHub to discover, fork, and contribute to over 330 million projects.

A – Don’t be late

距離と速さと時間が与えられて時間内にその距離に到達できるか、みはじの計算です。

ちなみに高橋君の最大速さは分速10000メートルです。

B – Substring.py

文字列SとTが与えられ、TがSの部分文字列になるためにはSを何文字変えればよいか、という問題。

文字列Sの中にTとマッチする文字の最大数を求め、Tの長さからそれを引くことで答えを求めました。部分文字列があるかどうかだけをジャッジするならば、1文字違う時点でfor文をbreakしていいのですが、そうではなく末尾が一致していることもあるので全文字を毎回ジャッジしました。

C – Sum of product of pairs

n個の整数A1 ~ AnにおいてAi * Aj(i < j)の総和を求めます。

もちろんfor文を入れ子構造にして単純に計算するとTLEです。

なんとなく例を眺めていたらA1 * A2 + A1* A3 + A1 * A4 = A1 * (A2 + A3 + A4)であることに気付いたのでこれを使えないか考えます。

N=4のときAの総和sum(A)からA1を引くと(A2 + A3 + A4)となるので引いたA1と掛けると求めたい値が出ます。次に計算したいものはA2 * (A3 + A4)なので後はこれを繰り返すだけです。

解説、twitterを見ていたらよりなるほどと思った解法を引用させていただきます。

D – Friends

友達の友達は友達です。例1を見てみると、

(1, 2), (5, 1)から2と5も友達、(3, 4)が友達になっているので友達のグループ化をすると

(1, 2, 5), (3, 4)の2グループになります。これらのグループをバラバラにしたいので(意地悪な学校の先生みたい)人数が一番多いグループをばらして、ばらした中にほかのグループの人を別々に入れていけば1人も友達がいないグループができると思います。

なので答えは友達同士のグループを作りそのグループの中で人数が一番多いグループの人数が答え

グループの作り方は解答を見るとUnion-Findなるものを使うとよいみたいので使ってみます。こちらの記事を参考にさせていただきました。

PythonでのUnion-Find(素集合データ構造)の実装と使い方 | note.nkmk.me
PythonでのUnion Findデータ構造(素集合データ構造)の実装とその使い方を説明する。まずはじめに最終形のクラスとその使い方のサンプルコードを示し、後半で素朴な実装からいくつかの工夫を加えて最終形に至るまでを説明する。Union Find(素集合データ構造)の概要 PythonでのUnion Findの実装例...

入力されたNをもちいてUnionFind(N)と初期化、

findメソッドをmループだけ回し、情報を入れていくことで友達同士のグループを作成しています。

最後にgroup_countメソッドでグループ数を求め、その分ループさせ、sizeメソッドで各グループの大きさ(人数)を求め、最大値を返します。それが答え。

振り返り

ABC問題は特に難なく解けましたが、C問題は紹介した解法があったのでこういった時方でもできるのかとやはり解説を見るのは大事。

D問題は解説を見たがとりあえずACまではできた。UnionFindは詳しくは分かってないがfindとunionの仕組みくらいは分かっておいたほうがいいと思う。

コメント

タイトルとURLをコピーしました