6/7 21:15-23:15 http://codeforces.com/contest/814
今回は配点がイレギュラー(CとDが1500/2000じゃなくて1750/1750)だけど、C→B→Aの順で。 問題が化物語…
C. An impassioned circulation of affection (1750) x1642
http://codeforces.com/contest/814/problem/C なでこ&暦お兄ちゃん
色cと塗り回数mごとの最大長を先に全部求めたやつ pre[c][m] を用意して、クエリで参照 ・色cそれぞれについて(例えば ‘o') ・文字列(例えば “koyomi")で o 以外の文字の累積出現回数を数える → [ 0 1 1 2 2 3 4 ] ・塗り回数mそれぞれについて ・開始位置 s を選び(0≦ s<N-m)その開始位置における累積出現回数 + m でどこまで行けるか、累積出現回数表を upper_bound() で探索して見つけて、最遠位置を table[c][m] に記録 計算量O(MN2logN) // Mは色数 // N2logN: (m:[1..N]) x (開始位置:[0..N-m]) x (到達可能位置:log(N-m)) // 26 x 15002 x log(1500) ≒ 6.4e8 クエリO(1) x Q = O(Q) // Q=200000
自前で用意した最悪ケース(N=1500,Q=200000)がローカルで1.48秒 多分行けるっしょ… →AC (0:48; 1414pts)
agwたんとの反省会(ビデオチャット)で、agwたんの解法が O(MN2) で、表を用意するのは一緒なんだけど、開始位置・終了位置の総当りで、文字'o'がその区間に何回出てる(これは累積表で求めてる)ってことはあと何文字埋めればその幅を満たせるかを求め、テーブルのその文字数の箇所を更新していく方式。総当りって言っても N(N-1)/2 ≒1e6だし、mを逐一選ばなくても、〈その文字数〉の最小がmだし、〈その幅〉の最大が最長文字列長になってる。
テーブルなんか作らずに尺取り法で(クエリ時に)やると O(QN) で、これでも間に合うみたい。(200000x1500=3e8) クエリ1回の計算量を O(1) ないし O(logN) に落としたい、と思って頑張ってたけど。
#include <iostream> #include <sstream> #include <cstdio> #include <cmath> #include <cctype> #include <algorithm> #include <string> #include <vector> #include <deque> #include <stack> #include <queue> #include <list> #include <map> #include <set> using namespace std; typedef long long ll; typedef pair<int, int> ii; #define sz(a) int((a).size()) #define pb push_back #define all(c) (c).begin(),(c).end() #define tr(i,c) for(auto i=(c).begin(); i!=(c).end(); i++) #define rep(var,n) for(int var=0;var<(n);var++) #define found(s,e) ((s).find(e)!=(s).end()) #include <cassert> int main(){ int n; cin >> n; string s; cin >> s; vector<vector<int>> pre(26, vector<int>(n+1, 0)); rep(c, 26) { // x26 vector<int> acc(1+n); acc[0] = 0; int diff = 0; char ch = 0x61 + c; rep(i, n) { if (s[i] != ch) ++diff; acc[1+i] = diff; } for (int m=1; m<=n; ++m) { // x26x1500 int maxw = 0; for (int start=0; start<=n-m; ++start) { // x26x1500x1500 int vStart = acc[start]; int vEnd = vStart + m; int w = (int)(upper_bound(acc.begin()+start, acc.end(), vEnd) - (acc.begin()+start))-1; if (w > maxw) maxw = w; } pre[c][m] = maxw; } } int q; scanf("%d", &q); rep(i,q){ int mi; char ci; scanf("%d %c", &mi, &ci); printf("%d\n", pre[ci-'a'][mi]); } return 0; }
B. An express train to reveries (1000) x2264
http://codeforces.com/contest/814/problem/B 千石+ららちゃん
数列a, bで違っている箇所を拾い出す。 違うのは1箇所ないし2箇所。(問題文に1箇所以上違うと制約がある+3箇所以上違うとpからそれぞれ1つ違いという制約が満たせない) ・2箇所違いの場合:aとbが共通の部分についてはそのまま使う。違ってる箇所について、(a[場所1], b[場所2]) ないし (b[場所1], a[場所2]) で辻褄のあう方を採用する。(p が1..N のpermutationになるような方。ab共通部分ですでにN-2個の数字を使っているので、使える数字は残り2個のはず。採用できるのはこの2個の数字のpermutationのみ) ・1箇所違いの場合:aとbが共通の部分についてはそのまま使う。違ってる箇所について、使われていないはずの数字(1つ)をそこに埋める。 →AC (1:10, 720pts)
#include <iostream> #include <sstream> #include <cstdio> #include <cmath> #include <cctype> #include <algorithm> #include <string> #include <vector> #include <deque> #include <stack> #include <queue> #include <list> #include <map> #include <set> using namespace std; typedef long long ll; typedef pair<int, int> ii; #define sz(a) int((a).size()) #define pb push_back #define all(c) (c).begin(),(c).end() #define tr(i,c) for(auto i=(c).begin(); i!=(c).end(); i++) #define rep(var,n) for(int var=0;var<(n);var++) #define rep1(var,n) for(int var=1;var<=(n);var++) #define found(s,e) ((s).find(e)!=(s).end()) #include <cassert> int main(){ int n; cin >> n; // assert(2<=n && n<=1000); vector<int> a(n), b(n); rep(i,n) { cin >> a[i]; a[i]--; } rep(i,n) { cin >> b[i]; b[i]--; } vector<int> diff_at; rep(i,n) { if (a[i] != b[i]) diff_at.push_back(i); } int D = diff_at.size(); assert(D == 1 || D == 2); vector<bool> used(n, false); int used_cnt = 0; vector<int> p(all(a)); if (D == 2) { int u = diff_at[0], v = diff_at[1]; rep(i,n) { if (i == u || i == v) continue; used[a[i]] = true; ++used_cnt; } assert(used_cnt == n-2); set<int> unused; rep(i,n){ if (!used[i]) { unused.insert(i); } } assert(unused.size() == 2); if (a[u] != b[v] && found(unused,a[u]) && found(unused,b[v])) { // a[u], b[v] p[u] = a[u]; p[v] = b[v]; } else if (b[u] != a[v] && found(unused,b[u]) && found(unused,a[v])) { // b[u], a[v] p[u] = b[u]; p[v] = a[v]; } else { assert(false); } } else if (D == 1) { int u = diff_at[0]; rep(i,n) { if (i == u) continue; used[a[i]] = true; ++used_cnt; } assert(used_cnt == n-1); int unused = -1; rep(i,n){ if (!used[i]) { unused = i; break; } } p[u] = unused; } rep(i, n) { if (i>0) putchar(' '); printf("%d", 1+p[i]); } putchar('\n'); return 0; }
A. An abandoned sentiment from past (500) x3844
http://codeforces.com/contest/814/problem/A ひたぎ+貝木
貝木数列を降順ソートしたものをひたぎ空欄に左から埋めていって、出来た数列が昇順になっているか見るだけ →AC (1:20, 340pts)
#include <iostream> #include <sstream> #include <cstdio> #include <cmath> #include <cctype> #include <algorithm> #include <string> #include <vector> #include <deque> #include <stack> #include <queue> #include <list> #include <map> #include <set> using namespace std; typedef long long ll; typedef pair<int, int> ii; #define sz(a) int((a).size()) #define pb push_back #define all(c) (c).begin(),(c).end() #define tr(i,c) for(auto i=(c).begin(); i!=(c).end(); i++) #define rep(var,n) for(int var=0;var<(n);var++) #define rep1(var,n) for(int var=1;var<=(n);var++) #define found(s,e) ((s).find(e)!=(s).end()) #include <cassert> int main(){ int n, k; cin >> n >> k; vector<int> a(n), b(k); rep(i,n) { cin >> a[i]; } rep(i,k) { cin >> b[i]; } bool yn = false; sort(all(b), greater<int>()); for (int i=0,j=0; i<n; ++i) { if (a[i] == 0) a[i] = b[j++]; } rep(i, n-1) { if (a[i] > a[i+1]) { yn = true; break; } } printf("%s\n", yn ? "Yes" : "No"); return 0; }
D. An overnight dance in discotheque (1750) x590
http://codeforces.com/contest/814/problem/D 月火(白金ディスコ)
とりあえず、各円の包含関係を求めて レイヤーの奇数番目偶数番目を交互に分配していけばいい?と思ったけど、サンプルケース1はそれで行けるけど2はダメ どっちの組に入れるか(その円をプラスに使うかマイナスに使うか=奇数レイヤーにするか偶数レイヤーにするか)ってDPで行ける? って辺りまで考えて終わり
以下嘘解法(サンプルケース1しか通らないやつ)
#include <iostream> #include <sstream> #include <cstdio> #include <cmath> #include <cctype> #include <algorithm> #include <string> #include <vector> #include <deque> #include <stack> #include <queue> #include <list> #include <map> #include <set> using namespace std; typedef long long ll; typedef pair<int, int> ii; #define sz(a) int((a).size()) #define pb push_back #define all(c) (c).begin(),(c).end() #define tr(i,c) for(auto i=(c).begin(); i!=(c).end(); i++) #define rep(var,n) for(int var=0;var<(n);var++) #define rep1(var,n) for(int var=1;var<=(n);var++) #define found(s,e) ((s).find(e)!=(s).end()) #define repC2(vari,varj,n) for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj) #include <cassert> int main(){ int n; cin >> n; assert(1<=n && n<=1000); vector<vector<int>> circles(n); rep(i,n){ int x,y,r; cin >>x>>y>>r; circles[i] = {x,y,r}; } vector<int> lev(n, 0); repC2(i,j,n){ double d = hypot(circles[i][0]-circles[j][0], circles[i][1]-circles[j][1]); int rsum = circles[i][2] + circles[j][2]; if (rsum < d + 1e-9) { // 別々 printf("%d | %d\n", i, j); } else if (circles[i][2] > circles[j][2]) { // j in i printf("%d in %d\n", j, i); lev[j]++; } else { // i in j printf("%d in %d\n", i, j); lev[i]++; } } cout << lev << endl; long double S = 0, pi = 3.141592653589793238462643383; rep(i, n) { int h = lev[i]/2; printf("layer %d is alive\n", i); int r = circles[i][2]; long double s = pi*r*r; if (h % 2 == 0) { S += s; } else { S -= s; } } printf("%.8Lf\n", S); return 0; }
E. An unavoidable detour for home x52
開いてない
System Test
all passed (ABC)
rating: 1633 → 1676 (+40)