2021/02/14
楽しすぎる家庭菜園
unrated
最大全域木(造語？)
南極
unrated
ダイクストラで解いた。マス(h,w)から(nh,nw)に移動する時、A(nh,nw)!=0 and A(h,w)!=A(nh,nw)の場合はコストがC(A(nh,nw))かかるとした。それ以外はコスト0。
通学路
unrated
親の顔より見た拡張ダイクストラ。
総入れ替え
unrated
メモ化dfs。mapでメモをするとTLEになったので生配列でやった。
連呼
unrated
解けなかった。dpか？O(min(N,M)*(N+M))だから無理→ほうじょでもなさそう→組み合わせか？分からんって感じだった。結論から言うと組み合わせだった。できる文字列は以下を満たす。
①A...AB...BA...AB...B(グループは2*k個)
②A...Aの長さは1or2 長さの総和はN
③B...Bの長さは1以上 長さの総和はM
kを全探索する。②は「A...Aの長さは0or1 長さの総和はN-k」と言い換えると式が立てやすい。③も同様。
ライ麦畑で待ちながら
unrated
セグ木を使う。型はpair(数字、その数字の右側にある記号(+ or *))のvectorにした。あるノードのvectorのサイズは高々3なので計算量は大丈夫そう。マージの実装に手間取った。↓のようにすると書きやすかった。
vector<T> ret;
if(A.size()==0) return B;
if(B.size()==0) return A;
for(auto b:B){
if(A.back().second=='*'){
A.back().first*=b.first;
A.back().second=b.second;
}else{
A.push_back(b);
}
}
ModInt sum=0;
for(int i=1;i+1<A.size();i++){
sum+=A[i].first;
}
if(A.size()<=2) return A;
ret.push_back(A[0]);
ret.push_back(T(sum,'+'));
ret.push_back(A.back());
return ret;
};
根室の巫女
unrated
kmp法で作られるテーブルが与えられて、元の数列を復元する問題。
分からなかったから解説を見たけど、よく分からなくて結局自分で考えた。
A[1~i-1]は分かっていると仮定して、A[i]を考える。↓をして問題ない。
①i<=B[i]:あり得ないので"No"を出力してプログラムを終了
②0<B[i]<i:A[i]=A[B[i]]
③B[i]=0:A[i]=今までに使ってない数字
③が駄目な場合は、j>=i and B[j]>=(j-i+1)となるjが存在する場合。その場合は、B[i]が正の値になっているはずなので存在しないことが分かる。
最後に解が正しいかをkmp法を使って判定する。
「ここはこの値で問題ない」を繰り返して解を作って、最後にその解が正しいのかを判定する流れ、構築でよくありそう(適当)。
日記
いろはコンDay2の残りを埋めた。
