atcoder.jpえ〜、なんかすぐ出来た。括弧列であることと、(の個数と) の個数が同じで、さらに前から部分列を取得したときその部分列において( の個数が )の個数以上であることは同値である。 また、追加する個数が同じとき、(は先頭、)は末尾に持ってきても(…

atcoder.jp問題を見てダイクストラ法ですかねと思い、ダイクストラ実装…してから気づいたけどよく考えたら最長経路問題だった。部分構造最適性が成立していないのでダイクストラ法みたいに計算量少なくは出来なかった…（色々考えた）辺の値全てに-1をかける…

atcoder.jp前回のやつより簡単だった（ただのナップサック問題で考察がほとんどいらないただのDPだったので） 何個選ぶか決めた時、価値の平均値が大きい順は価値の合計値が大きい順と同じ。合計を保持するDPを作って、最後にそれを個数で割って平均値を出し…

ところでD問題って（n年前の感覚としては）普通に解けるような感覚でいたけど結構厳しい 精進をn年もサボっていたせいですねatcoder.jp二通りのやり方で解きました。半分全列挙全探索すると2^40かかる。 半分全列挙すると2^21かかる。難しいこと考えずにこれ…

コンテストの時だけ思い出したように進捗を生むのも良くないと思うので、精進をしようと思います。なお、証明とかがガバガバかもしれませんのでご了承ください。現在の私にとっては、苦手だったり勘違いしなければコンテスト時間内に、そうでなくても時間を…