裏紙

ほぼ競プロ、たまに日記

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)。

CF 958 E3 - Guard Duty (hard)

問題

Problem - E3 - Codeforces

問題概要

N個の白い点とN個の黒い点の座標が与えられるので、完全二部マッチングをつくりたい。マッチングさせた者同士を線分で結ぶ時に、その線分が交差しないような割り当て方を答えよ。

  •  1 \le N \le 10000
  •  |x|,|y| \le 10000
  • 2点が同じ位置にある・3点が同じ直線上にのることはない

イデア

(いきなり)余談だが、このように交差しないマッチングを作ることは必ず出来る。そのようなマッチングとは、線分の長さの合計が最小になるような割り当て方である。仮に、このマッチングに対して交差があるような線分があると仮定する。線分B_0 W_1B_1 W_0が交差するとき、これらはB_0 W_0B_1 W_1の組に繋ぎ替えれば交差はなくなる。そして、この線分の長さの合計は、三角不等式から前者よりも短くなっていることが分かる。

さて、このようなマッチングをどのように構築するかを考える。上で述べたように、白の点と黒の点が同じ個数なら、必ず題意を満たすマッチングを作ることが可能である。よって、1つのマッチングを構成して、それによって出来る線分に対して、領域が2つに分割される時に両方の領域でまた白の点と黒の点が同じ個数になるような線分を常に選び続ける事ができれば、このマッチングは完成する。

今回は、その領域内で、x座標が最小の位置にある点bとどれをマッチングさせるかを考える。この時に、点bを基準にして偏角ソートしておき、その順番で点bを同じなら+1、違うなら-1という風にカウントしていくと、初めはカウンターが0からスタートし、最終的には(領域内には白と黒は同じ個数あり、基準にする点として1つ使っているので)-1でカウンターが止まる。このカウンターが-1になる瞬間に、その点とbを結ぶことにすれば、それより上と下の領域が両方ともまた白の点と黒の点が同じ個数になる。

これを繰り返して、全てのマッチングが終了するまで試せば良い。これは全部でN回行い、1回の動作の中ではソートをするので、全体としてO(N^2 log N)で解くことが出来る。

実装(C++)

続きを読む