http://yukicoder.me/contests/163
以下、解説
No.504 ゲーム大会(ランキング)
http://yukicoder.me/submissions/167293
点数が自分を上回ると順位が1つ下がるので、点数が上回ったら順位を1つずつ下げていけばよい。
No.505 カードの数式2
http://yukicoder.me/submissions/167862
dp[i][j] := i番目までの数を使った最大(j=0)と最小(j=1)
を使ってDPしていく。
DPをする時に端だけを持ってDPしていく典型。
No.506 限られたジャパリまん
http://yukicoder.me/submissions/167864
フレンズの数が少ないので、ジャパリまんを上げるフレンズを全探索する。
あとは、端から端までの最短経路の数を数え上げればよいのだが、このサイトの書き込み方式のような方法でDPすることで数え上げる事ができる。
具体的には、dp[y][x] = dp[y - 1][x] + dp[y][x - 1]としてDPしていけば良い。
あと組合せはmodをいちいち取らなくてもlong longに収まる(modを取ると最大値を考えにくくなるということもある)ので、long longで数えて、modで答える
No.507 ゲーム大会(チーム決め)
http://yukicoder.me/submissions/167867
自分以外の要素を昇順ソートしておく。
二分探索をする。
「chk(int idx) := idx番目の人と組むと確実に商品が得られるか」という評価関数を用意して、[1,N-1]の範囲で二分探索をする。
あとは、idx番目と0番目以外の要素でA[idx]+A[0]より大きい数のペアの最大数を求めるが、これは貪欲法で求めることができる。
idxと0番目以外の数で最大の数を取り出し、足すとA[idx]+A[0]を越える最小数を取り出す。
この操作を繰り返すことで貪欲にペアの最大数がとりだせる。
これは尺取り法の要領で左右から範囲を絞っていき確定していくとO(N)でできるので、全体として間に合ってAC
