裏紙

ほぼ競プロ、たまに日記

2018/3 solved(2)

3/16

HL分解を使って解く。そこよりもどういうSegmentTreeを作るかに時間がかかった。区間Addをするが、そのAddに頂点ごとに異なる係数がかかるので、一様にAddできない、どうしようってなった。ただ、区間sumを求める分には、区間全体にAddされるものは係数の和全部をかけて区間に足しておけば良いので、予め累積和を計算しておくことで、その区間に実際に足される値が何なのかが分かる。子に伝播させる時も同様のことを考えれば良い(submission)。

状態数が[tex:174]以下で抑えられるから、サイクルが見つかる(submission)。

マスの数は100個以下なので、確率の遷移行列を作って、t秒後の遷移行列を繰り返し自乗法で求めることが出来る(submission)。

3/17

コンテストに参加できるのはある連続した長さf-sのtimezoneにいる人の区間になることが分かる。あらかじめ累積和を計算しておいてから、どのtimezoneで開催すればよいかを線形に計算でき、あとは、その最大値を取れる時間を答えるべきtimezoneに変換してやれば良い(submission)。

同じindexごとに見ていくと、文字が異なる位置は、なんらかの呪文をつかって同じにしないと行けない箇所ということになる。アルファベットを頂点にして、このような同じindexでも字が異なる位置に辺をはると、それぞれの連結成分で木を構成するように取るように呪文を買うのが最適で有ることが分かるので、UFをしながら買う呪文を決めていくことが出来る(submission)。

3/18

subsetとしてi個の要素を選ぶ時に、目的関数を最大化するためには選ぶべきものは最大値と小さい方からi-1個を選ぶのが最適であることが分かる。なので、何個選ぶときが最適であるかを求める必要があるが、目的関数fは、f(i+1)-f(i)を計算してみて、更に分子の変化量を計算してみると分子の変化量が単調減少であることが分かるので、fが凸関数であることが分かる。よって、最大値となるiを三分探索できる。追加される数が、クエリ全体を通して単調増加であるので、累積和をとっておくことでfをO(1)で計算できる(submission)。

各インターバルで、ひっくり返す回数は2回以下しか考える必要がない(それ以上ひっくり返すのは無駄で、2回以下になるようにまとめることが出来る)。そこで、dp[i][j][2] = i番目のインターバルに注目,表をj秒焼いた,いま表/裏を焼いている という状態に到達するためのひっくり返す回数のmin を計算する。1回ひっくり返すのと2回ひっくり返すのがスライド最小値の形に帰着するので、全体でO(NK)でこのdpは計算できる(submission)。

NWERC 2015 Virtual

dayamaと2人でやった。Dいいところまで考察してたのに肝心なとこを見落としていた。

dp[i] = i行のプログラムに対してバグを見つけるための最悪時間の最小値を持つようにすると、何個printを仕込むかで遷移が作ることができる。printを均等に割り振るようにするので、j個仕込んだ時に、i行のプログラムはi/jの切り上げの行数になる。という遷移を作ると、あとはただ再帰すればよく、再帰を呼ぶたびに少なくとも毎回2以上で割られるので実際に呼び出されるのはO(logn)箇所しかないことが分かる(submission)。

3/19

まず、他の区間を内包できるような区間を除外して考える。すると、残った区間を始点でソートすると終点も必ず昇順になっている(もし、降順になっている箇所が存在するとしたら、そこで内包関係が成立するのでそのような区間は除外される)。始点にも終点にも単調性ができたので、これらの区間のみでまずはdp[i][j] := i番目の区間以降に注目、これまでにj個の機械に割り当て終了という状態の時のmaxとすると、次の機械に割り当てるのはi~k番目の区間(連続した区間のみを考えれば良い。それが最適なので)という遷移を考えられる。よって、この遷移はO(n^2 p)で完了する。残りの区間についてだが、まだp個埋まりきっていない場合にはまず1人ずつ時間が長いやつを割り当てていけば良い。それでも余ったら、適切な位置に割り当てること(それを内包するところ)によって、稼働時間を損なわずに割り当てることが出来る。区間を割り当てる時に、内包する区間を除外すると両端点に単調性が出て割り当ての順序が決まってDPできるという面白い問題だった(submission)。

