裏紙

ほぼ競プロ、たまに日記

2018/7 solved(2)

7/17

imulan.hatenablog.jp

7/18

1が自由に動けて、0と2の順序はどう頑張っても入れ替えられないことに注目すれば、2の後に来る0を境目として0...01...12...2のような文字列が繰り返されることが分かるが、1だけは前に持ってくる事ができるので0...01...12...20...02...200...02...2のような形が最適になる(submission)。

xの部分はどこに置こうが関係ない。dの部分は、真ん中に置けば最小化できて、端におけば最大化できるので、正負によって使い分ける。あとは誤差に注意。最後の直前まで整数型で計算できる(submission)。

グラフが連結じゃないといけないので、とりあえず全頂点を1と繋ぐ。あとは、単純な二重ループを回してgcdが1になるところに辺を張って、m本になったら止めるというのをやると間に合う。二重ループなのでTLEしそうに見えるが、約数の個数を考えるとlogぐらいで抑えられているはずだから、辺をはるのに失敗するのがその回数で、m回成功すれば終わるので間に合うっていうやつ(submission)。

すべての区間について、何回現れるかが数えられれば良いが、端にあるか否かと、区間の長さによって回数を決定することができるので、2のべき乗を予め計算しておけば高速に計算できる(submission)。

7/19

上位k個を貪欲に取ることができるので、いい感じに区間に分割する。

7/20

尺取りっぽく、左を1つ進めるたびに右から動かしていけば良い。

4箇所に注目して、条件を書き出す(submission)。

DFSをして、オイラーツアーのような配列を得ておくと、クエリ(u,k)に対してこの配列のuがある位置のk-1個右を見ればいいことが分かる。ただ、それが部分木に入ってないと行けないので、DFSと同時に部分木のサイズも計算しておく(submission)。

移動回数を考えると、(n+m-2)回なので、両側探索を考えると、両側とも深さ20以下のdfsに抑えることができる(submission)。

最大値の最小化→二分探索を考える。二分探索をすることを考えると、店の配置についてこのペアで設置してはダメ、という条件がいくつか生えてくるので、これを2-SATによって解けるかどうかを判定する問題にできる。あとは、店から店に移動するためにかかる距離を前計算しておけばよいことになるが、まずは工場を全部巡回するのにかかる距離をbitDPによって求める。あとは、スタート地点とゴール地点を全探索して店i→工場start→工場goal→店jが最短になるようなものが店iからjにいくのに向上を全部回って移動するときの最短距離になる(submission)。

まず、ペアが存在するものだけで回文を作っていく。ペアが存在するものを辞書順最小にとっていく。それで、余ったものの中から中心になれるものがあればその中で辞書順最小のものを選べば良い(submission)。

連続して上昇したり、連続して下降する部分はどうしても指をまたげないので、その連続するぶんだけ指が必要になる。なので、それが最長になる部分を見つければ良い。はじめに、連続で現れる同じ値について処理しておき(c++vectorのuniqueについて調べるとよい)、差分に注目して連続する部分を尺取りっぽく数えていけば良い(submission)。

7/21

コピークエリが来たときに、いちいち全コピーしてるとTLEしてしまうが、差分位置だけコピーするようにすれば、クエリ全体を通してO(N+Q)でコピークエリを処理することができる(submission)。

2016 ACM ICPC Asia Nha Trang Regional Contest Virtual

7/22

7/23

7/24

配列dを陽に持ちながらdfsしていく。そのときに、子からもらってきたdたちを合成する操作を考えると、すべて足し上げて先頭に自分が増える(新しい要素1を追加する)ということをやっているので、ひっくり返して持てば良さそうな気分になる。そうすると、vectorで実装すればpush_backをするだけという単純な操作になる。あとは、2つのdをマージするときに、配列のサイズが大きい方に小さい方をマージするようにする(マージテク)を利用すれば、間に合う(submission)。

7/25

文字と文字の集合の二部マッチングのフローグラフを作って、前の方から貪欲にフローを押し戻しながら文字を決定していくのが想定解として書いてあったが、Hallの定理を利用しても解けると書いてあったのでそっちを書いてみた。基本的には前から順に貪欲に使えるかどうかの判定をしていく。その判定の部分で、Hallの定理を利用して全部分集合に対してHallの定理が成り立っているかをチェックしている。文字がabcdefの6種類なので、その空でない部分集合すべてに対して、文字の集合へのマッチングがそれ以上の個数存在していればいいことになる。この数え上げの部分で、繋ぐことのできないほうを数えることにすると、高速ゼータ変換っぽいことをやって部分集合を数えておいて、bit反転したindexの部分を参照すると個数を数えることができてチェックできる(submission)。

