裏紙

ほぼ競プロ、たまに日記

2018/5 solved(1)

5/1

和と積と大小関係を情報に持ちながら桁dpする。積の部分は、大きい値になりうるけどsparseなのでmapで管理する(submission)。

各光源に対して、光を到達させるために取り除くべき風船を予め計算しておく。その条件は風船の表面が線分上にないことが条件となるので、風船が線分と最も近くなる点と遠くなる点の間に表面が入ってくるかどうか(半径との大小比較)で判定できる。あとは届かせたい光源を決め打ちした時に風船が何個取り除かれるかをbitsetのmergeによって判定している(submission)。

どの順番に布団を積んでいくかを考える時に、すでに使ったふとんを集合として最小コストをbitDPする。遷移を考える時に、遷移前と線維先の間にあるdに対してはどちらかを選ぶのが最適なので、そのタイミングでコストを計算すれば良い(submission)。

本題のdpをする前に2つのdpを前計算しておく。1つ目は、訪れる町の集合を決めた時に、市場からスタートしてまた市場に戻ってくるまでにかかる最小時間(巡回セールスマン問題のようにbitDPで解ける)、2つ目は、訪れる町の集合を決めた時に、訪れる町で変える商品の中で重さW以内で買い物をする時に得られる最大利益(これが個数制限なしナップザック問題として解ける)である。この2つを前計算しておけば、本題のdpは時間を重さ、利益を価値とした個数制限なしナップザック問題となるので、最後にこれもdpすると解ける(submission)。

5/2

最適なルートを考えると、その途中で通過する点として考慮すべきなのはスタート、ゴールと円と円の交点になる。それぞれの点のペアに対して、それを結ぶ線分が引けるかどうかをチェックする。この時のチェック方法に関して、今考えている区間の間にあるそれぞれの円と円の共通部分を通るかをチェックできれば良い。つまり、それは結ぼうとしている線分が、円と円の交点を2つ結んだ線分と交わるかどうかで判定ができる。ここまでできれば最短経路問題になる(submission)。

5/3

カード全体の並びを考えるのではなくて、ある1枚のカードが、x桁目にくるようなカードの並べ方が何通りあるかというのを数えて足していくという方針にした。カードに書いてある数は10000未満なので、たかだか4桁。カード枚数はn<=200なので、800桁で抑えられる。カードを桁数で分類して、そこから何枚ずつとって下側にくっつけるかでxが決定する。それぞれの桁のカードを何枚採用するか決めると、その選び方も組み合わせで高速に計算でき、1桁のカードは10枚、2桁のカードは90枚までしかないので、全通りを試してもパターン数が結構抑えられる。さらに、ここまでは1枚のカードについて、という考察を進めてきたが、結局注目しているそのカードの桁数を見ておけば組み合わせの個数は変わらないのでまとめて計算できる。そのカードより上側の組み合わせを計算する時に、0が一番上に来てしまわないように気をつける。ただ、それも全体から0が一番上に来るパターンを引いておけばいいので、苦ではない(submission)。

5/4

5/5

構文解析をしながら、文字列を復元していく。ただ、全部復元する必要はなく、x文字までで良いので、それ以上読みすぎないように注意する(submission)。

行列累乗で数え上げるけど、途中の障害物のある行は遷移行列が変わるので、それを上手く考慮しながら、障害物のない場所については高速化する(submission)。

点Sと点Tを両方内部に含んだり、どちらも含まない円を壁として作る意味はないので無視する。そうすると、残るのはSだけ含む円とTだけ含む円の2種類に分割できる。それぞれで、i番目の円を一番外側にするときに何重の壁が作れるかをDPする。これは、内側から外側の円に有向辺を張って、トポロジカル順にDPを更新していくことで求められる。最後に、求めたこの2つのDPを使って、その外壁と外壁がぶつからないかどうかをチェックして、最大値を更新していく(submission)。

5/6

5/7

連結成分が具体的にどのように構成されるかがイメージできなかったが、連結になる部分は全て連結になり、孤立点だけになるので、連結成分ができるときとできないときで分けて考えて良い(submission)。

5/8

Cが現れる位置を固定した時に、それを実現するA,B以下の数が何通りあるかを各桁について調べる。何通りになるかは、CとA,B該当する位置の部分列との大小関係で、その位置よりも大きい桁側と小さい桁側でどのような数が取れるかが決まってくる。また、Cが0のときに、これが一番上の桁になってしまわないように気をつける(leading zeroになってしまうので)(submission)。

