知らないと解けないなと思ったのでメモ。参考 CODE FESTIVAL 2014 あさプロMiddle : B - 枕決め - kmjp's blogN人の人とM個の枕がある。 N人はそれぞれ高さがX[i]以上Y[i]以下の枕が好みであり、そのような枕を１個使いたい。 M個の枕の高さA[0] ~ A[m]が与…

NOMURA プログラミングコンテスト 2020 A,B,C の3完 ABC170 A,B,C,D の4完でした。 土曜日の方はまずまず。C は直ぐセグ木じゃん楽勝と思った割に、実装をバグらせまくり時間をロスしすぎました。いもす法は知らなかったので、セグ木で毎回リスト A をみて 1…

a[p]+b[q]+c[r] の最大値を k 個求める問題。 取り合えず逆順でソートすれば、最大値は a[0]+b[0]+c[0] になるのは確定で、その次に最大になるのが、a[1]+b[0]+c[0], a[0]+b[1]+c[0], a[0]+b[0]+c[1] のどれかだと分かれば後は heap で k 回ぶん回すだけ。気…

a として実装した。 import sys input = sys.stdin.readline n,m = map(int,input().split()) chk = [] for i in range(n): a,b = map(int,input().split()) if a <= m: chk.append((a,b)) from heapq import heappop, heappush from operator import itemge…

尺取り法：数列の連続した部分列にあてはまる条件を O(n) で求めてくれる優れもの。 XOR四天王の二人目を倒しました。(弱さも多分2番目) 個人的な尺取り法の実装については、条件を満たさなくなった瞬間に（部分列の長さ - 1）を使って求めたいものを求めて…

拡張ダイクストラで解く。総時間、頂点に加えて今持っている銀貨の数を追加して heap に入れる。時間を増やす要因が通過時間と通貨を交換する時間の二つ（疲れているのでダジャレみたいになっている）あるので、交換するか、移動するかで分けて考える。移動…

A の小さいものを Ci のうち一番大きいものに変えていくのが一番大きくなるなあと考えた。 大きいものから変えていくので、N枚変える or Aの最小値が現在の Ci 以上になったらそこで終了してよい。 最小値を取り出すのを heapq で高速化 値の変更がなくても …