AOJ2501
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2501
解法:商と余のマンハッタン距離を求める
計算量:O(N)
サンプルを見ればなんとなく分かるだろうか。
図が丁寧に書かれているのが分かりやすい。
但し入力の数字をそれぞれ-1しないと余りがw=4の時の出力が合わない。(それを注視したケースもある)
#include <iostream> #include <cmath> using namespace std; int main(){ int n,a,b,c,d,p,q,res=10000; cin >> n >> a >> b >> c >> d; a--;b--;c--;d--; for(int w=1;w<=n;w++){ p = abs(a/w-b/w) + abs(a%w-b%w); q = abs(c/w-d/w) + abs(c%w-d%w); //cout << p <<" " << q << endl;; res = min(res,p+q); } cout << res << endl; }
AOJ2101
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2101
解法:線形に調べるだけ
コーナーケースがN=1の場合というのは恐れ入った。流石UT
N=1をどう弾いてやるかと思ったが結局最後の出力で無理やりdeficientにする方法で落ち着いた。
#include <cstdio> #define i64 long long using namespace std; int main(){ i64 r,n; while(scanf("%lld",&n),n){ r=0LL; for(i64 i=1LL;i*i<n;i++){ if(!(n%i)){ r+=i;if(i>1)r+=n/i; } } // printf("%d %d\n",n,r); if(r>n){ puts("abundant number"); } else if(r==n&&n!=1){ puts("perfect number"); } else{ puts("deficient number"); } } }
AOJ2440
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2440
解法:やるだけ O(nm)
制約がゆるいのでソートの必要もない
ソートすると二分探索できるのでクエリが早く終わるはず
#include <bits/stdc++.h> using namespace std; int main(){ int n,m; vector<string> u(257); string t; cin >> n; for(int i=0;i<n;i++){ cin >> u[i]; } cin >> m; bool open=false;//opened : true //closed : false for(int i=0;i<m;i++){ cin >> t; if(find(u.begin(),u.end(),t)!=u.end()){ if(open){ cout << "Closed by " << t << endl; open = false; }else{ cout << "Opened by " << t << endl; open = true; } }else{ cout << "Unknown " << t << endl; } } }
ICPCにっき
結果:3完
A:5分でささっと書いてAC。プリンターの動作が怪しくB、Cをメンバーが見れず。
B:文字列の分割が見えた時点でメンバーにパス。1回WAを見て交代。
C:Bをコーディングしてもらっている間にO( (dw)^2 )の雑なコードで大丈夫と見えていたので交代即実装。如何せんdw<=100
B:Cの小バグを埋めている間にBの方のデバッグが終わったのですぐにデバッグを行ったがemacs保存ミスという痛恨のアホをやらかし2回目のWA。3回目でAC。
C:交代後バグを取り切ってAC。D行けるかもと希望を持った(ここまで1時間台)
D:最初問題を誤読しており無向グラフの隣接行列か何かと勘違いしていた。
すぐに勘違いを修正したはいいが今度はろくな解法が思いつかない。
Fに逃亡。
Eはとっつきにくそうだった。
その後3人でDとFを読んでいたがどちらも有効な解法が出ず、Gを実装してもらったがバグで無限ループ。終了
はんせい
DがbitDPに見えたが場合分けしてもmax(min(n,m))=22を見て断念した。
が、実はそれが正解だったらしい。
そして、全探索を枝狩りする方向に走ったがいい方法が見当たらなかった。
が、これでも通していたチームがいた。
けつろん:精進が足りなかった
max(min(n,m))=22で通るのか…(16くらいが限界だと思っていた)
AOJ1188
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1188
Hierarchical Democracy
ICPC2013のC問題
解法:やるだけ
括弧が閉じるたびに下階層から表を集めて上に持っていく作業をする
sstreamが案外便利かもしれない気がしてきた
#include <string> #include <iostream> #include <sstream> #include <vector> #include <algorithm> using namespace std; int parseint(string s){ stringstream ss(s); int r; ss >> r; return r; } int sumdiv2(vector<int> &a){ int r=0; sort(a.begin(),a.end()); for(int i=0;i<a.size()/2+1;i++){ r+=a[i]/2+1; } return r; } int sum2(vector<int> &a){ int r=0; sort(a.begin(),a.end()); for(int i=0;i<a.size()/2+1;i++){ r+=a[i]; } return r; } int main(){ int n; int stack; cin >> n; string s; vector<vector<int> > votes; while(n--){ votes.clear(); stack = 0; int max = 0; cin >> s; while(s[max]=='[')max++; votes.resize(max+3); for(int i=0;i<s.size();i++){ if(s[i]=='[')stack++; else if(s[i]==']'){ stack--; if(!votes[stack+2].empty()){ if(stack+2==max){ votes[stack+1].push_back(sumdiv2(votes[stack+2])); }else{ votes[stack+1].push_back(sum2(votes[stack+2])); } votes[stack+2].clear(); } }else{ int r = parseint(s.substr(i)); votes[stack].push_back(r); while(r/10){r/=10;i++;} } } cout << votes[1][0] << endl; } }