裏紙

ほぼ競プロ、たまに日記

2016/10 solved(2)

10/17

imulan.hatenablog.jp

まず、N個の家に対して、どこまで増築していいか値段を二分探索する。Kが大きいので、それぞれの家に増築の回数を1回ずつ余地を残すためにK-N回以下の増築が許されるところを探索して、それがおわったらそこまで増築してそこからO(N)回をpriority_queueを使って貪欲に処理していくことで時間内に間に合う(submission)。

10/18

CF #377(Div2)に参加

ABCの3完。Dも些細なミスで落としてしまっていた...Eはわからなかったので要復習。

最大値を持つSegtreeを使って各iについて左右にどこまで見えているかをそれぞれ二分探索。以前はすごい難しい問題に見えていたけど、いまやってみると結構すんなりできてしまった(submission)。

まず最小化したいので既に決まっている位置が1箇所しかなければ必ずuglinessを0にでき、それは1通りになる。既に決まっている位置が2箇所以上あるときも、端は最適に選ぶ方法がただ1つに定まるので、既に決まっている位置の間を見ていく。間が無く、隣合うものを無視すると間の状況は4通りに分けられる:

  1. X(奇数長)X: これはYXY...Yがuglinessを増やさない唯一の最適な選択になる。
  2. X(偶数長)X: これは最適に選んでもどこかにダブりが一箇所だけ生じてしまう。間の長さをbとするとそのダブりの位置がb+1通りありえるので、それを掛ける。
  3. X(奇数長)Y: これもどこかにダブりが一箇所だけ生じてしまう。間の長さをbとするとそのダブりの位置がb+1通りありえるので、それを掛ける。
  4. X(偶数長)Y: これはYXY...YXがuglinessを増やさない唯一の最適な選択になる。

これを全ての間に対して見ていけば良い。予めきめられた位置は50以下なので、余裕で間に合う(submission)。

微分したりしてみると、最大値となりうるものとして \sqrt{2} dがあり得るが、いつもこうなるとは限らない。x座標が1未満の幅に収まる時、行って戻るという動作が最大値となりうる場合が発生するので、そのときは別に扱ってy+1が最大値となる場合があるのに注意。

10/19

色ごとにカードを分けて、その色に対して数の小さい方からセットを貪欲に決定していくことが出来る。

(場所,馬車券使用状況)の頂点に拡張して最短経路問題を解く。頂点数も多くならないのでBFSでも普通に間に合う。

bitDPをする。静的に224のintの配列を作るとMLEしたので、unordered_mapでDP配列を管理した。と思ったけど、最大でもDPの値が24にしかならないのでdfsの返り値はintなんて大きいのにする必要が無いのでcharにしてみたらMLE回避ができたし、速くなった(submission)。

10/20

式の形的に、相加相乗平均の関係なのでマージして行くと必ず質量が減らせる。そして、この変形される形をみるとできるだけ大きい値に多くのルートが被さった方がいいような感じがするので、大きい方から2つ選んでマージを繰り返す。

t/d が大きい方からやればよさそうじゃね?とか思ってやってみたらそれが本当に正しかった。その正当性はたくさんあるなかで特定の2頭に注目してA→BとB→Aのどちらが最適かを考えてみると同じ形に落ち着く。

交互にカードひく説明いるか?って感じがする。逆にわかりにくくするためなのか...解法としては、何番目で決着が着くかを二分探索することで、O(n^2 logm)で出来る。

10/21

クラスカル法で最小全域木を構成する。クラスカル法は辺が小さい方から選んでマージしていくが、今回は最小コスト辺と最大コスト辺の差を最小化したいので、辺をコストでソートした後に、i番目をスタートしてMSTを構成する。この構成はm回行われるが、nが十分小さいので間に合う。

最小全域木

(何日目,サイクルの位置)を保存してDPする。遷移はその日にカフェインを飲む、飲まないの2通りなので簡単に書ける。

