Codeforces #464-468 Div2C

依然として風邪気味だけど謎の鬱はおちついてきた気がする.

Codeforces #464 Div2C Convenient For Everybody

1日はn時間で,1時からn時までである.n個のタイムゾーンがあり,タイムゾーン1で1時のときタイムゾーンiではi時である.1時間のプログラミングコンテストを開きたい.タイムゾーンiにいる人はa[i]人であり,そのタイムゾーンにおいて開始時間tが区間[s,f)に含まれるようなコンテストに参加できる.参加できる人数が最大となるような開始時間をタイムゾーン1での時間で答えよ.

めんどうなので時間は0-indexedでかんがえる.たくさん区間が与えられてその区間全体に一様な値を足す問題なのでimos法を使うといいとわかる.

ソースコード

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
int a[100000];
int b[100010];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    int s, f;
    cin >> s >> f; s--; f--;
    //[s,f)
    for (int i = 0; i < n; i++) {
        if (s < f) {
            b[s] += a[i];
            b[f] -= a[i];
        }
        else {
            b[0] += a[i];
            b[f] -= a[i];
            b[s] += a[i];
        }
        (s += n - 1) %= n;
        (f += n - 1) %= n;
    }
    for (int i = 1; i < n; i++) {
        b[i] += b[i - 1];
    }
    int ans = 0;
    int idx = 0;
    for (int i = 0; i < n; i++) {
        if (ans < b[i]) {
            ans = b[i];
            idx = i;
        }
    }
    cout << idx + 1 << endl;
}

Codeforces #465 Div2C Fifa and Fafa

二次元平面上に中心(x1,y1)で半径Rの円1がある.この円内の適当な点を中心とした円2を作りたい.ただし円2は円1の外側にはみ出てはならず,点p(x2,y2)を含んではならない.このような円2のうち円1との共通部分の面積が最大のものを一つ答えよ.という問題.

まず点(x2,y2)が円1の外側にある場合は,明らかに円2は円1と同じにすればよい.また円1の中心と点pが重なるときは,中心をR/2だけx方向(y方向でもよいが)にずらした半径R/2の円が答えになる.これ以外のときは,半径はr=(R+d)/2で,点pの位置ベクトルをp,円1の中心から点pへ向かう単位ベクトルをvとしたときp-r*vが円2の中心の位置ベクトルになることが図を描くとわかる.場合分けを気をつけよう.

ソースコード

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
struct P {
    double x, y;
    P(double x, double y) :x(x), y(y) {}
    P operator+(const P& p) const {
        return P(x + p.x, y + p.y);
    }
    P operator-(const P& p) const {
        return P(x - p.x, y - p.y);
    }
};
P operator*(double k, const P& p) {
    return P(p.x*k, p.y*k);
}
double dist(const P& p) {
    return sqrt(p.x*p.x + p.y*p.y);
}
int main() {
    double R, x1, y1, x2, y2;
    cin >> R >> x1 >> y1 >> x2 >> y2;
    P p1(x1, y1), p2(x2, y2);
    P v = p2 - p1;
    double d = dist(v);
    if (d == 0) {
        printf("%.15lf %.15lf %.15lf\n", x1 + R / 2, y1, R / 2);
    }
    else if (d >= R) {
        printf("%.15lf %.15lf %.15lf\n", p1.x, p1.y, R);
    }
    else {
        double r = (R + d) / 2;
        P p3 = p2 - (r / d)*v;
        printf("%.15lf %.15lf %.15lf\n", p3.x, p3.y, r);
    }
}

Codeforces #466 Div2C Phone Numbers

文字列xに現れる文字の集合をc(x)と書く.文字列sが与えられる.C(t)⊆C(s)かつ辞書順比較でt>sとなるような文字列tのうち,辞書順最小のものを答えよ.という問題.

|s|≦kのときは,sのうしろにsに現れる文字の中で辞書順最小の文字をk-|s|文字くっつけるだけ.そうでないとき,sのk文字目から1文字目に向かって見ていって,その文字がsに現れる辞書順最大の文字なら辞書順最小の文字で置きかえていき,そうでないなら辞書順で次の文字に置きかえて処理を終了する.こうして出来た文字列が求めるtである.

