ICPC2012 新入生教育編1 ループと配列と
本日は新入生に向けて配列・ループのテクニックを伝授した。以下は、その練習問題と解説を記す。
(ここ教えたほうがいいとかフィードバックあったらお願いします)
和の合計問題
n個のボールが与えられ、i番目のボールには数字a[i]が記されています。 ボールを3つ取り出した時に和がmとなる組み合わせが存在するか。存在する場合はYES、存在しない場合はNOを出力せよ。 なお、同じボールを複数回取り出せるものとする。 ただし値の範囲は以下のものとする。なお、n=0,m=0のとき終了とする。 0 <= n <= 100 0 <= m <= 3000 0 <= a[i] <= 1000 input n m a[0] a[1] ... sample input 4 5 1 2 3 4 4 128 1 2 3 4 0 0 sample output YES NO
解説編1 新入生に望む解法
nより大きい配列a[MAXN]をあらかじめ確保しておき、a[i]にボールの数字を入れていく
3重ループでa[i]+a[j]+a[k]==mとなれば存在する。
#include <iostream> using namespace std; const int MAXN=100; int a[MAXN]; int main() { int n,m; while(cin>>n>>m&&(n||m)) { for(int i=0;i<n;i++) cin>>a[i]; bool ans = false; for(int i=0;i<n;i++) for(int j=0;j<n;j++) for(int k=0;k<n;k++) { ans |= (a[i]+a[j]+a[k]==m); } cout<<(ans?"YES":"NO")<<endl; } return 0; }
また、下記の点について補足して教えておいた。
cinの使い方(値の取得からEOFの認識など)
const intや#defineで定数化しておくこと
ひと通り全員出来たところで、O(オーダー)の概念についても説明した。
今回の問題はforが1重と3重の部分がある。一番時間かかっている部分は3重の部分であるので、O(n^3)とする。
また、競技プログラミングにおける時間計算量の概算方法についても補足した。
O(n^3)でn<=100なので、100^3 => 10^6 => 1M(メガ)
プロセッサが1GHzとすると、10^6/10^9 => 0.001秒くらいである。
競技プログラミングでは2秒以内に終わるように求められることが多いので注意が必要である。
n<10000となった場合について考えてもらい
10000^3 => 10^12 => 1000秒くらいなので、もう少し早いアルゴリズムを考えてもらう。
解説編2 2年目以降の人に望む解答
O(n^2)で解くと、10000^2 => 10^8 => 0.1秒くらい
配列をうまく使う、類題が蟻本に載っているのでそちらを参考にしてもらった。
a[i]+a[j]==m-a[k]なので2重ループと2重ループなのでO(n^2)となる
#include <iostream> // cin cout #include <cstring> // memset using namespace std; const int MAXN=10000; const int MAXM=3001; int a[MAXN]; char b[MAXM]; int main() { int n,m; while(cin>>n>>m&&(n||m)) { for(int i=0;i<n;i++) cin>>a[i]; memset(b,0,sizeof(b)); for(int i=0;i<n;i++) for(int j=0;j<n;j++) { b[a[i]+a[j]]=1; } bool ans = false; for(int i=0;i<n;i++) { ans |= (m>=a[i]) && (b[m-a[i]]); } cout<<(ans?"YES":"NO")<<endl; } return 0; }
配列bの添字とa[i]+a[j]を対応させて記録しておくことが大事である。
素数の問題
素数とは、1と自分自身以外には割り切れない数のことをいう。 問題1 0 <= n <= 100 までの数が与えられる、素数の場合はYES 素数以外の場合はNOと出力せよ、なお0は終了を意味する。 問題2 6桁の素数を大きい順番に100個表示させなさい 問題3 6桁の素数の平均を整数で表示しなさい 問題4 6桁の素数のうち、3のつく素数の個数を表示しなさい (XXX3XXや3XXXXXなど) 入力例 問題1 1 2 3 4 5 6 7 出力例 問題1 NO YES YES NO YES NO YES 問題2 999983 ... 998539 問題3 550964 問題4 388800
問1,問2は問題文の素数の定義通りに考えれば良い。
問3は愚直にやると実行時間がかかるし、intの上限についても考慮すべきという落とし穴も用意した。
問4は各自工夫すべし。
新入生に望む解法1
#include <iostream> using namespace std; bool isPrime(int n) { if(n<=1) return false; for(int i=2;i<n;i++) if(!(n%i)) return false; return true; } int main() { int n; while(cin>>n&&n) { cout<<(isPrime(n)?"YES":"NO")<<endl; } return 0; }
新入生に望む解法2
ここでふるいさせても良かったけどさせなくてもいいことにした。
#include <iostream> using namespace std; const int MAXN=1000000; // 7桁の最小値 const int MINN=100000; // 6桁の最小値 bool isPrime(int n) { if(n<=1) return false; for(int i=2;i<n;i++) if(!(n%i)) return false; return true; } int main() { int num = 0; for(int i=MAXN-1;i>=MINN;i--) if(isPrime(i)) { cout<<i<<endl; if(num<100) num++; else break; // 中で比較した方が回数が減るけどあんま気にしない } return 0; }
2年目以降に望む解法3
#include <iostream> using namespace std; const int MAXN=1000000; const int MINN=100000; typedef long long int ll; // intよりでかい char prime[MAXN]; // グローバル変数は0で初期化される int main() { // エラトステネスのふるい for(int i=2;i*i<MAXN;i++) if(!prime[i]) for(int t=i*2;t<MAXN;t+=i) prime[t]=1; ll ans = 0; ll num = 0; for(int i=MAXN-1;i>=MINN;i--) if(prime[i]) { ans += i; num += 1; } cout<<(ans/num)<<endl; return 0; }
ansやnumをintにすると-1994になっちゃうよ。
エラトステネスのふるいのアルゴリズムは以下のとおり
とりあえず全部素数としておく (prime[x]==0)
2は素数 => 2の倍数は素数でない prime[4]=1; prime[6]=1; ...
3は素数 => 3の倍数は素数でない prime[6]=1; prime[9]=1; ...
4は素数でない (4の倍数は2の倍数の時に消したから気にしない)
5は素数 => ...
2年目以降に望む解法4
オーダー的に死ぬかと思ったけどそうでもなかった。
#include <iostream> using namespace std; const int MAXN=1000000; const int MINN=100000; char prime[MAXN]; // グローバル変数は0で初期化される int main() { // エラトステネスのふるい for(int i=2;i*i<MAXN;i++) if(!prime[i]) for(int t=i*2;t<MAXN;t+=i) prime[t]=1; int ans = 0; for(int i=MAXN-1;i>=MINN;i--) if(prime[i]) { int da = 0; for(int n=i;n;n/=10) da |= ((n%10)==3)?1:0; ans += da; } cout<<ans<<endl; return 0; }
その他、細いテクニックは他人のソースコードを見て勉強すべし。
