裏紙

ほぼ競プロ、たまに日記

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全部落とした。疲れてたのもあって適当になってたけど、とりあえず通過できそう。

CF 938 F - Erasing Substrings

問題

Problem - F - Codeforces

問題概要

英小文字のみで構成された長さnの文字列sがある。これに対して、i回目の操作では長さ2^{i-1}sの連続する部分列を切り取り、残った部分を連結してsとする、ということをsがなくなってしまう直前まで行う(つまり回数をkとすると、k= \lfloor \log_{2} n \rfloor)。

k回操作した後にあり得る文字列の中で辞書順最小のものを答えよ。

  •  1 \le n \le 5000

イデア

まず、n \le 5000であることから、行われる操作の回数はたかだか12回であるという事実と、入れ子になっているような削除操作は入れ子にならないように分解できるので、削除する区間は元の文字列でも連続していると考えてしまって構わない。

以上のことからdp[i][mask] := i文字目まで決定済み、削除操作はmaskの状態で行った時の答え(=辞書順最小の文字列)ということを考えると、状態数がO(n^2)なので間に合いそうに見えるが、陽に文字列を持とうとすると、1状態辺りでO(n)の空間を使用することになり、MLE,TLEが発生すると考えられる。

今、上で考えたことに対して、dp配列の中に入っているのはこの問題の答えの候補に対するprefixが入っていることになる。そこで、違う状態だが、このprefixの長さが同じである2状態に注目してみる(dp[i1][mask1]dp[i2][mask2] とする)(ちなみに、この状態(i,mask)に対してprefixの長さは一意に定まるし、簡単に計算できる)。

さて、このprefixの時点でdp[i1][mask1]dp[i2][mask2]に大小関係がついていたら、大きい方についてはそれ以降の遷移を考えるのは無駄である。何文字目まで見ていようが、その時点でprefixが小さい方を選ばなければ、大きい方をそれ以降いくら頑張って選んでも小さい方の後ろに適当にくっつけたものでさえ敵わないからである。(辞書順最小はとこのようなgreedyなアプローチと相性が良い(要出典))。

そうすると、各状態について陽に文字列を保つ必要はなく、この状態は最小に到達できうるか否かを持てば良いということになる。遷移の順番をどうすればいいのかで悩んだが、状態に対してprefixの長さが決まるので、これが短い順に遷移していき、それと同時に1文字ずつ答えを決定していけば良い。nに対して、最終状態の文字の長さも一意に定まるので、その文字に到達すれば終了とすれば良い。

実装(C++)

続きを読む

2018/4 solved(1)

4/1

dp[i] := iがsubsetの中で最大になるような適切な選び方は何通りあるかを計算する。このとき、文字列でソートされた順でiを処理していくと、i未満の部分のdpの和を取ることでdp[i]の値を得ることが出来るので、部分和を高速に取れるセグ木やBITなどを使ってこのdpを高速化出来る(submission)。

4/2

GCJ 2018 Practice Sessionに参加

今年からコード実行になったらしい。ルール的にはhackのないこどふぉに近いのか...?smallを確実に取りに行ってからlargeをやるとペナルティが付くのか?

位置と方向を決めると、そこにたどり着くまでコマンドを使う回数の最小値を計算する。なぜ最小値で良いかというと、向きが同じでそれ以上のものは、その場で実行するだけで辿りつけるからである(submission)。

4/3

4/4

各頂点について、その部分木が深さiの頂点をいくつもつかを上に持ち上げならDFSしたいが、陽に配列を持って処理しようとするとO(n^2)かかってしまう。そこで、適当なbaseとmodを複数用意して、この配列を多項式と見なしてローリングハッシュと同じ要領でこの配列をハッシュとして扱うと、上に持ち上げる時はbaseをかけて1をたすだけで上への伝播を完了できる。それを一通り求めたら、mapでそれぞれのハッシュ値が何回現れるかを数えればよい(submission)。

4/5