まず、音程がジグザグになるように設置するのは折り返し部分が明らかに無駄なので、一番低い音をスタート地点として固定すると、そこから一番高い音まで単調増加で上がっていき、そこから単調減少で戻ってくると考えられる。そこで、その左右に今最後に何個目の音が置いてあるかを状態に持つDPをする。状態から、次に置く音は左と右のmax+1になるので(左か右のどちらかは直前に置いたものだから)、遷移はどちらに置くかの2通りになる。消費する精神力は、累積和で持っておけば、遷移が高速にできる(submission)。

5/9

水の量を決めると、それぞれの肥料の量が一意に定まる。コスト関数は、水の量Wに関して線形な式の和なので、三分探索出来る(submission)。

1マスずつ状況が進んでいくと考えると、dマス進んだ時に、ある方向を向いていないと行けないという条件がt個出来る。それをdpで進めていく。Uターンがダメなことと、チェックのタイミングでちょうど曲がっている時は曲がる前後の方向を考慮していいことに注意して実装する(submission)。

i個目の色を塗る時、かぶっていい頂点はたかだかi-1個(直前のi-1色からそれぞれ1つずつ)だけなので、答えは、sum(a)-10未満になることは絶対にない。また、aが大きければそれが必ず実現出来る。なので、そのかぶせる部分だけについて全探索をする。自分のコードはバックトラックっぽく、i番目の色に塗る頂点のj個目にどれを含むかというのを各色から1つずつしかもってこれないというのを考慮しながらチェックしている(submission)。

長方形の周を数直線のように見なすと、1人が見ることの出来る範囲はひとつの区間として表せる。更に時計を置く場所の候補は、中途半端な位置に置くことは考えなくて良いので区間の端に置くことだけを考えれば良い。この問題は区間が端同士がつながっているのでややこしいが、端点の中からとりあえず1つ時計を置く場所を決めると、そこをまたがるような区間を除外することが出来るので、そこを始点とする区間スケジューリングとして考えることが出来る。あとは、残った区間で、区間の終わりが一番早いものを貪欲に取っていくということをする(submission)。

座圧すると、O(n^2)個の領域になるので、それぞれに対して、窓の内部で、カーテンの外部であるかを判定すれば良い(submission)。

5/10

5/11

まず多角形のペアについて、隣接しているかを愚直にチェックする(共有する辺があるかどうかを2重ループでチェックしている)。その結果、国同士の隣接関係を求めることができ、国の数は10以下なので、色を決めていくdfsをする。だいたい10!通りくらいか(submission)。

5/12

5/13

n個のsuffixのmod qの値を持っておくと、部分列の末尾がi桁目になるようなqの倍数がいくつあるかを引き算をして10^xで割ることで求めることが出来るので、これらの値をmapなどで管理しながら高速に数え上げることが出来るが、qが2と5のときは10で割るということをする時にそれ自体がqで割り切れて正しく数えられないので、別の方針を取る。幸い、2の倍数、5の倍数の判定は末尾の桁にのみ注目すればいいので、O(n)で出来る(submission)。

Asia Singapore 2015 Virtual

2人で組んで7完だった。かなりいい感じに時間を使うことが出来たけど、現地は9完maxで、あと1問は解きたかった(result(WUmember2))。

5/14

5/15

連絡先の関係を有向グラフで表すと、強連結成分内は、その中で少なくとも誰か一人が起きれば全員が起きられることになる。さらに、SCCしたあとのDAG上で、入ってくる辺がないような連結成分の人たちが起きられれば全員起きられることになるので、そのようなグループが全部起きられる確率を求めれば良い(submission)。

5/16

答えを二分探索する。答えをdで固定した時、いずれかの辺からはd離れている位置にあるはずであるから、もとの辺をdだけ移動させた線分を用意して、その線分同士の交点を候補とし、それが実際に条件を満たしているかをチェックする。epsを厳しくしすぎていて発生していたバグに気づくのにかなり時間かけてしまった、、(submission)

dp[フィールドの状態mask][車がある場所] = 最小コストを、ルールに従ってBFSしながら計算する。これだと一見間に合わなさそうに見えるが、全状態に到達するわけではないので、探索はそこまで重くない(submission)。

想定というか、多くの人は辺が取り除かれていなかったら2wの周期があることに注目して、もし取り除かれているところにぶつからなければ一気に2wぶんさかのぼる、ということをやると多分O(H+N)くらいでできるんだろうなあ、 という感じだったけど、自分はTreapで殴った。方針としては、まず、列を奇数番目と偶数番目の2つの列に分ける。そうすると、1段進める走査が、区間同士のswapになる。そして、棒が消されている箇所はn個しかないので、このswapはH+N回だけ発生するので、間に合う(submission)。