CF 749 E - Inversions After Shuffle
問題
問題概要
から
までの数を並べた長さ
の順列がある。1回だけ以下の操作を行う:
全ての区間個のうち、区間(
から
)をランダムに選ぶ。そして、その区間の長さを
とし、その区間に対して、シャッフルを行う(つまり、
通りの並び替え方のうち、ランダムに1つ選ぶ)。
この操作の後にできあがる数列の反点数の期待値を求めよ。
アイデア
以下、配列は問題に従って1-indexで考えることにする。
考えるべき区間の選び方は個あるわけなので、これが分母になってくるとして考えていくことにする。
考察にあたり、もう一つ重要なことはただ単に順列の全体をシャッフルした時の反転数はということである。これは、1つの配列に対して、それをreverseしたような配列を考えてみると、その2つの配列の反点数の和が
になっており、そのようなreverseしたもののpairが全ての順列に対して見つかるので、それを2で割ったものということである。
上記の考えから、この問題において求めるべき値は与えられる順列の区間
]の反点数を
とおくと、次のようになる:
分子がなぜこのような形になるのか、区間 ]をシャッフルした後に、その順列全体の反点数がどのように変化するかを考える。すると、2つのindexに対して、反点数に変化があるかどうかは、どちらかのindexがこのシャッフルの区間の外ならその順番が入れ替わることはないので反点数は変化しないわけである。つまり、反点数が変化しうるのはこの区間内についてのみ注目すればいいということになる。そして、前述の通り長さ
の順列をシャッフルした時の反点数の期待値は
であるから、その元の反点数を引いてその期待値を足しているという式の形になっている。
さて、ただこれを愚直に計算するのでは間に合わない。分母はなので、分子をどうするか考えてみると、全体の反点数についてはBITなどをつかうことによって
で計算が可能であり、この分数についても、
に着目すれば
種類の値がそれぞれ何回ずつ現れるのかが簡単にわかるので
で計算できる。
そして残るはの計算である。以下で、これについて考える。
いま、をまとめて計算することを考えてみる。そのために、
を
から
の方向に動かしながら考えていく。そして、配列
を考えて、
とする。
さて、このの値について計算したいが、この値は
を使って表すことが出来る。それは区間
]を
]と
]に分けて考えることが出来るからである。
そして、いまは始点を固定しているので、この区間に対して例えば番目の値は1つの区間(
])に入り得る。一方で、
番目の値に注目すると2つの区間(
]と
])に入る。つまり、この2つの区間でこの反転がカウントされる。このように
を固定したときに
番目の値は全部で
個の区間に入ってくることになる。
つまり、を計算するときに、
なる
を考えて、その中で
となっている位置のみに対してこの上記の反点数カウントをすればよいことになる。これは、まさにBITによって実現される。
(自分の用意してたBITにちょっとバグがあってそれに気づいて直すまでに時間かかった...このBITで何問か通してたはずなんだけど、見つかってよかった)
実装(C++)
続きを読む2016/12 solved(2)
12/17
Wikipediaの画像ながめて、正方形の周上に移動できるのかーってなったときに、最大のdの内側に入ってるなら2回でどこでもいけるのではという事に気づいてからは場合分けで一瞬だった...
左から順に見て、右から順に見て、何人避難できるかを最大更新していく。
クラスカル法でMSTを構成していき、使った辺のうちの中央値を答えればいい。
とりあえず1日1枚以上は食べるとすると、N日以内に食べ終わる。なので、dp[i][j] = i日目までに合計j枚食べる方法の順列の個数をで計算できる。あとは、その正の枚数食べるところがi日あったら、残りのD-i日は0枚ということになり、それをどこに入れていくかは重複組合せによって計算出来る。
まず何桁の数字の位置で来るのかを計算し、その分をnから引いておく。更に、そこから桁数dが決まるとn/dだけ進めれば直前にたどり着けるので、あとはstringのくっつけてsubstrで出した。
12/18
トポロジカルソートしてから、その順番に辺を見ていって最大値更新をしていくDPを先頭からと、後ろからとやっておけばよい。トポロジカルソートはDFSによってで出来る。
まず、1からxまでのFizzBuzz stringの長さがs未満になる限界のxを二分探索によって探すことが出来る。そして、そこからstringを構成してsubstrすればいい。
二部マッチングで解いた。b[i]とr[j]の間に辺をはれるかどうかの判定は、事前に約数列挙をしておけばO(約数の個数)でできる。
dp[i] = i番目の要素が終端になるときの単調増加部分列を考えたときに、合計の荷物の重さの最大値とすると、で更新していくことが出来る。これはSegtreeを利用して、xの小さい順に更新していくようにすることで
で実現出来る。
12/19
隣接しているスライム同士に辺を張り、連結している個数を調べる。連結が1つだけならn-1が答えになり、2つ以上ある時は壁に寄せることになるので四方のどの壁に寄せるのが良いかを4通り試した。
コストが大きい方から柱を作っていく。閉路ができてしまってはいけないが、できてしまうかどうかはUnion-Findによって検知することが出来るので、結局出来上がるのは木の形になる。
暗い部屋に人がいるかの状態を表すbitDPでBFSで解いた。
12/20
8!通り試す。その際に、回転して同じ状態になりうる24通りを試して、その順列の中で一番小さいもので正規化しておいて種類をカウントすると楽。
BFSすると、根からの距離と訪れる頂点の順番が分かる。それとLCAを利用して、全体の移動にかかる距離を高速に計算出来る。
12/21
(最後に訪れた店,今までに訪れた店の集合)を状態に持ちbitDPをする。この遷移のための準備として、スタート地点と、各店をスタート地点としてダイクストラで最短距離を求めておき、各頂点間の最短距離を予め計算しておく。
取りうる値が0~255までなので、変数に関して全探索をしてその変数を含む計算結果がどのように取りうる値を変化させるかを計算することができる。除算のときに、変数が0を取りうるならerrorを返す。
12/22
答えにたどり着く方法が1通りのみと決まっているので、その都度行ける3通りを試して行き止まりになったらやめる単純な枝刈りで十分間に合う。
12/23
まずy座標の種類を列挙してソートしておき、平面走査でx座標が小さい順に見ていく。xが窓枠の左に来るとして、最大値を返すsegtreeで、i番目にy_iを枠の下側に来るようにした時の輝きの合計を保存するようにしておく。このような形にすると、区間に対するaddが必要になることが分かるので、いわゆるStarrySkyTreeを実装した。
12/24
Xmas Contest 2016 昼の部に参加
友達と一緒にゆるい感じでやった。ら、Aしかできなかった...Cずっと考えてたけど、から落ちず、辛かった。
12/25
使ってはいけない辺をsetで保存しておく。そして、まだ訪問していない頂点をsetで管理し、スタート地点からBFSしてまだ訪問してない頂点のsetに全探索して、行けるところは行ってsetから取り除くということをすると辺を張るのに失敗するのが回なので間に合うという、結構シンプルな考え方だった...グラフの直径を求めたりしようとしたけど、木じゃないとそういうのは厳しいっぽいし見当違いだった。
12/26
座標圧縮して、その区間ごとに何匹の魚がいるかを調べる。区間は個になり、区間ごとの判定は線形にできるので全体として
で間に合う。
どのカードを取り除くかを全探索してシミュレーションすれば良い。
距離ごとにシミュレーションしていく。確定する場合は2人と出て両方にいることが分かる時と、1人出るが片方は範囲外になっていている位置が確定するときがある。
100以下の素数を列挙すると25個ある。ただ、合成数かどうかを判定できればいいので50以下の素数を用意しとけば十分。ただ、その素数ごとに聞いていくだけだと9のように1種類しか素因数を持たないものの判定ができないで気をつける。
12/27
に対して
を満たす最大の整数
とすると、次に選ぶキューブの大きさは
か
のどちらかが最適であることがわかる(Editorialより)。そして、実験してみると最大でも個数の最大値は18なので、普通に再帰で全探索しても間に合う。
部分文字列にした時にどの文字列だったかわからなくなってしまうパターンを考えてみると、同じ文字の間が全部詰まってしまって 1つになるパターンなので、s[i]とs[j]の距離がK以下で同じ文字のところがあれば不定の例を作れる。それ以外はOK。
Aを何個使うかを全探索することにすると、それに応じて最適なBの配置の方法が決まる。そうして作られたもののうち、長さがN以下になるものがあればそれを答えればよい。
12/28
答えを二分探索していく。そして、高さmの建物が立てられるかの判定は、長さNの配列を用意しておけば簡単に判定できる。
まず、現れる順番は無視していいので、ソートしておく。そして、1つの基準点を作り、その値を動かさないようにしてその前後の値をconsecutiveになるように調節する全探索をすればいい。これで、で実現できる。
まず、滞在の終わりが早い順にソートしておき、前から順番に見ていく。i番目の人がまだspecial promotionの人と繋がっていない時、その人は繋がないといけないが、このときに最も選ぶべきものは「i番目の人をカバーできて、かつ滞在の終わりが遅い人」なので、後ろから見ていって見つかった人をspecial promotionする人に選ぶという貪欲で客の数に対して
でできる。
- [SRM 644 Div1 Easy - OkonomiyakiParty]
(Unrated回なのか、リンクがなかった)(はじめにそれを確認しておいて問題を選ぶべきと言う感じがある(これ何回やれば気が済むんだ))
お好み焼きのサイズでソートしておく。そうして、番目と
番目のサイズの差が
以下ならその間から
個を選ぶことにする。その組み合わせは、2次元配列を用意して事前に用意しておくことで全体は
で実現できる。
12/29
はじめに、それぞれの町を始点としたBFSをして、到達可能な範囲を調べておく()。そして、到達可能な町にはコスト
の有向辺を張る。すると、辺の個数は
個になるので、ダイクストラで間に合う。
Oの位置を基準に全探索する。Jの個数を前から累積和で持っておき、Iの個数を後ろからの累積和で持っておき、Jを先頭に置く場合・Iを最後尾に置く場合・Oを置く位置の全探索でで出来る。
dp[r][s][j] = r行目,s番目の石にいて、一行飛ばしのジャンプの回数がj回の時の最小コストを更新していくDP。行が増える方向にしか遷移しないので結構シンプル。
座標圧縮して個のグリッドに分ける。そして、BFSなどで連結成分の個数をカウントすれば良い。
dp[i][j] = 最後に切った位置i,今の合計の長さjのときにかかるコストの最小値を更新していく。愚直にやるとだが、遷移を上手く保存してまとめるようにすると1つオーダーを落とせる。
12/30
まずはショッピングモールからの距離をダイクストラで求めておく。その次に、辺を1つずつ見ていく。そのときに、辺の両端のダイクストラした最短距離の情報を見ながらどの位置に置くのが最適なのかは簡単な1次方程式を立てることで求めることが出来るので、その最大値を更新していけば良い。これで、全体でとなる。
まず、ダイクストラして始点からの距離を求めておく。すると、Xとして選ぶのはこのいずれかの頂点までの距離にするのが最適なのは明らか(中途半端な値にする意味がない)ので、Xとして選ぶ値は通りある。これを全探索していく。そのときに残る道の長さの合計がどれくらいになるのかというのは、まず、頂点をスタート地点からの距離順でソートしておくと、その道が撤去されるタイミングは端点のうち距離が大きい方がX以内になるタイミングなので、辺をこの端点のmaxをkeyにしてソートしておくと尺取的に
で計算していくことが出来る。
まず、全体で重さが1になると仮定して、各場所にいくらの錘が来るのかを分数で表して計算する。その伝播の方法は、トポロジカルソートで簡単にできる。そのあとで、錘を全部整数に直すために錘の分母のLCMを取って計算してやれば良い。
dp[i][j][IO] = 次に使えるのがsのi文字目,tのj文字目で末尾の文字がI/Oのときに作れる列車の長さの最大値を更新していく。
2周分の累積和をとっておき、1個目の切り込み位置を全探索する。そして、2個目はsum/3あたりに、3個目はsum*2/3あたりをlower_boundで見つけてチェックする。
まず普通にシミュレーションしておく。そして、そのシミュレーションの最中に、各辺でどれとどれを入れ替えているのかを保存しておく。その辺だけを除いた時、そのシャッフルが無効になってその2つの行き着く先が変わるので、横の棒を全探索してスコアを最小化する。
桁DPをする。(B以下の条件に合う数の個数) - (A以下の条件に合う数の個数) + (Aが条件に合うか)で求めた。
CF Good Bye 2016に参加
ABDの3完。Cはケアレスミスで落としてしまったっぽい...本当に反省。気持ちよく2016を締められなかった...
12/31
本当に僅かなミスだった...(ずっとdiv2にいたときでも、最後の1回の後にDiv1に上がりうることを考慮していなかった)
読み終わる時間を最小化したいというのが前提にあることに留意すると、読むのにかかる合計時間のうち、一番時間のかかる本が半分以上を占めているとどうしてもその2倍の時間読み切るのにかかってしまう。また、そうでなければ1人は1番時間のかかる本から読み始め、2,3,4,...と読み、もう1人は2番目に時間のかかる本から読み始めて、3,4,5,...と読んでいけば、nまで読み終わった後に1番時間のかかる本は読み終わっていることになっているのでそれを読むという方針を取ることで、隙間なく時間を詰めることが出来る。なので、この場合はちょうど読む合計+書く合計になる。
ただ、読むのにかかる合計時間のうち、一番時間のかかる本が半分以上を占めている時は、1人がその本を読んでいる間に、もう1人はそれ以外の本を全部読んでも時間を持て余すことになる。その空いている時間に書けるぶんの感想文を書いておくのを、最大時間を求めるためにDPする(dp[i][j] = iまで読んで、時間jぶんの感想文を書けるか)。jが大きくなりそうに見えるが、このDPをするにあたり、そもそも余る時間は一番時間のかかる本以下なので1000以下ということになり、間に合う。
それぞれのLPG stationからダイクストラする。
トポロジカルソートする。
