裏紙

ほぼ競プロ、たまに日記

2018/4 solved(2)

4/16

2次元ロリハのverify(submission)。

4/17

4/18

初めに初期値を全部突っ込んでおいてdijkstraする。dijkstraが1頂点からの最短経路を求めるものだと思っているとこういうのは解けないし、いつも思いつくのに時間がかかってしまう...(submission)。

ある要素に注目して、その要素が足されるためにはどのような順列でなければいけないかを考えると、その要素以上の値は自分より前に現れていてはダメで、更に自分より後に自分より大きい値が1つ以上来てなければいけない。そのような順列が何通りあるかをどう数え上げるかというと、初めに自分とその要素以上の値を並べてしまってから、その要素未満の値をどのように間に入れるかを数えている(重複組合せで入れる位置を決めてから、順列で順番を決めている)(submission)。

4/19

4/20

imulan.hatenablog.jp

途中で対応が切れてしまわないように注意しながら、先にネストを貪欲に深くしていく。ここまでは考察できていたのだが、閉じていく時に関しては、反対側から同じようなことをすれば良いという発想がなかった...(submission)

4/21

Any finger appears at most once in S.を見落としていて何時間も溶かした。こうすると、枝分かれが無いので、各fingerを折る/折らないのは何通りかをdpすることで求める事ができる(submission)。

はじめ、構文解析をしながら行列累乗を考えたけど、1行シフトとかできないって絶望したが、n^2の要素を持つ写像と考えて、repetitionをダブリングで処理すれば十分高速であると考えて実装した。返ってくる関数は、初めにiにいたものは処理によってどこに行くかという行き先を示す関数になっており、この関数を合成するのは容易である(submission)。

4/22

2017-2018 ACM-ICPC Pacific Northwest Regional Contest (Div. 1) Virtual

週末バチャ。今回は2人チームで参加。途中までかなり調子が良かったのに、終盤どの問題の考察を詰めるかでどれも詰めきれなかったのが悔しい(直後に2問通した)。メンバーにどんなタイプをやってもらって、自分でどれを考察するのがいいかとかが少しずつ分かり始めた気がする。

削除クエリや挿入クエリを区間を分割していくクエリだと考えて、どの位置に入るかを線形で探してそこに対して処理を加えていくという素直なシミュレーションをすればよいが、どう実装するかでこの問題は難易度が変わると思う。ただクエリが2000個しか来ないので、区間に対して毎回前から順番に今何文字目を同時に管理しながら処理していく。はじめからあるもじを#として扱うと最終的にvectorの一致でプログラムの一致判定ができる。また、挿入して削除のような操作をすると、連結だった部分が一度切り離されて、また連結になるということがあるので、一致判定のために最後に結合しておくとよい(submission)。

4/23

直線を横になった状態から、縦になる状態まで動かしていく時に、注目する多角形との交差回数がどのように変化するかを考えると、2*2のセルのパターンで4通りが角の形になっていて、交差回数が変化することが分かる。あとは、その角がどの位置にあるかをチェックして、原点からの直線の傾きでソートすると訪れる順番が分かるので、その順に処理しながら、交差が最大になるところを見つければ良い(submission)。

高さを固定すると、各ロープが動ける領域は円の内部になる。この時に、n個の円に内包される領域があればその高さは実現可能である。また、この領域は高さに比例して小さくなっていくので、この高さを二分探索によって求めることを考える。すると、n個の円に内包される領域があるかどうかを判定しなければならないが、この領域を考えると、この領域の周上のどこかはある円とある円の交点になっているはずであるので、O(n^2)個の交点を候補として、その点で実現可能かをチェックすれば十分である(submission)。

平面走査で解いた。各x座標ごとに、直線で囲まれる上限と下限を取って累積和を取ってから実際にカバーされるマス目を数えている。実装方針によって難易度が変わりそう...(submission)。

4/24

