AGC 029

最近言語能力がかなり低下している自覚があるので、物を書いて感覚を取り戻そうと思います。

A, B, Cを解いて304位でした。Bでハマりまくった上にDを誤読してしまい、めちゃくちゃでした。レーティングは下がるし悲しい。二回連続でAGCひどい順位取ってる気がする。

A

問題 白黒(B/W)のオセロが一直線にN(≦2*105) コ並んでいる。B->Wの順で隣接するオセロの色を反転させることを繰り返すとき、最大で何回操作ができるか。

解法 転倒数。

最大というのは実は無視できる。つまり、どんな順番で反転させても回数は変わらない。その回数はi < j かつ (Si, Sj) = ('B, 'W') であるような組の数に等しくて、これは転倒数そのもの。 転倒数の数え上げは、一般のO(N log N)のものを使っても良いがそれは明らかに牛刀なので、値が2種類なことを利用してO(N)で解くと良い。 具体的には、転倒数は普通に左から配列を舐めて、'W'が現れたときにそれまでに現れた'B'の数を足して上げる。

B

問題: N(≦2*105)コの要素が与えられる。各要素は1以上109以下の整数である。要素X,Yの和が2べきのときだけその要素同士のペアを作れる。同じ要素が複数のペアに使われないようにペアを作るとき、作れるペアの数はいくつか。

解法: 貪欲。

本番では重複する数を一つにまとめてから、ペアが作れるかどうかでグラフを作るとそれは森になることを利用して解いた。 基本的には、葉の要素から貪欲に親とマッチさせていくことで最大のペア数が達成できる。しかし、2べき要素(1,2,4,8,...)については、同じ数同士でマッチさせるという追加の選択肢があるので困る。 でも、2べき要素を根とした木を考えると、その選択肢について最後に考えても良いことが分かる。従って、この木で普通に葉から貪欲して、最後にその2べき要素が2つ以上余ったらそれらをペアにする。 二つの異なる2べき要素は1つの木に含まれないことを確認したいが、これは2で割る回数が一致していないとペアに出来ないことから問題ない。

実際はグラフとかを意識しなくて良い方法があり、ソートして最大要素から貪欲にペアを作っていけば良かったらしい...

作れるペアを列挙するパートと、それを実際に使うか使わないか決めるパートを分けて考えることにする。 X≦Yとなるペア(X,Y)だけを考えても一般性を損なわないので、それを全て列挙することを考える。実は、各数に対してペアとして考える数は1つ(2べきを達成する最小の正整数)で、それで全てのペアを列挙できる。

なんで1つを考慮するだけでいいかを説明する。整数Yとそれとペアになるべき整数 X = 2k - Y (Y < 2k ≦ 2Y)を考えるとすると、選び方からX≦Yなので(X,Y)はペアになりうる。 一方、2番目に小さいX' = 2k+1 - Yもペア候補ではあるが、X' > Yとなってしまうため、考えなくて良い。

Yが大きい順にペア(X,Y)を使うか使わないか決定していくと最大数が求まる。 このとき、ペア(X,Y) が使えるなら必ず使って損はない。というのは以下の理由に基づく。

  • 使わなかったらそのYは未来永劫使われないので損をする可能性がある。
  • 使うとして、Xを含む別のペア(X,Z)を作るのを妨げてしまう可能性はあるが、それによる損失は高々1つの別のペア(X,Z)が作れなくなるだけなので、少なくとも損はしない。

C

問題: 文字列{Si}がN(≦2*105)コある。S1 < S2 < ... < Snという関係が成り立っている。i番目の文字列の長さAiのみを知っているとき、文字列に使われる文字の種類数として最小としてあり得るのは何か。

解法: 二分探索 + シミュレーション

文字の種類数の最小は、二分探索で見つけます。 なので、二分探索の中では、種類数kで、S1, ..., Snが存在するかどうかを判定すれば良い。

存在するかどうかを判定するのはシミュレーションを用いれば良い。 つまりできるだけ辞書順で小さい文字列を貪欲に割り当てて行けば良い。

これは以下のアルゴリズムで行える。n種類の文字からなるアルファベットを{0, 1, 2, ..., n-1}と表すことにする。 明らかに、S_1は0をA_1コ繰り返したものを考えれば良い。 i ≧ 2 に対してどうするか考える。

  • A{i-1} < A_i のとき、S_iをS{i-1}の末尾に0を必要数足したものにすれば良い。
  • A_{i-1} ≧ A_i のとき、S_iから必要数末尾を削った後、末尾の文字を一つアルファベット順で大きいものにしてあげればよい。もしその文字がアルファベット順で最大なときは、繰り上がりが発生するのでそれをシミュレーションする。このシミュレーションは連長圧縮をしておくことで文字種類数が2以上のときは愚直にやっても高速に動作する。なぜならO(log N)桁くらいしか繰り上がりの影響を受けないため。

もし繰り上がりに失敗して長さA_iが達成できなくなったらシミュレーションは失敗、そうでなければ成功となる。

文字種類数が1のケースだが、これはA1 < A2 < ... < Anのときかつそのときに限り達成できる。

D

誤読

E

読んでない

F

読んでない

感想

書いて思ったんですけどやっぱり言語だめですね・・・