■A - Signed Difficulty
書いているとおりになる
stringで受け取る
■B - Same Name
setに打ち込む。
■C - Many Balls
二進法。
■D - Pair of Balls
これこんなに解かれるもんなのか。。
queで頑張るのは明らかだけど、実装面倒だし絶対に嫌なので
デッドロックが起きる条件をうまいことやろうとするも、計算量的に無理なので諦める。
と思ったけど、これグラフに落として閉路検出(トポロジカルソートで十分らしい。)
■E - Amusement Park
二分探索。
まず。満足度が0のアトラクションに乗る必要はないので、
Kを使い切らない場合をコーナーケースとして先に処理しておく
あとは満足度x以上のアトラクションにのみ乗りたい場合、何回以上乗れるかを調べる。
■F - Max Sum Counting
入力をpairで受け取りソートする
最後に選ぶものを固定させる。
これまでに選んだsumのmaxがai-biなので適当にナップサック。
■G - 01Sequence
牛ゲーを私は知りませんでした。
基本的に解説のまま。
数列Bを用意する
Bi := a1,a2,,,,,anに含まれる0の数。
とすると、この数列は
B0 = 0
Bi<=B(i+1)
B(i+1)<=Bi + 1
を満たす。
また、問題の条件を落とし込むと
AlからArに1がx個以上含まれる
⇔AlからArに0は(r-l+1)-x個以下含まれる
⇔Br - Bl-1 <= (r-l+1)-x;
上の4条件を改めて抜き出すと
B0 = 0
Bi- B(i+1) <= 0
B(i+1) - Bi <= 1
Br - Bl-1 <= (r-l+1)-x
これは牛ゲーと言われる問題らしい。
ダイクストラで配列Bが求まるので復元ができる。
■H - Random Robots
LGV公式と言うらしい。
dag上で{start,goal}のペア集合を決めたときに
それぞれのパスがどれも交わらないようなパスの選び方が求められる。
但し条件として、トポロジカルに並べた頂点上で、
startX,startY,goalY,startXと並んでいた場合
パスは絶対に交点を持つ必要がある。
なので、inputでもらったものがstartの集合なので
考えうる全てのgoalの集合に対してLGV公式を使って行列式を求めればいい。
だが、これは量が多すぎるのでうまいことdpでやりたい。
行列式をバラせば、これはk!の置換すべてが出てくるので
それぞれをバラバラに考える
dp[i][j]:=i番目まで考えた、ここまでのgoalの座標がj以下。
このようにすれば、
dp[i + 1][j] = dp[i + 1][j - 1] + dp[i][j - 1] * c(n, j - vx);
のように遷移できる。
しかし、O(k!)の部分がネックなのでこれだと間に合わない。
これはbitdpの要領で考えればいい。
上の説明では省いたが、sgn(σ)の部分もちゃんと考える必要がある。
転倒数が偶数なら、sgn(σ) = 1,奇数ならsgn(σ) = -1
