Codeforces Round #421 (Div. 2)

http://codeforces.com/contest/820
今日もC→B→A(→D)の順で。2完 (oox--)。
f:id:n4_t:20170628102436p:plain
（C問題（Div1だとA）のごたごたでunratedになった模様）

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角形なら $\displaystyle k\cdot\frac{360}{n}$
求める角度の2倍がこれに一番近くなるようなkを選んで。
Aを固定したらCの場所はそこから時計回りに（あるは逆に）k個進んだ頂点になる。
Bは、弧ACに含まれないどこか。
A: $1$ 番目の頂点
C: $k+1$ 番目の頂点
B: $[k+2\cdots n]$ 番目のどこか。←どこでもいい！
そこから導き出される $1\le k\lt n-1$ という制約も考慮しつつ。
→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
$\displaystyle\sum_{i=0}^{n-1}{|p_{(i+k)\%n}-(1+i)|}$ のminとargminを求めたい
変形して下に凸な関数 $\displaystyle\sum_{i}^{n-1}{|k - (p_i-1)|}$ の最小化に帰着して、傾きが変わるn個の点 $k=p_i-1$ のうち、nが奇数個なら左から $:\displaystyle\frac{n-1}{2}$ 番目がargmin（この点が [0,n) の外にあるなら0かn-1がargmin）、偶数個なら左から $\displaystyle\frac{n}{2}-1, \frac{n}{2}$ 番目がargmin（〃）、みたいな事を考えた。
そこまで考えて試合終了。

E. Mister B and Beacons on Field (x1)

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

終了後

D問題、%nが入るからもうちょっと複雑なはず、と思って改めて考える。
$\displaystyle\sum_{i=0}^{n-1}{|p_{(i+k)\%n}-(1+i)|}$
$p$ の添字ではなく、 $p_i$ から引く $(1+i)$ の側にkを載せて
$\displaystyle\sum_{i=0}^{n-1}{|p_i-(1+(i+k)\%n)|}=\sum_{i=0}^{n-1}{|(p_i-1)-(i+k)\%n|}=\sum_{i=0}^{n-1}{|(k+1)\%n-(p_i-1)|}$
$c_i=p_i-1$ は定数（ $1\le p_i\le n$ なので $0\le p_i-1\le n-1$ ）で。
$y=|(k+i)\%n-c_i|$ は定義域 $0\le k\lt n$ においてどういう振る舞いをする？
f:id:n4_t:20170628064801j:plain
こんな感じさね
これを $i=0\cdots n-1$ すべてについて求めた総和の関数のminとargminを求めるだけの問題に帰着できました！
いやn=10万とかあるし無理っしょ
…
いやそんなこともないだろ
これimos法の出番では
折れ線の傾きが変わる箇所・不連続な箇所に注目して、微分成分・二階微分成分を求め（１枚につき高々3,4箇所）、
これを累積＆累積する
まさかのO(N)解法
→AC

// 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;
}

Cのlとrを1ベースから0ベースに直すの忘れてる（けれどサンプルケースもテストケースのいくつかも通ってしまう）
abcde/zzz/abcde/zzz/ みたいなパターンと両方試してみる、という方法（agwたんから聞いた）を試してみたけど前と同じテストケースで止まってる

そもそもCは周期性がないのではという議論があって（いまここ）

naoya_t@hatenablog

いわゆるチラシノウラであります

C. Mister B and Boring Game (x328)

B. Mister B and Angle in Polygon (x2463)

A. Mister B and Book Reading (x3446)

D. Mister B and PR Shifts (x163)

E. Mister B and Beacons on Field (x1)

終了後