blog.bouzuya.net

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 に当てるかを、入次数による分類の制限の範囲で数える

今日のコミット。