裏紙

ほぼ競プロ、たまに日記

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