naoya_t@hatenablog

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

Codeforces Round #419 (Div. 2) [Virtual participation]

れじってたけど起きられなかった回。
今日もC→B→A(→D)の順で。

Virtual participationの良いところは、きちんと時間を区切って(自分を甘やかさずに)問題に取り組める点、本番に出ていたらどの位のスコア&ランクになっていたかが分かる点、FRIENDS STANDINGSで本番に出ていたフレンズと並んで表示される点、など。
f:id:n4_t:20170619141313p:plain
時間を過ぎたsubmit分は(別の段に)表示される。
いやもうちょっとフレンズ欲しいし
f:id:n4_t:20170619142152p:plain
名前を見たことのある日本人を何人か追加してみたらこんな感じ。

カレンってきんモザか。全部見たはずなのに覚えてない。
イギリスから来た日本大好きな、簪が刺さらない髪質の子?

C: Karen and Game

http://codeforces.com/contest/816/problem/C
横方向、縦方向にsumを取って、一番小さい行/列に合わせるように引いていく
(この縦横ってnumpyでaxis指定するとき0か1か迷うとこだよね;今回はC++だから関係ないけど)
最後に盤面全体が同じ数字になったところで、縦横短い方を使って引いて終わり
途中で無理って分かったら-1
→AC(0:35;一発で通せて嬉しい)

// いろいろ略

inline void oq(vector<int>& a, vector<ii>& res) {
    int n = a.size();
    res.resize(n);
    rep(i,n) res[i] = ii(a[i], i);
    sort(all(res)); reverse(all(res));
}

int main(){
    vector<int> tmp(2);
    loadvec(tmp, 2);
    int R=tmp[0], C=tmp[1];

    vector<vector<int>> mp(R, vector<int>(C, 0));
    vector<int> tate(C, 0), yoko(R, 0);
    rep(r, R) {
        loadvec(mp[r], C);
        rep(c, C) {
            int x = mp[r][c];
            yoko[r] += x;
            tate[c] += x;
        }
    }
    vector<ii> yq, tq;
    oq(yoko, yq); int ymin = yq.back().first;
    oq(tate, tq); int tmin = tq.back().first;
    int yc = 0, tc = 0;
    vector<ii> ans;
    rep(r, R) {
        int row = yq[r].second;
        while (yoko[row] > ymin) {
            yoko[row] -= C;
            rep(col, C) tate[col]--;
            ans.push_back(ii(0, row));
            ++yc;
        }
        if (yoko[row] != ymin) goto impossible;
    }
    tmin -= yc;
    if (tmin % R) goto impossible;
    rep(c, C) {
        int col = tq[c].second;
        while (tate[col] > tmin) {
            tate[col] -= R;
            rep(row, R) yoko[row]--;
            ans.push_back(ii(1, col));
            ++tc;
        }
        if (tate[col] != tmin) goto impossible;
    }
    ymin -= tc;
    if (ymin % C) goto impossible;
    if (tmin/R != ymin/C) goto impossible;

    if (R <= C) {
        rep(i, ymin/C) rep(row, R) {
            ans.push_back(ii(0, row));
        }
    } else {
        rep(i, tmin/R) rep(col, C) {
            ans.push_back(ii(1, col));
        }
    }

possible:
    cout << ans.size() << endl;
    for (ii a : ans) {
        cout << (a.first ? "col ":"row ") << (1 + a.second) << endl;
    }
    return 0;
impossible:
    cout << -1 << endl;
    return 0;
}

B: Karen and Coffee

http://codeforces.com/contest/816/problem/B
猫舌なので温度の範囲が1〜200000とか意味がわからない
それはさておきimos→「k以上なら+1」のaccum、で配列を作ってa[r]-a[l-1]
→AC(0:57)

// いろいろ略

int main(){
    vector<int> tmp(3);
    loadvec(tmp, 3);
    int n=tmp[0], k=tmp[1], q=tmp[2];

    vector<int> b(200002, 0);
    rep(i, n) {
        loadvec(tmp, 2);
        int li=tmp[0], ri=tmp[1];
        ++b[li]; --b[ri+1];
    }
    vector<int> ba(200002, 0);
    int here = b[0], accum = 0;
    if (here >= k) { ba[0] = ++accum; }
    for (int i=1; i<=200001; ++i) {
        here += b[i];
        if (here >= k) ++accum;
        ba[i] = accum;
    }
    rep(i, q) {
        loadvec(tmp, 2);
        int a=tmp[0], b=tmp[1];
        int ans = ba[b] - ba[a-1];
        printf("%d\n", ans);
    }

    return 0;
}

A: Karen and Morning

http://codeforces.com/contest/816/problem/A
とりあえず可能なpalindrome時刻を全部見つけておく(←h=10\cdot h_{10}+h_1=00〜23としてm=10\cdot h_1+h_{10}が0〜59の範囲に収まるやつ)。
00:00からの経過分数で昇順で配列に保持。
これをもう1つ、+24h(=+1440m)したものを右にくっつけた配列から、現在時刻がどこに来るかをlower_bound()で探索
→AC(1:07)

// いろいろ略

inline int rev(int h) {
    int h10 = h/10, h1 = h%10;
    return 10*h1 + h10;
}

