2020-10-01から1ヶ月間の記事一覧
D - Powers 解法 である全てのペア について、【 と について対称な式】の値を合計せよ。 という問題設定はよく登場します。このような問題では、 という条件を外して かつ である全てのペア について、【 と について対称な式】の値を合計せよ。 と考えると…
B - Bracket Score 解法 正しい括弧列の必要十分条件 いわゆる「正しい括弧列」の問題です。よく使われるアプローチとして累積和がありますが、今回は括弧が2種類あるので2つの累積和を管理する必要があり厳しそうです。 今回は別の性質を使うことにします。…
D - Pocky Game 解法 各山の石の個数について、その初期値を と表し、ゲームの途中経過における値を と表すことにします。 まずは全ての状態を網羅するDPを もし石の総数が十分少なければ、以下のDPで全ての局面の勝敗状態を求めることができます。 :「先手…
先日のコンテストの問題における、最後の高速化について知りたいというリクエストがあったため、解説を書きます。より一般的な「個数制限付き部分和問題+条件を満たす選び方の数え上げ」という枠組みで説明します。 扱う問題 正整数 と、正整数からなる長さ …
E - Random LIS 公式解説とは違う解法です(たぶん)。 解法 あり得る全ての場合に対するLISの長さを合計して、全事象数 で割ることにします。 取っ掛かりが非常に掴みにくい問題ですが、 という制約から何らかの全探索をやることを目指してみます。 座標圧…