2021-10-07

AtCoder Beginner Contest 196　F - Substring 2

そのままSとTをコンボリューションすると下図のようになる

f:id:yagura37s:20211007153136p:plain — 図１

f:id:yagura37s:20211007153200p:plain — 図２

配列の４番目には、S[3]*T[1] + S[2]*T[2]*S[1]*T[3]

配列の５番目には、S[4]*T[1] + S[3]*T[2]*S[2]*T[3]

配列の６番目には、S[5]*T[1] + S[4]*T[2]*S[3]*T[3]

が入っている

これが仮に

配列の４番目には、S[1]*T[1] + S[2]*T[2]*S[3]*T[3]

配列の５番目には、S[2]*T[1] + S[3]*T[2]*S[4]*T[3]

配列の６番目には、S[3]*T[1] + S[4]*T[2]*S[5]*T[3]

であれば、配列の４番目にはS[1..3]とT[1..3]で両方とも１みたいな数値が入っている。

　SかTのどっちかを反転する。

　convolutionをとる(両方とも１みたいな数値を計算）

　SとTの配列の中身をすべて反転する

convolutionをとる(両方とも0みたいな数値を計算)

で答えが出る。

解説見た　難しかった。慣れてたらいけるかも？

2021-09-20

典型９０問　015 - Don't be too close（★6）

(k-1)個のボールを(a-1)回挿入する。
挿入した後、ボールの合計がNより大きくなってはいけないので、
N-(k-1)(a-1)からa個選ぶパターンを考える。
それぞれのパターンで、(1, 2, ...a)番目のボールの内、(2,...a)番目のボールの添字にk-1を加算する。
これは全部相違なるパターンになると思われるからこれでいいという理解であっているのかしら。

むずい　高校数学やりなおそうかしら

2021-09-17

第七回アルゴリズム実技検定　O - コンピュータ

公式解説とか正解コードとかブログとかいっぱい見た

dp[i]= i日目に必要なコンピュータを手に入れるまでに必要な最小の金額

というdpテーブルを作ることを考える

f:id:yagura37s:20210917023100p:plain

dp[0] = 0にしておく

dp[i] = min(dp[j]+B[i] | B[i] <= ( Σ(0~j)A[k] - dp[j]) )

f:id:yagura37s:20210917023535p:plain

後ろを全部調べるとO(n^2)になるので、

B[i] <= ( Σ(0~j)A[k] - dp[j])　←この条件を満たす遷移をmin-outヒープで、

dp[j] ←上のヒープに入っている遷移の中で最小をc++のmultisetで出す

dp[X]を計算した後

ヒープに、 ( Σ(0~X)A[k] - dp[X], 　dp[X] )

multisetに、(dp[X] , Σ(0~X)A[k] - dp[X] )

と、(a, b) (b, a)みたいなタプルを入れる

dp[X+1]を計算する時、

ヒープ中のタプルで,これを(a, b)としたときに、a<B[X+1]なものを取り除き、multisetから(b, a)を取り除く。

dp[X+1] = B[X+1] + (multiset中最小の要素の第一成分)

と更新できる。

むずい

fn solve(){
let sssss = std::io::stdin();
let mut sc = Scanner { stdin: sssss.lock() };
let mut N:usize =sc.read();
let mut A = vec![0i64;N+1];
let mut B = vec![0i64;N];
for i in 0..N{
A[i+1] = sc.read();
B[i] = sc.read();
A[i+1]+=A[i];
}
let mut h = BinaryHeap::new();
let mut m = MultiSet::new();
let mut ma = -1;
h.push*1;
m.insert*2;
let mut dp = vec![0;N+2];
for i in 0..N{
if B[i]<=ma{
B[i] = ma;
}
else{
ma = B[i];
}

while(h.len() != 0){
let mut t = h.pop().unwrap();
if -(t.0)<B[i]{
m.remove(&(t.1, -t.0));
}
else{
h.push(t);
break;
}
}
if m.set.len() == 0{
println!("-1");
return;
}
let mut mm = m.get_min().unwrap();
dp[i+1] = B[i]+mm.0;
if i != N-1{
h.push*3;
m.insert*4;
}
}

println!("{}", A[N]-dp[N]);

}

*1:-A[1], 0

*2:0, A[1]

*3:-(A[i+2]-dp[i+1]), dp[i+1]

*4:dp[i+1], A[i+2] - dp[i+1]

2021-09-07

典型９０問　 073 - We Need Both a and b（★5）

グラフDPをする

dp[i][j] = (i=0 なら、jが所属している連結成分はaのみで出来ていて、それ以外の連結成分はaとbで出来ている

i=1なら、jが所属している連結成分はbのみで〜〜〜

i=2なら、jが所属している連結成分はaとbから〜〜〜

今見ているノードがaの時、状態の全体（i=0 or i=1 or i=2)は

子がa:

エッジを引く　ー＞　子の状態が、i=0 or i = 1 or i = 2

エッジを引かない　ー＞　子の状態が、i=2　（子の状態がi=0 or i=1のときにエッジを引かないと、すべての連結成分がaとbを含むという制約を満たさない)

