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） クエリ１回の計算量を 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)