ソースコード

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
int main() {
    int n, k;
    cin >> n >> k;
    string s, t;
    cin >> s;
    t = s;
    sort(t.begin(), t.end());
    t.erase(unique(t.begin(), t.end()), t.end());
    if (k > s.size()) {
        cout << s + string(k - s.size(), t[0]) << endl;
        return 0;
    }
    for (int i = k - 1; i >= 0; i--) {
        if (s[i] == t.back()) {
            s[i] = t[0];
        }
        else {
            s[i] = *upper_bound(t.begin(), t.end(), s[i]);
            break;
        }
    }
    cout << s.substr(0, k) << endl;
}

Codeforces #467 Div2C Save Energy!

あるレンジは,一旦オンにしてもk分経つと自動でオフになる(オフになってもある程度温かいままである).あなたはd分おきにレンジの所にいってもしオフになっていたらオンにする.今,あなたはオン状態のレンジならt分,オフ状態のレンジなら2t分加熱すれば完成する料理を作りたい.この料理は何分で完成するだろうか?という問題.

オン状態のレンジは毎分2,オフ状態のレンジは毎分1だけ加熱するとかんがえると,この料理は合計2tだけ加熱されると完成することになる.d*a≧kとなるような最初のaを計算する.そうすると,d*a分周期で同じことの繰り返しになることがわかる.よって,1周期でどれだけ加熱されるかを計算すれば何周期分か+端数で加熱が終了するかが計算できるので算数.

ソースコード

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
int main() {
    LL k, d, t;
    cin >> k >> d >> t;
    LL A = ((k + (d - 1)) / d)*d;
    LL B = 2 * k + (A - k);
    LL C = (2 * t) / B;
    LL D = (2 * t) % B;
    if (D <= 2 * k) {
        printf("%lf\n", C*A + D / 2.0);
    }
    else {
        printf("%lld\n", C*A + k + (D - 2 * k));
    }
}

Codeforces #468 Div2C Laboratory Work

最小値と最大値の差が高々2であるような長さnの数列xが与えられる.長さnの数列yであって,(yの最小値)≧(xの最小値)かつ(yの最大値)≦(xの最大値)かつ(yの平均値)=(xの平均値)であるもののうち,xと一致している要素の数が最小のものを求めよ(ただし,一致している要素の数は,yの各要素を同じ値のxの要素とマッチングしていったとき何組のペアができるかで計算する).という問題.

もしxの最大値と最小値の差が1以下なら,平均を同じにするためにはyはxの順列でないといけない.そうでないとき,xの最小値をmとすると現れる数はm,m+1,m+2のいずれかである.yにm+1がいくつ含まれるかを固定してやると平均が等しいことからm,m+2がいくつ含まれるかが定まるので全探索してやって一致している要素の数が最小のものを探す.

ソースコード

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
int d[100000];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> d[i];
    int m = d[0], M = d[0];
    for (int i = 0; i < n; i++) m = min(m, d[i]), M = max(M, d[i]);
    if (M-m<=1) {
        cout << n << endl;
        cout << d[0];
        for (int i = 1; i < n; i++) cout << " " << d[i];
        cout << endl;
        return 0;
    }
    int a = 0, b = 0, c = 0;
    for (int i = 0; i < n; i++) {
        if (d[i] == m) a++;
        else if (d[i] == m + 1) b++;
        else c++;
    }
    int ans = 1 << 30;
    int A = 0, B = 0, C = 0;
    for (int i = 0; i <= b + 2 * c; i++) {
        if ((b + 2 * c - i) % 2) continue;
        int j = (b + 2 * c - i) / 2;
        if (i + j > n) continue;
        int sum = min(a, n - (i + j)) + min(b, i) + min(c, j);
        if (ans > sum) {
            ans = sum;
            A = n - (i + j);
            B = i;
            C = j;
        }
    }
    cout << ans << endl;
    vector<int> v;
    for (int i = 0; i < A; i++) v.push_back(m);
    for (int i = 0; i < B; i++) v.push_back(m + 1);
    for (int i = 0; i < C; i++) v.push_back(m + 2);
    cout << v[0];
    for (int i = 1; i < n; i++) cout << " " << v[i];
    cout << endl;
}