JOI 春合宿 2010 Day 1
5時間ちゃんと時間測ってやってみた。
JOI ポスター
なんか昔解いた気がするけどまぁやるだけ。
適当に再帰で書きました。
時間かけすぎた気がする。
string rec(int N,int K) { string ret; if(!N)return "J"; if(K>=(1<<(N-1))) { rep(i,1<<(N-1))ret+='I'; return ret+rec(N-1,K-(1<<(N-1))); } else { rep(i,(1<<(N-1)))ret+='J'; rep(i,(1<<(N-1)))ret+='O'; return ret; } } int main() { int N,K; scanf("%d %d",&N,&K); cout << rec(N,K-1) << endl; return 0; }
戦国時代
各武将は角の動ける範囲を守れる。
↗方向と↘方向に分けて考える。
それぞれ(x,y)->(x+y,x-y)みたいな変換をしてやると数えられる。
後は重複を引く。重複は各↗方向に対して、かぶりうる↘の範囲を求めて、にぶたんする。
この時偶奇にわけないといけないことに注意。
LとN間違えてて、デバッグでハマった。
#include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <complex> #include <string> #include <sstream> #include <algorithm> #include <numeric> #include <vector> #include <queue> #include <stack> #include <functional> #include <iostream> #include <map> #include <set> using namespace std; typedef pair<int,int> P; typedef long long ll; typedef vector<int> vi; typedef vector<ll> vll; #define pu push #define pb push_back #define mp make_pair #define eps 1e-9 #define INF 2000000000 #define sz(x) ((int)(x).size()) #define fi first #define sec second #define SORT(x) sort((x).begin(),(x).end()) #define all(x) (x).begin(),(x).end() #define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++) #define repn(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++) #define EQ(a,b) (abs((a)-(b))<eps) int L,N; ll ans = 0ll; vector<int> xy,yx; vector<int> odd,even; int x[100100],y[100100]; int main() { scanf("%d %d",&L,&N); rep(i,N)scanf("%d %d",&x[i],&y[i]); rep(i,N) { xy.pb(x[i]+y[i]); yx.pb(y[i]-x[i]); if((y[i]-x[i])%2)odd.pb(y[i]-x[i]); else even.pb(y[i]-x[i]); } sort(all(xy)); sort(all(yx)); sort(all(odd)); sort(all(even)); xy.erase(unique(all(xy)),xy.end()); yx.erase(unique(all(yx)),yx.end()); odd.erase(unique(all(odd)),odd.end()); even.erase(unique(all(even)),even.end()); rep(i,xy.size())ans += L-abs(xy[i]-(L-1)); rep(i,yx.size())ans += L-abs(yx[i]); rep(i,xy.size()) { int beg,end,k; end = (xy[i]>L-1)?2*L-2-xy[i]:xy[i]; beg = -end; if(xy[i]%2)k = upper_bound(all(odd),end)-lower_bound(all(odd),beg); else k = upper_bound(all(even),end)-lower_bound(all(even),beg); ans -= k; } printf("%lld\n",ans); return 0; }
階段
なんの変哲もない普通のDP。segtreeで加速してやるだけ。
#define MOD 1234567 const int SIZE = 1<<19; struct segtree { int seg[SIZE*2]; void update(int k,int x) { k += SIZE-1; seg[k]=x; while(k) { k = (k-1)/2; seg[k]=(seg[k*2+1]+seg[k*2+2])%MOD; } } int query(int a,int b,int k,int l,int r) { if(r<=a||b<=l)return 0; if(a<=l&&r<=b)return seg[k]; return (query(a,b,k*2+1,l,(l+r)/2)+query(a,b,k*2+2,(l+r)/2,r))%MOD; } }seg; int dp[500100]; int h[500100]; int N,P; int main() { scanf("%d %d",&N,&P); for(int i=1;i<=N;i++)scanf("%d",&h[i]); rep(i,N+1)h[i+1]+=h[i]; dp[0]=1; seg.update(0,1); for(int i=1;i<=N;i++) { int k = lower_bound(h,h+N+1,h[i]-P)-h; if(k<i)dp[i]=seg.query(k,i,0,0,SIZE); seg.update(i,dp[i]); } printf("%d\n",dp[N]); return 0; }
100+100+100=300 (2:03)
終わってからDEGwerさんにこの日はクソ簡単な日だと教えていただいた。
実際簡単でほぼ3時間余らせて全完できたので良かった