imulan.hatenablog.jp

10/22

過半数に0点、残りにm点を取らせるのが良い。

i番目まで使った,残り体積jの時の高さの最大値を保存しながらDPする。それぞれの壺には整数ぶんだけいれることだけを考えれば良い。

10/23

はじめにgcdで割ってしまってから考えたほうが分かりやすい。割ったあとの長さが同じ(1にしかなりえないが)なら、赤しか通過しない。また、どちらかが偶数なら対称性があるので1:1になる。なので、割った後にどちらも奇数の場合を考えてみる。何パターンか試してみると、a:b=(hw/2+1):(hw/2)になるような感じがして、それを出してみたら通った。理由は要考察。

実は括弧はどのように並んでいてもよく、開括弧と閉括弧の数が同じだけで成立する。

シミュレーションする。ゲームのルールを知らなかったので、その理解に凄い時間がかかった。

10/24

シミュレーションする。

DPを和で保存してオーダーを落とす。

dijkstra法を2回やる。頂点xから帰るのは簡単にそのままやればよいが、xに来るということを考えた時、グラフの逆辺を作ってxからの最短経路を求めることで来る時の最短経路を考えることが出来る。

UnionFindを使う。2*N個の頂点を用意して、「criminal iがDragon/Snake」に属するという事実を頂点とし、Dクエリが来たら(a-Dragon,b-Snake)と(a-Snake,b-Dragon)を結べば良い。

隣り合う2つを見て、最大値が更新されている瞬間はその高さで確定である。高さの設定自由度が有るのはaもtも前後で変化していない位置のみで、そこは1~(2値の最小値)までの高さがあり得る。あとは、高さの記録に矛盾がないかをチェックする(ここでバグらせて悩んだ)(submission)。

10/25

部分点解法は思いついたけど、満点は思いつけなかった。ただ2列ごとに考えればよく、その最適な相対順序を保ったままW列の処理が可能なのでそれぞれの2列で最小コストをDPで計算して足せば良いことになる(submission)。

コロンとカンマで区切れたら、グループの名前を記録しておいてBFSしてグループの名前じゃない名前をsetに入れて管理すると答えが簡単に出せる。

10/26

下の桁から順番にkeyのbitが何であったかを決定していくことが出来る。問題文にもあるように、最下位のbitは8つの数の最下位のbitの和とchecksumのbitの違いが有る時は1で無い時は0に確定する。すると、8つの数のもともとの数の最下位のビットが何であったかが分かる。それを足して、繰り上がりを記録する。あとは同じ事を2bit目以降も繰り上がりを考慮しながら進めていけばよいということになる。

実はワーシャルフロイド2回でいけるっぽい。自分の方針ははじめに鉄道会社ごとに辺を張ってそれぞれでワーシャルフロイドをして頂点間の最短距離を求め、その2駅間の距離に該当する金額を計算してその金額の辺を張り、すべてはり終わった後に拡張ダイクストラをする、と言う方法を取った。

10/27

貪欲にニンジンを食べてしまって良い。どういうことかというとまず手に入れた瞬間にニンジンブーストがなければその場で発動する。そして、ブーストしていて、ストックに空きがあればストックに追加する。空きが無い時はその場で食べてしまう。それをiメートル地点で1mごとにシミュレーションした。O(L)で、L \le 10000なので間に合う。

はじめにそれぞれの汚れたタイルから最短距離を求めておいて、全汚れたタイル間の最短距離を保存しておいてから巡回セールスマン問題のように訪れた地点、最後に訪れた地点を保存するbitDPをする。

ベルマンフォードを使って負の閉路を検出する。

10/28

Dijkstra法で最短経路を求めていく過程で、その経路における親を保存しておく。また、経路長が同じ時でも、建設コストが低ければそちらの方を選んでおく方が最適である。すると、この保存したコストを首都以外に足し合わせれば良いことになる。

imulan.hatenablog.jp

