木の直径のパスを一つ挙げるライブラリ 木の直径のパスを一つ挙げるやつをライブラリ化しました。これを解いている時に必要になって、自明なのに妙に実装に時間がかかったので作りました。この問題でverify済みです。中のアルゴリズムは非常に簡単で、次の通…

Educational Codeforces 035 div.2 F. Tree Destruction Problem - F - Codeforces 解法 まず直径をできるだけ残しておくべきであることがわかります。なぜなら、直径を残している間は、それ以外の辺を破壊していくときに、その辺を破壊したときに得られる最…

CS Academy 062 E. Tree Partition CS Academy 解法 なんらかの方法によって、各部分木の頂点集合とその補集合が即座にわかればよさそうです。しかし各ノードに部分木の頂点集合のsetを持たせるのはさすがに厳しいです。そこで、各頂点に乱数を割り振って、…

CS Academy 061 F. Xor the Graph CS Academy 解法 これを読んでいるとこの解法がかなり自然に見えます。まず明らかに同じ辺を3回以上使うメリットはありません。そのような構造は、パスの個数を増やすことなく、パスの長さを小さくできるからです。すべての…

平面上のロシアゲー（構築ゲー）を解くためのそこそこ一般的なテクについて この記事はCompetitive Programming Advent Calendar 2017の12月13日の記事です。 ロシアゲーとは 「ある条件を満たすものを何でもいいから一つ出力しなさい」という形式の問題のこ…

CS Academy 060 E. Flip the Edges CS Academy 感想 DPの書き方がよくわからなかったので、pekempeyさんより解説をいただきました。 解法 まず二度以上選ぶ辺は存在しないことが言えます。なぜなら、もし仮にそのような部分があるとき、そのような部分は反転…

この記事はCompetitive Programming Advent Calendar 2017の12月8日の記事です。 競プロにおけるオイラー路とその応用について 目次 ・はじめに ・オイラー路とは？ ・無向グラフのオイラー路 ・有向グラフのオイラー路 ・無向オイラー路の構築 ・有向オイラ…

CODE THANKS FESTIVAL 2017 参加記 CODE THANKS FESTIVAL 2017 - AtCoder 前日 前日はボードゲームの会に参加しました。会う予定の人は全員初対面だったため、もちろん緊張でヒザがガクガク震えていました。Tikeさん、TsutaJさん、フェリンさん、らてあさん…