　　　全部でdp[0]+dp[1]+dp[2]*2

この内、親の所属している連結成分にaのみ含まれるようになる状態は

dp[0] +dp[2] (エッジを引いたときに子の状態がi=0と、引かないときのi=2)

子がb:

エッジを引く　子の状態が、i=0 or i = 1 or i = 2

エッジを引かない子の状態が、i=2　（子の状態がi=0 or i=1のときにエッジを引かないと、すべての連結成分がaとbを含むという制約を満たさない)

全部でdp[0]+dp[1]+dp[2]*2

この内、親の所属している連結成分にaのみ含まれるようになる状態は

dp[2]

今見ているノードがbの時、〜〜〜

全部からaのみになるやつを引くと、aとbを含むやつが計算できる

aとbを含む奴を計算して、全体から引いてaのみを計算するようにしてみる

v0 = 今見ている部分木が、aかbどっちかしか含まないようになる or 両方含むようになる　パターン

v1 = aかbどっちかしか含まないようになる　パターン

v0-v1が i=2の答え

fn dfs(s:usize, bef:usize, g:&Vec<Vec<usize>>, dp:&mut Vec<Vec<usize>>, c:&Vec<char>){
let mut all = 1;
let mut v0 = 1;
let mut v1 = 1;
for i in &g[s]{
if *i == bef{
continue;
}
dfs(*i, s, g, dp, c);
if c[s] == 'a'{
if c[*i] == 'a'{
all*=(dp[0][*i]+dp[2][*i]*2%MODu)%MODu;
all%=MODu;
v0 *= (dp[0][*i]+dp[2][*i]*2%MODu)%MODu;
v0 %= MODu;
v1 *= (dp[0][*i]+dp[2][*i])%MODu;
v1 %=MODu;
}
else{
all*=(dp[1][*i]+dp[2][*i]*2%MODu)%MODu;
all%=MODu;
v0 *= (dp[1][*i] + dp[2][*i]*2%MODu)%MODu;
v0 %= MODu;
v1 *=dp[2][*i];
v1 %=MODu;
}
}
else{
if c[*i] == 'a'{
all*=(dp[0][*i]+dp[2][*i]*2%MODu)%MODu;
all%=MODu;
v0 *= (dp[0][*i] + dp[2][*i]*2)%MODu;
v0 %= MODu;
v1 *=dp[2][*i];
v1 %=MODu;
}
else{
all*=(dp[1][*i]+dp[2][*i]*2%MODu)%MODu;
all%=MODu;
v0 *= (dp[1][*i]+dp[2][*i]*2)%MODu;
v0 %= MODu;
v1 *= (dp[1][*i]+dp[2][*i])%MODu;
v1 %=MODu;
}
}
}