Codeforces Round #621 (Div. 1 + Div. 2)

　pretestは四完でしたが、システムテストでCが落ちてしまいました。

コンテストへのリンク

B. Cow and Friend

・まず、一歩でいける場合を調べる。

・一歩でいける最大の距離max(A)を考え、それで何歩でたどりつけるか。最後の二歩でどんな距離でも調整できるので、進みたい距離/max(A)の繰り上げが2ならそれが答え。進みたい距離がmax(A)未満なら、答えは2

C. Cow and Message

　”abc"で等差数列をなしているものの数と、"ab"で等差数列をなしているものの個数を比較すると、前者なら必ず後者に含まれます。

　なので、一文字・二文字の場合だけ調べればOK。

D. Cow and Fields

　新たにsからtまでの道を作るとする。

　1から各点までの距離、nから各点までの距離を求めておく。

　s→tがショートカットになるとすると、1からsの距離より1からtの距離は長く、nからsの距離よりnからtの距離は短い。

　なので、できるだけショートカットにならないようにするには、１からの距離が長い順に点を見ていき、考慮している点より、「さらに1からの距離が長い点たち」のうちでnからの距離が長いものを選ぶ。

E. Cow and Treats

アルメリアさんのブログの解説記事を大いに参考にしてACしました。全く思いつかなかったのですが、解説されてみるとシンプル……。

　まず、

・左右の牛たちのために、草も左右で分ける

　すら思いついてなかった。その上で、

・重複して数えないため、境界の一つ左側の草は必ず使う

　という条件で数えるのが重要。
　二点目はかなり難しそうだけど、一点目すら思いついていなかったのでコメントしにくい。でも、重複して数えないためにある要素を固定して数える、というのは重要そう。


　ただ、やり方が分かっても実装が大変ですね。（実装部分は大体自力でやったこともあり）非常に苦労しました。

　なお、PyPyだとアルメリアさんの実装そのままだとTLEすると思います（自分の場合はそうでした）。

　ここの実装方針では、牛の総和・総積を取っていますが、ここも差分計算でできます。総和・総積のうち、今見ている草と一つ前の草以外については同じなので、その差分だけ計算すればOKです。（modが素数なので、積も逆元が取れます）

　これをしたらACできました。

　この変更をしても計算量のオーダーは変わらない……と思っていたのですが、これをすればO(nlogn)になりますね。
　でも、実装は複雑になるので、C++使いにはあまり意味のない改善かも……。