長ったらしいし誰得なんだろうけどどうせ誰も見ないから・・・。
ここに載ってた本選問題例を解いてみた。FizzBuzzチックな問題をひたすら解き続けるのは脳みそがトロンとします。
まあ本選第1ステージ問題の方は以前に解いたものなんですがその時で5問15分掛からずに解けたので、本番もピンッとくる問題ばかりだといいなー。
本選第１ステージ問題
問1.友愛数
言われた通りのことを。速度問題かな ? O(√n)で解けるけど実装楽なのでこっち。
#include <iostream> using namespace std; int main(){ int n,r = 0; int a,b,c,d; cin >> n; while(n--){ c = d = 0; cin >> a >> b; for(int i=1;i<a;i++){ if(a%i==0)c+=i; } for(int i=1;i<b;i++){ if(b%i==0)d+=i; } if(a==d && b==c)r++; } cout << r << endl; }問2.素因数分解
適当なアルゴリズムで。最適化したらもっと早くなる。
#include <iostream> using namespace std; int main(){ int n; cin >> n; for(int i=2;i<=n;i++){ if(n%i==0){ cout << i; n/=i; if(n!=1)cout << "*"; i=1; } } cout << endl; }問3.相性度
小文字と大文字の時の条件分岐して足すだけ。
Aが1で始まるので1足す。2人分の名前を一つの文字列にまとめたら楽。
#include <iostream> using namespace std; int main(){ string a,b; int sum = 0; cin >> a >> b; a+=b; for(int i=0;i<a.length();i++){ if(a[i]<'a'){ sum +=(a[i]-'A'+1); }else{ sum +=(a[i]-'a'+1); } } cout << sum%11 << endl; }問4.欠席者を探せ
AからZまで26個分の配列用意して表示するだけ。
#include <iostream> using namespace std; int main(){ int alpha[26]={0}; string str; cin >> str; for(int i=0;i<str.size();i++) alpha[str[i]-'A']++; for(int i=0;i<26;i++) if(!alpha[i])cout << (char)(i+'A') << endl; }問5.実質の参加者数は?
出てきた数字でユニークなものを数えるだけ。
#include <iostream> using namespace std; int main(){ bool p[100]={0}; int n,t,r=0; cin >> n; while(cin>>t){ if(!p[t-1])r++; p[t-1]=true; } cout << r << endl; }
本選最終ステージ問題
問1.合計額は何通り?
10個なので二進数を利用した組み合わせの生成で解ける。
生成した額をキーにしてmapにアクセスしてsizeを増やしてる。mapなので重複も勝手に消える。
最後に生成できるパターン数 = mapのサイズなのでそれを出力。(1個以上選んだ時なので1からループ)
#include <map> #include <iostream> using namespace std; int main(){ map<int,bool> able; int coin[10],price; for(int i=0;i<10;i++){ cin >> coin[i]; } for(int i=1;i<(1<<10);i++){ price = 0; for(int b=0;b < 10;b++){ if( i&(1<<b) )price+=coin[b]; } able[price]; } cout << able.size() << endl; }問2.ビンゴ
やるだけ、実装だるい。最初にビンゴなったのを出力すれば良い。最初、ビンゴ成立の時に読み上げられたやつ全部出力しないといけないと思って絶望してた。まあ絶望するほどのことではないけど。
初期化面倒くさいのでグローバル変数でしてる。
#include <iostream> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) int n,bingo; int x,y,key; bool flag; int p[5][5]; bool b[5][5]; int main(){ cin >> n; rep(i,5)rep(j,5)cin >> p[i][j]; rep(k,n){ cin >> key; y=-1;x=-1; rep(i,5)rep(j,5)if(p[i][j]==key){y=i;x=j;} if( y==-1 || x==-1 )continue; b[y][x] = true; /* 横 */ rep(i,5){ flag = true; rep(j,5)if(!b[i][j]){flag=0;break;} if(flag && !bingo)bingo = p[y][x]; } /* 縦 */ rep(i,5){ flag = true; rep(j,5)if(!b[j][i]){flag=0;break;} if(flag && !bingo)bingo = p[y][x]; } /* ＼ */ flag = true; rep(i,5)if(!b[i][i]){flag=0;break;} if(flag && !bingo)bingo = p[y][x]; /* ／ */ flag = true; rep(i,5)if(!b[4-i][4-i]){flag=0;break;} if(flag && !bingo)bingo = p[y][x]; } cout << bingo << endl; }問3.都市間バス
都市の数が(N≦10)なので普通にワーシャルフロイド法で実装できる。
#include <iostream> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) int main(){ int n,m; int a,b,c; int cost[10][10]; rep(i,10)rep(j,10)cost[i][j]=(1<<21); rep(i,10)cost[i][i]=0; cin >> n >> m; rep(i,m){ cin >> a >> b >> c; a--;b--; cost[a][b] = cost[b][a] = c; } rep(k,n)rep(i,n)rep(j,n) cost[i][j] = cost[j][i] = min(cost[i][j],cost[i][k]+cost[k][j]); cout << cost[0][n-1] << endl; }問4.為替レート
四捨五入とかすごい適当に書いたのでもしかしたらWAもらうかもしれない。%.0lfは四捨五入してくれなかった。
cinちゃんマジ便利。scanf("%c%d",&type,&money)じゃうまく読み込んでくれなかった。
#include <iostream> #include <cstdio> using namespace std; int main(){ char type; double money; double a,b; double y,e,s; cin >> a >> b; cin >> type >> money; if(type=='Y'){ y = money; s = money / a ; e = money / b ; } if(type=='E'){ y = money * b ; s = y / a; e = money; } if(type=='S'){ y = money * a ; s = money ; e = y / b; } printf("Y%d S%.2lf E%.2lf\n",(int)(y+0.5),s,e); }問5 多項式を割った余り
愚直に筆算再現する方法しか思いつかなくて、シミュレーション面倒くさかったので解いてません。効率的な解法があるんだろうけど。
とりあえず解いてみて問題の傾向とかが全然違うなーと感じた。PC甲子園とかJOIとかより容易だけどいかに早く実装できるかみたいな感じ。それも楽しそう。
