Open18
青diff 精進木
とりからABC397 F Variety Split Hard
- 1つの区間を固定して、残った区間を2分割したときの種類数の総和を高速に求められればよい
- 左からi個とった区間を2分割し、残りの右の方は1つの区間として採用することを考える
- 右側はC問題と同じく、端っこから順に見て初めて出てきたものを数えあげることで構築可能。これを前計算し、i番目より右の区間の種類数をr(i)としておく
- 左側についても、端っこから見て行く
- ある数が種類数の総和に効くのはたかだか2
- 初めて出てきたときは、分割をどうわけても種類数の総和に常に寄与
- 2回目以降に出てきたときは、区間の両方にわけて存在させられれば総和に寄与する
- そんな分割は一つ前に出てきたとき〜今見てるところの間に分割する場合
- i個目まで見たとき、そこまでの種類数の総和のmaxを求めたい
- 区間加算と区間maxがとれればいいので遅延セグ木を用いる
- [0,l)[l,i]で分割するlのmaxを求めるものとして、各lで分割したときの種類数の総和を遅延セグ木に乗せる。各aを見た時の操作として、初めて出てきたときは0〜nまでの区間に1加算、2回目以降に出てきたときはlast+1〜iの区間に1加算すればよい
- 空の区間を分割に含めても、i以降の項を含めても、求める最大値を越えることはないので、最大値取得は0〜nまでで適当にやってもよい
- 簡単にメイン所のコードを記載するとこんな感じ
rep(i,n){
if(last[a[i]]==-1)seg.apply(0,n+1,1);
else seg.apply(last[a[i]]+1,i+1,1);
ans=max(ans,seg.all_prod()+r[i+1]);
last[a[i]]=i;
}
ABC407F Sums of Sliding Window Maximum
- あるa[i]の寄与を考えたい気持ちが自然と湧くので、区間内でa[i]が最大となるような区間を考える
- a[i]より左で初めてa[i]より大きいものと、a[i]より右で初めてa[i]より大きいものを探せば、その間の区間ではa[i]が最大
- これを前からと後ろからの2回の計算で、スライド最大値のようなイメージで求める
- priority queueを使う。各a[i]を見て、それより小さいものがqueueの先頭なら先頭要素のインデックスの箇所にiを記録してpop。a[i]とiのペアをpushとすれば求まる。計算量はO(nlogn)で十分高速
- こうして作った区間の長さkの連続部分列でa[i]を含むものの数がkの場合のa[i]の答えへの寄与
- さて何個あるかを数える。k=1であれば1個なのは自明。2,3と増えてった時に両端(l,rとする)を気にしなければ同じく2,3個と増えて行く。この増加はk=min(l,r)に至ると止まって、その後は同じ数のままk=max(l,r)まで推移し、その後0に向けて1ずつ減って行くということが、区間をスライドするイメージを持つことで思い浮かぶ
- 愚直にこれを計算すると、制約に間に合わないので、imos法で端点だけいれておいて、最後にn点分まとめて累積和をとることで高速化を図る
- imos法について、端点いれて2回累積和とると等差数列が作れるのはすぐにわかる
と、こんな感じだけど、実装においては以下の点でかなり手こずった
- imos法の端点のindexでバグらせた。kが1-indexなのに、0-indexで考え直して計算したせい。拘らなくてもよかったかもしれない。余裕を持って領域とって適当にやればよいかも
- 最大値の一意性について、上ではごまかして書いているが、ある区間に同じ数字が入って、かつその数字が最大となるようなケースを漏れなく、ダブりなく数えなくてはいけない。前からと後ろからで「a[i]より小さいなら」って書いてる部分について等号を片方は入れて、片方は入れないことにして、同じ数字にある意味での順序付けをすることで回避した(どちらも等号入れるとダブるし、どちらも不等号だと漏れる)
- サンプルが優しかったので気づけたけど、サンプル通ったあと、WA出してたら気づくのに時間がかかりそうだった
とりから解説の、先にindexをふったペアで持って降順に並べるやりかた、同じ数字の順序付けもできるし、左右を一度に計算もできて賢い
imos法で求めたところ遅延セグ木に乗るらしい。それはそうだが実際乗せたことはなかったので気づき
とりからABC387F Count Arrays
- 各iに対してA[i]が対応するので、どこかでループすることがわかる
- すなわち、この問題は、サイクルからいくつか足が出ているようなグラフがいくつかあって、その各頂点に設定可能な値のパターンを数えあげればよいとわかる
- 連結成分毎に独立に考えてよいので、union findで連結成分を分離して、それぞれの連結成分の答えの積が最終的な答え
- 不等式を考えるとサイクルの中の値は全部同じでなくてはいけない
- サイクルを縮約して、ここを根とした根付き木としてみたとき、親から子に対しては、子は親以下の数字にならなくてはいけない
- 数え上げで子の向きに伝播していくのはうまくないので、親の向きに集約していくことを考える。つまり上のことを逆に読んで、親は子以上の数字にならなくてはいけないとしてデータを集める
- 親の値がiとなる通り数は、各子の値がi以下であるような通り数の積となるので、累積和を使って戻りがけ順に求めればよい。最終的に根の値がM以下となる通り数がこの連結成分の答え
- 考察自体はすっきりできたが、実装上の根付き木の構成に少し手間取った
- 最初にunion findでマージしてる時に同時にA[i]からiの向きに辺を張る。
- union findから適当に一点(s)をとり、sをA[s]で置き換えることを十分数行うとsはサイクルにいる、サイクルにいるかどうかのブール配列をもって、sから一周サイクルを回って更新。
- 縮約した後の根を超頂点としてもたせて、union findの各点が、サイクルになくかつ次の点がサイクルであるようなとき、超頂点からその点に向けて辺を張る
- このようにして木を構成した
- バグらず実装できたのは大きかった(前にmint使ったとき1000000007だったので、エイリアスそのままになってて1WA出したのはご愛嬌)
- メイン部分のコードは以下
int main(){
INT(n,m);
VC(int,a,n);
vvi b(n*2);
dsu uf(n);
rep(i,n){
a[i]--;
uf.merge(i,a[i]);
b[a[i]].pb(i);
}
vvi gr=uf.groups();
int l=len(gr);
mint ans=1;
auto f=[&](auto f,int cur)->vc<mint>{
vc<mint> ret(m+1,1);
ret[0]=0;
each(nxt,b[cur]){
vc<mint> res=f(f,nxt);
rep(i,m+1){
ret[i]*=res[i];
}
}
rep(i,1,m+1){
ret[i]+=ret[i-1];
}
return ret;
};
rep(i,l){
int st=gr[i][0];
rep(n+1)st=a[st];
vc<bool> cycle(n,false);
while(!cycle[a[st]]){
cycle[a[st]]=true;
st=a[st];
}
each(e,gr[i]){
if(cycle[e])continue;
if(cycle[a[e]]){
b[n+i].pb(e);
}
}
vc<mint> t=f(f,n+i);
ans*=t[m];
}
out(ans.val());
}
ABC386F Operate K
- 解けずに解説を見ました
- 編集距離をグラフに落とし込むという発想がなかったので、これまでイメージつきにくかったところの見通しがよくなった
- このグラフによってDPがすごくイメージしやすくなったので、遷移をK以内に限定してやるところはすぐに腑に落ちた
- 実装上は2個目の添え字jがiからの相対距離になってること+kズラして考えてることにより頭をバグらせてしまい、かなり時間がかかった
- 頭の悪い解決として、今見てるのがi+j-k文字目だとコメントを書いて乗り切った
- 解説のうち高速化については実装してみてはないので、今後の課題
とりからABC385F Visible Buildings
- 誤差が本質
- 問題自体は隣り合うビルをチェックするだけで十分であることがすぐわかる
- これは仮に離れたビル間が見えなくなっているとき、その間のビルはもっと見えなくなっている、またはその間のビルがもっと邪魔してるかのどちらかであることが簡単にわかるため、帰納的に近づけていくしかないということ
- 誤差は当然のように1WAを出してから、極力整数でもたせて、最後に割り算の部分だけでdoubleにするという小手先テクで切り抜けた
- これで大丈夫なのかは未証明だけど、これでダメだったら通りようがないだろうとも思っている
とりからABC384F Double Sum 2
- 高速化を念頭におくとbit的な考え方がわく
- ちょうど
2^k - ちょうど
2^k 2^k - ちょうど
2^k 2^k 2^{(k+1)} - ここまで考察すれば、各kにおいて、
2^k 2^k - 同じ項2つを選べることに気づいておらず一敗しかけた(サンプルに助けられる)
- mapを使ってTLEし、unordered_mapにしてAC
- 計算量からは間に合う想定O(NlogNmax(logAi)) だったんだけど、mapの定数倍が重いのか、めんどくさがって何度も剰余計算させたり、logA[i]を計算せずに余裕をもった幅で設定したりしてるのが悪いのか
int main(){ INT(n); VC(ll,a,n); vl v; rep(b,30){ ll k=(1LL<<b); unordered_map<ll,ll> c,s; rep(i,n){ ll r=a[i]%k; c[r]++; s[r]+=a[i]; } ll res=0; rep(i,n){ ll r=a[i]%k; ll rd=(k-r)%k; res+=c[rd]*a[i]; res+=s[rd]; c[r]--; s[r]-=a[i]; } v.pb(res); } ll ans=0; rep(i,29){ ll res=v[i]-v[i+1]; res>>=i; ans+=res; } out(ans);
}
ABC383E Sum of Max Matching
- 頂点が多すぎて、具体的なABのマッチングを構成する方針は厳しいだろうと感じる
- 重みの小さな辺から使って連結となったABのペアを即採用する貪欲を考える
- 後からやっぱり別のペアと組んだ方が得かということを考えると、結局その後から入ってきた重い辺+今以上の辺で新しいペアを組まなきゃいけないから、上の貪欲より得をすることはないことがわかる
- union findを使って、連結成分のもつAの個数とBの個数を管理しながら順にグラフを構築していけばいい
- 結構素直に解けた
とりからABC383F Diversity
- 盛大に誤読して、同じ商品を複数個買えると思っていたので、必要以上に複雑な解き方をしているかも
- 本質は色でソートすることで保持する情報を減らすこと
- 最後に買った色lcを-1で初期化
- lc未満の色の商品からi円以下を使って得られる最大の効用を表す配列を用意(コードではlast)
- 今見てる商品と同じの色(nc)でそれ以前に出てきた商品を1個以上買う前提でi円以下を使って得られる最大の効用を表す配列を用(コードではcur)
- 今見てる商品まで含めてi円以下使って得られる最大の効用を表す配列を用意(コードではnxt)
- nxt[i]をi=1から昇順で次のmaxで更新
- 今見てる商品を買わない場合:max(last[i],cur[i])
- 今見てる商品を買う場合:max(last[i-p]+u+k,cur[i-p]+u)
- i円以下での最大にするため、nxt[i-1]とのmaxをとる
- curをnextに置き換える。このとき実はcurには色ncの商品を買ってないパターンも入りうるが、特に問題にならないので放置
- lcをncで更新
- 次の色を見て、以前の色と異なっていれば、lastを各項についてlastとcurのmaxで置き換える。このあとcurは0で初期化しなくても問題にならないので放置
- ちなみに誤読したままの解は、next[i]への遷移についてnext[i-p]+uとのmaxもとればよいと思う
- 計算量はO(NX)なので問題なし
- こんなDPに名前はついていますか？ナップサックの一種ですかね？
int main(){ INT(n,x); LL(k); vc<pill> v; rep(n){ LL(p,u);INT(c); v.pb(mp(c,mp(p,u))); } SORT(v); int lc=-1; vl last(x+1,0); vl cur(x+1,0); rep(t,n){ int nc=v[t].fi; if(nc!=lc){ rep(i,1,x+1){ last[i]=max(last[i],cur[i]); last[i]=max(last[i],last[i-1]); } } vl nxt(x+1,0); auto [p,u]=v[t].se; rep(i,1,x+1){ nxt[i]=max(last[i],cur[i]); if(i>=p){ nxt[i]=max(nxt[i],last[i-p]+u+k); nxt[i]=max(nxt[i],cur[i-p]+u); } nxt[i]=max(nxt[i],nxt[i-1]); } lc=nc; swap(nxt,cur); } out(cur[x]);
}
スマホで解いてるから、インデントがたがただな、、、
とりからABC372F Teleporting Takahashi 2
- 移動のほとんどがスライドなので、一つrotateすれば効率的に計算できる
- rotateは物理的にやる必要はなく、始点となる点のインデックスだけ管理して1動かせばいい
- 円環になってるのでインデックス管理はmodで
- 残りのM本の辺の文は愚直に動かす
- 最初かっこをつけて、M本の依存関係を考えた上で、適当な順番で直接遷移させようとしたが、頑張ってDAG作ったのにバグってて涙
- 結局普通に一回退避させて、後から足しました
- これをインラインDPって呼ぶのだと解説から学んだ
とりからABC369F Gather Coins
- HWが大きいので愚直にグリッド移動はできない
- コインのある位置に行く順番だけを把握すれば間をDとRで埋められる
- あるコインから見たとき、自分より左上にあるコインからなら来れる
- サイズwの配列を0で初期化して、(r,h)の昇順でコインを見て行って、配列のうちh以下で最大の要素+1で配列を更新していけばいい(自分より上のコインは更新済で、h以下を見ることでそのうち自分より左のものを選ぶ。同行のコインも左から順番に探索されてるから問題ない)
- このmaxをとる操作はsegment treeの出番
- 更新したときに、そのコインの座標と通ってこれるコインのmaxをvectorに放り込んでおくと復元が楽
- このとき復元の終点として(0,0)を入れておくとよい
- 答えとなる枚数をansとしたとき
- vectorをこのコインのmaxの降順でソートして、(n-1,n-1)を視点にansから1ずつ小さくして行きながら、値が合致して、かつ自分より左上にある座標まで移動しながら現在地を更新していけば復元できる
とりからABC368G Add and Multiply Queries
- 解けずに解説をチラ見しました
- 制約の活用方法が秀逸。どうやってもr-lかかると思って困っていたが、制約から一方の操作が行える回数が高々60回にも満たないことがわかる
- こうなれば実装は簡単。Bを使う候補はB>=2となる位置だけで、lから見て最も近いBの採用候補までAの和をとってvに加算し、Bの位置ではAを加算するかBを乗じるか大きい方をとって、lの位置をここに更新というのを繰り返せばいい
- Aが動的に変更されることからこの区間和はsegment treeでとった
- Bの採用候補は、B>=2となるインデックスをsetに入れておいてlからのupper_boundで発見する
- Bの更新時もこのインデックスのセットを更新すればいい
- このsetには番兵でnを入れとくと楽
- 一個前に解いた問題のセグ木が残ってたのでopを適当にいじったら、引数がintのままでオーバーフローさせるという新たなWAの形に困惑した
- mainのコードは以下
int main(){
INT(n);
VC(ll,a,n);
VC(ll,b,n);
set<int> id;
rep(i,n)if(b[i]>=2)id.insert(i);
id.insert(n);
segtree<ll,op,e> seg(a);
INT(q);
rep(q){
INT(t,i,j);i--;
if(t==1){
seg.set(i,j);
}
elif(t==2){
if(id.contains(i))id.erase(i);
b[i]=j;
if(j>=2)id.insert(i);
}
else{
ll v=seg.get(i);
if(i+1==j){
out(v);continue;
}
while(i+1<j){
int nxt=*id.ub(i);
nxt=min(nxt,j-1);
v+=seg.prod(i+1,nxt);
v=max(v+seg.get(nxt),v*b[nxt]);
i=nxt;
}
out(v);
}
}
}
ABC366F Maximum Composition
- 基本はただのナップサック
- ただし選ぶ順序に優劣がある
-
f_{i}(f_{j}(x)) f_{j}(f_{i}(x)) (A-1)/B - なので、(A,B)のペアを配列に放り込んで、上の式で評価して昇順に並べたあと、その順番でナップサックDPをすればよい
とりからABC364F Range Connect MST
- 素朴にクラスカル法のようにコストの低い辺から張っていって最小全域木を構成しながらコストを計算したい
- あるn+iからはL→Rの間の全てに辺を張るので、次以降L→ Rの区間は縮約しておくことで、結局O(n+q)で辺を張れる
- 具体的な縮約としては、0〜n-1の各頂点について、属している区間の右端を保持して、次回以降は各点に辺を張ったら次はその右端まで飛ぶというやり方をする
- 連結性はunion findで管理
- main部分のコードは以下。解説と実装は違うけどコンセプトは似ているかな
int main(){ INT(n,q); vc<pair<ll,pii>> v; rep(q){ INT(l,r);l--; LL(c); v.pb(mp(c,mp(l,r))); } vi rg(n+q); rep(i,n+q)rg[i]=i+1; dsu uf(n+q); SORT(v); ll ans=0; rep(i,q){ auto c=v[i].fi; auto [l,r]=v[i].se; int cur=l; while(cur<r){ if(!uf.same(cur,q+i)){ uf.merge(cur,q+i); ans+=c; } int nxt=rg[cur]; rg[cur]=r; cur=nxt; } } if(uf.size(0)!=n+q)out(-1); else out(ans);
}
ABC363F Palindromic Expression
- どうせ答え候補が少ないから適当に全部列挙して評価する典型
- あるNに対して答えをみたすなら、N自身か、「x*(N/xyの時の答え)*y」の形に限られる
- 作れるのに長さが1000を超えることは考えなくていい。2べきが長くなりそうだが、それでも制約の中で1000文字を超えるなんて到底ありえないだろう
- ということで、再帰で解くことが思い浮かぶ
- このx,yの候補がめちゃくちゃ少ないことを思えば(約数ですら大した数ないのに、さらに相当厳しい制約をかけるので)、先に列挙した上でかなり緩い評価で計算していっても間に合いそう
- 実際、以下のようなコードで候補の2乗に加えてsetをいじるような重そうなものでも爆速で通る
- メモ化や一個答え見つけたらbreakとかで地味に高速化を図る
- 適当に補助関数を用意して解く
bool is_palin(ll x){
str s=to_string(x);
str t=s;
REV(t);
return s==t;
}
ll to_palin(ll x){
str s=to_string(x);
REV(s);
ll ret=stoll(s);
return ret;
}
bool is_cont_zero(ll x){
while(x>0){
if(x%10==0){
return true;
}
x/=10;
}
return false;
}
int main(){
LL(n);
set<pll> v;
for(ll i=2;i*i<=n;i++){
if(n%i!=0)continue;
if(is_cont_zero(i))continue;
ll k=n/i;
ll d=to_palin(i);
if(k%d!=0)continue;
if(i>d)continue;
v.insert(mp(i,d));
}
map<ll,str> memo;
auto f=[&](auto f,ll x, set<pll> s)->str{
if(is_palin(x)&&!is_cont_zero(x))return memo[x]=to_string(x);
if(s.empty())return memo[x]="-1";
str ret="-1";
each(d,e,s){
set<pll> sd;
ll xd=x/d/e;
each(dd,ed,s){
if(xd%(dd*ed)==0){
sd.insert(mp(dd,ed));
}
}
str res=f(f,xd,sd);
if(res=="-1")continue;
ret=to_string(d)+"*"+res+"*"+to_string(e);
break;
}
return memo[x]=ret;
};
str ans=f(f,n,v);
out(ans);
}
ABC362G Count Substring Query
- 文字列マッチングを高速に行う
- suffix arrayを学ぶことで攻略した
- suffix arrayは辞書順に並んでいるので、マッチングを二分探索で高速化できる
- イメージ的にはT以上T+1未満の幅を答えればいいのだが、stringにおいてT+1を表現するのにどうすればいいのか少し迷った。末尾に適当にzより大きい文字を加えておけばいい
- 毎回Sの末尾までコピーしたstringと比較していたためTLEを出した
- LCP arrayも併用することで、さらに高速化できるらしいが未履修
とりからABC361F x = a^b
- あるbに対して、これを満たすaの個数は
\sqrt[b]{n} - ただし、これはかなり重複してるので約数包除の要領で重複を除いて足しあげる
- 1は邪魔なので別途足しとく
- 考察より、オーバーフローに気をつけつつ、誤差も気にして、
\sqrt[b]{n}