5完1TLE。
各問題
A - Don't be late
簡単な算数ではありますが、距離Dを分速Sで移動するからかかった時間はD / Sとすると面倒なことになります。
なので、分速SでT分移動したときの距離S * TをDと比較するのがよいです。
B - Substring
全探索すればよいです。
自分は面倒臭そうだと思って、一旦飛ばしてDまで解いてから戻ってきました。落ち着いてみればなんてことなかった。
C - Sum of product of pairs
単純に計算しようとすると時間計算量が間に合わないので、工夫が必要です。
式変形すると、iの値で考えて 1 * (2 + 3 + 4 + ... + n) + 2 * (3 + 4 + ... + n) + ... + (n - 1) * (n) となりまして、1からnまでの和は前計算で求めておくと全体でもO(N)で済みます。
D - Friends
友達のグループのうち、最低でも最大派閥の人数分は分割する必要があり、そしてそれ以上分割する必要もないので、それが答えです。
グルーピングはUnion-Findでやると楽です。ABCでUnion-Findは久しぶり？
E - Coprime
それぞれの数字を素因数分解して、同じ素因数が出た時点でpairwise coprimeにはなりえません。また、setwise coprimeについては、実際に全部のGCDを計算しちゃえばいいです。
素因数分解が重い実装の場合、pairwise coprimeでないことがわかったら処理を打ち切るなどの工夫がないとTLEしてしまいます。私はそれで1TLEしました。もったいない・・・。
ていうか、軽い素因数分解を実装せよって話ですね・・・。
F - I hate Shortest Path Problem
DPかと思ったら、制約が重いので無理っぽい。セグメントツリーを使うのかなとは思い当たったのですが、何をどう管理するとよいのかまではわからずじまいでした。
まとめ
青パフォを出して堂々の水色復帰。素因数分解が重くてTLEしたのが唯一反省点ですが、Dまできっちり早解きできたので満足の回でした。
