CSA Round #69 (Div. 2 only)

こうきやまぐち @Ymgch_K

@Lepton_s あれ、いや、僕が意図していたのは、{a, n + i}, {n + i, b}ですね🙏

こうきやまぐち @Ymgch_K

えーと、正しいのは以下です😭（a-bを新しい頂点cを使ってa-c-bにしているだけです） g[a].push_back(n + i); g[n + i].push_back(a); g[b].push_back(n + i); g[n + i].push_back(b);

こうきやまぐち @Ymgch_K

葉に関する重心を考えるとうまくいく CS Academy 069 D. Cover the Tree - Learning Algorithms learning-algorithms.com/entry/2018/02/…

けんちょん @drken1215

かいた ・CSA 069 B: drken1215.hatenablog.com/entry/2018/02/… ・CSA 069 C: drken1215.hatenablog.com/entry/2018/02/… ・CSA 069 D: drken1215.hatenablog.com/entry/2018/02/… ・CSA 069 E: drken1215.hatenablog.com/entry/2018/02/…

けんちょん @drken1215

もう二度とツリーの重心絡みの問題は落とさないのん

けんちょん @drken1215

ところで、leaf に関する重心分解をすると、適切な操作後には 10 6 4 2 みたいな 2 つ以上の整数が与えられて、異なる2つの整数を選んで 1 を引く操作を繰り返して全部 0 にできるかを問う問題に落ちるわけだけど、ここまで来てもまだ直ちに自明とは思えてないのん……むむむ。。。

けんちょん @drken1215

いや、大きい2つを選んで操作し続ければちゃんと全部 0 になるのは、言われた後には少し考えれば示せるんだけど、初見だと怖くなって手が出なくなりそう。これはもう覚えてしまうしかないかの。

kmjp @kmjp_pc

はてなブログに投稿しました #はてなブログ CSAcademy Round #69 : D. Cover the Tree - kmjp's blog kmjp.hatenablog.jp/entry/2018/02/…

けんちょん @drken1215

DP記事続編として、区間DPとbit DPを書こうと思ってからもう半年が経とうとしているのん… あとツリー DPも。

こうきやまぐち @Ymgch_K

パスの自明な性質（端点のみ奇数次）よりグラフの奇数次点はパスの端点でないとダメで、従って（奇数次点の数）/2本は最低必要で、一方オイラーグラフにするために仮に加える辺の本数がそれと同じ本数なので、オイラー閉路（これはどう繋いでもできる）を作り、仮の辺の部分で切ればこれを達成できます twitter.com/drken1215/stat…

けんちょん @drken1215

奇数次数の頂点はテキトーにつないでしまって全体をオイラーグラフにしてからオイラー閉路を求めて切ればいい、ってところがまたすごいのん！！！！！ 素人考えだと、奇数次の頂点をどう組んだら、うまくつないで行けるようになれるか...という思考の方に行ってしまうん。 twitter.com/Ymgch_K/status…

2018-02-15 22:12:09

kmjp @kmjp_pc

はてなブログに投稿しました #はてなブログ CSAcademy Round #69 : E. The Wall - kmjp's blog kmjp.hatenablog.jp/entry/2018/02/…

けんちょん @drken1215

@Ymgch_K ちなみに、「重複あり・ツリーに限らない一般の無向グラフ」だと、どうなるだろう？？ 大分難しそうだし NP-hard かな？？