8/17

8/18

CF 980 C - Posterized

辞書順最小→貪欲(submission)。

CF 980 D - Perfect Groups

同じグループにできるのは、正負が一致かつ素因数の個数の偶奇が一致するものが同じグループにすることができる。ただし、0だけは特別扱いする必要があり(0はどのグループに入っても差し支えないので)、それ以外のグループがいくつできるかを全部の部分列に対して $O(n^2)$ で試す(始点iを決めて、そこから右に動かしながら要素を追加していく)。この全探索部分に余計なlogなどを載せたくないので、前計算として素因数分解したものをmapでID化しておくと計算量がちゃんと $O(n^2)$ で抑えられる(submission)。

CF 980 E - The Number Games

残す人数を最大化したいと考えると、nから降順に貪欲に残していいかを考えることで、残す頂点n-k個を選ぶことができる。なぜなら、 $2^i$ は $2^0 + 2^1 + \ldots + 2^{i-1}$ よりも大きいことを考慮すると、とにかく大きい方を残すほうが得になるからである。そして、残すと決めたときには、nまでのパス上の頂点を全部残さないといけないことになる。よって、nを根としてみなし、ダブリングで親を計算しておくことで、すでに残すうことを決めた頂点までの距離が $O(logn)$ でわかる。これによって上から貪欲に残す頂点を決定できるので、自ずと消す頂点が決まる(submission)。

8/19

KUPC 2013 Virtual

8/20

まず桁数が違った場合は、できるだけ大きくすれば良いので簡単。同じ場合を考えると、先頭何文字までを一致させるかを全探索することにすると、各場合について貪欲に構成することができる(submission)。

8/21

CF 915 D - Almost Acyclic Graph

まず、1つ閉路を見つける。するとその閉路の長さはn以下なので、そのどれかを削除して、そのグラフに対して閉路がないことを逐一チェックすれば $O(nm)$ で間に合う(submission)。

8/22

CF 915 E - Physical Education Lessons

non-working dayの区間をsetで管理することにする。追加するクエリの時は、その間の区間をマージしないといけないので、lower_boundでその区間のスタート地点を見つけて、全部eraseしてから新しい区間を追加する。削除するクエリの時は、同様にスタート地点を見つけて、逐次削除していく。ただ、端は残るかもしれないのでそこを全部消してしまわないように気をつける。このようなことをやると、1回のクエリ処理でたくさんアクセスしてヤバいんじゃないかと思えるが、クエリ全体を通して見ると、このような区間の追加や削除の回数は $O(Q)$ で抑えられているので、余計なところにアクセスしないように気をつけて実装すれば $O(QlogQ)$ になっている。実装の部分で結構悩んだが、やっぱり半開区間で管理するのが実装の見通しが良い。区間を併合するのが楽なように感じる(submission)。

8/23

AOJ 2549 - 7 Age

その星で布教すると決めたら、その星の期間が終わるまでい続けても最適性は失われないのでそういう動きしかとらないことにすると、区間を終端でソートして、 $O(n^2)$ の配るdpができる(submission)。

AOJ 2549 - Lion

8/24

8/25

RUPC 2016 day1 Virtual

Summer Festival Contest 2018 (Division 1)に参加

8/26

8/27

8/28

8/29

CF 915 F - Imbalance Value of a Tree

計算すべき値はペアに対して設定されているが、最小値と最大値に分離して考える。すると、各頂点に対して、この頂点が最大値/最小値になるようなパスはいくつあるか、を各頂点に対して数え上げていくことになる。最小値も最大値も同様に計算できるので、ここでは最大値について考えることにする。頂点にかかれている値が小さい方から順に数えていくことにすると、その頂点から順番に、サイズを管理できるUnionFindを利用しながら、そのパスを通過するようなパスの個数を数えていくことができる。具体的には、小さい方から順に処理するので、いま注目している頂点 $u$ に対して隣接する頂点 $v$ が、すでに処理済みだった場合は $u$ のほうが最大値になるので、まず、その $v$ の連結成分と $u$ のパスは $u$ が最大値になる。また、隣接していてすでに処理済みである別の頂点 $w$ があった場合は、 $v$ を経由して $w$ の連結成分へ伸びるようなパスも $u$ で最大値を取るので、そのようなパスを全部考慮するには和を取って2乗してから2乗の和を引いて重複を除去すればよい。このようにして $O(nlogn)$ で数え上げることができる。最小値も同様に、逆に大きい方から数えれば良い(submission)。

各a[i]について、それを $x$ に選んだときに適切な $y$ がいくつあるかを数える。 $y$ に選ぶ数の桁次第で、 $x$ の位置がずれるので、桁ごとに分類して考える。すると、10のべき乗を計算しておくことで、 $x$ が来る位置と合わせて $k$ での剰余がわかるので、 $y$ に来るべき値が決まる。この $y$ に来る候補を、事前にmapなどで数えておけば、入力の数列は10桁以下なので、 $O(nlogn)$ で十分に間に合う(submission)。