Codeforces darkshadows's blog 「DP on Trees Tutorial」Problem 2の続編です。 codeforces.com 問題３． 「頂点数nの木が与えられたとき、頂点がk個以下のサブツリーの数はいくつあるか？」 ここでいう「サブツリー(sub tree)」は、今まで使っていた「部分…

codeforces.comCodeforces darkshadows's blog 「DP on Trees Tutorial」Problem 1の続編です。 問題２． 「頂点数がnの木の直径を求めよ（木の直径とは、木の異なる2頂点間の距離の最大値です）。」 木全体の根を頂点1とし、ある頂点xに着目してみましょう…

codeforces.com 木に関する考察や操作がいまいちなので、今まで解いた問題含めて復習です。 内容はdarkshadowsさんが書いてくれた木DPの記事の（自分用）まとめです。 基本的に引用記事を和訳したものとなっています。 全部で問題1~5があり、本記事は問題1の…

Problem - D - Codeforces 問題概要は 「n個の模様を円形にならべたカルーセルについて、隣り合う模様が異なるときは違う色に塗る。このとき使用する色の最小数と、その塗り方を答えよ」 というものです。ちなみにカルーセルはメリーゴーランドという意味の…

atcoder.jp 全探索系の問題ですが、競プロ初心者はかなりとっつきにくい問題だと思います。 僕もこの問題の解法を見たときは衝撃を受けました（？）「竹の長さを変える魔法」と「2本の竹を1本に合成する魔法」がありますね。 竹の長さを変えるだけであれば、…

atcoder.jp実装に工夫が必要な問題として認識されているようです。 実際、この問題を解くときに引っかかるポイントは 「県ごとに、市が誕生した順番を整理（座標圧縮）する必要がある」 という点です。 座標圧縮の方法としては①値をset等で管理⇒sort⇒lower_b…

最近トゥイッターをやってると面白い記事がたくさん回って来ますが、読まずに忘れてしまった！なんてことがないようにまとめることにしました。 記事の並び順には特に意味がありません。良かったら見ていってください。 「最短経路問題特集！！！～BFSから拡…