それぞれの人が知っているリストを作って、contributeが低い順にsalaryを決定していく。問題の条件を愚直に適用すると条件がO(n^2)個になって間に合わないが、小さい方から処理することで最低限のsalaryを更新していきながら更新できる。問題文をよく読んでなくて、この構成の仕方だと片方向しか満たせてないので、UFを使いながらもう片方の条件をみたすように合わせていく(具体的には、contibutionが同じで、条件に引っかかる時はどちらかのmaxに合わせないといけない)(submission)。

分離できる直線があったとして、それをがちゃがちゃ動かすとかならず黒い点1つと白い点1つを通るようにできるので、そのような2点を通る直線のみを考える。直線を弾いた時に複数の点が乗っているとめんどくさいが、ちょっとずらせば大丈夫かどうかは、直線上の点を順番に見ていった時に綺麗に2つに分かれていればちょっと回転すると分離直線を作ることが出来てOKとなる。幾何ライブラリを使おうと思ったが、誤差が怖いので、今回は自前で実装した(submission)。

4/6

imulan.hatenablog.jp

4/7

各bitについて、0と分かっている/1と分かっている/どちらかわからないの3状態をもつO(3^m)のbitDPをする。この情報を基に、最悪の場合が最小になるような行動を選ぶので、次に聞く箇所を全探索し、その結果がどちらであったかのmaxを取るという遷移になっている。現段階の状態で、何個にまで絞り込めているかのcheckを、ビット演算子をつかってO(m)かからないように実装した(submission)。

4/8

GCJ 2018 Qualificationに参加

全完してた。smallとlargeで本質的に違う問題を解かせる辺りに、GCJを感じた。本番の時はちゃんとサーバー動くようになってるといいが...

NWERC 2014 Virtual

8完だった。途中で実装詰まってなければもう1問狙えたかもしれない。

問題を言い換えると、四角い枠の中にn個のbike stationがあり、枠の上にも無限個個のbike stationがあると見なしてよい。そうすると最適を考える上で取るべきルートは2点を直接結ぶ / 1点を選んで1回壁を経由 / 最初から最後まで だけで良い。また、反射の場所は、三分探索によって綺麗に見つけることが出来る(単なる反射ではないことに注意)。それを全方向に試せば良い(submission)。

4/9

4/10

差が1より大きい移動があれば、それが縦の移動であることが分かるので幅が確定する。まずその幅に矛盾が無いことを確認したら、もう一度最初から最後までの移動に矛盾が無いかをチェックする(幅を決定する段階では差が1の移動を無視したが、行をまたいで右端と左端の値になっている可能性があるため)。

sとtからそれぞれBFSで距離を求めておくと、新しい道(i,j)を1つ追加するとなった時に、新たな経路の長さは(sからiへの経路)+1+(jからtへの経路)となるのでそれが元の最短経路とり短くならないかをチェックすれば、最短経路を損なう道になるかどうかがチェックできる(submission)。

答えを二分探索することにすると、左から順番に何人配置すべきかが決まっていくので、その合計がkを超えるかどうかで可能かを判定する(submission)。

温度をTに保ったまま、(Tに近い方から順に)熱い水と冷たい水を同時に加えていくことを考えると、どちらかの水が尽きて、これ以上追加できない状態になる。ということは、追加する水の量は温度でソートした時にどちらかは使い切っているはずで、それに合わせてもう片方を調節しているというかたちになっているはずである。それがどっち側になるかは、仮に全部の水をフルで入れた時に温度がTより高いか低いかで判断できる。あとは、適切な位置を見つけて、その蛇口で出す量だけ二部グラフすれば良い(submission)。

4/11

4/12

2つの多角形で囲まれるサーキットを、最短で一周するのにかかる距離を求めるというシンプルな問題だが、かなり実装に気を使う。基本的には、外側を無視すると内側の多角形の凸包のルートが最短であるが、そのルートが外側の多角形の外を走るルートはダメなので、そこは、外側から凸包を押し戻すようなルートになることがイメージできる。すると、考えられる最短ルートは、内側と外側の多角形の頂点を結んでいくようなルートになり、かつ内側の凸包上の点は必ず通っている。この情報をもとに、内側の凸包上の点をチェックポイントにしながら一周していく。が、気をつけないと一周してくれずに逆走して一周した気になってゴールしてしまうので、ゴールラインを引いてそれをまたぐ線が引かないとか、counterclockwiseになるように辺をつくるとか、そういう注意が必要になってくる(submission)。

