2018/8 solved(1)
8/1
8/2
まず、lcmとgcdの関係から、xy = abが成り立ってないといけないが、これを満たすようなaの個数は約数の個数で抑えられており、それはlogで抑えられていると考えれば、xとyを素因数分解して、それぞれがもつ素因数をマージした情報を持っておき、あとはdfsで因数をどちらにどれくらい配るかの全探索をし、それが条件にあっているかどうかをチェックすれば良い(submission)。
Cの方が簡単じゃないか...?繰り返し二乗法と逆元がわかってれば解ける(submission)。
8/3
もし1が無かった時のことを考えると、積の方がすごいスピードで大きくなっていき、区間の長さがlognより大きいとこは見る意味がなくなってくるのが分かる。なので、連続している1をまとめて処理するようにすると、区間の左端を固定したときに試すべき右端が個に抑えられるので、
で計算できる(submission)。
8/4
あり得る操作の有向グラフを作って、dfsしながら、全部訪れられるところを始点にすれば良い(submission)。
8/5
連結成分ごとにチェックしていく。cycleであるかの判定は、各頂点の次数が2であることを確かめれば十分(このとき、cycle以外作れないので)(submission)。
値が小さい方から埋めていくDPをする。復元も必要なので、親のindexも持っておくと良い。遷移に関しては、隣接している値に注目して、尺取りっぽく更新していくことができる(submission)。
sを使ったかどうかのフラグでdpしたくなるが、それだとsを使わずに自然発生したものと重複して数え上げてしまうので、それを避けて1文字ずつ決めていく方針にする。そうすると、今sと何文字目まで一致しているかという状態が更に必要になる。こうすると状態数がになる。遷移に関しては、2通りであり、前計算でこの先頭何文字が一致するかを求めておけば、このdpは
で計算できる(submission)。
8/6
UAPC2015Day2 Virtual
初心者の2年生も交えて3人チームで。Jは最初からtreapで殴ればよかったー。
8/7
8/8
拡張BFSを頑張る(submission)。
8/9
スタートからとゴールからのダイクストラで距離を求めておき、fsが低い順にクエリを処理していく。和を持つセグ木を用意しておいて、fgの方も条件を満たす頂点数を計算できる(submission)。
コストが低い辺から順に、UFで辺の端点2つをつないでいく。繋ぐ直前のそれぞれの連結成分の大きさの積が、全パスの中でそこがネックとなって現れる回数になる(submission)。
8/10
E1は制約が緩い版なのでまとめて解いた。各マスに対して、4方向にどれくらい伸ばせるかを独立に前計算しておくと、そのマスを中心としておけるstarのサイズは4方向のminになる。ここで、各マスからいちいち伸ばしていると間に合わないので、方向を固定して1つ手前の位置を注目して計算するdpをすることで前計算がでできる。おける場所が分かったら、その通りに置いてみて(この試し置きも愚直にやるとTLEする可能性があるので、横棒と縦棒に分けて累積和っぽくとる)、復元できているかをチェックする(submission)。
各数について、含まない部分列の個数を数えることにすると、間がどれくらい空いてるかに注目すればよく、この間は全体で個しかないので、間に合う(submission)。
両側探索。24回以下が保証されるので、23回以下でできるか探しに行く。メモしておくほうをスタートから11回分、dfsでゴールから12回分を探索する(submission)。
与えられた情報から、dpによって答えを前計算しておく(submission)。
8/11
ABC 105
Cむずかった。プラスとかマイナスを考えるのがややこしいので、マイナスになる項を反対側に持っていくと、下の桁から素直な貪欲ができるようになる。
8/12
dp[i][j] = うまか棒をi本、ふがしをj本を持ってるときのブタメソの個数のmaxを持ちながら1人ずつ順番にどの交換をするかを遷移とするものを考える。このときに、順番にやっていくと後で辻褄を合わせることを考えないといけないが、それは遷移の途中で個数が負になることを許せば良い。最終的に2つのkeyであるiとjが0以上になっていれば、その中からmaxを見つけられる(submission)。
うまく探索する場所を減らしたいので、問題の性質に注目して減らせるとこを考える。まず、回す必要性についてだが、回す軸にスタートとゴールが両方乗っているような回転は無駄なので、考えない。また、ゴールだけが移動するような回転は、相対的に見ればスタートだけが移動するような回転と同じにみなせるので、ゴールは固定された位置にあるものだと考える。さて、そうなると回転させるタイミングは、始めにやろうと途中でやろうと基本的に関係ないことが分かるので、回転をスタート直後に済ませてしまい、そこから移動する、みたいな経路だけを考えれば良い。よって、スタート直後のアクションを全探索することを考える。ただし、軸がかぶっていると回せないので、一歩すれるという動作も考慮して、深さ6までのアクションを全探索した(submission)。
8/13
8/14
8/15
だめな方を数えるのが楽。xを根とみなして、各部分木のサイズをdfsで求めておけば、xを通ってから、yを通るようなパターンが何通りあるかは簡単にわかる(submission)。
8/16
タイプ2のクエリ(x,k,s)がややこしいので整理する。GCD(x,v)がkで割り切れる && v <= s-x なるvのなかで、x XOR v が最大となるようなvを既に(タイプ1のクエリによって)追加された値の中から見つける、ということになる。条件を満たすようなvを考えてみると、vはkの倍数であれば良いことがわかる(そもそもxがkの倍数出ない時は何を選んでもだめだが)。よってkの倍数の値だけの出現を管理するトライ木を作り、その木をdfsすることで条件を満たすvを見つけることができる。基本的にはxと反対方向に進むが、そっちに進むと詰んでしまうときは逆に進む。そのために、進んだ方向に関して「こっちに進んだら最低でもこの値を取らないといけなくなる」という値を持っておけば、それとs-xを比較することで判断ができる。約数の個数はだいたいlogで抑えられるので、追加クエリに関してもlogの2乗くらいで対応できる(空間計算量も同様)(submission)。
解説を見た。言われてみればそうだなあという感じのdpだった。組み合わせを前計算しておくことでオーダーを落とす(submission)。
こういうの嫌い...
2018/7 solved(2)
7/17
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してしまうが、差分位置だけコピーするようにすれば、クエリ全体を通してでコピークエリを処理することができる(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だった(でもその貪欲本当に正しいのかわからない)。
