100-200-300-400-500(1)-0で1ペナ5完1500点。
A - Don't be late
先週も同じような問題文見たな...(既視感)
2つの解法を紹介する。どちらも、「問題文で与えられたすべての変数を同時に見ない」のが特徴的。
解法1:分後の待ち合わせ時刻に間に合うためには、どれだけの速さで移動すればいいか計算する。
メートルを
分で移動したい、つまり、
分間で
メートル移動したい。つまり、分速
メートル(以上)の速さで歩ければ待ち合わせ時刻に間に合わせることができる。ここで、高橋君は分速
メートルで歩けるので、
なら間に合うことがわかる。
解法2:分速メートルで歩けるので、待ち合わせ時刻までの
分間では
メートルまで移動することができる。ここで、待ち合わせ地点までは
メートルあるので、
なら間に合うことがわかる。
どちらの解法も、最終的に同じ不等式が導出されていることがわかる。ただし解法1の不等式では整数同士の割り算が登場しており、切り捨ての処理などが発生すると正しい答えが得られない可能性があるので、「答えを小数で出す」「両辺に同じ数をかけて割り算を掛け算に直す」などの処理をした方が安心!
計算量は、。
B - Substring
むずくないか?
文字列の長さを
、文字列
の長さを
とする。
文字列のどこの文字をどんな文字に変更すれば最適なのかを調べたい。ここで、
の何文字目から
と一致するのかを全探索する。
を満たす
に対して、
の
文字目からの
文字を
と一致させたい。逆に言えば、この
文字以外の文字はどんな文字でも関係ない!
を満たす
に対して、
の
文字目と
の
文字目が異なっている箇所が何か所あるか数えて、異なっている箇所が一番少なくなるような
を選べばよい!(説明がむずい!)
聞かれているのは「何文字変えるか?」である。と
で異なっている箇所だけ変えればよく、その個数は先ほど数えたものそのままなので、それを出力すればよい。
計算量は、。
C - Sum of product of pairs
計算量について学べる良い数学問。
問題文の通りに実装すると、計算量がとなり、実行時間制限に間に合わない(TLE)。なので、計算方法を工夫する必要がある。
であり、
とかけられる数は
の
個ある。これらの総和は、分配則を用いると
となる。このうち、
の部分は
から
に増えるとき
だけ増えるので、
についてのループを前から回していけば計算することができる。この場合の計算量は、
となり、高速に計算できるのでACとなる!
ちなみに、として、
の総和を2で割ることでも答えを求められる(九九の表みたいなのをイメージするとわかりやすい)。
D - Friends
すぐ解けたのでよかった(小並感)
「人」を頂点、「人と人が友達であること」を辺と見ると、グラフの構造に落とし込める。さらに、友達の友達は友達であるという条件より、友達同士の人を集めた集合がいくつかできることもわかる。このような集合がいくつかあるN人をグループに分けるとき、同じグループに友達同士の人がいないようにするには、同じ友達同士の集合から2人以上選ばないようにすると良い。つまり、最大人の友達集合があるなら、少なくとも
個のグループを作ってそこに1人ずつ振り分ける必要がある。逆に、友達ではない関係の人は同じグループに何人いても問題ないので、
がいくつか求められれば良い!
友達同士の集合を構成するには、例えばUnionFindというデータ構造を用いると上手くいく。UnionFindでは、2頂点を連結したり、ある頂点がどの集合に属するかを調べたりするのをとても高速に行うことができる。入力を受け取る過程で集合を作り、その集合の要素数の最大数を求めればよい。計算量は、およそ*1。
ほかにも、幅優先探索で連結成分を調べると同様に解ける。
E - Coprime
提出前にコーナーケースを確かめず1ペナしてしまった…。
この問題は、「pairwise coprimeであるか」「setwise coprimeであるか」の2種類の判定問題を解くことができれば正解となる。
2種類のうち、「setwise coprimeであるか」は比較的簡単に求められる。3つ以上の正の整数に対して、最大公約数を求める関数をとすると、この関数は結合則が成り立つ。つまり、
という風に2組の最大公約数を順に求めていけば
個の数の最大公約数が求まる。このパートの計算量は、2数の最大公約数の計算に
かかるので、全体で
となる。
残った「pairwise coprimeであるか」について。もしpairwise coprimeでないなら、共通する素因数が1つ以上存在するはずである。それぞれの数を素因数分解して素因数を調べることで、共通する素因数があるかどうかがわかる。一つの数を素因数分解するのにかかるので、全体で
となり、制約よりおよそ
回の計算が必要となるが、
以下の素数の個数を
とすると、素数定理より
と表せるあるため、鳩ノ巣原理より素因数が被った時点で探索を打ち切れば計算量はおよそ
となる。この計算量の式に制約の最大値を代入して計算するとおよそ
回の計算となり、十分高速に計算できる。
あとは問題文の通りに条件分岐させれば答えが求められる。全体の計算量は、およそとなる。(式が複雑で自信がない…)
または、素因数分解をするパートでかわりにエラトステネスの篩を用いることで「pairwise coprimeかどうか」を計算することもできる。
F - I hate Shortest Path Problem
難しい。解けなかった。
まとめ
今回のコンテストでレートが1400を突破した。この調子で青色まで行きたい!