ABC177参加記 - knzkkkkkkkkkk

AtCoder Beginner Contest 177 に参加して5完163位だった。爆速5完キメて最高に気持ちええ　ありがとう　競プロ最高！一番好きなギャンブルです！ww

f:id:knzk398:20200830124459p:plain

A. Don't be late

D,T,Sが与えられるD<=T*Sか

B. Substring

Tの始点を全部試して実際に何個一致しないか数える

Python :

https://atcoder.jp/contests/abc177/submissions/16397045

C. Sum of product od pairs

$\sum_{i=1}^{N-1} \sum_{j=i+1}^{N} a_i * a_j$ を求める問題。愚直に計算すると $O(N^{2})$ になってTLEしてしまうが、内側の $\sum_{j=i+1}^{N}a_i * a_j$ に注目すると、 $a_i$ の値は定数という事がわかるので $a_i * \sum_{j=i+1}^{N} a_j$ にしてよい。 $\sum_{j=i+1}^{N} a_j$ は累積和を使うと $O(1)$ で求まるので、 $i=1...N-1$ まで計算すればよい。オーバーフローしないようにMODをとる場所に注意する。

C++ :

https://atcoder.jp/contests/abc177/submissions/16393159

Python :

https://atcoder.jp/contests/abc177/submissions/16397137

D. Friends

見た瞬間にグラフの最大連結成分の大きさが答えということがわかるのでunion findを貼ってsizeのmaxを出力します。直感的にそうなので、論理的に説明するのは難しいです。ふつうにbfs/dfsをしてもいいと思います。

C++ :

https://atcoder.jp/contests/abc177/submissions/16393388

Python :

https://atcoder.jp/contests/abc177/submissions/16397426

E. Coprime

N要素の配列Aは対ごとに素ですか、互いに素ですか、どちらでもないですか？という問題。 $gcd(a,b)=1$ であることをaとbは互いに素であるといい、 $gcd(a,b,c)=1$ とか、数が2つ以上になってもそのすべての $gcd$ が1であるなら互いに素と言います。「互いに素」というと2つの間の関係しか指さないような気がして直感的ではない気がしますね。

対ごとに素というのは問題文の $\forall(i,j), gcd(a_i,a_j)=1$ という意味です。(ところでこの書き方は正しいですか？わかりません　誰か教えてください)

全ての $a_i$ を素因数分解したときに、ある素数 $p$ が2つ以上の数に含まれていたら $A$ は対ごとに素ではありません。全ての $a_i$ を愚直に素因数分解して確かめると $O(N\sqrt A_{max})$ で解くことが出来ますが、この問題は $N=A_{max}=10^{6}$ なので $N\sqrt A_{max} = 10^{6} * \sqrt 10^{6} = 10^{9}$ となり、TLEしてしまう可能性が高いです。(僕は競プロ初心者なので時間計算量解析をしずにコンテスト中にこれを書いて1916msで通ってしまいました。ごめん....)