お題箱より。 Problem - D - Codeforces 問題概要 人の子供がいて の番号を持っている。以下の 個の操作についてそれぞれ、実行するかしないかを選ぶことができる。 区間 に属する子供に1個ずつキャンディを与える。 ここで整数 が与えられ、 個を超える操作…

お題箱より。 E - Max GCD 解法の正当性について知りたいというリクエストだったので、そこをメインに解説します。 解法 操作によって全ての要素の合計は変わりません。そして操作後の の全要素が値 の倍数であるならば、 の合計値も の倍数であるはずです。…

お題箱より。 Aizu Online Judge Arena 解法 公式解説と逆になってしまいますが、与えられる を改めて と定義します。これが正である頂点は「過剰なので減らす必要がある」、負である頂点は「不足しているので増やす必要がある」ことになり、全ての を にす…

お題箱より。 E - Second Sum 解法 まずは「数え上げの順番をひっくり返す」という発想が大事です。 全ての区間 について、その区間内で2番目に大きい値 を求め、合計する をひっくり返して、 順列内の全ての要素 について、その要素が2番手になるような区間…

イマイチ良い言葉が見つからなかったのでタイトルが長くなりました。最近見る機会が多かったので記事を書いてみます。 以下のような形に帰着されるような区間の数え上げに使えるテクニックです。 例題 以下の2つの数列が与えられる。 左端から見た右端の条件…