1241: Lagrange's Four-Square Theorem
ラグランジュの四乗定理なんて初めて聞いた。。。
2^15より小さくて四乗未満だから動的計画法でなんとかなりそうと思って適当に漸化式作ってみる
ans[i][j]と置いてiは入力した求めたい合計の値、jは2乗の何個の和であるか（0<=i<=2^15,0<=j<=4)
2乗の値はあらかじめ2^15までで計算しておき、dataという配列に入れている
あとはfor文を適当に回したらでる（ここの説明が難しい）
REP(i,data.size()){
REP(j,32769){
if(j+data[i]>32768)break;
REP(k,4)ans[j+data[i]][k+1]+=ans[j][k];
}
}
動的計画法の中身はこんな感じ
後はデータの数からあらかじめ計算してって感じ
int ans[32769][5]; int main(){ vector<int>data; for(int i=1;i*i<=32768;i++)data.push_back(i*i); ans[0][0]=1; REP(i,data.size()){ REP(j,32769){ if(j+data[i]>32768)break; REP(k,4)ans[j+data[i]][k+1]+=ans[j][k]; } } int n; while(1){ cin>>n; if(n==0)break; int sum=0; REP(i,4)sum+=ans[n][i+1]; cout<<sum<<endl; } }
2300: Calendar Colors
英語の時点で辛かった。ただ翻訳に投げて内容を掴めたら、NとMが小さいことからそれぞれの累乗和をあらかじめに計算しておき、後は全探索でなんとかなりそうってなって、なんとかなった。O(2^N)
double d(double a,double b){ return (a-b)*(a-b); } int main(){ int n,m; double a[20],b[20],c[20]; double fld[20][20]; cin>>n>>m; REP(i,n)cin>>a[i]>>b[i]>>c[i]; REP(i,n)REP(j,n){ fld[i][j]=d(a[i],a[j])+d(b[i],b[j])+d(c[i],c[j]); } double ans=0; REP(i,1<<n){ int cnt=0; vector<int>V; REP(j,n)if(i>>j&1){ cnt++; V.push_back(j); } if(cnt!=m)continue; double res=0; REP(j,m){ for(int k=j+1;k<m;k++){ res+=fld[V[j]][V[k]]; } } ans=max(ans,res); } printf("%.10f\n",ans); }
2706: Let's Solve Geometric Problems(幾何問題を解こう)
「幾何問題かよ、やる気無くすわ」って思ったら全然幾何もんじゃなかった件、しかもそんなに法則見つけるのも難しくなく、素因数分解の要領でなんとかなる。
ただ最初は全然TLEが取れずなんでだろうと思ったらi*i<=qのところをi<=qとしてたからだった、初歩的なミス
int gcd(int a,int b){ if(b==0)return a; return gcd(b,a%b); } int main(){ int p,q; cin>>p>>q; int r=gcd(q,p); p/=r;q/=r; int ans=1; for(int i=2;i*i<=q;i++){ if(q%i!=0)continue; ans*=i; while(q%i==0)q/=i; } ans*=q; cout<<ans<<endl; }
1610: Bamboo Blossoms(竹の花)
最初は7368791なんて大きさの配列作れないやんけ終わったと思って一時間以上考えたけど分からず、やけくそでエラトステネスの篩でやったら通った。配列ってどの大きさまで入るんや、、、単なる知識不足。
エラトステネスの篩って本当に便利
int MAX = 7368791; int main(){ int n,m; bool f[MAX+1]; while(1){ cin>>m>>n; if(m+n==0)break; REP(i,MAX+1)f[i]=false; for(int i=m;;i++){ if(!f[i]){ if(n==0){ cout<<i<<endl; break; }else{ n--; for(int j=i;j<=MAX;j+=i){ f[j]=true; } } } } } }
2700: Airport Codes(空港コード)
それぞれの文字列に対してkにおける操作をして、setで管理したらなぜか通った。setの計算量が未だによくわかってないのに乱用していて良くない。
int gcd(int a,int b){ if(b==0)return a; return gcd(b,a%b); } int main(){ int p,q; cin>>p>>q; int r=gcd(q,p); p/=r;q/=r; int ans=1; for(int i=2;i*i<=q;i++){ if(q%i!=0)continue; ans*=i; while(q%i==0)q/=i; } ans*=q; cout<<ans<<endl; }
CodeForce#286(Div2)
初めてVirtual participationをやってみたので。
時間内に解けたのはA,Bだけで終わったあとにC通せました
Problem - A - Codeforces
文字列全部入れていっても間に合うから全探索
(自分はstringのinsert使ってゴリ押し)
Submission #14895476 - Codeforces
Problem - B - Codeforces
それぞれの色についてワーシャルフロイドしてもN=100だかた間に合う(O(N^4))
あとは数え上げ
Submission #14895548 - Codeforces
Problem - C - Codeforces
DPでどの状態を保存するかが問題
dp[i][j](iへj分だけジャンプしてきた)
っていう状態ではdp[30000][30000]となり配列があふれる
だから
dp[i][j](iの場所へDからjだけ増減した分だけジャンプしてきた)
とすれば配列の確保が少なくてすむ(1000くらい確保したら十分のはず)
でもそれではjがマイナスになる可能性があるので一番最初を500とかにしてjがマイナスにならないように調整する
Submission #14898273 - Codeforces
やる気を維持するためにまた書くかもしれない
日本語力が足りない
JOI予選参加記
JOI 2015/2016 予選 問題文・採点用入出力・解説
こことのdiffを取ってみたら520だった
適当な解説とソースコードだけ貼ります
問1
やるだけ
int main(){
int a[4],b[2];
REP(i,4)cin>>a[i];
REP(i,2)cin>>b[i];
sort(a,a+4);
sort(b,b+2);
cout<<a[3]+a[2]+a[1]+b[1]<<endl;
return 0;
}問2
swapでゴリ押し
int a[110];
int main(){
int n,m;
cin>>n>>m;
REP(i,n)cin>>a[i];
for(int k=1;k<=m;k++){
REP(i,n-1){
if(a[i]%k>a[i+1]%k){
swap(a[i],a[i+1]);
}
}
}
REP(i,n)cout<<a[i]<<endl;
return 0;
}問3
dp解もあるらしいけど全探索しました
char fld[55][55];
int h,w;
int rec(int r,int l){
int cnt=0;
for(int i=0;i<=r;i++)REP(j,w)if(fld[j][i]!='W')cnt++;
for(int i=r+1;i<=l;i++)REP(j,w)if(fld[j][i]!='B')cnt++;
for(int i=l+1;i<h;i++)REP(j,w)if(fld[j][i]!='R')cnt++;
return cnt;
}
int main(){
cin>>h>>w;
REP(i,h)REP(j,w)cin>>fld[j][i];
int ans=INF;
for(int i=0;i<h;i++){
for(int j=i+1;j<h-1;j++){
ans=min(ans,rec(i,j));
}
}
cout<<ans<<endl;
return 0;
}問4
隣同士で左側が東、右側が西になっている（反対側にすすんでいく）場所を保存してほげ
int n,q,d[100100];
ll t,a[100100];
ll dist[100100];
vector<int> dat;
int main(){
scanf("%d%lld%d",&n,&t,&q);
REP(i,n){
scanf("%lld%d",&a[i],&d[i]);
}
if(d[0]==1)dat.PB(0);
REP(i,n-1){
if(d[i]==2&&d[i+1]==1)dat.PB(i+1);
}
if(d[n-1]==2)dat.PB(n);
for(int i=0;i<dat[0];i++){
dist[i]=a[i]-t;
}
for(int i=0;i<dat.size()-1;i++){
ll btw;
for(int j=dat[i];j<dat[i+1]-1;j++){
if(d[j]==1&&d[j+1]==2){
btw=(a[j]+a[j+1])/2LL;
}
}
for(int j=dat[i];j<dat[i+1];j++){
if(d[j]==1){
dist[j]=min(a[j]+t,btw);
}else{
dist[j]=max(a[j]-t,btw);
}
}
}
for(int i=dat[dat.size()-1];i<n;i++){
dist[i]=a[i]+t;
}
int x;
REP(i,q){
scanf("%d",&x);x--;
cout<<dist[x]<<endl;
}
return 0;
}問5
幅とダイクストラゴリ押し
計算量考えてなかったけどなんかできた
int n,m,k,s,p,q,c[100100];
ll d[100100];
bool ok[100100];
bool no[100100];
bool used[100100];
vector<int> G[100100];
ll INF =(1<<29)-1;
void dijkstra(int s){
priority_queue<P,vector<P>,greater<P> > Q;
fill(d,d+n,LLONG_MAX);
d[s]=0;
Q.push(P(0,s));
while(!Q.empty()){
P pp=Q.top();Q.pop();
int v=pp.second;
if(d[v]<pp.first)continue;
if(no[v])continue;
for(int i=0;i<G[v].size();i++){
int to=G[v][i];
int cost=(ok[to]?q:p);
if(d[to]>d[v]+cost){
d[to]=d[v]+cost;
Q.push(P(d[to],to));
}
}
}
}
int main(){
memset(ok,false,sizeof(ok));
memset(no,false,sizeof(no));
scanf("%d%d%d%d",&n,&m,&k,&s);
scanf("%d%d",&p,&q);
REP(i,k)scanf("%d",&c[i]);
REP(i,m){
int a,b;
scanf("%d%d",&a,&b);a--;b--;
G[a].PB(b);G[b].PB(a);
}
REP(i,k){
c[i]--;
memset(used,false,sizeof(used));
no[c[i]]=ok[c[i]]=true;
queue<P> Q;
Q.push(P(c[i],0));
while(!Q.empty()){
P pp=Q.front();Q.pop();
if(pp.second>=s)break;
int v=pp.first;
REP(i,G[v].size()){
int to=G[v][i];
if(!used[to]){
used[to]=true;
ok[to]=true;
Q.push(P(to,pp.second+1));
}
}
}
}
dijkstra(0);
if(ok[n-1])cout<<d[n-1]-q<<endl;
else cout<<d[n-1]-p<<endl;
return 0;
}問6
bitDPだなーと思って実装してたらわけわからなくなって死
6-1だけ紙で解いた
問6に1時間半以上も残したのに解けなかったのが痛かった
ボーダーは全完って聞いてるので予選落ちです