答えを二分探索できる。

7/26

7/27

左から、前1列の状態を持ってdpしていく(submission)。

桁dpをしていけば良い。現れてる数字は1回以上使わないといけないのと、0が先頭にあってはいけないことに注意(submission)。

7/28

条件を満たすように、4個以上設置するのはどう頑張っても無理そうだということに気づけば、3個おけるか、2個おけるかを順にチェックすれば良いことになる(submission)。

7/29

傘を複数個同時に持ち歩くのに意味はない(一番軽いやつだけ持ってればいい)ので、dp[i][j] = 今iにいて、j番目に重い傘を持っているというdpを計算する。遷移は、傘を持ち変える、捨てるを考慮した後に、1マス進むという形になっている(submission)。

下2桁が25,50,75,00になればいいので、どれにするかを決め打ちすれば貪欲にswapしていくことができるのだが、その過程で先頭に0が来てしまうのがめんどくさすぎる。なので、予め先頭に持っていく桁も決め打ちしておき(もうそれはいじってはいけない)、そこからシミュレーションを始めることでそれを回避できる(submission)。

Codeforces Round #481 (Div. 3) Virtual

最終問、一瞬でフローを思いついてしまったから書いたけど、解説はgreedyだった(でもその貪欲本当に正しいのかわからない)。

7/30

7/31

CF 1004 F - Sonya and Bitwise OR

問題

Problem - F - Codeforces

問題概要

はじめ、長さnの数列aと整数xが与えられる。次のようなクエリを考える:

  • クエリ1 (i,y) : a_i yに変更する。
  • クエリ2 (l,r) :  l \le L \le R \le rを満たすpair(L,R)について、数列aにおける区間 [L,R] のすべての要素のbitwise ORを取ったときの値がx以上になるようににできるpair(L,R)の個数がいくつあるかを答える。

クエリ1と2が合計でm個与えられるので、順に処理せよ。

  •  1 \le n \le 10^5
  •  1 \le m \le 10^5
  •  0 \le a_i , x \lt 2^{20}

イデア

区間valueをその区間全体に対してbitwise ORを取ったときの値とし、「良い区間」というのを、その区間の全体のbitwise ORを取ったときに、xが部分として含まれているときにその区間が良い区間であると呼ぶことにする。

クエリ2についてどう高速に答えるかを考えたいが、その前に、まずはクエリ2に [ 1 , n ] が来た場合にどうするかを考える。

分割統治のアプローチを考えてみる。区間を、 [ 1 , \frac{n}{2} ]  [ \frac{n}{2} +1 , n ] に分割し、それぞれの区間内で完結するものについては再帰的にそちらで計算してもらうことにして、ここでは、区間の左端が前者にあり、右端が後者にあるものの中で、条件を満たしている区間が何個あるかを数えたい。

さて、区間の左端のindex iに対して、区間 [ i, \frac{n}{2} ] (いわゆるsuffix)のvalueを考えてみると、iが減っていくに従って立つビットの個数は単調増加になっているはずで、立ったビットが戻ることもないので、この\frac{n}{2}個の区間valueについて、現れる値の種類数はlog( MAX a_i)個しか無いということが分かる。

ということで、区間のマージを考えるときには、左側に関してはsuffix(各ビットごとに、現れてくる最も右の位置)が欲しくて、右側に関してはprefix(各ビットごとに。現れてくる最も左の位置)が欲しくなる。左側はiを減らす方向に動かすと考えると、右側も同様に、prefixを全部含んでいる状態からスタートして徐々に左に動いていく、みたいな感じで尺取りっぽくやれば区間をまたぐ良い区間の個数がO(log( MAX a_i))で数えることができる。

以上で考えていたことをそのままSegment Treeに乗せて処理することを考える。セグ木の1つのノードに乗せる必要があるものは、上でも述べたようにsuffixの情報とprefixの情報、あとは区間内で完結している答えの個数、の3つの情報である。上でも考察したように、このセグ木のノードとノードのmergeがO(log( MAX a_i))で実現できることが分かっている。つまり、クエリ2に対してO(logn \ * \ log( MAX a_i))で答えることができる、ということである。

では、残ったupdateに関してだが、点更新によって、ノードの更新をしなきゃいけない区間の個数というのは、セグ木の深さを考えるとO(logn)個なので、updateクエリもO(logn \ * \ log( MAX a_i))で実現できる。

以上より、全体の計算量はO( (n+m) \ *  logn \ * \ log( MAX a_i))となり、間に合う。

実装(C++)

続きを読む