E - Golf 解法 コの字の作り方を考えてみる まずは考えやすい＆実装しやすいように座標変換をします。 に負の値がある場合、符号反転させて両方とも非負としておきます。 始点 から終点 までボールが移動する軌道は、長さの総和が の倍数になっている必要が…

F - Permutation Oddness ※問題文で与えられている は小文字ですが、 を添え字として使いたいので本記事では と表記します。 解法 順列のDP 順列の場合の数を求める問題です。何か条件を満たす数列の個数を求める問題として「左からDP」というのはメジャーな…

D - 9 公式Editorialと違う解法で解いたので記録。 計算量多めのゴリ押し解法なのでRuby・PyPyでは通りませんでした… 解法 まず桁DPを考えました。以下のように状態を考えることができます。 上から 桁目までの数字まで決めて、そこまで決めた値を で割った…

お題箱より。 E - Mogu Mogu Gummi 解法 木DPを考えてみる 「連結成分の個数」よりも「切った辺の本数」のほうが遷移を組みやすいので、そっちで考えます。連結成分の個数は切った辺の本数に1を足したものです。 シンプルなグラフを例にして考えてみましょう…

お題箱より。 B - PackDrop 解法 まずは問題をシンプルに みたいなのがややこしいですね。まずは問題をシンプルに言い換えましょう。 ネットワーク全体は機器を頂点、その間を接続する経路を辺とするグラフとみなせます。より具体的には機器0を根とする根付…

Problem - C - Codeforces 問題概要 0または1からなる 文字の文字列 と整数 が与えられ、それを用いて2人がゲームをする。交互にターンが回り、それぞれのターンで各プレイヤーは「連続する 文字を選び、それらを全て0または全て1にする」という操作を行う。…

F - Colorful Tree 解法 木の2点間距離たくさん→LCA 長さの変更についていったん無視すると、この問題は「木の2点間距離をたくさん求めてください」というものです。これはLCA（最小共通祖先）というものを用いると効率的に求めることができます。 根付き木…

お題箱より。 E - MUL 解法 私自身、この問題は解説を読んで衝撃を受けた記憶があります。知らないと自力で思いつくのは相当難しいので、テクニックとして覚えてしまいましょう。 先人の知恵 競プロでは俗称「燃やす埋める問題」と言われている問題カテゴリ…