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問題でこの実装量、絶対理想解じゃない気がするんだよなあ…(˘ω˘)
AGC018
大爆散☆
http://agc018.contest.atcoder.jp/
AC:Aのみ300点
A
解法:鳩ノ巣応用
全ての数のGCDを取ってKがその数で割り切れればOKなのになんでこんな実装をしたのか自分でもこれが分からない
因みに実行時間1600ms超
#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; //////////////////////// /* a */ int d[10005]; int main(){ int n,k; cin >> n >> k; bool f=true; int a[n+1],m=0,m2=ATCODER; for(int i=0;i<n;i++){ cin >> a[i]; if(m<a[i])m=a[i]; if(a[i]==k)m2=a[i]; } if(m2==k); else if(k>m)f=false; else{ for(int i=0;i<n;i++){ if(!(a[i]%2)){ d[2]++; while(!(a[i]%2))a[i]/=2; } for(int j=3;j<=a[i]&&j<10005;j+=2){ if(!(a[i]%j)){ d[j]++; while(!(a[i]%j))a[i]/=j; } } } int c = 0; for(int i=2;i<10005;i++){ // cout << d[i] << " "; if(d[i]==n&&(k%i)){f=false;break;} } // cout << endl; } if(f)cout << "POSSIBLE" << endl; else cout << "IMPOSSIBLE" << endl; }
ちゃんとGCDをとるとこう
実行時間50ms
#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; //////////////////////// /* a */ int d[10005]; int gcd(int l,int r){ int m; while(r){ m = r; r = l%r; l = m; } return l; } int main(){ int n,k; cin >> n >> k; int a[n+1],m=0,m2=ATCODER; for(int i=0;i<n;i++){ cin >> a[i]; if(m<a[i])m=a[i]; if(a[i]==k)m2=a[i]; } int t=gcd(a[0],a[1]); REP2(i,2,n){ t = gcd(t,a[i]); } if(k<=m&&!(k%t))cout << "POSSIBLE" << endl; else cout << "IMPOSSIBLE" << endl; }
TOEICを無勉強で受けた結果
TOEICL&R受けるために昨日は何もせず
受けた感想:
・リスニングがむずい センターとは比べ物にならない
日本語でも聞き直すことが多い()自分には辛いものでした
・一方でリーディングは簡単 センターほどの長文が出ず高々第5問程度…だが数が多い めちゃんこ多い でも斜め読みができて案外楽だった(明治大学の全学統一試験の英語を受けた経験からか)
まとめ:単語レベルは大体足りていたので問題はリスニング力