いつもの
今日か明日中に反省と目標書きます
JOI Qualifying Open Contest
たぶん100点です．適当にGoogle Docで作ったものを持ってきています．
JOI Qualifying Open Contest Problem editorial
1
解説書きます．5つの数値が与えられる．これを，前半4つと後半2つとで分けて，それぞれ降順ソート→前半3つと後半1つを加算して出力．解説などを見ると前半は合計して最も小さい値を引く，などの解法もあった．
以下ソース
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) #define pb push_back int main() { int x; vector<int> vi; rep(i,4){ cin>>x; vi.pb(x); } int des=0,def=0; cin>>des>>def; if(des>def){ des=des; }else{ des=def; } sort(vi.begin(), vi.end(), greater<int>()); int ans=0; rep(i,3) ans+=vi[i]; ans+=des; cout<<ans<<endl; return 0; }
2
入力で嵌ったけどそこ以外は何とかなった．バトンの処理がネックになる．バトンは与えられる配列内の生徒が最後まで行ってから次の周回に入るので，ループは
#define rep(i,n) for(int i=0;i<n;i++) #define REP(a,b,c) for(int a=b;a=c;a++) REP(i,1,M) rep(j,n)
となる．処理の中心部になるゼッケンの交換処理は，std::swap()を使うと簡単に書ける．交換する条件は，a[j]とバトンkの剰余と，a[j+1]とバトンkの剰余において，前者のほうが後者より大きかった際に交換する．
以下ソース
#include <bits/stdc++.h> using namespace std; int main() { int n,m; scanf("%d%d",&n, &m); int a[200]; for(int i-0;i<n;i++){ scanf("%d",&a[i]); } for(int i-=1;i=m;i++){ for(int j=0;j<n;j++){ if(a[j]%k>a[j+1]%k) swap(a[j], a[j+1]); } } for(int i=0;i<n;i++){ printf("%d",a[i]); } return 0; }
3問目以降についてはまだ目を通していないので，そのうち書くか書かないと思います．
強化週間・・・？
何を思ったか強化週間と位置づけてAOJ解いてます．久々に1日で4問以上解いてる・・・
0608 Water Rate
去年の一問目です．ちゃんと条件を読めば60点なんて取るはずが無いですねｗ
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) int main() { int a,b,c,d,p; cin>>a>>b>>c>>d>>p; int ans=0, diff=0, com=0; ans=p*a; diff=b; if(p>c){ int cnt=p-c; com=cnt*d; diff+=com; } if(diff>ans){ cout<<ans<<endl; }else if(diff<ans){ cout<<diff<<endl;} return 0; }
一回提出して，CEを貰ったので修正して再度提出しなおしました．たしかCとDとの関係を全く書き間違えていました．
0554 Total Time
全部足して60で除算と剰余．
#include <iostream> using namespace std; int main(){ int a,b,c,d; cin>>a>>b>>c>>d; int ans=a+b+c+d; cout<<ans/60<<endl; cout<<ans%60<<endl; return 0; }
0565 Lunch
ものすごくグチャグチャなコードになってしまった．もう少しいいやり方あるだろコレ
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) #define pb push_back int main() { vector<int> a; vector<int> b; vector<int> ans; int cnt=0; rep(i,3){ int x; cin>>x; a.pb(x); } rep(i,2){ int x; cin>>x; b.pb(x); } sort(a.begin(), a.end()); sort(b.begin(), b.end()); cout<<(a[0]+b[0])-50<<endl; return 0; }
確か去年に過去問をCで解こうとしていた時は全く解らず解説を乞っても意味不明だったのですが，そんなに難しくなかった．ソートが使えたのが最大の利点かも．それぞれの最小値を足して引いて投げれば○．
0576 Homework
今回最大の面倒くさかった問題かもしれない．何回か計算の分岐に嵌った．しかも最大に汚い．
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) #define MAX 100 int main() { int l,a,b,c,d; cin>>l>>a>>b>>c>>d; int ans=0, diff=0; if(a%c==0){ ans=a/c; }else{ ans=a/c+1; } if(b%d==0){ diff=b/d; }else{ diff=b/d+1; } if(ans>diff){ cout<<l-ans<<endl; }else{ cout<<l-diff<<endl; } return 0; }
もう少し解いたら寝ることにしたい．昨日の21時に寝てついさっき7時ころに起きたのだけれど，既に眠たさが込み上がってきてる．流石に18時とかに寝て試験遅れるのは勘弁なので程々にします．
今日解いたもの
AOJ 0535 Crossing Black Ice
簡単そうに見えて簡単じゃなかった．辛い．理屈としては，1と0で示された図の中で，1がある個所を最大でいくつ回れるかを求める．再帰を使う&最大値を求めるので，max()を使う，再帰は別の自作関数で適当に記述する，の3つは想像ついたし書いたけど，max()を書く過程で，比較するものが解らなかったりした．必要だったのはほぼそこだけで，それ以外は特に変えることもなく書いた．
ACコード
//AOJ 0535 Crossing Black Ice non-submited code. //??????????????°??????????????°???????????¨?????? #include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <functional> using namespace std; #define rep(i,n) for(int i=1;i<=n;i++) typedef long long ll; #define MAX 92 int map[MAX][MAX]; //node ex. int vx[]={1,0,-1,0}; int vy[]={0,1,0,-1}; int dfs(int y, int x){ if(map[y][x]==0) return 0; int res=0; map[y][x]=0; for(int i=0;i<4;i++){ res=max(res, 1+dfs(y+vy[i],x+vx[i])); } map[y][x]=1; return res; } int main(){ int m,n; while(cin>>m>>n,m||n){ memset(map, 0, sizeof(map)); int ans=0; rep(i,m) rep(j,n) cin>>map[i][j]; rep(i,n){ rep(j,m){ ans=max(ans,dfs(i,j)); } } cout<<ans<<endl; } return 0; }
AOJ 0573 Receipt
一回whileを書くのを忘れていて，WAをもらったりして辛い．凡ミスすぎた．やるだけ．初期化をしっかりしいていれば問題無し．
// AOJ Problems id:0573 Receipt Accepted Code. #include <iostream> #include <vector> #include <list> #include <string> #include <algorithm> #include <cstdio> #include <cstring> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) #define repeat(a,b,c) for(int a=b;a=c;a++) #define pb push_back #define md 10000007 int main() { int n; while(cin>>n){ if(n==0) break; int ans=0; rep(i,10){ int x=0; cin>>x; ans+=x; } cout<<n-ans<<endl; } return 0; }
AOJ 0512
時間がないので(家を出る数分前)，簡単に書きます．AOJ 0512 Caesar Cipher : AC
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) int main() { char diff[27]={"ABCDEFGHIJKLMNOPQRSTUVWXYZ"}; char leg[27]={"DEFGHIJKLMNOPQRSTUVWXYZABC"}; int i=0; string ans; cin>>ans; while(ans[i]){ rep(j,26){if(ans[i]==leg[j]){ans[i]=diff[j];break;}} i++; } cout<<ans<<endl; return 0; }
解法
A〜Zの文字配列と，D〜Cの文字配列の２つを用意．それを，入力に応じた文字から文字コード-3した文字を，用意した2つの文字配列から選んで代入．それをループさせて，最後に出力．
SRM 669 Div.2 Easy
昨日20:00(JST)から出てました。0完です。分が悪いのは、サンプルI/O見つつやっと理屈を理解した辺りで(図や絵を書いたりして、筋道立てて説明できるようにはなった)20:51くらい。そっからなんとかコーディングしようとしたけどどうしようもなく眠いのと、理屈わかってるのにコードに落とせない・・・もとい書けなくて詰まっていた事です。
さっきArenaに入ってサマリーから何人かのコードを見ました。実際にコンテストに出て問題熟読して理屈理解してみての解答コード閲覧は、すごく(自分の発想力に対して)残念な気持ちになりました。大体の人はSTLのsort()使っている感じでした。で、「なにやってんだろう」と思いながら書いて通しました。
#include <bits/stdc++.h> using namespace std; class LiveConcert{ public: int maxHappiness(vector<int> h, vector<string> s){ sort(s.begin(), s.end()); s.erase(unique(s.begin(), s.end()), s.end()); sort(h.begin(), h.end(), greater<int>()); int ans=0; for(int i=0;i<s.size();i++){ ans+=h[i]; } return ans; } };
最初に書いてた時はif文使って、それをforで回して、というのを考えていたのですが、解答コード見てたら「必ずしもSTL使わない発想は無い」ことに気づいたりした。もともとfor・ifを使おうとした理由が文字列配列sにおいての重複削除だったのですが、よくよく考えたら確かにunique()で重複要素削除できるなぁ、と思い、STLの良さを再認識しました。重複削除したらどうすればいいかは分かってた(あとはただ単に降順ソート+要素数を全て加算してreturn)のでこれが問題でした。。。
いつもの
二問解いてた、AOJ 0011 Drawing LotsとAOJ 0075 BMI
Drawing LotsはいつものようにSolutionガン見なので書かないとして、BMIは普通に書きました。
AOJ 0075 BMI
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main(){ ll num; double p, c; char g; while(cin>>num>>g>>p>>g>>c){ if(p/(c*c)>=25) cout<<num<<endl; }return 0; }
2回提出してどちらもTLEだったので、テンプレ使って解いたら、あっさり解けた。一回一回BMI計算してからifってたのを、ifの中にぶち込んで番号変数numをlong long intで定義しなおしたら、あっさりと解けた。なんだったんだあのガバガバTLEは・・・