壁が8個までしかないので、階乗を回してどの順番でボールを壁に衝突させるかを決めて、シミュレーションして実際に穴にたどり着けるかを見ていく。壁に衝突させる順番を決めると、逆順で穴を壁に対して線対称の位置に移すと、最初に打ち出すべき方向が決まるので、あとはその打ち出す方向に打ち出して、ちゃんと決めた順番で壁に衝突してくれるかをチェックしていけばよい。方向を決めて打ち出した時に、どの壁に最初に衝突するかは、線分と直線の交差判定 → 交点の導出 → 交点までの距離のminという流れで見つけている。「線分と直線の交差判定」で、始点から打ち出す方向の反対側にも交差判定が発生してしまうので、実際に交点を求めた後にccwがどうなっているかをチェックして反対側に無いことを確認している。シミュレーションは二重ループを回す愚直なものだが、十分に間に合う(submission)。

pipeが交差していると、どちらかにしかrobotを派遣できないが、そのintersectionを掃除するためにはどちらかのpipeからrobotを出さないといけない。すると、パイプを頂点にして、intersectionに辺を張ったグラフを考えると、「全てのintersectionを通過」→「全ての辺について、どちらかの端点は採用されてないといけない」と言い換えることができ、このような頂点の選び方(ここではロボットを送るpipeに対応)は、二部グラフであれば片側の頂点グループを採用すれば良いので可能である。逆に二部グラフでなければ、奇数長の閉路があることになるので、閉路のどこかで必ず矛盾が生じてしまう。よって、intersectionに辺をはったグラフに対して、二部グラフ判定をすれば良い(submission)。

3/20

k=1がコーナーなので注意。あとは効率の良いシミュレーションをすれば良い。具体的にはkで割り切れる時は、実際にkで割った値まで引き算で行くのか割り算で行くのかの試し、そうじゃない時はkの倍数になるように引き算をまとめてする(submission)。

初めて文字が変わるべき位置は、後ろから見ていくと見つけることができ、それより前は一致させてその位置は1つ大きい文字を選んで、それ以降は最小の文字を取り続ければ良い(submission)。

本当にシミュレーションするだけ。何でこの位置にあるのか...

考察すると、partitionは1個かc個しか必要ないことが分かる。c個未満の区間は、結局1つも除外されないので、1個ずつのpartitionにしてしまっても構わないことになる。逆に、c個より多いpartitionは、区間が大きくなるほど、小さい値が入ってくる可能性が上がるので、全体のsumが大きくなってしまいうるので、c個より増やす意味もない。ここまで考察できれば、累積和と、区間の最小値を持ちながらdpすることが出来る(submission)。

3/21

3/22

imulan.hatenablog.jp

laptopと中心を結んだ直線との交点と、laptopのある位置を直径にした円が条件を満たす最大の円である。 laptopが円の外にあるときや、laptopが円の中心と一致する時に注意(submission)。

3/23

dp[i][j]でi番目まで見た,aがbよりも既に辞書順で大きいことが確定しているか否かで数え上げる。遷移は、数の大小関係に注目すればいいので、どの数を選ぶかではなく、相対的な大小関係のみを考えれば良いので3種類に分けられる(1つは遷移する必要ないけど)(submission)。

最初、Grundy数をdpしてO(NK)で求められるかと思ったけど、TLEしたので、よく中身を見たらK+1周期になっていたので書き換えた。やっぱり実験が正義なのか...?

3/24

入力が全て乱数で与えられることを利用して、値をバケットに分割して持っておくと、各バケットの中に値が入る個数がそんなに多くならないので、累積和+バケット内愚直にチェックで間に合う。こういう考察はなかなかできない...(submission)。