半径Rの球を置くことを考えると、壁や針からどれくらい話さないといけないかが決まり、禁止される領域を図示することが出来る。残った領域に置くことで、条件を満たすように置くことができるわけだが、Rを大きくしていくとこの禁止される領域が大きくなっていくのが計算すると分かる。よって、Rを二分探索することを考え、この時に可能な領域が残っているかをチェックする。可能な領域と禁止される領域の境界を考えると、それは正方形の角か、正方形と円の交点か、円と円との交点が存在するので、これらを列挙して、これらの点で可能であるかをチェックすれば十分である。よって、二分探索の一回の処理はO(n^3)ででき、十分である(submission)。

4/25

4/26

4/27

kが割と大きいと必ず答えはNoになる(小さい方からシミュレーションしていくと割とすぐにstopする)ので、普通にシミュレーションしてしまえばよい(submission)。

sとhの個数に注目し、それらを特徴量としてくっつけた時に隣り合う2つに注目すると、どちらがより多く作れるかはsの個数とhの個数によって決まる。よって、それを比較関数としてn個の文字列をソートした後に、その順番にくっつけた文字列のスコアを計算すれば良い(submission)。

n種類で考えるのではなく、1匹ずつ取るか取らないかを決めていくことを考えると、dp[i][j] = i匹目まで見た、今までにj匹取ったときの、マナのmaxを持つようにすると、2乗のdpができる。回復のタイミングは、木を移動するタイミングなので、それも簡単に判断できるし、マナのcapacityはjにのみ依存するので簡単に求められる(submission)。

まず、1本も取り除かない状態でMSTを構築する(できなかったら終わり)。すると、MSTに含まれない辺は、それを取り除いたとしてもMSTが変動しないので、答えはMSTのコストと一致する。残りは、MSTに含まれている辺を取り除いた時にコストができるだけ増えないようにMSTを再構築したいということになるが、MSTの中で1本だけ辺を取り除くと、MSTは2つの連結成分に分かれる。すると、2つの連結成分を繋ぐことの出来る辺の中で、コストが最小の辺ということになる。今、MSTのある辺を消す時に、新しい辺になりうる候補と言うものを考えていたが、この見方を変えて、MSTに含まれないある辺は、MST上のどの辺を切断する時に候補になりうるかという風に考えると、それはMST上でパスになっていることが分かる。そのパスに対して、最小値を更新していくようなことを考えると、HL分解+区間update区間minのsegtreeがあれば、MSTに含まれない辺をコストが大きい方から順にこの区間updateをしていくことでMST上の辺を削除したときに対するMST再構築の最小コストが分かる (submission)。

4/28

頂点を(今いる駅, (路線iのj番目の駅))に拡張すると、乗り換えは各頂点同士を結ぶと辺の数が爆発するので、(今いる駅, (-1,-1))のような頂点を用意してそこを経由するような形にまとめると辺の数がO(N)になって間に合う。また、求めるものが、最短経路かつ乗り換え回数をできるだけ抑えるなので、距離も(経路長, 乗り換え回数)のペアでもって大小比較する必要がある。駅も文字列で与えられるし、色々めんどくさいけど、結局頑張って変換してdijkstraすればよい(submission)。

ボロノイ図を作る。元の多角形から、垂直二等分線を引いて切るのを繰り返すことでその点にたいする領域が得られる(submission)。

平方分割でクエリを処理する。各ブロックに対して、個々の状態と、全体に対するデコレーションが(連続的なら)その始点と終点を管理する。連続じゃないものが来た時点でそのブロックは全部ダメになるのでそれもフラグで管理している(submission)。

4/29

座標圧縮しておき、各x座標,y座標について何が残っているかをsetで管理しながらシミュレーションすると、1つのスタート位置に対してO(nlogn)でシミュレーションができ、それを全ての点をスタートとしてシミュレーションすれば良い(submission)。

2013-2014 Northwestern European Regional Contest (NWERC 2013) Virtual

2人チームでばちゃした。結構調子良かったけど、やはりもう少しWAは減らしたい...

4/30

GCJ Round 1B 2018に参加

aabcでLarge全部落とした。疲れてたのもあって適当になってたけど、とりあえず通過できそう。