競プロ参加日記015 AtCoder Beginner Contest 179(ABC179)
・はじめに
A,B,C,Eの4完でした。
DのDPの書き方が変でバグが取れなくて、時間を溶かしてしましました...。コンテスト後に、Dのバグがすぐとれたし、Fは一瞬で通せたで消化不良です...。
・A - Plural Form
問題文通りにif文を作ればOKです。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
string s;
cin>>s;
if(s[s.size()-1]=='s') cout<<s<<"es"<<endl;
else cout<<s<<"s"<<endl;
}・B - Go to Jail
Di1==Di2ならカウントを増やして、Di1!=Di2ならカウントを0にする。ということを、i=0～N-1までやります。
こうすることで、カウント=連続ゾロ目の回数となるので、カウントが3以上になったタイミングでフラグ等を立てればOKです。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int N;
cin>>N;
int c=0;
bool f=false;
for(int i=0;i<N;i++){
int D1,D2;
cin>>D1>>D2;
if(D1==D2) c++;
else c=0;
if(c==3) f=true;
}
if(f) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}・C - A x B + C
N=A+B+Cの問題(ABC085Cのこれとか)です。競プロでは多分典型です。
A,Bの2値が決まれば、C=N-A*Bの右辺が全て定数となるため、Cが一意に決まります。なので、A,Bの全パターンの中でCが題意に満たしているかを調べればよいです。
これだけだとO(N^2)っぽさそうですが、C>0であることを考えると、A,Bの取りうる範囲は凄く小さく、あり得ないケースをカットしていけば十分早くなります。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int N;
int c=0;
cin>>N;
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
if(i*j>=N) break;
c++;
}
}
cout<<c<<endl;
}・D - Leaping Tak
今回の戦犯問題。
範囲なのでセグ木を使いましょう(想定解は違う)。
セグ木を使って丁寧にDPをすると、O(NlogN)くらいで求まります。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
//https://algo-logic.info/segment-tree/
/* SegTreeLazyProportional<X,M>(n,fx,fa,fm,fp,ex,em): モノイド(集合X, 二項演算fx,fa,fm,p 単位元ex,em)についてサイズnで構築
set(int i, X x), build(): i番目の要素をxにセット。まとめてセグ木を構築する。O(n)
update(i,x): i 番目の要素を x に更新。O(log(n))
query(a,b): [a,b) 全てにfxを作用させた値を取得。O(log(n))
*/
template <typename X, typename M>
struct SegTreeLazyProportional {
using FX = function<X(X, X)>;
using FA = function<X(X, M)>;
using FM = function<M(M, M)>;
using FP = function<M(M, int)>;
int n;
FX fx;
FA fa;
FM fm;
FP fp;
const X ex;
const M em;
vector<X> dat;
vector<M> lazy;
SegTreeLazyProportional(int n_, FX fx_, FA fa_, FM fm_, FP fp_, X ex_, M em_)
: n(), fx(fx_), fa(fa_), fm(fm_), fp(fp_), ex(ex_), em(em_), dat(n_ * 4, ex), lazy(n_ * 4, em) {
int x = 1;
while (n_ > x) x *= 2;
n = x;
}
void set(int i, X x) { dat[i + n - 1] = x; }
void build() {
for (int k = n - 2; k >= 0; k--) dat[k] = fx(dat[2 * k + 1], dat[2 * k + 2]);
}
/* lazy eval */
void eval(int k, int len) {
if (lazy[k] == em) return; // 更新するものが無ければ終了
if (k < n - 1) { // 葉でなければ子に伝搬
lazy[k * 2 + 1] = fm(lazy[k * 2 + 1], lazy[k]);
lazy[k * 2 + 2] = fm(lazy[k * 2 + 2], lazy[k]);
}
// 自身を更新
dat[k] = fa(dat[k], fp(lazy[k], len));
lazy[k] = em;
}
void update(int a, int b, M x, int k, int l, int r) {
eval(k, r - l);
if (a <= l && r <= b) { // 完全に内側の時
lazy[k] = fm(lazy[k], x);
eval(k, r - l);
} else if (a < r && l < b) { // 一部区間が被る時
update(a, b, x, k * 2 + 1, l, (l + r) / 2); // 左の子
update(a, b, x, k * 2 + 2, (l + r) / 2, r); // 右の子
dat[k] = fx(dat[k * 2 + 1], dat[k * 2 + 2]);
}
}
void update(int a, int b, M x) { update(a, b, x, 0, 0, n); }
X query_sub(int a, int b, int k, int l, int r) {
eval(k, r - l);
if (r <= a || b <= l) { // 完全に外側の時
return ex;
} else if (a <= l && r <= b) { // 完全に内側の時
return dat[k];
} else { // 一部区間が被る時
X vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
X vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
return fx(vl, vr);
}
}
X query(int a, int b) { return query_sub(a, b, 0, 0, n); }
};
int main(){
int n,k;
cin>>n>>k;
using X = long long;
using M = long long;
auto fx = [](X x1, X x2) -> X { return (x1 + x2)%998244353; };
auto fa = [](X x, M m) -> X { return (x + m)%998244353; };
auto fm = [](M m1, M m2) -> M { return (m1 + m2)%998244353; };
auto fp = [](M m, long long n) -> M { return (m * n)%998244353; };
long long ex = 0;
long long em = 0;
SegTreeLazyProportional<X, M> rmq(n, fx, fa, fm, fp, ex, em);
for(int i=0;i<n;i++){
rmq.set(i,0);
}
rmq.set(0,1);
int l[k],r[k];
for(int i=0;i<k;i++){
cin>>l[i]>>r[i];
}
for(int j=0;j<n;j++){
for(int m=0;m<k;m++){
int l2=l[m]+j;
if(l2>=n) continue;
int r2=r[m]+j;
if(r2>=n) r2=n-1;
int nn=rmq.query(j,j+1);
if(nn!=0){
rmq.update(l2,r2+1,nn);
}
}
}
cout<<rmq.query(n-1,n)<<endl;
}※https://algo-logic.info/segment-tree/
こちらのセグ木をお借りしました。
セグ木に乗せられるのがモノイドと呼ばれる変なものだけらしく、MODはモノイドじゃないのでセグ木じゃ解けないのでは？？？みたいなことを考えて、setとかの解法をやってたら時間が解けました。(ACしたとこを見ると、MODでも大丈夫そうですね。)
・E - Sequence Sum
MODがある場合はループを疑えばよく、この問題もループします。
ex.10 2 1001 の場合、
2 → 4 → 16 → 256 → 471 → 620 → 16 → 256 → 471 → 620
となり、3～6,7～10が同じです。
f(x,m)のxがmodの影響で0<=x<mの範囲内のどれかになるため、少なくともm回以内に同じ数字が出現します。(ループし始めます)
setか何かで出現を管理して、ループを感知したら(同じ数字が出たら)、残り可能なループ回数分*ループで増える分を足すことで、シミュレーション回数を大幅に減らして高速に計算できます。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
long long N,X,M;
cin>>N>>X>>M;
set<long long> s;
long long A=X;
s.insert(A);
long long sum=A;
N--;
while(N>0){
A=A*A%M;
if(s.find(A)!=s.end()){
long long sum2=A;
long long c=1;
long long A2=A;
while(1){
A2=A2*A2%M;
if(A2==A) break;
c++;
sum2+=A2;
//cout<<c<<","<<sum2<<endl;
}
sum+=sum2*(N/c);
//cout<<N<<","<<c<<","<<sum2<<endl;
N%=c;
s.clear();
if(N==0) break;
}
s.insert(A);
sum+=A;
//cout<<A<<endl;
N--;
}
cout<<sum<<endl;
}・F - Simplified Reversi
セグ木で殴る(想定解法じゃないっぽいです)。
各行の一番左の白コマ、各列の一番上の白コマをセグ木で管理すれば、白コマを置いたときに、何個ひっくり返せるかが分かるようになります。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
//https://algo-logic.info/segment-tree/
/* SegTreeLazy<X,M>(n,fx,fa,fm,ex,em): モノイド(集合X, 二項演算fx,fa,fm, 単位元ex,em)についてサイズnで構築
set(long long i, X x), build(): i番目の要素をxにセット。まとめてセグ木を構築する。O(n)
update(i,x): i 番目の要素を x に更新。O(log(n))
query(a,b): [a,b) 全てにfxを作用させた値を取得。O(log(n))
*/
template <typename X, typename M>
struct SegTreeLazy {
using FX = function<X(X, X)>;
using FA = function<X(X, M)>;
using FM = function<M(M, M)>;
long long n;
FX fx;
FA fa;
FM fm;
const X ex;
const M em;
vector<X> dat;
vector<M> lazy;
SegTreeLazy(long long n_, FX fx_, FA fa_, FM fm_, X ex_, M em_)
: n(), fx(fx_), fa(fa_), fm(fm_), ex(ex_), em(em_), dat(n_ * 4, ex), lazy(n_ * 4, em) {
long long x = 1;
while (n_ > x) x *= 2;
n = x;
}
void set(long long i, X x) { dat[i + n - 1] = x; }
void build() {
for (long long k = n - 2; k >= 0; k--) dat[k] = fx(dat[2 * k + 1], dat[2 * k + 2]);
}
/* lazy eval */
void eval(long long k) {
if (lazy[k] == em) return; // 更新するものが無ければ終了
if (k < n - 1) { // 葉でなければ子に伝搬
lazy[k * 2 + 1] = fm(lazy[k * 2 + 1], lazy[k]);
lazy[k * 2 + 2] = fm(lazy[k * 2 + 2], lazy[k]);
}
// 自身を更新
dat[k] = fa(dat[k], lazy[k]);
lazy[k] = em;
}
void update(long long a, long long b, M x, long long k, long long l, long long r) {
eval(k);
if (a <= l && r <= b) { // 完全に内側の時
lazy[k] = fm(lazy[k], x);
eval(k);
} else if (a < r && l < b) { // 一部区間が被る時
update(a, b, x, k * 2 + 1, l, (l + r) / 2); // 左の子
update(a, b, x, k * 2 + 2, (l + r) / 2, r); // 右の子
dat[k] = fx(dat[k * 2 + 1], dat[k * 2 + 2]);
}
}
void update(long long a, long long b, M x) { update(a, b, x, 0, 0, n); }
X query_sub(long long a, long long b, long long k, long long l, long long r) {
eval(k);
if (r <= a || b <= l) { // 完全に外側の時
return ex;
} else if (a <= l && r <= b) { // 完全に内側の時
return dat[k];
} else { // 一部区間が被る時
X vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
X vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
return fx(vl, vr);
}
}
X query(long long a, long long b) { return query_sub(a, b, 0, 0, n); }
};
int main(){
long long n,q;
cin>>n>>q;
using X = long long;
using M = long long;
auto fx = [](X x1, X x2) -> X { return min(x1, x2); };
auto fa = [](X x, M m) -> X { return min(x,m); };
auto fm = [](M m1, M m2) -> M { return min(m1,m2); };
long long ex = numeric_limits<long long>::max();
long long em = numeric_limits<long long>::max();
SegTreeLazy<X, M> rmqy(n-2, fx, fa, fm, ex, em);
SegTreeLazy<X, M> rmqt(n-2, fx, fa, fm, ex, em);
for(long long i=0;i<n;i++){
rmqy.set(i,n-2);
rmqt.set(i,n-2);
}
long long sum=(n-2)*(n-2);
for(long long i=0;i<q;i++){
long long f,x;
cin>>f>>x;
x-=2;
if(f==1){
long long a=rmqy.query(x,x+1);
sum-=a;
//cout<<a<<endl;
rmqt.update(0,a,x);
}
else{
long long a=rmqt.query(x,x+1);
sum-=a;
//cout<<a<<endl;
rmqy.update(0,a,x);
}
/*for(long long j=0;j<n-2;j++){
cout<<rmqt.query(j,j+1)<<" ";
}
cout<<endl;
for(long long j=0;j<n-2;j++){
cout<<rmqy.query(j,j+1)<<" ";
}
cout<<endl;*/
}
cout<<sum<<endl;
}※https://algo-logic.info/segment-tree/
Dと同じく、こちらのセグ木をお借りしました。
セグ木分を除けば実装も軽く、考察も簡単な問題でした。
(想定解はややこしそう)
・おわりに
区間の文字を見ると頭がセグ木一色になるので、一回忘れたいですね？？？
この記事が気に入ったらサポートをしてみませんか？