2018-06-06から1日間の記事一覧
K番目を求める
文字列
辞書順
AtCoder
AtCoder300点
ABC-C
緑色diff
区間
最適化の考察:探索候補を絞る
解空間:O(N^2)通りの選択肢
ARC-C
NoviSteps3Q
ちゃんと見積もることが大事な問題。 問題へのリンク 問題概要 文字列 s が与えられる。s の連続する部分文字列のうち、辞書順で K 番目の文字列を求めよ。 制約 1 <= |s| <= 5000 1 <= K <= 5 解法 K が小さいのが怪しい。 冷静に考えると、辞書順 K 番目の…
DP
Union-Find
グラフ
N個のペア値の問題
操作を逆順に見る
操作
ARC-F
AtCoder
AtCoder1000点
最小コスト
赤色diff
Union-Find上のDP
個人的要復習
価格に関する問題
Union-Findのマージ過程を表す木を考える
高度典型
最適化問題
本番中に解きたかった... ARC 098 F Donation 問題概要 N 頂点 M 辺の連結な単純無向グラフがあります。 頂点 i には二つの整数 Ai, Bi が定められています。 このグラフ上で次のようなゲームをします。 初めに、W 円を持った状態で好きな頂点に立つ。 ただ…