読者です 読者をやめる 読者になる 読者になる

CF #278

不参加
A:やるだけ
B:過去のある範囲maxのDP→segtree
C:{0,-1,+2,-3}(mod 4)とかで部分和で全種類出てくる
C気づかないのが幼稚園児
A.cpp

#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <cstring>
#include <functional>
#include <cmath>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define rep1(i,n) for(int i=1;i<=(n);++i)
#define all(c) (c).begin(),(c).end()
#define fs first
#define sc second
#define pb push_back
#define show(x) cout << #x << " " << x << endl
int main(){
	int myh,mya,myd,eh,ea,ed,uph,upa,upd;
	cin>>myh>>mya>>myd>>eh>>ea>>ed>>uph>>upa>>upd;
	int ans=1e9;
	rep(i,300){
		int a=mya+i;
		if(a<=ed) continue;
		int t=(eh+a-ed-1)/(a-ed);
		rep(j,300){
			int money=i*upa+j*upd;
			int d=myd+j;
			if(d>=ea){
				ans=min(ans,money);
				break;
			}
			int dam=ea-d;
			int needhp=t*dam+1;
			if(needhp<=myh){
				ans=min(ans,money);
			}else{
				ans=min(ans,money+(needhp-myh)*uph);
			}
		}
	}
	cout<<ans<<endl;
}

B.cpp

#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <cstring>
#include <functional>
#include <cmath>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define rep1(i,n) for(int i=1;i<=(n);++i)
#define all(c) (c).begin(),(c).end()
#define fs first
#define sc second
#define pb push_back
#define show(x) cout << #x << " " << x << endl
const int p2=1<<17;
int n,s,l,a[100000],r[100000],seg[p2*2];
multiset<int> msi;
void update(int x){
	while(true){
		x=(x-1)/2;
		seg[x]=min(seg[x*2+1],seg[x*2+2]);
		if(x==0) break;
	}
}
int inf=1e8;
int segmin(int a,int b,int l,int r,int k){
	if(a>=b) return inf;
	if(b<=l||r<=a) return inf;
	if(a<=l&&r<=b) return seg[k];
	return min(segmin(a,b,l,(l+r)/2,k*2+1),segmin(a,b,(l+r)/2,r,k*2+2));
}
int main(){
	cin>>n>>s>>l;
	rep(i,n) cin>>a[n-1-i];
	int it=0;
	bool ok=false;
	rep(i,n){
		int mn=0,mx=0;
		if(!msi.empty()) mn=*(msi.begin()),mx=*(msi.rbegin());
		while(mx-mn<=s){
			if(it==n){
				ok=true;
				break;
			}
			msi.insert(a[it]);
			mn=*msi.begin(),mx=*(msi.rbegin());
			it++;
		}
		r[i]=it-2;
		if(ok) r[i]=n-1;
		msi.erase(msi.lower_bound(a[i]));
	}
	reverse(r,r+n);
	rep(i,n) r[i]=n-1-r[i];
//	rep(i,n) show(r[i]);
	rep(i,p2*2-1) seg[i]=inf;
	seg[p2-1]=0;
	update(p2-1);
	rep1(i,n){
		seg[p2-1+i]=1+segmin(r[i-1],i-l+1,0,p2,0);
		update(p2-1+i);
	}
	int ans=seg[p2-1+n];
	if(ans>=inf) ans=-1;
	cout<<ans<<endl;
}

C.cpp

#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <cstring>
#include <functional>
#include <cmath>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define rep1(i,n) for(int i=1;i<=(n);++i)
#define all(c) (c).begin(),(c).end()
#define fs first
#define sc second
#define pb push_back
#define show(x) cout << #x << " " << x << endl
typedef long long ll;
const int ccc=100000;
bool prime[ccc+1];
vector<int> pr;
void makeprime(){
	int i,j;
	for(i=2;i<=ccc;i++) prime[i]=true;
	for(i=2;i*i<=ccc;i++) if(prime[i]) for(j=2;j*i<=ccc;j++) prime[j*i]=false;
	for(i=2;i<=ccc;i++) if(prime[i]) pr.push_back(i);
}
int p[ccc+1];
int main(){
	makeprime();
	int n;
	cin>>n;
	if(n==1){
		puts("YES");
		puts("1");
		return 0;
	}
	if(n==4){
		puts("YES");
		printf("1\n3\n2\n4\n");
		return 0;
	}
	if(!prime[n]){
		puts("NO");
		return 0;
	}
	int g=2;
	for(;;g++){
		ll now=1;
		bool can=true;
		rep(i,n/2){
			now*=g;
			now%=n;
			if(now==1){
				can=false;
				break;
			}
		}
		if(!can) continue;
		p[0]=1;
		rep(i,n) p[i+1]=p[i]*g%n;
		puts("YES");
		rep(i,n-1){
			if(i%2==0) cout<<p[i]<<" ";
			else cout<<p[n-1-i]<<" ";
		}
		cout<<n<<endl;
		return 0;
	}
}