titiaのノート: Codeforces Round #615 (Div. 3)

2020年2月20日木曜日

　なんとか全完できました。

コンテストへのリンク

A. Collecting Coins

まず、三人の最大値までコインを割り振る。（割り振れなければNO）
　その後、3で割った余りが0ならばYES、そうでなければNO。

　ソートした順番でしか回収できない。移動も辞書順なので、右に行ってから上、と進み方一意に定まる。

　（1を除く）約数を列挙。その中で最も小さいものを使うのが最善。これをaとする。

　次にbを、列挙した中から全探索する。a, bを定めたときn/(a*b)が正の整数になり、1, a, bと重ならなければOK。

　mod xで考えたとき、各要素が何個ずつあるかを管理しておきます。mexを大きくするためには、それらを小さい順に並べれば良いです。

　要素の個数の最小値をMINとすると、0～xのうちMINを始めて取るindexが分かれば答えも分かります。

　たとえば、Exampleの最後のクエリ、a=[0,1,2,2,0,0,10] のときを考えると、

0: 3個

1: 2個

2: 2個

　なので、MIN=2、はじめてMINを取るindexは1です。

　mexは、余り0～2を二周した後、もう一歩だけ進むことができるので、3*2+1のように求められます。

　よって、この二つの値を高速で求めれば良いのですが、コンテスト中は区間加算・区間最小を求めることができるSegment treeと二分探索を用いて処理しました。

　このようなSegment treeを使えば、全体の最小値は求めることができます。あとは、[0,i]における最小値がMINになる最小のindex iが分かれば良いですが、これは二分探索で求められます。

　なお、この問題はSegment treeを使わずとも解くことができます。mexが減ることはないし、高々qまでしか増えないので、「mod xで考えたとき、各要素が何個ずつあるか」という情報を持ってシミュレーションすればOKです。実装も楽だし、計算時間もこの方が速いですね。

　各列について、その数字がローテーションの結果一致するなら、何回ローテーションしたときか、を調べる。それを使ってローテーション回数を全探索する。

　直径＋1点を全探索。その残りの一点と直径との距離を調べるところでLCAを使ってしまいましたが、DFSすればOKでした……。

　コンテスト後、直径で良いことの正当性がツイッター上で話題になっていたけど、一応コンテスト中に示したつもり。

　ただ、直径が二つ以上あるときがコンテスト中は良く分からなかった。
　そういう場合、中心Vに対して、V-a, V-b, V-cの距離が等しくなる三点a, b, cが存在するので、それらを取ればOKなのですね。（ながたかなさんのブログの記事を読んで気付きました）

　なので、適当な直径を一つ選んできて良いですね。