int main(){
    int h, m;
    scanf("%02d:%02d", &h, &m);
    int curr = h*60 + m;

    vector<int> valid;
    rep(h, 24) {
        int m = rev(h);
        if (0 <= m && m < 60) {
            valid.push_back(h*60 + m);
            valid.push_back(h*60 + m + 1440);
        }
    }
    sort(all(valid));
    int ix = (int)(lower_bound(all(valid), curr) - valid.begin());
    cout << (valid[ix] - curr) << endl;

    return 0;
}

D: Karen and Test

http://codeforces.com/contest/816/problem/D
\displaystyle\frac{n(n-1)}{2}が偶数なら最後の演算は−、奇数なら+。
最後から逆算してみる。

最終行の演算が−の場合:(最後から数えてn行目(n\ge0)の第k要素(k\ge0)a_k^{(n)}と表記)
a_0^{(0)}
=-a_0^{(1)}+a_1^{(1)}
=-(+a_0^{(2)}+a_1^{(2)})+(-a_1^{(2)}+a_2^{(2)})=-a_0^{(2)}-2\cdot a_1^{(2)}+a_2^{(2)}
=-(+a_0^{(3)}+a_1^{(3)})-2\cdot (-a_1^{(3)}+a_2^{(3)})+(+a_2^{(3)}+a_3^{(3)})=-a_0^{(3)}+a_1^{(3)}-a_2^{(3)}+a_3^{(3)}
=-(-a_0^{(4)}+a_1^{(4)})+(+a_1^{(4)}+a_2^{(4)})-(-a_2^{(4)}+a_3^{(4)})+(+a_3^{(4)}+a_4^{(4)})
=+a_0^{(4)}+0\cdot a_1^{(4)}+2\cdot a_2^{(4)}+0\cdot a_3^{(4)}+a_4^{(4)}=a_0^{(4)}+2\cdot a_2^{(4)}+a_4^{(4)}
と、4段目で途中の項が交互に消えて(+1,0,+2,0,+1)という係数が残る。
これ、n-1が4の倍数になるところまで解いたらあとはこれの繰り返しで行けるよね
(+1,0,+2,0,+1)を2回やったらいくつになる?(1,0,2,0,1,\cdots)+2\cdot(\cdots,1,0,2,0,1,\cdots)+(\cdots,1,0,2,0,1)=(1,0,2,0,1,\cdots)+(\cdots,2,0,4,0,2,\cdots)+(\cdots,1,0,2,0,1)=(1,0,2,0,3,0,4,0,3,0,2,0,1)
とすると(1,0,2,0,...,\frac{n-1}{2},...,0,2,0,1)みたいな係数を掛ければいいのか。
↑★間違い。正しくは(1,0,4,0,6,0,4,0,1)なので二項係数の計算になる。

最終行の演算が+の場合も、4段やると(+1,0,+2,0,+1)が残る。
というわけで、n=4k+1になるところまで(高々3段)普通に計算して、そこから上述の係数を用いて答えを出す。
残り20秒弱あたりで提出。→WA(1:59)

終了後

(1,0,2,0,1,\cdots)+(0,2,0,4,0,2,0)+(\cdots,1,0,2,0,1)=(1,2,3,4,3,2,1)だけど
(1,0,2,0,1,\cdots)+(0,0,2,0,4,0,2,0,0)+(\cdots,1,0,2,0,1)=(1,0,4,0,6,0,4,0,1)
二項係数じゃん
(1,0,2,0,1), (1,0,4,0,6,0,4,0,1), \cdots, (1,0,\cdots,0,{}_r\mathrm{C}_k,\cdots0,1), \cdots
ここで\displaystyle r=\frac{n-1}{2}
{}_r\mathrm{C}_kの計算をインクリメンタルにやればr=50000でも十分間に合う。→AC

// いろいろ略

const ll M=1000000007LL;

ll ADD(ll x, ll y) { return (x+y) % M; }
ll SUB(ll x, ll y) { return (x-y+M) % M; }
ll MUL(ll x, ll y) { return x*y % M; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { return MUL(x, POW(y, M-2)); }
/// ll comb(ll n, ll k) { ll v=1; for(ll i=1; i<=k; i++) v = DIV(MUL(v, n-i+1),i); return v; }

void reduce(vector<ll>& a, int to) {
    int n = a.size();
    int pm = 1;
    for (int r=n; r>to; --r) {
        for (int i=0; i<r-1; ++i) {
            a[i] = (a[i] + pm*a[i+1] + M) % M;
            pm = -pm;
        }
        a.pop_back();
    }
}

ll solve(vector<ll>& a) {
    int n = a.size();

    int rem = (n-1) % 4;
    reduce(a, n-rem);
    n -= rem;

    ll lev = (n-1/4), r = (n-1)/2, ac = 0LL;
    ll comb = 1LL;
    for (int i=0; i<n; i+=2) {
        int k = i/2;
        if (k >= 1) comb = DIV(MUL(comb, r-k+1), k);
        ac = ADD(ac, MUL(a[i], comb));
    }
    return ac;
}

int main(){
    ll n = loadint();
    vector<ll> a(n);
    loadvec(a, n);

    if (n < 5) {
        reduce(a, 1);
        cout << a[0] << endl;
        return 0;
    }

    ll ans = solve(a);
    cout << ans << endl;

    return 0;
}

E: Karen and Supermarket

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