Educational Codeforces Round 19 - 君はまるで砂漠に咲く、一輪の花。

A. k-Factorization

#include<bits/stdc++.h>
using namespace std;
 
#define rep(i,n)  for(int i=0;i<n;++i)
#define sc2(a,b)  scanf("%d %d",&a,&b)
 
int main(){
    int n,k;
    sc2(n,k);
    vector <int> ans;
    for(int i=2;i<334;i++) {
        if(i==2 && k==1) {ans.push_back(n); k=0;}
        //cout<< n ;
        while (n%i==0 && k>0) {
            if (k>1) {
                ans.push_back(i);
                k--;
                n/=i;
            } else {
                ans.push_back(n);
                k=0;
                n=1;
            }
        }
    }
    if (k>0) {
        printf("-1\n");
    } else {
        bool f=0;
        for(auto x:ans) {
            if (f) {
                printf(" %d",x);
            }else {
                printf("%d",x);
                f=1;
            }
        }
        puts("");
    }
    return 0;
}

334以上の素数について考慮不足で自力AC出来ず。334以上の素数でもk=1ならそのまま出力で解になりました。k>1なら素因数分解出来ないので-1になりますけど。考慮不足でした。

B. Odd sum

▶クリックで開閉

#include<bits/stdc++.h>
using namespace std;
 
#define rep(i,n)  for(int i=0;i<n;++i)
#define sc1(a)  scanf("%d",&a)
 
int main(){
    int n,m,p=-1e9,q=1e9,ans=0;
    sc1(n);
    rep(i,n) {
        sc1(m);
        if(m>0) ans+=m;
        if(m<0 && m%2!=0) p=max(p,m);
        if(m>0 && m%2) q=min(q,m);
    }
    if (ans%2) printf("%d\n",ans);
    else if (ans==0 && p>-1e9) printf("%d\n",p);
    else if (ans%2==0) printf("%d\n",max(ans+p,ans-q));
    return 0;
}

数列全て負の数などの場合に注意。

C. Minimal string

▶クリックで開閉

#include<bits/stdc++.h>
using namespace std;
 
#define rep(i,n)  for(int i=0;i<n;++i)
 
//BEGIN CUT HERE
template <typename T,typename E>
struct SegmentTree{
  typedef function<T(T,T)> F;
  typedef function<T(T,E)> G;
  int n;
  F f;
  G g;
  T d1;
  E d0;
  vector<T> dat;
  SegmentTree(){};
  SegmentTree(int n_,F f,G g,T d1,
          vector<T> v=vector<T>()):
    f(f),g(g),d1(d1){
    init(n_);
    if(n_==(int)v.size()) build(n_,v);
  }
  void init(int n_){
    n=1;
    while(n<n_) n*=2;
    dat.clear();
    dat.resize(2*n-1,d1);
  }
  void build(int n_, vector<T> v){
    for(int i=0;i<n_;i++) dat[i+n-1]=v[i];
    for(int i=n-2;i>=0;i--)
      dat[i]=f(dat[i*2+1],dat[i*2+2]);
  }
  void update(int k,E a){
    k+=n-1;
    dat[k]=g(dat[k],a);
    while(k>0){
      k=(k-1)/2;
      dat[k]=f(dat[k*2+1],dat[k*2+2]);
    }
  }
  inline T query(int a,int b){
    T vl=d1,vr=d1;
    for(int l=a+n,r=b+n;l<r;l>>=1,r>>=1) {
      if(l&1) vl=f(vl,dat[(l++)-1]);
      if(r&1) vr=f(dat[(--r)-1],vr);
    }
    return f(vl,vr);
  }
};
//END CUT HERE
 
char s[100005];
vector <int> ans;
int main(){
    vector <int> w;
    scanf("%s",s);
    long dd=strlen(s);
    SegmentTree<int,int> rmq(100005,[](int a,int b){return min(a,b);}, [](int a,int b){return b;}, INT_MAX);
    for (long i=0;i<dd;i++) rmq.update(i,s[i]-'a');
    
    for(long i=0;i<dd;i++){
        if(w.empty()) {
            w.push_back(s[i]-'a');
        } else {
            int x=rmq.query(i,dd+1);
            while(!w.empty()) {
                auto y=w.back();
                //cout<< x<< " " << y << endl;
                if (y>x) break;
                ans.push_back(y+'a');
                w.pop_back();
            }
            w.push_back(s[i]-'a');
        }
    }
    int vs=w.size();
    rep(i,vs) {
        int vv=w.back();
        ans.push_back(vv+'a');
        w.pop_back();
    }
    for (auto e:ans) printf("%c",e);
    puts("");
    return 0;
}

セグ木で区間の最小値を確認してますけど全く必要ありませんでした。先頭から1つずつ末尾に近づくのと末尾固定の区間の最小値を知りたいなら末尾からループ回しておけば確認できました。
ストックしている文字と残り区間の辞書順最小文字を比較してストック優先で出力候補に。最小でないものはストックして末尾へ近づいて行きます。
セグ木必要ありませんでした。練習になったのでいいことですけど。