ABC069
８位でした。わーい
ただ、簡単な問題だったので速度勝負だったのがなんとも
頭悪い自分は600点問題がDに出ると死んでしまうなさけない人だからねしょうがないね
A：-1して乗算するだけ
B：stringを使えばあら不思議な問題
C：これよくわからず全通り場合分け
2の倍数を2,4の倍数を4,残りを1と書き換える
1)141422...2244...44
2)1414...14141
3)22...2244...44
この3通りのいずれかに並べ替えることができない配列はNo
この時要素数c(1),c(2),c(4)に注目すると
1)はc(1)<=c(4),c(2)!=0
2)はc(2)=0,c(1)+1=c(4)
3)はc(1)=0
これをちゃんと分ければOK
でも縮約できそう＆正しいのか疑問
D：ジグザグに数字を埋めていけばOK Testcaseで分かるレベルのバグを埋めてしまい手間取って順位が3つくらい落ちた模様
#include <iostream> #include <deque> #include <vector> #include <cstdio> #include <cstring> #include <utility> #include <algorithm> #include <string> #include <cmath> #include <queue> #include <cmath> #define i64 long long #define ui64 unsigned long long #define REP(i,n) for(int (i)=0;(i)<(n);i++) #define REP2(i,k,n) for(int (i)=(k);(i)<(n);i++) #define MDIST(a,b) abs(a-b) #define DIST(a,b) sqrt((a)*(a)+(b)*(b)) #define ATCODER 1000000007 using namespace std; //////////////////////// /* a */ int main(){ int a,b; cin >> a >> b; cout << (a-1)*(b-1) << endl; } /* b */ int main(){ string a; cin >> a; cout << a[0] << a.size()-2 << a[a.size()-1] << endl; } /* c */ int main(){ int n; cin >> n; int c1=0,c2=0,c4=0; int a; REP(i,n){ cin >> a; if(!(a%4))c4++; else if(!(a%2))c2++; else c1++; } // cout << n << " " << c2 << " " << c4 << endl; if(c1){ if(c2){ if(c1<=c4)cout << "Yes" << endl; else cout << "No" << endl; }else{ if(c1<=c4+1)cout << "Yes" << endl; else cout << "No" << endl; } }else cout << "Yes" << endl; } /* d */ int main(){ int H,W,N; cin >> H >> W >> N; int a[N]; REP(i,N){ cin >> a[i]; } int d[H][W]; int f=0; REP(i,H){ if(i%2){ for(int j=W-1;j+1;j--){ d[i][j]=f+1; if(a[f]>1)a[f]--; else f++; } }else{ for(int j=0;j<W;j++){ d[i][j]=f+1; if(a[f]>1)a[f]--; else f++; } } } for(int i=0;i<H;i++){ for(int j=0;j<W;j++){ cout << d[i][j] << " "; }cout << endl; } }
DSL_2_B
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B
この手のクエリが出たときに系が弱すぎる気がしたのでとりあえずBITの実装をやることに
幾何はどうしたって…？忙しさで忘れました
とりあえずこんなんでいいかなと精進に際してペタリできるようにちゃんとクラスを実装
最近こういうのちゃんとした方がいいかもなと思い始めたのでやることにしました
#include <iostream> #include <deque> #include <vector> #include <cstdio> #include <cstring> #include <utility> #include <algorithm> #include <string> #include <cmath> #include <queue> #define i64 long long #define ui64 unsigned long long #define REP(i,n) for(int (i)=0;(i)<(n);i++) #define REP2(i,k,n) for(int (i)=(k);(i)<(n);i++) #define MDIST(a,b) abs(a-b) #define DIST(a,b) sqrt((a)*(a)+(b)*(b)) #define ATCODER 1000000007 using namespace std; //////////////////////// class BIT{ int size; vector<i64> tree; public: BIT():size(0),tree(0){}; BIT(int n):size(n),tree(n+1,0){}; void add(i64 x,int n){ for(int i=n;i<=size;i+=i&-i){ tree[i]+=x; } } i64 sum(int s,int t){ if(s>t)return 0; i64 res=0; for(int i=t;i>0;i-=i&-i){ res += tree[i]; } for(int i=s-1;i>0;i-=i&-i){ res -= tree[i]; } return res; } i64 get(int n){ return tree[n]; } }; int main(){ int n,q; cin >> n >> q; BIT d(n); int com,x,y; for(int i=0;i<q;i++){ cin >> com >> x >> y; if(com)cout << d.sum(x,y) << endl; else d.add(y,x); } }
CGL_1_A
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_1_A
なかなか忙しい（大嘘）のでとりあえずなかなか手を出していない幾何問題を
これ実装するだけで相当疲れているあたり重症なので早急に問題を解いておきたい
#include <iostream> #include <deque> #include <vector> #include <cstdio> #include <cstring> #include <utility> #include <algorithm> #include <string> #include <cmath> #include <queue> #include <iomanip> #define i64 long long #define ui64 unsigned long long #define REP(i,n) for(int (i)=0;(i)<(n);i++) #define REP2(i,k,n) for(int (i)=(k);(i)<(n);i++) #define MDIST(a,b) abs(a-b) #define DIST(a,b) sqrt((a)*(a)+(b)*(b)) using namespace std; //////////////////////// struct po{ double x,y; po(double x_,double y_):x(x_),y(y_){}; po():x(0),y(0){}; }; struct vc{ double x,y; vc():x(0),y(0){}; vc(po f ,po t):x(t.x - f.x),y(t.y - f.y){ // x = t.x - f.x; // y = t.y - f.y }; }; double norm(vc &a){ return DIST(a.x,a.y); } double dot(vc &a,vc &b){ return a.x*b.x+a.y*b.y; } int main(){ double a,b,c,d; cin >> a >> b >> c >> d; po p(a,b),q(c,d); vc v1(p,q); cin >> a; cout << fixed; cout << setprecision(10); REP(i,a){ cin >> b >> c; po r(b,c); vc v2(p,r); double t = dot(v1,v2) / (norm(v1) * norm(v1)); cout << p.x+v1.x*t << " " << p.y+v1.y*t << endl; } }
AOJ2407
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2407
解放：やるだけ O(N)
互い違いが奇数なら先手必勝
偶数なら外側が必勝
#include <iostream> #include <string> using namespace std; int main(){ string s; cin >> s; int c = 0; for(int i=0;i<s.size()-1;i++){ if(s[i]!=s[i+1])c++; } // cout << c << endl; if(c%2)cout << 'o' << endl; else cout << s[0] << endl; }
AOJ2502
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2502
ボカロかな？（）
解法：制限なしナップサック同様のDP 計算量謎
ナップサック問題の重さに幅があるというだけ
数の制約が小さいのでこれでOK
#include <iostream> #include <vector> using namespace std; int main(){ int n,m; cin >> n; int s,l,p; int w[400]={0,}; for(int i=0;i<n;i++){ cin >> s >> l >> p; for(int j=s;j<=l;j++){ for(int k=0;k+j<=399;k++){ w[k+j]=max(w[k+j],w[k]+p); } } } cin >> m; int d[m]; bool ans = true; for(int i=0;i<m;i++){ cin >> d[i]; if(!w[d[i]])ans=false; } if(!ans)cout << -1 << endl; else{ for(int i=0;i<m;i++){ cout << w[d[i]] << endl; } } }
ARC076_D
解法：最小全域木 O(NlogN)？
普通に最小全域木をやろうとすると辺の数O(N^2)で死亡するので辺の数を減らす必要がある
とりあえずサンプル2をxで昇順ソートすると
4 9 7 6 8 3 12 19 13 5 18 1
yでソートするとこう
18 1 8 3 13 5 7 6 4 9 12 19
で、このサンプル2の解答は
{((4,9),(7,6)),((7,6),(8,3)),((8,3),(13,5)),((13,5),(12,19)),((8,3),(18,1))}の辺集合選択で合計の重みは8
つまり、xかyでソートした時に隣り合う点を繋ぐ辺しか採用されることはない
これらの辺の数は2n-2本なのでクラスカルすればいい、という問題
この日のABCでとけなかったので解説を直後に読んでいたので解法は覚えてたけどクラスカル法の実装に不安を覚えたので6割ほど素で書くことを目標に書きましたとさ
結果：全然だめでした
主にjoinの実装が雑すぎたせいで幾度となく閉路を作ってしまうアホやってたとか
結局こちら↓を参考に修正
http://www.prefield.com/algorithm/container/union_find.html
こちらのソースは1配列で経路圧縮とrank実装を同時実装してunionfindをすんごい小さい計算量に圧縮してるけど自分はrank実装してないので少し遅いです
#include <iostream> #include <deque> #include <vector> #include <cstdio> #include <cstring> #include <utility> #include <algorithm> #include <string> #include <cmath> #include <queue> #include <numeric> #define i64 long long #define ui64 unsigned long long #define REP(i,n) for(int (i)=0;(i)<(n);i++) #define REP2(i,k,n) for(int (i)=(k);(i)<(n);i++) #define MDIST(a,b) abs(a-b) #define DIST(a,b) sqrt((a)*(a)+(b)*(b)) #define ATCODER 1000000007 using namespace std; //////////////////////// class point{ public: int x,y,id; point(int x_,int y_,int i_):x(x_),y(y_),id(i_){} point():x(0),y(0){} }; bool compx(const point &b,const point &a){ return b.x==a.x?b.y<a.y:b.x<a.x; } bool compy(const point &b,const point &a){ return b.y==a.y?b.x<a.x:b.y<a.y; } class edge{ public: int f,t,c; bool operator<(const edge &a){ return c<a.c; } edge(int f_,int t_,int c_):f(f_),t(t_),c(c_){} }; class uf{ public: vector<int> r; uf(int n):r(n,-1){}; int find(int x,int y){ if(root(x)==root(y))return 0; if(root(x)<root(y))return -1; if(root(x)>root(y))return 1; } int root(int x){ if(r[x]==-1)return x; else return r[x]=root(r[x]); } void join(int x,int y){ x=root(x);y=root(y); if(x!=y){ r[x]=y; } } }; class graph{ public: int vnum; vector<edge> E; uf u; graph(int n):vnum(n),u(n){}; int kruscal(){ int res=0; sort(E.begin(),E.end()); for(int i=0,c=0;i<E.size()&&c<vnum-1;i++){ if(u.find(E[i].f,E[i].t)){ u.join(E[i].f,E[i].t); res+=E[i].c; c++; } } return res; } }; int main(){ int n; cin >> n; int x,y; vector<point> p; for(int i=0;i<n;i++){ cin >> x >> y; p.push_back(point(x,y,i)); } graph g(n); sort(p.begin(),p.end(),compx); for(int i=0;i<n-1;i++){ g.E.push_back(edge(p[i].id,p[i+1].id,min(abs(p[i].x-p[i+1].x),abs(p[i].y-p[i+1].y)))); } sort(p.begin(),p.end(),compy); for(int i=0;i<n-1;i++){ g.E.push_back(edge(p[i].id,p[i+1].id,min(abs(p[i].x-p[i+1].x),abs(p[i].y-p[i+1].y)))); } cout << g.kruscal() << endl; }
D問題でこの実装量、絶対理想解じゃない気がするんだよなあ…(˘ω˘)
