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)。
こういうの嫌い...