それぞれの人に対してDPによって、まず合計でi回休憩する確率を求める(dp[i][j]=今i番目の休憩地点まで通過して、j回休憩する確率とすると計算できる)。求めたあとで、それぞれの人が勝つ確率を考える。まずその人の休憩回数を仮定すると、勝つために他の人が何回以上休憩を取らなければいけないかがそれぞれ決まるので、その積になる(誰か一人がm回休憩したとしても追いつけない時は不可能)。そして、各休憩回数に対しての和を取れば良い。

10/29

必ず文字列長が増える変換しか無いので、現在の文字列状態から全ての変換を再帰的に試す。

訪れた場所、向き、手の位置を保存しながらバックトラックする。実装重くて辛かった。

振り直しになる面も結局は何かしらの目がでるまで続けることになる。つまり、出目の確率の割合を保ったまま全体が1になるように底上げして、それから期待値を普通に計算すれば良い。

壁をx個壊したときにうまくいくかBFSで確かめるというのを二分探索して、十分間に合った(submission)。解き終わってから気づいたが、BFSをしながら行けるところがなくなったら壁を1つ壊してそこがすでに訪れたところに隣接していればqueueに入れて...とすれば実質BFSを1回するだけで済む(submission)。

桁DPによって妥当な組み合わせの個数を計算する。

AGC 006に参加

ABの2完。難しかった...

10/30

解説を読んで実装した。この問題数段階の考察が必要なのにその全てに気づくのが難しすぎる...というか期待値の問題に慣れていなさすぎている(submission)。

再帰していくときに次の単位分数を選ぶ時の分母の上限と下限をちゃんと枝刈りしたら通せた。

10/31

解説を読んで実装した。二分探索内でチェックしていく時、連続している区間の値は斜めに拡散していく。その拡散の線が衝突したところで、縦に境界線ができる。なので、連続している区間の中で中心に最も近いものが頂上まで伝播していくことになるからそれを探せば良い。ただ、そのように連続する区間が無い場合には、端の値が頂上に一致するのでそれを判定すれば良い(submission)。

クエリごとにスタート地点をA、ゴール地点をBとする。そして、オブジェクトごとにこの線分が球体の障害物を通過するかを調べる。オブジェクトの中心をCとすると、Cから線分ABへの距離が半径以下ならそのオブジェクトを通ることになる。その垂線の足をHと表すことにすると、 \overrightarrow{CH} = \overrightarrow{CA} + \overrightarrow{AH} = \overrightarrow{CA} + t \overrightarrow{AH} \ (0 \le t \le 1)と表せることになる。そして、Hは垂線の足であるから、 \overrightarrow{CH} \cdot \overrightarrow{AH} = 0となる。この式からtの値が求まる(ここで、0 \le t \le 1の範囲に入らない時はスタート地点かゴール地点がその中心との最短距離を取る点になるわけだが、制約からスタート地点とゴール地点がオブジェクトの中に入ることは無いので考える必要はない)。よって、Hの座標も求まるので、CHの距離を求めることが出来るので、コストをクエリごとにO(N)で計算できる。doubleでの計算をすることになるので、誤差には注意する。

実はW+Sの値が小さい順に上に来るようにするのが最適になる。牛A(( w_a , s_a ))と牛B(( w_b , s_b ))に注目したときにw_a + s_a \gt w_b +s_bを仮定すると牛Aが下に来るときのほうが答えが小さくなることがわかる。

 a+b+c=dを変形してa+b=d-cにする。そして、a+bの値を列挙しておいて、cdを全探索する。d-cの値が列挙された値の中にあり、かつそれはset内の異なる値であるかをlower_bound,upper_boundを利用してO(logn)で探すことが出来るので、全体はO(n^2 logn)で求められる。

1セットあとの状態がどうなるかの行列をO(KN)で作ることが出来る。あとはそれをM回するので、行列累乗の要領でO(N^3 logM)でできる。