ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

数式の変形

ABC166 E - This Message Will Self-Destruct in 5s

問題 提出コード 解法 もちろん、ペアを全探索することは難しいです。 ペアとしてカウントされる条件を詳しく見ていきます。 としたとき、カウントされる条件は、 となります。 これを式変形すると... となります。 より小さくて、とペアになれるの個数は、…

ABC107 D - Median of Medians

D - Median of Medians 提出コード 初めてBITを使った問題です。 この問題では、中央値となる条件をうまく言い換えていき、最終的に転倒数を求める問題に帰着させます。転倒数を求める段階で、BITを利用します。蟻本をみたらそこにも載っていた問題になりま…

ARC028 D - 注文の多い高橋商店

D - 注文の多い高橋商店 提出コード 満点を取るには、ほぼでクエリにこたえていかないといけません。 そこで、 ans[i][j] = i番目の品物を使わずにj個選ぶ方法 とすると、与えられたk、xを用いてans[k][m-x]を参照するだけで答えを出すことができます。 まず…

動的計画法における重複組み合わせの式変形について

蟻本に載っている重複組み合わせの式変形がピンとこなかったので、頭の整理をするためにメモを。 問題 種類の品物が存在し、番目の品物が個あるとき、これらの中から個選ぶ組み合わせの総数を求めよ、というものになります。 解法 まずはの解法からです。 番…

ABC101

最近忙しいですがICPCも近いので少しでもプログラミングに触っていたいですね。 A - Eating Symbols Easy 提出コード 0からスタートして、+が出現したら1をたし、-が出現したら1を引いていきます。sの長さの指定をよく見ていなかったので、sの長さだけループ…