2018/8 solved(2)
8/17
8/18
辞書順最小→貪欲(submission)。
同じグループにできるのは、正負が一致かつ素因数の個数の偶奇が一致するものが同じグループにすることができる。ただし、0だけは特別扱いする必要があり(0はどのグループに入っても差し支えないので)、それ以外のグループがいくつできるかを全部の部分列に対してで試す(始点iを決めて、そこから右に動かしながら要素を追加していく)。この全探索部分に余計なlogなどを載せたくないので、前計算として素因数分解したものをmapでID化しておくと計算量がちゃんと
で抑えられる(submission)。
残す人数を最大化したいと考えると、nから降順に貪欲に残していいかを考えることで、残す頂点n-k個を選ぶことができる。なぜなら、は
よりも大きいことを考慮すると、とにかく大きい方を残すほうが得になるからである。そして、残すと決めたときには、nまでのパス上の頂点を全部残さないといけないことになる。よって、nを根としてみなし、ダブリングで親を計算しておくことで、すでに残すうことを決めた頂点までの距離が
でわかる。これによって上から貪欲に残す頂点を決定できるので、自ずと消す頂点が決まる(submission)。
8/19
KUPC 2013 Virtual
8/20
まず桁数が違った場合は、できるだけ大きくすれば良いので簡単。同じ場合を考えると、先頭何文字までを一致させるかを全探索することにすると、各場合について貪欲に構成することができる(submission)。
8/21
まず、1つ閉路を見つける。するとその閉路の長さはn以下なので、そのどれかを削除して、そのグラフに対して閉路がないことを逐一チェックすればで間に合う(submission)。
8/22
non-working dayの区間をsetで管理することにする。追加するクエリの時は、その間の区間をマージしないといけないので、lower_boundでその区間のスタート地点を見つけて、全部eraseしてから新しい区間を追加する。削除するクエリの時は、同様にスタート地点を見つけて、逐次削除していく。ただ、端は残るかもしれないのでそこを全部消してしまわないように気をつける。このようなことをやると、1回のクエリ処理でたくさんアクセスしてヤバいんじゃないかと思えるが、クエリ全体を通して見ると、このような区間の追加や削除の回数はで抑えられているので、余計なところにアクセスしないように気をつけて実装すれば
になっている。実装の部分で結構悩んだが、やっぱり半開区間で管理するのが実装の見通しが良い。区間を併合するのが楽なように感じる(submission)。
8/23
その星で布教すると決めたら、その星の期間が終わるまでい続けても最適性は失われないのでそういう動きしかとらないことにすると、区間を終端でソートして、の配るdpができる(submission)。
8/24
8/25
RUPC 2016 day1 Virtual
Summer Festival Contest 2018 (Division 1)に参加
8/26
8/27
8/28
8/29
計算すべき値はペアに対して設定されているが、最小値と最大値に分離して考える。すると、各頂点に対して、この頂点が最大値/最小値になるようなパスはいくつあるか、を各頂点に対して数え上げていくことになる。最小値も最大値も同様に計算できるので、ここでは最大値について考えることにする。頂点にかかれている値が小さい方から順に数えていくことにすると、その頂点から順番に、サイズを管理できるUnionFindを利用しながら、そのパスを通過するようなパスの個数を数えていくことができる。具体的には、小さい方から順に処理するので、いま注目している頂点に対して隣接する頂点
が、すでに処理済みだった場合は
のほうが最大値になるので、まず、その
の連結成分と
のパスは
が最大値になる。また、隣接していてすでに処理済みである別の頂点
があった場合は、
を経由して
の連結成分へ伸びるようなパスも
で最大値を取るので、そのようなパスを全部考慮するには和を取って2乗してから2乗の和を引いて重複を除去すればよい。このようにして
で数え上げることができる。最小値も同様に、逆に大きい方から数えれば良い(submission)。
各a[i]について、それをに選んだときに適切な
がいくつあるかを数える。
に選ぶ数の桁次第で、
の位置がずれるので、桁ごとに分類して考える。すると、10のべき乗を計算しておくことで、
が来る位置と合わせて
での剰余がわかるので、
に来るべき値が決まる。この
に来る候補を、事前にmapなどで数えておけば、入力の数列は10桁以下なので、
で十分に間に合う(submission)。
8/30
8/31
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)。
こういうの嫌い...