+と-の少ないほうが100以下という制約に注目すると、その少ない方の配置をどうするか考えながら、余った場所はもう片方を埋めるというふうに考えると、式を木構造のように見なして左と右の部分木にどれくらい少ない側の演算子を割り振るかを決めながらdfsしていけば良い。演算子の数は、文字列の長さが10000以下だが、演算子が入るたびに括弧や数字も描かなきゃいけないので実際には3000個にも満たないくらいになる。部分木の計算結果のmaxとminの両方を渡しながらdfsすれば計算結果のmaxを計算することが出来る(submission)。

3/25

RUPC 2016 Day2 Virtual

Iの幾何は方針間違ってなかったのになせかバグってて終了した...難易度もちょうどよく、おもしろかった。

線を引いて、どの円を通過したかをbitDPで計算する。どういう線を引くかについては、考察をすると2円の共通接線のみを考えればよいことに気づく。2円の共通接線のライブラリがバグってて、とりあえず通せたけど、見直さないといけないsubmission

ARC 093に参加

CDの2完。Eはなんとなく考察してたけど、結局詰めきれなかった...

3/26

共通接線チェックしたくて解いたけど、この問題ではバグらなかったし、あの問題のmainに欠陥があるのかもしれない(submission)。

3/27

Ritsumeikan University Competitive Programming Camp 2018 Day 2に参加

オンラインで大学の人とチームを組んで参加。チームとしてかなりいい動きができて良かった。

3/28

Ritsumeikan University Competitive Programming Camp 2018 Day 3に参加

WAの数で1位のがしたのが悲しい...(自分のせい)。

3/29

imulan.hatenablog.jp

3/30

条件がパッと見だとややこしいが、g,hについてはg(b_i ) = h(b_i )が成り立っていると見ると、数列bの中にはなくて、aにはある値でg,hを好きにいじることが出来るので、そのような値が見つかれば反例が存在することになる(submission)。

mapでそれぞれ前側から数えた時と後側から数えた時の個数をカウントする。setに要素数が異なる値が何かを持つようにして、setが空なら一致という判定方針にすると、1個要素を増やした時に、setの更新は今注目してる2つの箇所しか更新する必要がないので十分間に合う(submission)。

DPする。左から決めていくことを考えて、右端をどこにするかを全通り試す遷移をする(submission)。

最終的に完成する最小距離の最短経路を考えると、a_i , b_i , c_iから2つ以上選ばれているようなものは存在しないので、結局3種類とも全部張ったグラフで最短経路を求めれば、条件を満たすようにパスを完成させることが出来る(submission)。

桁dpをする。必要な状態は、dp[注目している桁][n以下が確定しているか][今注目している桁の手前がどうなっているか][既にごちうさ数は登場しているか]となる。「今注目している桁の手前がどうなっているか」という部分に関しては、手前4桁の状態をそのまま持っていてもいいのだが、その状態は5種類にまとめることが出来る(詳しくは提出を参照)(submission)。

3/31

区間更新と区間クエリなので、遅延セグ木を使うことを考えたのだが、はじめi番目には「i階からスタートした時にどこまで登れるか」をmaxをとりながら更新しようとしたのだが、エレベーターの建設が2つ来る時にうまく情報をマージすることができなくて悩んだ。そこで、持つ情報を変えて、i番目には「i階からi+1階に行けるかどうか」というフラグを管理することにした。すると、質問クエリにはANDで問い合わせることで答えることが出来る(submission)。

とりあえず辺のコストをいじる時は必ず0にすることにすると、あとでそれ以上には調節できる。(今いる頂点,いじった辺の個数)の拡張ダイクストラをして、そのときの最小コストを求める。初めてc以下になる箇所が必要な変更箇所の最小に一致する。いじる辺の個数は、最短経路に思いを馳せると頂点の個数以下であることが分かるのでこの拡張ダイクストラは間に合う(submission)。

今いる場所、フロア、スイッチの稼働状況を頂点にしてBFSした。かなりややこしい実装になりそうだけど、結構綺麗にかけたので満足(submission)。

ルートが決まっていて、障害物と取らなければ行けない距離は単調増加なので(R=hで関数が切り替わるが)、玉の大きさを二分探索出来る。線分と線分の距離で障害物と玉の距離を判定するが、sampleにもある通り、スタートもゴールも障害物の中に入ってしまっているパターンに注意(submission)。