E - Gluttony 解法 この問題はいくつか考察ステップが必要なので、順に見ていきましょう。 記法などについて 簡単のため、入力として与えられる値の集合 を単に 、 を単に と書くことにします。 また、最小化すべき値である「メンバーと食べ物の組み方を決め…

お題箱より。 Problem - D2 - Codeforces 問題概要 整数を端点とする 個の閉区間 が与えられる。これらから0個以上の区間を捨てて、全ての整数点について「その整数点を含んでいる区間は 個以下である」という状態にしたい。 捨てる区間の最小個数と、その選…

お題箱より。 E - 根付き森二人用ゲーム 解法 それぞれの木を小規模なゲームとして解く スタート地点からある木に移動し、その木の葉に到達してスタート地点に戻るまでの一連の動作を考えます。このときゲームに本質的に影響するのは「次にスタート地点で手…

Problem - B - Codeforces 問題概要 長さ の括弧列 が与えられる。長さ の括弧列のスコアを、「 を 回だけ右巡回シフトした文字列が正しい括弧列になっている」という条件を満たす の個数とする。 に対して1度だけ、2箇所を選んでスワップする操作を行うこと…

F - Distinct Numbers 解法 色々な解法があるみたいですが…この記事ではそれぞれの について独立に解きます。ある について解くときには、可能な操作回数には単調性があるので二分探索できます。 ある と操作回数 を固定したときに、操作を 回行えるかどうか…

お題箱より。 E - guruguru 後半は公式解説と少し違う方法になっています。 解法 お気に入りで節約できる回数を定式化する ある1つの に対する から への移動を考えます。まず簡単のため、 と仮定しておきます。移動元と移動先をそれぞれ と書くことにします…

Problem - E - Codeforces 問題概要 以下の条件を満たす根付き木を二分探索木と呼ぶ。 任意の頂点 について以下が成り立つ。 「左側の子」と「右側の子」がそれぞれ高々1個存在する。 左側の子孫が存在する場合、それら全ての頂点番号は より小さい。 右側の…

お題箱より。 Problem - E - Codeforces Editorialのソースコードがよく分からないというリクエストだったんですが、見たところ確かによく分からなかったので、私の解法を書きます。 問題概要 長さ の順列 を と定義する。 長さ の整数列 （）が与えられる。…

お題箱より。ただ、この問題は元々書こうと思っていました。 Problem - E - Codeforces 問題概要 文字のアルファベットからなる長さ の文字列 が与えられる。アルファベット 個を並べる順列 を1つ決めた時、「 の隣り合う2文字のペアそれぞれについて、その…

お題箱より。同じ問題に2件リクエストがありました。 C - Maximize Minimum 簡潔に飛ばし気味ではあるものの公式解説の説明が分かりやすいと思うので、流れは公式解説に沿いつつ図や行間を補って書いていきます。 解法 イチゴの最適な折り返し方 まずクエリ…

お題箱より。 Programming Problems and Competitions :: HackerRank 解法 分数のままでは考えにくいので、通分します。 の最大公約数は なので、まず重りを全て 倍して とします。そして目標の重さも に置き換えます。するとこの問題は「重さ の重りをそれ…

お題箱より。 D - Mixing Experiment 半分全列挙解法を…とのリクエストだったので、そちらを書きます。 解法 個の薬品をグループ0・グループ1に分け、それぞれについて薬品の選び方を決めたとします。これらを混ぜてちょうど混合比 になっているかどうかを判…