競技プログラミングの記事を書くのはいつ以来でしょうか、なんだかんだたまにやると面白いのでやってます。相変わらずがっつりやるわけでもなくチビチビとやっていましたが、茶色になりました。
仕事柄pythonを使うことが多くなったのでこの記事からpythonで書いていきたいと思います。今回の177は時間内ではなく後日解いたものです。自分用なのでメモとコードは殴り書きです。ご容赦を
今回解いたものはこちらにあげています。
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なるものを使うとよいみたいので使ってみます。こちらの記事を参考にさせていただきました。
入力されたNをもちいてUnionFind(N)と初期化、
findメソッドをmループだけ回し、情報を入れていくことで友達同士のグループを作成しています。
最後にgroup_countメソッドでグループ数を求め、その分ループさせ、sizeメソッドで各グループの大きさ（人数）を求め、最大値を返します。それが答え。
振り返り
ABC問題は特に難なく解けましたが、C問題は紹介した解法があったのでこういった時方でもできるのかとやはり解説を見るのは大事。
D問題は解説を見たがとりあえずACまではできた。UnionFindは詳しくは分かってないがfindとunionの仕組みくらいは分かっておいたほうがいいと思う。
コメント