問題
https://www.hackerrank.com/challenges/even-tree木が与えられるので、エッジを取り除いてノード数が偶数であるような木幾つかに分解したいので最も多くエッジを取り除くためにはどうすれば良いかを求める問題。
解法
各エッジに対して「このエッジを取り除いて二つに木を分割した時に双方の木に含まれるノード数がどちらも偶数である」ならば、そのエッジを取り除く。そうでなければ取り除かないとすれば良い。ノード数が800なので十分間に合う。
登録:
コメントの投稿 (Atom)
-
最近、ミレニアム未解決問題の一つがAIによって解決されたという情報やその過程が世間を騒がせている。特に今後の数学の在り方について、様々な意見が表明されており、私は毎日興味深く拝聴している。この流れに乗じて、 P vs. NP問題（ひいてはその分野）は現状どのような状況なのか につ...
-
0. 背景 グラフ理論とは文字通り, グラフについて解析する分野です. グラフ理論のモチベーションとしては, 「最小全域木」「最大マッチング」「最大フロー」などのアルゴリズムを考える際に対象となるオブジェクト(この例で言えば全域木, マッチング, フロー)に対する「良い」... -
概要 焼きなまし法 は遺伝的アルゴリズムなどと並ぶ最適化問題の発見的解法の一つとして有名であり, 競技プログラミングの文脈ではマラソン(厳密解を求めるのが困難とされる一つの最適化問題に長時間取り組み最も最適値に近い解を得るという種目) においては常套手段の一つとして用いられていま...
0 件のコメント:
コメントを投稿