寝癖頭の解法

学習中の覚え書きを投稿、更新していきます。

AtCoder Problems in C++ #cheating - カンニング対策 (Cheating)

2008年 日本情報オリンピック春合宿OJから、その提出コードの解答例です。
AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。
atcoder.jp
プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。
競技プログラミング」を略して、「競プロ」などと呼ばれています。

#cheating - カンニング対策 (Cheating)

https://www.ioi-jp.org/camp/2008/2008-sp-tasks/2008-sp_tr-day2_21.pdf

僕が作成、提出したコードは、以下のとおりです。

/*
AtCoder Problems in C++
#cheating - カンニング対策 (Cheating)
https://www.ioi-jp.org/camp/2008/2008-sp-tasks/2008-sp_tr-day2_21.pdf
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int x[200000],y[200000];
int main(void){
  int n,m;
  cin>>n>>m;
  for(int i=0;i<m;i++){
    cin>>x[i]>>y[i];
  }
  sort(x,x+m);
  sort(y,y+m);
  int ok=1e9;
  int ng=-1;
  while(ok-ng>1){
    int d=(ok+ng)/2;
    int c=0;
    int i=0;
    while(i<m){
      int X=x[i];
      while(i<m && x[i]<=X+d){
        i++;
      }
      c++;
    }
    int j=0;
    while(j<m){
      int Y=y[j];
      while(j<m && y[j]<=Y+d){
        j++;
      }
      c++;
    }
    if(c<=n){
      ok=d;
    }else{
      ng=d;
    }
  }
  cout<<ok<<endl;
  return 0;
}




AtCoder Problems in C++ #flu - インフルエンザ (Flu)

2008年 日本情報オリンピック春合宿OJから、その提出コードの解答例です。
AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。
atcoder.jp
プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。
競技プログラミング」を略して、「競プロ」などと呼ばれています。

#flu - インフルエンザ (Flu)

https://www.ioi-jp.org/camp/2008/2008-sp-tasks/2008-sp_tr-day1_20.pdf

僕が作成、提出したコードは、以下のとおりです。

/*
AtCoder Problems in C++
#flu - インフルエンザ (Flu)
https://www.ioi-jp.org/camp/2008/2008-sp-tasks/2008-sp_tr-day1_20.pdf
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
pair<ll,ll> p[100001];
ll c[1001][1001],f[100001];
int main(void){
  ll n,m,d,k;
  cin>>n>>m>>d>>k;
  for(ll i=1;i<=n;i++){
    ll x,y;
    cin>>x>>y;
    p[i]={x,y};
    c[x][y]=i;
  }
  stack<ll> s,t;
  s.push(1);
  f[1]=m;
  for(ll i=1;i<=k;i++){
    while(!(s.empty())){
      ll v=s.top();
      s.pop();
      auto[x,y]=p[v];
      for(ll j=x-d;j<=x+d;j++){
        for(ll l=y-d;l<=y+d;l++){
          if(j<0 || j>=1000 || l<0 || l>=1000){
            continue;
          }
          if((j-x)*(j-x)+(l-y)*(l-y)>d*d){
            continue;
          }
          if(!c[j][l]){
            continue;
          }
          if(f[c[j][l]]){
            continue;
          }
          t.push(c[j][l]);
          f[c[j][l]]=i+m;
        }
      }
    }
    swap(s,t);
  }
  ll ans=0;
  for(ll i=1;i<=n;i++){
    if(f[i] && f[i]>k){
      ans++;
    }
  }
  cout<<ans<<endl;
  return 0;
}




アルゴ式(beta版): C++による「設計技法とデータ構造 (#毎日アルゴ式)」プログラミングで学ぶ数学(6) 積分法

アルゴ式(beta版)の「設計技法とデータ構造 (#毎日アルゴ式)」プログラミングで学ぶ数学(6) 積分法からの出典です。
algo-method.com
アルゴ式とは...
>・プログラミングや情報科学をコツコツ学べる「教科書」
>・学んだ内容をゲーム感覚で大量に実践できる「練習問題」
>の2つで構成される、Web上で完結した学習コンテンツです。

C++による「設計技法とデータ構造 (#毎日アルゴ式)」プログラミングで学ぶ数学(6) 積分

僕が作成、提出したコードは、以下のとおりです。

面積を求める (1)

algo-method.com

/*
C++による「設計技法とデータ構造 (#毎日アルゴ式)」プログラミングで学ぶ数学(6) 積分法
面積を求める (1)
https://algo-method.com/tasks/602
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
    ll n;
    cin>>n;
    ll ans=0;
    for(ll i=1;i<=n;i++){
        ans+=i;
    }
    cout<<ans<<endl;
    return 0;
}
面積を求める (2)

algo-method.com

/*
C++による「設計技法とデータ構造 (#毎日アルゴ式)」プログラミングで学ぶ数学(6) 積分法
面積を求める (2)
https://algo-method.com/tasks/603
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
    ll l,r,a,b;
    cin>>l>>r>>a>>b;
    ll ans=0;
    for(ll i=l;i<r;i++){
        ans+=a*i+b;
    }
    cout<<ans<<endl;
    return 0;
}
面積を求める (3)

algo-method.com

/*
C++による「設計技法とデータ構造 (#毎日アルゴ式)」プログラミングで学ぶ数学(6) 積分法
面積を求める (3)
https://algo-method.com/tasks/604
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ld=long double;
int main(void){
    ld a,b,h;
    cin>>a>>b>>h;
    for(int i=0;i<=5;i++){
        ld n=pow(10,i);
        ld ans=0;
        for(int x=0;x<n;x++){
            ld S=(a+(b-a)/n*x)*(h/n);
            ans+=S;
        }
        cout<<fixed<<setprecision(10)<<ans<<endl;
    }
    return 0;
}
円周率を求める

algo-method.com

/*
C++による「設計技法とデータ構造 (#毎日アルゴ式)」プログラミングで学ぶ数学(6) 積分法
円周率を求める
https://algo-method.com/tasks/606
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ld=long double;
ld f(ld x){
    return sqrt(1-x*x);
}
int main(void){
    ld n;
    cin>>n;
    ld S=0;
    for(int x=0;x<n;x++){
        ld num=f(x/n)*(1/n);
        S+=num;
    }
    double ans=S*4;
    cout<<fixed<<setprecision(10)<<ans<<endl;
    return 0;
}
微分の逆操作

algo-method.com

/*
C++による「設計技法とデータ構造 (#毎日アルゴ式)」プログラミングで学ぶ数学(6) 積分法
微分の逆操作
https://algo-method.com/tasks/690
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n;
    cin>>n;
    vector<int> a(n+1);
    for(int i=0;i<=n;i++){
        cin>>a[i];
    }
    vector<int> b(n+2);
    for(int i=0;i<=n+1;i++){
        if(i==0){
            b[i]=0;
        }else{
            b[i]=a[i-1]/i;
        }
    }
    for(int i=0;i<=n+1;i++){
        cout<<b[i]<<((i==n+1) ? "\n" : " ");
    }
    return 0;
}
三角形の面積を求める

algo-method.com

/*
C++による「設計技法とデータ構造 (#毎日アルゴ式)」プログラミングで学ぶ数学(6) 積分法
三角形の面積を求める
https://algo-method.com/tasks/691
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int d,h;
    cin>>d>>h;
    cout<<d*h/2<<endl;
    return 0;
}
円錐の体積を求める

algo-method.com

/*
C++による「設計技法とデータ構造 (#毎日アルゴ式)」プログラミングで学ぶ数学(6) 積分法
円錐の体積を求める
https://algo-method.com/tasks/692
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int d,h;
    cin>>d>>h;
    cout<<d*h/3<<endl;
    return 0;
}
円の面積を求める

algo-method.com

/*
C++による「設計技法とデータ構造 (#毎日アルゴ式)」プログラミングで学ぶ数学(6) 積分法
円の面積を求める
https://algo-method.com/tasks/693
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int r;
    cin>>r;
    cout<<r*r<<endl;
    return 0;
}
発展: 球の体積を求める

algo-method.com

/*
C++による「設計技法とデータ構造 (#毎日アルゴ式)」プログラミングで学ぶ数学(6) 積分法
発展: 球の体積を求める
https://algo-method.com/tasks/698
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    double r;
    cin>>r;
    double ans=(double)4/3*pow(r,3);
    cout<<fixed<<setprecision(10)<<ans<<endl;
    return 0;
}
発展: 球の表面積を求める

algo-method.com

/*
C++による「設計技法とデータ構造 (#毎日アルゴ式)」プログラミングで学ぶ数学(6) 積分法
発展: 球の表面積を求める
https://algo-method.com/tasks/699
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int r;
    cin>>r;
    int ans=4*r*r;
    cout<<ans<<endl;
    return 0;
}
発展: ガブリエルのラッパ

algo-method.com

/*
C++による「設計技法とデータ構造 (#毎日アルゴ式)」プログラミングで学ぶ数学(6) 積分法
発展: ガブリエルのラッパ
https://algo-method.com/tasks/700
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    double n;
    cin>>n;
    double ans=(double)1-1/n;
    cout<<fixed<<setprecision(10)<<ans<<endl;
    return 0;
}

設問の出典は、情報科学をコツコツ積み立てて学習できるサービス「アルゴ式(beta版)」です。
algo-method.com