Codeforces Round #421 (Div. 2)

C. Mister B and Boring Game (x328)

http://codeforces.com/contest/820/problem/C
abcde/eeeee/abcdf/fffff/... みたいな（最後の1文字をBさんが繰り返す作戦）を考えた
2周で同じところに戻ってくるから、lとrの差が(a+b)*2以上ならa+1を返す
それ以下なら実際に何周期分かの文字列を作ってl%((a+b)*2)〜r%((a+b)*2)で使われている文字を数える
→WA
それ以上深める気力がなかったのでBへ

// WA解
// （いろいろ略）
int solve(int a,int b,int l,int r) {
    ++r;
    int c = (a+b)*2;
    if (r-l >= c) return a+1;
    l %= c; r %= c;
    if (r < l) r += c;
    vector<char> s(c*2); //abababab
    int ofs = 0;
    int u=1; if (a>b) u=a-b;
    assert(1<=u && u<=a);
    rep(k, 2){
        rep(i,a) s[ofs+i]=('a'+i);
        ofs += a;
        rep(i,b) s[ofs+i]=s[ofs-1];
        ofs += b;

        rep(i,a) s[ofs+i]=('a'+i);
        ofs += a-u;
        rep(i,u) s[ofs+i]=('a'+a+i);
        ofs += u;
        rep(i,b) s[ofs+i]=s[ofs-1];
        ofs += b;
    }
    set<char> st;
    for (int i=l;i<r;++i) {
        st.insert(s[i]);
    }
    return st.size();
}

int main(){
    int a,b,l,r; cin>>a>>b>>l>>r;
    // l,rを1ベースのまま使ってるよorz; ここで --l; --r; すべき
    cout << solve(a,b,l,r) << endl;
    return 0;
}

B. Mister B and Angle in Polygon (x2463)

http://codeforces.com/contest/820/problem/B
正n角形のすべての頂点の座標を求めて、そのうちの3つを選んで（nC3）角度を計算して、求める角度に一番近いやつを表示、なわけなくて
正n角形の3つの頂点ABCが成す角度∠ABCは、ABCの外接円の中心をOとしたとき∠AOCの半分になるよね？
∠AOCは正n角形なら
求める角度の2倍がこれに一番近くなるようなkを選んで。
Aを固定したらCの場所はそこから時計回りに（あるは逆に）k個進んだ頂点になる。
Bは、弧ACに含まれないどこか。
A: 番目の頂点
C: 番目の頂点
B: 番目のどこか。←どこでもいい！
そこから導き出される という制約も考慮しつつ。
→AC

// AC解
// （いろいろ略）
void solve(int n, int a) {
    double u = 360.0/n;
    double t = (double)a*2.0;

    vector<double> z(n+1);
    rep(i, n+1) z[i] = u*i;  // わざわざ全頂点の角度を求めて二分探索してるけど割り算で普通に出るでしょ
    int j = (int)(lower_bound(all(z), t) - z.begin());
    assert(j > 0);
    double d0 = abs(z[j] - t), d1 = abs(z[j-1] - t);
    if (d1 < d0) --j;
    if (j==0) j=1;

    if (j>=n-1) j=n-2;
    // 0, j+1, jとか
    printf("%d %d %d\n", 1, 1+(j+1), 1+j);
}
int main(){
    int n,a; cin>>n>>a;
    solve(n,a);
    return 0;
}

A. Mister B and Book Reading (x3446)

http://codeforces.com/contest/820/problem/A
愚直にシミュレーション。
→AC

// AC解
// （いろいろ略）
int solve(int c,int v0,int v1,int a,int l) {
    int day=1, rest=c, speed=v0;
    while(true) {
        int today = min(v1, speed);
        if (rest <= today) return day;
        rest -= today;
        rest += l;
        speed += a;
        ++day;
    }
}
int main(){
    int c,v0,v1,a,l; cin>>c>>v0>>v1>>a>>l;
    cout << solve(c,v0,v1,a,l) << endl;
    return 0;
}

D. Mister B and PR Shifts (x163)

http://codeforces.com/contest/820/problem/D
のminとargminを求めたい
変形して下に凸な関数 の最小化に帰着して、傾きが変わるn個の点 のうち、nが奇数個なら左から 番目がargmin（この点が [0,n) の外にあるなら0かn-1がargmin）、偶数個なら左から番目がargmin（〃）、みたいな事を考えた。
そこまで考えて試合終了。

E. Mister B and Beacons on Field (x1)

http://codeforces.com/contest/820/problem/E
開いてない

// AC解
// （いろいろ略）
typedef long long ll;
#define all(c)  (c).begin(),(c).end()
#define rep(var,n)  for(int var=0;var<(n);var++)

void solve(int N, vector<int>&p) {
    vector<ll> a(N, 0);
    vector<ll> b(N, 0);
    rep(i, N) {
        int c = p[i] - 1;
        int at0 = (-i + N)%N; // |＼
        int atV = (-i + c + N)%N; // ＼／
        assert(0 <= c && c < N);
        if (i == 0) {
            a[at0] -= 1; // at0 = 0
            a[atV] += 2;
            b[0] += c;
        } else if (i < c) {// -i+c > 0
            a[0] -= 1;
            a[at0] -= 2;
            a[atV] += 2;
            b[0] += c - i; // >0
            b[at0] += c - (N-c);
        } else if (i == c) {
            a[atV] += 1; // at1 = 0
            a[at0] -= 2;
            b[0] += 0;
            b[at0] += c - (N-c);
        } else if (c < i) {// -i+c < 0
            a[0] += 1;
            a[atV] += 2;
            a[at0] -= 2;
            b[0] += i - c;
            b[at0] += c - (N-c);
        }
    }

    a.insert(a.begin(), 0);

    vector<ll> aa(N);
    ll accum = 0;
    rep(i, N) {
        accum += a[i];
        aa[i] = accum;
    }
    vector<ll> aaa(N);
    accum = 0;
    rep(i, N) {
        accum += aa[i];
        aaa[i] = accum;
    }

    vector<ll> ba(N+1);
    ba[0] = b[0];
    rep(i, N-1) {
        ba[i+1] += ba[i] + b[i+1];
    }

    vector<ll> d(N);
    rep(i, N) {
        d[i] = ba[i] + aaa[i];
    }

    int k = min_element(all(d)) - d.begin();
    printf("%lld %d\n", d[k], k);
}

int main(){
    int N;
    vector<int> p;
    N = loadvec(p);
    solve(N,p);
    return 0;
}