ABC189
ABCD4完1ペナ42:17・・・Eは解けるべきだしペナの出し方も下手だったしCも正直間に合うだろうな〜って思ったのに躊躇って出さなかったのでさっさと投げるべきだったしで色々下手でした
A
if(s[0]==s[1] and s[1]==s[2])でもいいが，
std::sort(s.begin(),s.end());//文字列をソート s.erase(std::unique(s.begin(),s.end()),s.end());//連続する重複要素を削除を使えば10文字くらいあって面倒なときも一発で判定できて便利
#include<bits/stdc++.h> using namespace std; int main(){ string s;cin>>s; sort(s.begin(),s.end()); s.erase(unique(s.begin(),s.end()),s.end()); cout<<(s.size()==1?"Won":"Lost")<<endl; return 0; }
B
小数だと誤差が出るので整数で扱いましょうはABC-Bだとめっちゃ頻出なイメージ（例．ABC174-Bとか）
まあこの難易度帯に限らず小数は本当に最終手段って凄い人が言ってるので間違いない
#include<bits/stdc++.h> using namespace std; int main(){ int n,x;cin>>n>>x; int cur=0,ans=0; while(n--){ int v,p;cin>>v>>p; ans++; cur+=v*p; if(cur>100*x){cout<<ans<<endl;return 0;} } cout<<-1<<endl; return 0; }
C
制約で色々話題になったやつ（僕も惑わされた一人） 108回までは大丈夫って回数で判断したほうがいいのかもしれない・・・
ヒストグラムを考えてみる．
左端を固定してから区間を右に引き伸ばしたときに
をすればよい．
区間最小値は
min(直前までの最小値,新しく加えた右端の要素)
でO(1)で求まる
計算量はO(N2)だが，計算回数は高々(104)2/2=5*107<108なので間に合う
#include<bits/stdc++.h> using namespace std; using ll=long long; #define rep(i,s,n) for(int i=s;i<(n);i++) int main(){ int n;cin>>n; vector<ll>a(n); rep(i,0,n)cin>>a[i]; ll ans=0; rep(i,0,n){ ll mn=a[i]; rep(j,i,n){ mn=min(mn,a[j]); ans=max(ans,mn*(j-i+1)); } } cout<<ans<<endl; return 0; }
O(N)解法
ヒストグラムを考えるのはさっきと同じ
よくよく考えてみれば，答えはこのヒストグラムの中に作ることのできる長方形の最大の面積とみなすことができる
これは蟻本のp298ページに乗っていて，これをまんまコピペすればAC
ざっくり説明すると，最大長方形をなすとき，左端のindexをl,右端のindexをrとすれば
が成り立っているはずである（そうでなければそれぞれの方向にまだ引き伸ばせるはずなので） よって，a[i]を高さとしたときの左端，右端は一意に決まるはずで，これを管理していけば良さそう.それぞれはstackを用いて管理していけばいい．stackはindexを管理する．
具体的には例えば左端を考えてみると，配列aを左からなめていって，a[i]を考えた時に
stackが空になる or a[stackのtop]<a[i]
となるまでstackから取り出していく． そうすると操作後のstackの状態から以下のようにしてa[i]を高さとしたときの左端l[i]を決めることができる．
stackが空である
→自分より小さい要素が左にはない
→一番左端を取れるのでl[i]=0
stackが空でない
→stackの先頭のindexより左側に区間を引き伸ばすことができない
→l[i]=stack.top()+1
右端も同様に決めることができて，あとは各i(0<=i<n)について
a[i]:高さ r[i]-l[i]:区間の幅
と考えてやればこれらの積のmaxが答えになる
#include<bits/stdc++.h> using namespace std; using ll=long long; #define rep(i,s,n) for(int i=s;i<(n);i++) #define rrep(i,s,n) for(int i=n-1;i>=(s);i--) int main(){ int n;cin>>n; vector<ll>a(n); rep(i,0,n)cin>>a[i]; ll ans=0; stack<ll>sl,sr; vector<ll>l(n),r(n); rep(i,0,n){ while(!sl.empty() and a[sl.top()]>=a[i])sl.pop(); l[i]=sl.empty()?0:(sl.top()+1); sl.emplace(i); } rrep(i,0,n){ while(!sr.empty() and a[sr.top()]>=a[i])sr.pop(); r[i]=sr.empty()?n:(sr.top()); sr.emplace(i); } rep(i,0,n)ans=max(ans,a[i]*(r[i]-l[i])); cout<<ans<<endl; return 0; }
D
公式の解説とちょっと実装方針違うかも（方向性はだいたい同じ）
要するに
s[i]==OR→新しい要素x[i]がTrueならy[i]はどうあがいてもTrue，Falseならy[i]がTrueになればTrue
s[i]==AND→y[i]がTrueならx[i]はTrueでTrueに，Falseならx[i]がどうあがいてもFalse
なので，s[i]まで考えたときのTrueとFalseの個数を管理して（これらをそれぞれT[i],F[i]とおく）（実際にはpairとかを用いて実装すればいいと思う）
T[0]=1,F[0]=1
(s[i]==OR)T[i+1]=2*T[i]+F[i],F[i+1]=F[i]
(s[i]==AND)T[i+1]=T[i],F[i+1]=T[i]+2*F[i]
みたいな漸化式を立てればいい
#include<bits/stdc++.h> using namespace std; using ll=long long; using pll=pair<ll,ll>; #define rep(i,s,n) for(int i=s;i<(n);i++) #define rrep(i,s,n) for(int i=n-1;i>=(s);i--) int n; vector<string>s(70); pll rec(int i){ if(!i)return {1,1}; auto [T,F]=rec(i-1); if(s[i-1]=="OR")return {2*T+F,F}; else return {T,T+2*F}; } int main(){ cin>>n; rep(i,0,n)cin>>s[i]; cout<<rec(n).first<<endl; return 0; }
E
色々問題文がごちゃってて解釈がしんどいが，要するに何回か操作した後の変換式が求まれば良さそう．解説は行列と対応させているが，そうじゃなくても合成関数とかで考えられると思う（というか僕はこれでしか考えられなかった）
というわけで，変換式の係数と定数項を管理できれば良さそうである．つまり変換後の座標を(x',y')としたときに
x'=ax+by+c
y'=dx+ey+f
となるような(a,b,c,d,e,f)を管理する．
あとはこれをopに従って変換式を逐次記録していけばいい．
また，変換式の係数を持つ構造体を以下のように定義しておくと便利
struct S{ ll a,b,c; S& operator-(){ a=-a,b=-b,c=-c; return *this; } S& f(ll p){ a=-a,b=-b,c=2*p-c; return *this; } ll F(ll x,ll y)const{ return a*x+b*y+c; } };
というか我ながら割とキレイに実装できた気がする（コンテスト中に間に合わないと意味ないんだけど）
#include<bits/stdc++.h> using namespace std; using ll=long long; using pll=pair<ll,ll>; #define rep(i,s,n) for(int i=s;i<(n);i++) #define rrep(i,s,n) for(int i=n-1;i>=(s);i--)struct S{ ll a,b,c; S& operator-(){ a=-a,b=-b,c=-c; return *this; } S& f(ll p){ a=-a,b=-b,c=2*p-c; return *this; } ll F(ll x,ll y)const{ return a*x+b*y+c; } };
ll n,m,q; vector<pll>xy(200020),op(200020); vector<pair<S,S>>dp(200020); vector<bool>ok(200020,false);
pair<S,S> rec(int i){ if(ok[i])return dp[i]; ok[i]=true; if(!i){ S x={1,0,0},y={0,1,0}; return dp[i]={x,y}; } auto [t,p]=op[i-1]; auto [x,y]=rec(i-1); if(t==1)return dp[i]={y,-x}; else if(t==2)return dp[i]={-y,x}; else if(t==3)return dp[i]={x.f(p),y}; else return dp[i]={x,y.f(p)}; }
int main(){ cin>>n; rep(i,0,n)cin>>xy[i].first>>xy[i].second; cin>>m; rep(i,0,m){ cin>>op[i].first; if(op[i].first>2)cin>>op[i].second; else op[i].second=0; } cin>>q; while(q--){ ll a,b;cin>>a>>b; auto [fx,fy]=rec(a); auto [x,y]=xy[--b]; cout<<fx.F(x,y)<<' '<<fy.F(x,y)<<'\n'; } return 0; }
F
巡回しちゃう系dpはそれをxとおいて漸化式を立てると嬉しいことがある(EDPC-Jなど）
dp[i]:マスiからゴールに辿り着くまでの期待値
マスiが振り出しに戻るマスだとすると，そのマス自体を振り出しと見なすことができるので，答えをxとすると，dp[i]=xとなる．
そうでない場合は，そのマスからM通りの遷移が考えられるので，その遷移先の期待値の平均をとって+1してやればいい
あとはこれをそのまま実装するのだが，毎回期待値の平均をとっているとO(NM)になって簡単にTLEしてしまうので，累積和を持ってやる
僕はメモ化再帰だとこの表現の仕方がわからなかったのでおとなしくfor文で書くやつをやったが，書けないことはないんだろうか・・・
#include<bits/stdc++.h> using namespace std; using ll=long long; using ld=long double; using pll=pair<ll,ll>; #define rep(i,s,n) for(int i=s;i<(n);i++) #define rrep(i,s,n) for(int i=n-1;i>=(s);i--)ll n,m,k; vector<bool>trap(200020,false);
int main(){ cin>>n>>m>>k; ll seq=0; rep(i,0,k){ int x;cin>>x; trap[x]=true; if(trap[x-1])seq++; else seq=1; if(seq==m){cout<<-1<<endl;return 0;} } ld sp=0,sq=0; vector<ld>p(n+m+10,0),q(n+m+10,0); rrep(i,0,n){ if(trap[i])p[i]=1,q[i]=0; else{ p[i]=sp/m; q[i]=sq/m+1; } sp+=p[i]; sq+=q[i]; sp-=p[i+m]; sq-=q[i+m]; } ld ans=q[0]/(1-p[0]); cout<<setprecision(16)<<ans<<endl; return 0; }
