AtCoder Beginner Contest 177の解説・感想

100-200-300-400-500(1)-0で1ペナ5完1500点。

A - Don't be late

先週も同じような問題文見たな...（既視感）

2つの解法を紹介する。どちらも、「問題文で与えられたすべての変数を同時に見ない」のが特徴的。

解法1： $T$ 分後の待ち合わせ時刻に間に合うためには、どれだけの速さで移動すればいいか計算する。 $D$ メートルを $T$ 分で移動したい、つまり、 $1$ 分間で $\frac{D}{T}$ メートル移動したい。つまり、分速 $\frac{D}{T}$ メートル（以上）の速さで歩ければ待ち合わせ時刻に間に合わせることができる。ここで、高橋君は分速 $S$ メートルで歩けるので、 $\frac{D}{T} \le S$ なら間に合うことがわかる。

解法2：分速 $S$ メートルで歩けるので、待ち合わせ時刻までの $T$ 分間では $S\times T$ メートルまで移動することができる。ここで、待ち合わせ地点までは $D$ メートルあるので、 $D \le S\times T$ なら間に合うことがわかる。

どちらの解法も、最終的に同じ不等式が導出されていることがわかる。ただし解法1の不等式では整数同士の割り算が登場しており、切り捨ての処理などが発生すると正しい答えが得られない可能性があるので、「答えを小数で出す」「両辺に同じ数をかけて割り算を掛け算に直す」などの処理をした方が安心！

計算量は、 $O(1)$ 。

B - Substring

むずくないか？

文字列 $S$ の長さを $S.len()$ 、文字列 $T$ の長さを $T.len()$ とする。

文字列 $S$ のどこの文字をどんな文字に変更すれば最適なのかを調べたい。ここで、 $S$ の何文字目から $T$ と一致するのかを全探索する。 $1\le j\le S.len() - T.len() + 1$ を満たす $j$ に対して、 $S$ の $j$ 文字目からの $T.len()$ 文字を $T$ と一致させたい。逆に言えば、この $T.len()$ 文字以外の文字はどんな文字でも関係ない！ $1\le i\le T.len()$ を満たす $i$ に対して、 $S$ の $(j+i)$ 文字目と $T$ の $i$ 文字目が異なっている箇所が何か所あるか数えて、異なっている箇所が一番少なくなるような $j$ を選べばよい！（説明がむずい！）
聞かれているのは「何文字変えるか？」である。 $S$ と $T$ で異なっている箇所だけ変えればよく、その個数は先ほど数えたものそのままなので、それを出力すればよい。
計算量は、 $O(S.len()\times T.len())$ 。

C - Sum of product of pairs

計算量について学べる良い数学問。

問題文の通りに実装すると、計算量が $O(N^2)$ となり、実行時間制限に間に合わない（TLE）。なので、計算方法を工夫する必要がある。

$i\lt j$ であり、 $A_j$ とかけられる数は $A_1, A_2, \dots , A_{j-1}$ の $(j-1)$ 個ある。これらの総和は、分配則を用いると $A_j(A_1 + A_2 + \dots + A_{j-1})$ となる。このうち、 $A_1 + A_2 + \dots + A_{j-1}$ の部分は $j$ から $(j+1)$ に増えるとき $A_j$ だけ増えるので、 $j$ についてのループを前から回していけば計算することができる。この場合の計算量は、 $O(N)$ となり、高速に計算できるのでACとなる！

ちなみに、 $Sum = (全てのA_iの合計)$ として、 $((Sum - A_i) \times A_i)$ の総和を2で割ることでも答えを求められる（九九の表みたいなのをイメージするとわかりやすい）。

D - Friends

すぐ解けたのでよかった（小並感）

「人」を頂点、「人と人が友達であること」を辺と見ると、グラフの構造に落とし込める。さらに、友達の友達は友達であるという条件より、友達同士の人を集めた集合がいくつかできることもわかる。このような集合がいくつかあるN人をグループに分けるとき、同じグループに友達同士の人がいないようにするには、同じ友達同士の集合から2人以上選ばないようにすると良い。つまり、最大 $P$ 人の友達集合があるなら、少なくとも $P$ 個のグループを作ってそこに1人ずつ振り分ける必要がある。逆に、友達ではない関係の人は同じグループに何人いても問題ないので、 $P$ がいくつか求められれば良い！

友達同士の集合を構成するには、例えばUnionFindというデータ構造を用いると上手くいく。UnionFindでは、2頂点を連結したり、ある頂点がどの集合に属するかを調べたりするのをとても高速に行うことができる。入力を受け取る過程で集合を作り、その集合の要素数の最大数を求めればよい。計算量は、およそ $O(N)$ *1。

ほかにも、幅優先探索で連結成分を調べると同様に解ける。

E - Coprime

提出前にコーナーケースを確かめず1ペナしてしまった…。

この問題は、「pairwise coprimeであるか」「setwise coprimeであるか」の2種類の判定問題を解くことができれば正解となる。

2種類のうち、「setwise coprimeであるか」は比較的簡単に求められる。3つ以上の正の整数に対して、最大公約数を求める関数を $gcd()$ とすると、この関数は結合則が成り立つ。つまり、 $gcd(A_1, gcd(A_2, gcd(A_3, \dots)))$ という風に2組の最大公約数を順に求めていけば $N$ 個の数の最大公約数が求まる。このパートの計算量は、2数の最大公約数の計算に $O(\log A_i)$ かかるので、全体で $O(N \log A_i)$ となる。

残った「pairwise coprimeであるか」について。もしpairwise coprimeでないなら、共通する素因数が1つ以上存在するはずである。それぞれの数を素因数分解して素因数を調べることで、共通する素因数があるかどうかがわかる。一つの数を素因数分解するのに $O(\sqrt A_i)$ かかるので、全体で $O(N\sqrt A_i)$ となり、制約よりおよそ $10^9$ 回の計算が必要となるが、 $A_i$ 以下の素数の個数を $\pi(A_i)$ とすると、素数定理より $\pi(A_i) \fallingdotseq \frac{A_i}{\log A_i}$ と表せるあるため、鳩ノ巣原理より素因数が被った時点で探索を打ち切れば計算量はおよそ $O(\frac{A_i\sqrt A_i}{\log A_i})$ となる。この計算量の式に制約の最大値を代入して計算するとおよそ $5\times 10^7$ 回の計算となり、十分高速に計算できる。