naoya_t@hatenablog

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

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

当日出られなかった回。Virtual participationというやつを初めてやってみた。(6/3)

> Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.

"ACM-ICPC mode"ってのが何なのかは分からないけど
本番同様の制限時間(2時間)で、経過時間に基づいたスコアと再提出ペナルティを出してくれて、実際に参加したら何位だったかとか分かる(無論レートは付かない)。

解く順序はC→B→A縛りで。

C. Sagheer and Nubian Market (x2423)

http://codeforces.com/contest/812/problem/C
二分探索でkを求めるところまではよかった
WA(1): 計算はlong longでやらないとダメだ
WA(2): Tを(再)計算するときにa1,a2,と見てしまっていた
→WAx2, AC

#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())

#ifdef DEBUG
#undef NDEBUG
#endif
#include <cassert>

int n;
ll S;
vector<int> a;
map<int, ll> minimal;

bool p(int k) {
    if (k == 0) {
        minimal[0] = 0LL;
        return true;
    }

    priority_queue<ll, vector<ll>, greater<ll>> pq;
    rep(i, n) { // n:1e5, k:1e5
        pq.push((ll)a[i] + (1LL+i)*k);
    }

    ll cost = 0;
    int cnt = 0;
    while (!pq.empty()) {
        ll v = pq.top(); pq.pop();
        if (cost + v > S) break;
        cost += v; ++cnt;
        if (cnt == k) {
            minimal[k] = cost;
            return true;
        }
    }
    return (cnt == k);
}

int solve() {
    if (p(n)) {
        return n;
    }
    int lo=0, hi=n; // p(lo)=true, p(hi)=false
    while (lo+1 < hi) {
        assert(p(lo) == true && p(hi) == false);
        int mi = (lo+hi)/2;
        if (p(mi)) {
            lo = mi;
        } else {
            hi = mi;
        }
    }
    return lo;
}

int main(){
    cin >> n >> S;  // 1-1e5 1-1e9
    a.resize(n); // 1-1e5
    rep(i, n) cin >> a[i];
    minimal.clear();

    int k = solve();
    cout << k << " " << minimal[k] << endl;
    return 0;
}

B. Sagheer, the Hausmeister (x1840)

http://codeforces.com/contest/812/problem/B
ライトを消すやつ。
そのフロアの電気を(ついていれば)全部消して左側階段に最速で着く時刻、同じく右側階段に最速で着く時刻、を下から見ていく
→ AC

// 略
int solve(int n, int m, vector<string>& s) {
    reverse(all(s));

    vector<bool> lit(n, false);
    vector<int> leftmost(n, m+2), rightmost(n, -1);
    int maxfloor = -1;

    rep(i,n) {
        assert(s[i].size() == m+2);
        for (int j=1; j<=m; ++j) {
            if (s[i][j] == '1') {
                lit[i] = true; maxfloor = i;
                leftmost[i] = min(leftmost[i], j);
                rightmost[i] = max(rightmost[i], j);
            }
        }
    }
    if (1+maxfloor < n) {
        n = 1 + maxfloor;
        lit.erase(lit.begin()+n, lit.end());
    }

    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        assert(lit[0]);
        return rightmost[0];
    }
    else {
        int ltime = 0, rtime = m+1;
        if (lit[0]) ltime += rightmost[0]*2;

        for (int i=1; i<n-1; ++i) {
            int _ltime = ltime+1, _rtime = rtime+1;
            if (lit[i]) {
                _ltime = min(ltime+1 + rightmost[i]*2, rtime+1 + (m+1));
                _rtime = min(rtime+1 + (m+1 - leftmost[i])*2, ltime+1 + (m+1));
            } else {
                _ltime = min(ltime+1, rtime+1 + (m+1));
                _rtime = min(rtime+1, ltime+1 + (m+1));
            }

            ltime = _ltime; rtime = _rtime;
        }

        assert(lit[n-1]);
        return min(ltime+1 + rightmost[n-1], rtime+1 + (m+1 - leftmost[n-1]));
    }
}

int main(){
    int n, m; cin >> n >> m; // 1-15, 1-100
    vector<string> s(n);
    rep(i, n) cin >> s[i];
    cout << solve(n,m,s) << endl;
    return 0;
}

A. Sagheer and Crossroads (x3271)

http://codeforces.com/contest/812/problem/A
交差点と信号
WA(1): 自分のところからは直進だけでなく右折左折でも横断歩道を横切るよね…あああ
→WAx1, AC

// 略
int main(){
    vector<map<char,bool>> go(4);
    rep(i, 4) {
        int l,s,r,p;
        cin >> l >> s >> r >> p;
        go[i]['L'] = (l == 1);
        go[i]['S'] = (s == 1);
        go[i]['R'] = (r == 1);
        go[i]['P'] = (p == 1);
    }

    bool danger = false;
    rep(i, 4) {
        if (!go[i]['P']) continue;
        // if (go[i]['S']) { danger = true; break; }  /// oops
        if (go[i]['L'] || go[i]['S'] || go[i]['R']) { danger = true; break; }
        if (go[(i+1)%4]['L']) { danger = true; break; }
        if (go[(i+2)%4]['S']) { danger = true; break; }
        if (go[(i+3)%4]['R']) { danger = true; break; }
    }
    cout << (danger ? "YES" : "NO") << endl;

    return 0;
}

D. Sagheer and Kindergarte (x73)

http://codeforces.com/contest/812/problem/D
正答ユーザ数が一番少なかったので飛ばした。(開いてない)

E. Sagheer and Apple Tree (x328)

http://codeforces.com/contest/812/problem/E
nimのちょっと複雑になった感じ?
子供にりんごをいくつか移せる→全体のxorの値が変わる
どういうときに勝てるのか
2つのノードの中身を入れ替える事自体は全体のxorは変えない
ってとこまで考えて離脱