Codeforces Round #367 (Div. 2)
A. Beru-taxi
問題文
解法
シミュレーションする。
感想
やるだけ。
コード
#include <bits/stdc++.h> #define rep(i,n) for(int i = 0; i < n; i++) const double PI = 3.1415926535897932384626433832795028841971; const int INF = 100000000; const double EPS = 1e-10; const int MOD = 1000000007; using namespace std; typedef long long ll; typedef pair<int,int> P; double a, b; int n; double ans = 1000000.0; int main(){ cin >> a >> b; cin >> n; rep(i,n){ double x, y, v; cin >> x >> y >> v; ans = min(ans,sqrt((a-x)*(a-x)+(b-y)*(b-y))/v); } printf("%.9f\n",ans); }
B. Interesting drink
問題文
解法
飲み物の値段でソートしてクエリごとに二分探索をするだけ。
感想
やるだけ。
コード
#include <bits/stdc++.h> #define rep(i,n) for(int i = 0; i < n; i++) const double PI = 3.1415926535897932384626433832795028841971; const int INF = 1000000009; const double EPS = 1e-10; const int MOD = 1000000007; using namespace std; typedef long long ll; typedef pair<int,int> P; int n; int x[100001]; int q; int main(){ scanf("%d",&n); rep(i,n) scanf("%d",x+i); sort(x,x+n); x[n] = INF; scanf("%d",&q); rep(i,q){ int m; scanf("%d",&m); int s = 0, e = n, mid; while(e-s > 1){ mid = (e+s)/2; if(x[mid] <= m) s = mid; else e = mid; } if(x[0] > m) printf("0\n"); else printf("%d\n",s+1); } }
C. Hard problem
問題文
解法
dp[n][反転させるかどうか]のdpをするだけ。
感想
やるだけ。
コード
#include <bits/stdc++.h> #define rep(i,n) for(int i = 0; i < n; i++) const double PI = 3.1415926535897932384626433832795028841971; const long long int INF = 1000000000000000; const double EPS = 1e-10; const int MOD = 1000000007; using namespace std; typedef long long ll; typedef pair<int,int> P; int n; ll c[100000]; string str[100000], rev[100000]; ll dp[100000][2]; int main(){ cin.tie(0); ios::sync_with_stdio(false); cin >> n; rep(i,n) cin >> c[i]; rep(i,n) cin >> str[i]; rep(i,n){ rev[i] = str[i]; reverse(rev[i].begin(),rev[i].end()); } rep(i,n) rep(j,2) dp[i][j] = INF; dp[0][0] = 0; dp[0][1] = c[0]; for(int i = 1; i < n; i++){ if(str[i-1] <= str[i]){ dp[i][0] = min(dp[i][0],dp[i-1][0]); } if(rev[i-1] <= str[i]){ dp[i][0] = min(dp[i][0],dp[i-1][1]); } if(str[i-1] <= rev[i]){ dp[i][1] = min(dp[i][1],dp[i-1][0]+c[i]); } if(rev[i-1] <= rev[i]){ dp[i][1] = min(dp[i][1],dp[i-1][1]+c[i]); } } ll ans = min(dp[n-1][0],dp[n-1][1]); if(ans == INF) ans = -1; cout << ans << endl; }
D. Vasiliy's Multiset
問題文
解法
各xiを二分木の葉に対応させてそこに出現回数を記録する。
具体的には、xiを上位bitから見ていき、フラグが立っていれば右の子に、フラグが立っていなければ左の子にと遷移していけばよい。
そのような二分木を構築すると、"? x"クエリが来た時、xorを最大化するためには右の子と左の子のどちらに移動するべきかがxのbitを見ればわかるので解ける。
感想
そこまで難しい発想ではないんだけどコンテスト中に解けてよかった。
コード
#include <bits/stdc++.h> #define rep(i,n) for(int i = 0; i < n; i++) const double PI = 3.1415926535897932384626433832795028841971; const int INF = 100000000; const double EPS = 1e-10; const int MOD = 1000000007; using namespace std; typedef long long ll; typedef pair<int,int> P; struct v{ int ex; int dep; int r, l; int number; } vv[10000000]; int q; int counter = 1; int p[30]; void init(){ rep(i,30) p[i] = (1<<i); } void add(int x, int dep, int num){ vv[num].ex++; if(dep == 0){ vv[num].number = x; return; } if(x&p[dep-1]){ if(vv[num].r == -1){ vv[num].r = counter; vv[counter].dep = dep-1; counter++; } add(x,dep-1,vv[num].r); } else{ if(vv[num].l == -1){ vv[num].l = counter; vv[counter].dep = dep-1; counter++; } add(x,dep-1,vv[num].l); } } void del(int x, int dep, int num){ vv[num].ex--; if(dep == 0) return; if(x&p[dep-1]){ del(x,dep-1,vv[num].r); } else{ del(x,dep-1,vv[num].l); } } int que(int x, int dep, int num){ int ret = x; if(vv[num].ex == 0) return x; if(dep == 0) return x^vv[num].number; if(x&p[dep-1]){ if(vv[num].l != -1 && vv[vv[num].l].ex != 0) ret = max(ret,que(x,dep-1,vv[num].l)); else ret = max(ret,que(x,dep-1,vv[num].r)); } else{ if(vv[num].r != -1 && vv[vv[num].r].ex != 0) ret = max(ret,que(x,dep-1,vv[num].r)); else ret = max(ret,que(x,dep-1,vv[num].l)); } return ret; } int main(){ init(); cin >> q; rep(i,10000000){ vv[i].r = -1; vv[i].l = -1; vv[i].ex = 0;} vv[0].dep = 30; add(0,30,0); rep(i,q){ char a; int b; scanf(" %c%d",&a,&b); if(a == '+') add(b,30,0); if(a == '-') del(b,30,0); if(a == '?') printf("%d\n",que(b,30,0)); } }
E. Working routine
問題文
解法
全ての隣り合ってるセル間に辺をはり、クエリが飛んで来たらswapされる四角形の周囲のセルについてのみ辺を張りかえれば計算量がO(q*(n+m))となって解ける。
n*mの四角形の外に番兵的な用途でマスを追加しておくと実装が楽になる。
感想
わからなかったのでeditorialとか人のコードとか読んで通した。
解法自体は典型なのだが（思いつかなかったので猛省だけど）、辺を張りかえるという部分でやたらバグらせてしまった。
コード
#include <bits/stdc++.h> #define rep(i,n) for(int i = 0; i < n; i++) const double PI = 3.1415926535897932384626433832795028841971; const int INF = 100000000; const double EPS = 1e-10; const int MOD = 1000000007; using namespace std; typedef long long ll; typedef pair<int,int> P; struct ver{ int r, d; int val; } v[1500000]; int n, m, q; int find(int id, int h, int w){ int ret = id; rep(i,h) ret = v[ret].d; rep(i,w) ret = v[ret].r; return ret; } int main(){ scanf("%d%d%d",&n,&m,&q); rep(i,n) rep(j,m){ scanf("%d",&v[(i+1)*(m+1)+j+1].val); } rep(i,n+1) rep(j,m+1){ if(i != n) v[i*(m+1)+j].d = (i+1)*(m+1)+j; else v[i*(m+1)+j].d = -1; if(j != m) v[i*(m+1)+j].r = i*(m+1)+j+1; else v[i*(m+1)+j].r = -1; } rep(i,q){ int a, b, c, d, h, w; scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&h,&w); int l1 = find(0,a,b-1); int l2 = find(l1,0,w); int u1 = find(0,a-1,b); int u2 = find(u1,h,0); int L1 = find(0,c,d-1); int L2 = find(L1,0,w); int U1 = find(0,c-1,d); int U2 = find(U1,h,0); rep(j,h){ swap(v[l1].r,v[L1].r); swap(v[l2].r,v[L2].r); l1 = v[l1].d; L1 = v[L1].d; l2 = v[l2].d; L2 = v[L2].d; } rep(j,w){ swap(v[u1].d,v[U1].d); swap(v[u2].d,v[U2].d); u1 = v[u1].r; U1 = v[U1].r; u2 = v[u2].r; U2 = v[U2].r; } } int st = find(0,1,1); rep(i,n){ int now = st; rep(j,m){ if(j == 0) printf("%d",v[now].val); else printf(" %d",v[now].val); now = v[now].r; } printf("\n"); st = v[st].d; } }