区間の開始時間になる時計を10個の中から決め打ちして、針の割り当て方が6通り、回転が60通りある。この開始時間で、他のそれぞれの時計に対して開始時間以上で最小の時間になる針の割り当て・回転を全探索で見つければよい。気をつけて実装するだけ(submission)。

訪れる順番はDFSの形なので、与えられるメモは正の値においてはDFS木上の辺を表し、負なら後退辺を表わしていることになる。各部屋からドアがいくつあるかが与えられるので、その部屋を訪れきるタイミングもチェックして今いる場所に注意しながらDFSを再現すればグラフを復元出来る(submission)。

4/13

基本的に鏡の位置でクロスするようなレーザーのルートは最適ではなくてもっと少ない枚数で実現できそうなのでそれは考慮しないことにして、(座標,向き,typePの使用枚数) = typeQの使用枚数のminを持ちながらBFSする。ただしスタートの向きが決まっているので、スタートを北側に通過するような光は作れないことに注意(submission)。

tの開始地点を全探索する。その固定された位置に対して、elementを組み合わせて一致させることができるかをbitDPによって計算する。ただ、そのbitDPの中で文字列の一致判定などをやると重いので、それを前処理にしてからbitDP内は簡潔にする(submission)。

球体の大きさも考慮に入れて、球体同士の距離を表す関数を作ると、中心感の距離パートも半径の元帥パートも単調増加なので、関数が凸であることが分かり、関数の最小値が見つかる。その最小値が負なら衝突するので、衝突するタイミングを求めておき、あとはそのタイミングが早い順に衝突を処理すればよい(submission)。

何回バウンドをさせるかを全探索する。そうすると、放物線が全て同じ形なので、打ち出す角度を二分探索で見つけることが出来る。物理の式の変形がめんどい(submission)。

4/14

dp[何回移動したか][使用したポーションのマスク]でbitDPをする。マスクの遷移については、小さい方から処理すれば次にどのポーションを使うかだけ考えれば良い(複数個を同時に使う場合でも順に伝播してくれる)(submission)。

dfsしながら、部分木を処理するのに必要なコストを帰ってくる必要があるときとない時のフラグをもちながら計算する。2乗が間に合うので、全方位木dpにしなくても各頂点を根にして試せば良い(submission)。

Helvetic Coding Contest 2018 online mirror

チームで参加。初めて2次元ロリハを書いた。

4/15

imulan.hatenablog.jp

Bubble Cup 9 - Finals [Online Mirror] Virtual

週末バチャに人が少なかったので、適当に選んでチームでバチャしたけど面白かった。Bの解説があってなかったからTutorialのコメント欄見て復習したい。

segmentを移動しきれるかの判定を考えると、初め一直線に抜けることを考えると区間が全部1ならまずOKになる。そこから、折り返しを加えていくことを考えると、折り返しというのは隣り合う2要素にそれぞれ+1することに該当する。ということで、区間がOKかを判定したい場合には、区間を左から貪欲に1にしていって全部1にできるかを判定すればいい。このときに左から順に1にしていくことを考えると、必要な回数はla_l回、l+1a_{l+1} - a_l回、l+2a_{l+2} - a_{l+1} + a_l回...というように交互に+と-が現れる形になっている。これらが区間内で負になってる箇所がなく、かつrの位置の必要回数が0になっていることが判定の条件になる。あとはこの階差を交互に持つものをセグ木に乗せれば、判定クエリは処理できるので、区間addはこの階差のどこに実際に何が足されるのかを注意して足す場所に気をつける。indexの偶奇でセグ木を別に持つと区間addに落とし込める。かなりおもしろかった(submission)。