アルゴリズム忘備録

競技プログラミングとかデータ分析とか

Yukicoder Contest 161

No.505 カードの数式2 - yukicoder

 よくある数字を加減乗除した時の最大値を求める問題…であるが本番解けず。Nが小さいので思わず全探索してしまったがTLEする。変な貪欲をやってみたがもちろん合わず。

正しい方法はi項目まで使った時の最小値及び最大値を持ってdpする。最初の1項目は+限定なのに注意。

  

No.506 限られたジャパリまん - yukicoder

 本番時間切れ。よくある格子座標の組み合わせをdpで求めるやつ。これをK, Pの全組み合わせでやる。O(HW 2^K)

 

No.507 ゲーム大会(チーム決め) - yukicoder

K君除いた他の人をスコアでソートし、インデックスを二分探索。

二分探索中の仮indexがxであるとき、K君のスコア+a[x] + 1以上のスコアになるペアの最大数を計算。これはスコア最大値の人が、そのスコアを超えるような最低の人とペアになるようにすればよい。配列aのコピーが大量に発生する系の問題苦手。