公式にupされていたので。再度解くものもあるが、先輩が解いてて自分が解いていない問題なども解いた。時間を測りながらやった。長い記事になってるので注意。(続きを読むでソースとかいろいろ)
(*システムテスト通していないので間違っている可能性の方が高いです。)
1 水道料金を節約しよう。
本番でなんかパニくった問題。実際解いて混乱した。微妙にスマートな解法思いつかない。
11min.
#include <iostream> using namespace std; int main(){ const int prev = 4280; int n,ret; while(cin >> n , ~n){ ret = 1150; if(n>10){ if(n<20)ret+=(n-10)*125; else ret+=125*10; } if(n>20){ if(n<30)ret+=(n-20)*140; else ret+=140*10; } if(n>30)ret+=(n-30)*160; cout << prev-ret << endl; } }
2 病院でウォーキング
初見。
4min.
#include <iostream> using namespace std; int main(){ int n,p,a,b; while(cin >> n , n){ pair<int,int> ret = make_pair(0,0) ; for(int i=0;i<n;i++){ cin >> p >> a >> b; ret = max(ret,make_pair(a+b,p)); } cout << ret.second << " " << ret.first << endl; } }
3 塾のクラス分け
これもまた本選でパニくって先輩に修正してもらった問題。やるだけなのにパニくりすぎだ。
論理式を吟味しつつ冷静に解いた。
6min.
#include <iostream> using namespace std; int main(){ int n,a,b,c; while(cin >> n , n){ for(int i=0;i<n;i++){ cin >> a >> b >> c; if( (a==100||b==100||c==100) || a+b>=90*2 || a+b+c>=80*3 ){ cout << "A" << endl; }else if( a+b+c>=70*3 || (a+b+c>=50*3 && (a>=80 || b>=80)) ){ cout << "B" << endl; }else{ cout << "C" << endl; } } } }
4 人気のアイスクリーム店
初見。
5min.
#include <iostream> using namespace std; int main(){ int n,a; while(cin >> n,n){ int dat[10] = {0}; for(int i=0;i<n;i++){ cin >> a; dat[a]++; } for(int i=0;i<10;i++){ if(!dat[i])cout << "-"; for(int j=0;j<dat[i];j++) cout << "*"; cout << endl; } } }
5 博士の愛した2進数
本番で結局WA出した問題。悔しかった。原因はケアレスミス。
12min.
#include <iostream> #include <algorithm> using namespace std; string db(int n){ string ret; for(int i=0;i<8;i++){ ret+='0'+n%2; n/=2; } reverse(ret.begin(),ret.end()); return ret; } string check(double n){ double table[] = {1.0/2,1.0/4,1.0/8,1.0/16}; for(int i=0;i<(1<<4);i++){ double sum = 0; string ret = ""; for(int j=0;j<4;j++){ if( i & (1<<j) ){ sum += table[j]; ret += "1"; }else{ ret += "0"; } } if(sum == n)return ret; } return ""; } int main(){ double n,dbl; while(cin >> n , n>=0 ){ dbl = n-(int)n; if( (int)n < (1<<8) && check(dbl) != ""){ cout << db( (int)n ) << "." << check(dbl) << endl; }else{ cout << "NA" << endl; } } }
6 FizzBuzz
初解き。問題自体は知ってたかもしれないが、ヨセフスのお芋みたいな感じになってるとは知らなかった。環状の実装に少し悩んだ。
22min.
#include <iostream> #include <algorithm> #include <sstream> #include <vector> using namespace std; string fizzbuzz(int n){ if(n%15==0)return "FizzBuzz"; if(n%3==0)return "Fizz"; if(n%5==0)return "Buzz"; stringstream ss; ss << n; return ss.str(); } int main(){ int n,m; string s; while(cin >> m >> n, m){ vector<int> rem(m); for(int i=0;i<m;i++){ rem[i] = i+1; } int c = 0; for(int i=1;i<=n;i++){ cin >> s; if(s != fizzbuzz(i) ){ rem.erase(remove(rem.begin(),rem.end(),rem[c]),rem.end()); }else{ c =(c+1)%rem.size(); } } for(int i=0;i<rem.size();i++){ cout << (i?" ":"") << rem[i]; } cout << endl; } }
7 四つ子素数
なんでこれが17点問題なんだ(憤怒)。少々遅い。
8min.
#include <iostream> #include <vector> using namespace std; vector<bool> prime(10000001,true); void init_prime(){ prime[0] = prime[1] = false; for(int i=2;i*i<=10000000;i++){ if(prime[i]){ for(int j=i*2;j<=10000000;j+=i){ prime[j] = false; } } } } int main(){ init_prime(); int n; while(cin >> n , n ){ while(n){ if( prime[n] && prime[n-2] && prime[n-6] && prime[n-8] ){ cout << n << endl; break; } n--; } } }
8 迷子の双子
本番で非効率的な解き方したり、深さ優先したりして迷走して時間切れになったので思い入れがある問題。
今度は、頭の中を整理できるデータ構造でやった。
17min.
/* 44 - 01*/ #include <iostream> #include <vector> #include <queue> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) int dx[] = { 0, 0,-1, 1}; int dy[] = { 1,-1, 0, 0}; class NODE{ public: int x1; int y1; int x2; int y2; int depth; }; int main(){ int X,Y,tx,ty,kx,ky; bool data[52][52]; while(cin >> X >> Y , X){ cin >> tx >> ty >> kx >> ky; rep(i,52)rep(j,52)data[i][j] = 1; rep(i,Y)rep(j,X){ cin >> data[1+i][1+j]; } queue<NODE> Q; NODE t = {tx,ty,kx,ky,0}; Q.push(t); bool done[52][52][52][52] = {0}; while(Q.size()){ NODE q = Q.front();Q.pop(); if(q.depth >= 100)continue; if( done[q.x1][q.y1][q.x2][q.y2] )continue; done[q.x1][q.y1][q.x2][q.y2] = true; if(q.x1 == q.x2 && q.y1 == q.y2){ cout << q.depth << endl; goto end; } rep(i,4){ NODE next; next.x1 = q.x1 + dx[i]; next.y1 = q.y1 + dy[i]; next.x2 = q.x2 - dx[i]; next.y2 = q.y2 - dy[i]; next.depth = q.depth + 1; if(data[next.y1][next.x1] == 1){ next.x1 = q.x1; next.y1 = q.y1; } if(data[next.y2][next.x2] == 1){ next.x2 = q.x2; next.y2 = q.y2; } Q.push(next); } } cout << "NA" << endl; end:; } }
9 自転車でダイエット
問題文複雑すぎ+実装大変そう。で解くのを本番で諦めた問題。実際、今回問題文読んで理解するのに30分以上掛かった。
本番で解くのなんてムリムリ。むしろこのソースが間違ってる可能性が高い。特にノード情報の部分。AOJ出たらWAもらう可能性濃厚。
10/19(火) 01:56 AOJにWAもらったので修正。解法大幅変更。
105min.
#include <iostream> #include <vector> #include <map> #include <sstream> #include <queue> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) typedef pair<pair<int,string>,int> NODE; #define cost first.first #define pos first.second #define visit second map<string,vector< pair<string,int> > > nodeInfo; map<string,int> cakeShop; int dijkstra(){ int ret = (1<<25); priority_queue<NODE,vector<NODE>,greater<NODE> > Q; Q.push(make_pair(make_pair(0,"H"),0)); map<string,int> memo[1<<10]; while(Q.size()){ NODE q = Q.top();Q.pop(); //cout << q.visit << " " << q.cost << endl; if(memo[q.visit].find(q.pos) != memo[q.visit].end() ){ if(memo[q.visit][q.pos] <= q.cost)continue; } memo[q.visit][q.pos] = q.cost; if(q.pos == "D"){ ret = min(q.cost,ret); } rep(i,nodeInfo[q.pos].size()){ NODE next; next.visit = q.visit; next.cost = q.cost + nodeInfo[q.pos][i].second; next.pos = nodeInfo[q.pos][i].first; if(next.pos[0] == 'C' && (q.visit & (1<<(next.pos[1]-'1'))) )continue; if(next.pos[0] == 'C'){ next.visit |= (1<<(next.pos[1]-'1')); next.cost -= cakeShop[next.pos]; //cout << next.visit << endl; } Q.push(next); } } return ret; } int main(){ int m,n,k,d; int base; while(cin >> m >> n >> k >> d , m ){ nodeInfo.clear(); cakeShop.clear(); rep(i,m){ int c; cin >> c; stringstream ss; ss << 'C' << i+1; //cout << ss.str() << "=" << c << endl; cakeShop[ss.str()] = c; } //cout << cakeShop["C1"] << endl; rep(i,d){ string a,b;int c; cin >> a >> b >> c; nodeInfo[a].push_back( make_pair(b,c*k) ); nodeInfo[b].push_back( make_pair(a,c*k) ); } cout << dijkstra() << endl; } }
10 こぶたぬきつねこ
本番で、スマートな解法を目指してWAをもらった問題。あとで思えばこの解法にすれば計算量バッチグーやった・・・。
単語を端と端で圧縮して、出現度で管理して、バックトラック(というか深さ優先探索?)。
18min.
#include <iostream> #include <vector> #include <map> using namespace std; int n; map<string,int> data; string start; bool flag; void bt(string s,int depth){ if(depth == n-1){ if(s[1] == start[0])flag = true; } if(flag)return; for(map<string,int>::iterator it = data.begin(); it != data.end(); ++it){ if(s[1] == (*it).first[0] && (*it).second ){ (*it).second--; bt((*it).first,depth+1); (*it).second++; } } } int main(){ string s; while(cin >> n,n){ data.clear(); for(int i=0;i<n;i++){ cin >> s; s = s.substr(0,1) + s.substr(s.length()-1,1); data[s]++; } start = s; // 最後に入力されたs data[start]--; flag = false; bt(start,0); cout << (flag?"OK":"NG") << endl; } }
