2018-06-24から1日間の記事一覧
グラフ
二部グラフ
DFS
BFS
DP
ナップサックDP
ARC-E
AtCoder
AtCoder700点
補グラフを考える
補集合を考える
黄色diff
均等に分ける
そのまま覚えたいシンプル設定の中堅以上の典型問題
中堅以上の典型要素を詰め合わせた教育的問題
いわゆる本当に典型らしい典型ではあるけれども、「二部グラフ判定」と「ナップサック DP」とパートが 2 つあって重たい。 類題として AOJ 2370 RabbitWalking (二部グラフ判定からの部分和ナップサックが酷似) POJ 3692 Kindergarten (補グラフとって二部グ…
完全に冷静さを欠いたし、ハマった。。。 ARC 099 D - Snuke Numbers 問題概要 (ARC 099 D / ABC 101 D) 正の整数 N に対してその 10 進法での桁の和を f(N) で表す。今、正の整数 N がすぬけ数であるとは、任意の N より大きい正の整数 M に対して f(N) / N …
区間
最小回数・最小個数を求める
コーナーケース
操作
ABC-C
AtCoder300点
AtCoder
操作:上書き
操作:区間
順列を題材とした問題
緑色diff
被覆
最適化テク:自明な上界が最適解
条件の言い換え
ARC-C
最適化問題
ARC 099 C - Minimization 問題概要 1〜N の順列が与えられる。以下の操作を最小回数繰り返すことにより、全部 1 にせよ。 連続する K 個の区間を選んで、その区間のすべての数をその区間にある最小の数に置き換える 制約 1 <= K <= N <= 105 解法 間違いや…