2018/6 solved(2)
6/16
V(=T+L)人いるときに、頂点数2Vのグラフを作る(各頂点は、i番目の人がdivine/devilに対応)。すると、与えられる情報から、2本の辺を貼ることができる。x,y,"yes"なら、xのdivineとyのdivine、xのdevilとyのdevilの間に辺をはり、"no"ならxのdivineとyのdevil、xのdevilとyのdivineの間に辺をはる。そうすると、連結成分が矛盾しない事実を結んでいることになる。あとは、dp[i][j]:=i番目の連結成分に注目、divine側がj人いるような割り振り方が何通りあるかを計算し、dp[(連結成分の個数)][p1]が1通りになっていれば、dpを復元する(submission)。
見た瞬間に最小費用流だと思ったけど、あとから解説を見たら別解になっていた。indexがトポロジカル順になるように張っておけば、負辺を処理するベルマンフォードが1回のループで終了するので、indexの貼り方に注意する(submission)。
2017 Benelux Algorithm Programming Contest (BAPC 17) Virtual
Bの桁落ちによる誤差死はひどすぎる、結局まだ解決できていない。あとGは思いつきたかった...
6/17
6/18
6/19
まず、1つのX,Yに対して答えがどうなるかを考えると、dfsしながら、深さの偶奇によって最大か、最小を選んでいくような形になるというのは分かる。では、たくさんのクエリに対してどのように答えればいいのかという問題になってくるが、答えは大きいビット側に依存度が高いのは想像がつく。そこで、また、ビットごとに注目すると、使用する木は同じなので、X,Yのビットの組としては4通りの組に対して、ノードに到達するときに得られる値というのが決まってくる。なので、その4通りの組が大きいビット側からどのような順番で現れるかだけが重要なことがわかり、この4!通りに対して前述のdfsで答えを計算しておけば、クエリに対する答えを得られる(submission)。
6/20
期待値の線形性を利用して、各部門を独立させて考える。すると、自分のアイドルがある部門に関してx回のアピールを行うと決めたときに、最下位になる確率と、3位以内に入れる確率を求める。3位までしか考えなくていいので、のdpで求まり、そのときの期待値も決定する。それをすべてのxに対してやるととなる。その期待値が求め終わったら、各部門を何回ずつやるかをで全探索し、最良のものが答えとなる(submission)。
1つのコースを思い浮かべると、移動するパートとうろうろするパートに分類できる。ただ、このうろうろするパートが複数あるのは最適ではない(複数ある中で、一番稼ぎやすいところでうろうろしておくほうがいい)。ということで、次のdpを考える: dp[v][t][2] = vにいて、時間tだけ経過、もうすでにうろうろしたか
これは状態数で、ここからの遷移は移動かうろうろして自分の頂点に戻ってくるなので、通りの遷移がありえる。あとは、これを時間が小さい方から埋めていけば良い(submission)。
考察パートは鎖中経路と同じで、グラフを構築するとき、考えるべき頂点は始点、終点、円と円の交点だけで良い。あとは、それぞれの頂点間に辺が張れるかどうかを判定する必要があるが、辺とn個の円との交点を出し、ソートして各区間の中点が円の中にあればOKという方法を取った。ただ、座標系が大きく、誤差も厳し目なので、実装にかなりの注意を要する。具体的にハマったポイントは、円と直線の交点を使って求めた点が線分上にのっているかを判定するときに、ccwを利用して判定してしまっていて、誤差で死んでいた。ccwはcross,dotをとるので、大きい方は座標系の2乗オーダーの大きさになるため、今回だと1012くらいになる。それに対して、EPSを10^-9に設定しており、これらを比較しようとするのはlong doubleでも厳しい。そこで、ここの判定でccwを使うのをやめ、内積が負でないことをチェック&&距離が相手の点よりも近いことをチェック
という形にして、誤差死を回避している(submission)。
まず、お金の貸し借りを個人ごとに情報をまとめる。誰から返してもらわないといけないとかを全部無視して、ある人はx円返してもらう/払う必要があるという情報の形に落とす。そうすると、このm人を過不足なく部分集合に分け、かつその各部分集合が和が0になっているように分けられれば、その部分集合の人同士でやり取りをすることで解決することができる(その部分集合を連結にするの必要なやり取りの回数は、木ができることを考えると当然C-1になる)。なので、あとは部分集合の数を最大化したい、という問題になる。本番なぜか思いつけなかったが、これは簡単なbitDPで、すでに追加した要素をmaskとして持ち、次に追加する要素をどれにするかが遷移になる。その遷移後に、その部分集合の和が0になっていれば+1をして遷移させるということを考えればよい。1つずつ追加していくということを考えるのが大事だなと思った(部分集合がどうこうとかで悩みすぎた)(submission)。
n本の線分によって、線分によって囲まれる領域が何箇できるかを答えるという問題。つまり、平面グラフで、面がいくつあればわかればいいという問題である。平面グラフにはオイラーの多面体定理が利用でき、が成り立つが、これはグラフが連結であるときに成り立つ。連結成分の数をとすると、連結にするために個辺が増えたとみなして、となり、が成り立つ。外側はいらないので、。よって、答えはになる。あとは、与えられる線分からグラフを平面にする必要があるが、2つの線分が交差するとき、その交点を新たな頂点として生やし、辺はもともと2本だったものが4本になる。つまり、元のグラフでは頂点数が、辺の数がで、交点の個数分だけ頂点の数は+1、辺の数は+2になる。つまり、交点の個数ごとにE-Vは1ずつ増加するので、交点の個数をCPとして、となる(submission)。
6/21
わからない残りの2枚のトランプが何になるかを全探索して、そのカードが出たときに勝てるかどうかを逐一判定していく。7枚のカードが揃ったときにどの役になるかの判定は、そこから除く2枚を全探索して残った5枚で得られる役を求め、そのmaxを取るというものである。役の強さ関係の判定はvector<int>
に一任した(初めの要素を役の強さにし、それ以降は問題文に従って基準のものを入れていく)(submission)。
6/22
6/23
今のスレの状態を復元するためには、直前に誰が書き込んだか(これによってK個の順番が決まる)と、それ以外のN-K(<=3)個の要素がどのように並んでいるか(6通り)がわかれば復元できる。まず、状態間が遷移可能なものかどうかをチェックしてグラフを構築したあと、完成状態から初期状態の方に向かうようなBFSをして、初手としてありえるものを洗い出す。あとは、その洗い出した中で適しているものを初期状態にして、辞書順に取っていくシミュレーションをしてminをとればよい(submissin)。
6/24
ACPC 2013 Day2 Virtual
Eも通したかった。こういう実装をやりきれるのが大事だ...
光源はDAG関係になることが保証されているので、スタートの光源の向きを決めたら、トポロジカル順に光源の明るさを決定していくことができる。考えるべき光源の向きは、円の接線方向のみを考えればよいので、通りなので、全体の処理はになる。扇形の中に円が入っているかの判定に手こずってしまった(submission)。
6/25
答えを二分探索することにする。行ける階層を決めうちすると、考慮すべき条件は、起動条件のフロアも起動後のフロアもその階層以下のものだけを考慮すれば良いことになる。条件はXかつYの否定の形なので、2-SATの形にでき、2-SATで割当て可能かどうかを判定できる(submission)。
6/26
まず、3次元内で平行移動たり回転したりして円錐の底面の中心を原点、円錐の頂点をz軸上、点Pをx軸上に持ってくる。そうすると、これ以降y軸を無視して考察することができるようになる。斜めに切った時の断面は楕円になるので、その楕円の面積を求める。長径は交点を求めておけばその2点間の距離になる。短径は、中点の高さzに注目して、そこからz軸からどれだけ離れているか(x座標)に注目して三平方の定理によって求められる(submission)。
6/27
答えを二分探索する。値を決め打つと、目指すべきなのはある半径の円上になる。そこに来れば、円に沿って逃げれば良い。逃げる側は、その円の接線方向に動くのが一番良い。スナイパーが回る方向は、逃げる側が最終的にたどり着く点に近い方に回り込むのが良さそうに見えるが、そうではなくて、たとえ遠回りでも対象がいる川から回っていかないと行けない(そうじゃなければその場で待ってればいいので、生き残りやすくなってしまう)。ここの実装に注意する必要がある(submission)。
ほぼ同じような問題を見たことがあった(これ)ので、方針で悩むことはなかった。まず、それぞれの頂点を根にして考える。そして、まだ通していないパスの中から、貪欲に一番長くなるようなパスを取っていく。これは、dfsをして葉からの距離の最大値をとっておくと見つけることができる。あとは、priority_queueなどで一番パスを見つけていけばよい。一回のシミュレーションにかかるので、全体としてになる。mの制約は完全にハッタリで、以上のdeliveryを考える必要はない(submission)。
とりあえず、2個のスペースがバラバラな位置にある状況を状態として持つのはあまり意味がなさそうなので、kingが動かせるような状況に2個のスペースがある状態だけを考えて、その状態の間を重み付きの辺で結ぶことを考えると、状態数はkingの位置*4になり、10000となる。そして、各状態間のコストは、それぞれの位置でkingを固定した状態でBFSを行い最短経路の和として求めることができる。このグラフ構築がとても面倒だが、ここまでできてしまえばあとはダイクストラをやって終わりになる(submission)。
6/28
Educational Codeforces Round 46 (Rated for Div. 2)に参加
Eが橋検出ライブラリ持ってたら簡単で結構良い順位にはいれてしまった。FはMoを書いたけどTLEした(500000は平方分割を許さない意思を感じる)。
6/29
各学年のグループを1つの頂点にまとめてしまえば、その3頂点を結ぶ最小コストの木を求めたいという問題になる。1つの頂点からスタートすることを考えると、2つめの頂点と3つめの頂点までのパスを考える時、途中までは同じで、あるところから分岐するような形になる。つまり、全体の形はこの分岐点から各方面に3つのパスが伸びる形になっている。よって、この分岐点を全探索することを考える。そのときに木のコストは、予めこの3頂点から最短経路を求めておくことでその和とすることができる。また、そのときにパス上にある最小の頂点番号も一緒に伝播させておくことで、2つめのID最小化の問題にも答えることができる(submission)。
同じサイコロを複数回打つのに意味はなく、最後に打った時系列順に依存するので、古い方から打つ順番を決めながらbitDPをする。そのマスが確定する瞬間を予めそれぞれのサイコロが通る場所を計算しておくことで、bitmaskとして求めておき、そのmaskに到達した瞬間に遷移の考慮に入れるみたいなことをすると良い(submission)。
6/30
円を置く候補となる場所として考えるべきものは、レーザーに接するようなものだけで良い、具体的には2本のレーザーに接するような円を通り列挙し、それが場所として妥当かどうかをで判定すれば十分である。何故かと言うと、仮に置ける場所が見つかったとして、ギリギリまで動かせばそのような円にたどり着けるからである(submission)。
反射を折り返しとして考えると、円の中に点がいくつ含まれるかを数える問題になる。各x座標ごとに切って、y座標側にいくつあるかをカウントしていけばよい(submission)。
構文解析はそんなに複雑ではない。構文解析をして得られた多項式を、全て展開してしまい、その多項式同士を比較して答えを判定する(問題を完全に正確に読めたか怪しいけど、多分全部展開しても大丈夫な制約なんだろうなと思いながらこの方針を考えた)。比較する際に、足したり引いたりした結果係数が0になる項が残るのを防ぐために、比較の前には正規化を挟んでいる(submission)。
BAPC 2017 J - Jumping Choreography
問題
問題概要
はじめ、数直線上に匹のカエルがいる。番目のカエルの位置はである。
カエルはジャンプによって移動することができる。1回のジャンプでは、カエルは左か右に跳ぶことができる。しかし、その移動距離は、1回目のジャンプでは距離1、2回目のジャンプでは距離2、3回目のジャンプでは距離3、...、とジャンプ回数を重ねるごとに1ずつ増加していく。
カエルたちは、座標に集まりたいので、集まるために必要なジャンプ回数の和の最小値を求めてほしい。
次のようなクエリが合計で個与えられる:
- addクエリ : カエルを位置に1匹追加する
- removeクエリ : カエルを位置から1匹除外する
- moveクエリ : 集合位置をに変更する
このような変更指示が順番に与えられるので、そこまでのクエリを反映したときの集まるために必要なジャンプ回数の和の最小値を答えよ。
- add,removeクエリは合わせて5000個以下
アイデア
まず、移動幅が1,2,3,...と増えていくことに注目すると、全部同じ方向に振った時、その移動距離の和は2乗ぐらいになるので、今回のフィールドの幅を移動するのに、必要な移動の回数は、だいたいルートをとってくらいにおさまっていると考えられる(実際に計算してみると1415回が最大)。
なので、まずは幅を移動するのに必要な最小のジャンプ回数(とする)を求めたい。注目すると、回数が2回増えるごとに、移動距離の合計の偶奇が入れ替わるので、全体に対しては言えないが、の偶奇で分類すると、それぞれのは非減少な列になる(つまり、であり、である)。
これは、である時(幅の移動は回で実現可能な時)、幅の移動がからまでを過不足なく使って、(足すグループ) - (引くグループ) = x
のような形で実現されていることを考え、便宜上が引くグループの方に入っていると見なせば、が引くグループに入っていて、が足すグループに入っているというのが成り立つが必ず存在することが言えるからである。もしこのようなが仮に無かったとすると、0は必ず引くグループに属していることから、全部が引くグループに属してないといけないことになり、その和は明らかに負になって矛盾するからである。そうすると、幅の移動はとのグループを交換することで回で実現することが言えて、この不等号が成り立つことが言えた。
ここからは、クエリに答えることを考える。集合場所をにしたときの答えを持つBITを考える。の偶奇によって、2種類のBITで管理することにする。そうすると、カエルが1匹増える時、このBITに加算される値というのは、...44443333222222110112223333...
みたいな形になっていると考えられる。同じ値の区間は、まとめて加算処理できることを考えると、上の考察も合わせて、区間は3000個以内に抑えられることが考えられる。制約から、addやremoveはそんなに多くないと言われているので、この新しいカエルが来るごとに、このの処理を行っても間に合うと考えられる。また、moveクエリは、BITがまさに答えを保持しているので、その部分を参照すれば良いので、で答えられる。