2022-08-01 咳がとまらない / ABC262 の E を解いた
咳が止まらなくて息苦しい。
第三回日本最強プログラマー学生選手権-予選-（ ABC262 : AtCoder Beginner Contest 262） の E を解いた。
- E - Red and Blue Graph
https://atcoder.jp/contests/abc262/tasks/abc262_e
- 提出: https://atcoder.jp/contests/abc262/submissions/33709158
- 本番では解けず
- R から伸びる辺は R か B のいずれかの頂点と組になる
- 辺の数の偶奇性が問題だったので頂点の次数を数えてその偶・奇で分類は考えた
- 次数が 0 の頂点を R にした場合は問題にならない
- 次数が 1 の頂点を R にした場合は相手が B だと問題になる
- …… 2 階層掘らないと分からなさそう、でもそれだと構築以前という感じで厳しそうだった
- 解説 AC
- R の頂点の次数の和、 R-R の本数、 R-B の本数を整理して偶奇性を考えると、次数が奇数の R の個数が偶数なら良いとわかる (ここにまず到達できる気がしない)
- あとは K 本のうちいくつを R-R に当てるかを、入次数による分類の制限の範囲で数える
今日のコミット。