迷走

SRMとJOIとICPCを埋める日々。たまにほかのことも書くかも。

JOI2010 春合宿Day2-1 足し算 (a+b problem)

問題

https://www.ioi-jp.org/camp/2010/2010-sp-tasks/2010-sp-day2_21.pdf

解法

繰り上がりに注意しながら足し算をしていく。

ACコード

vector<pair<int, LL>> a, b, ans, anss;
LL m, x, y;
 
int main() {
    cin >> m;
    REP(i, m) {
        cin >> x >> y;
        a.emplace_back(make_pair(x, y));
    }
    cin >> m;
    REP(i, m) {
        cin >> x >> y;
        b.emplace_back(make_pair(x, y));
    }
    bool kuri = false;
 
    while (a.size() && b.size()) {
        pair<int, LL>topa = a[a.size() - 1], topb = b[b.size() - 1];
        a.pop_back(), b.pop_back();
        int sz;
        if (topa.second > topb.second) {
            a.push_back(make_pair(topa.first, topa.second - topb.second));
            sz = topb.second;
        }
        else if (topa.second < topb.second) {
            b.push_back(make_pair(topb.first, topb.second - topa.second));
            sz = topa.second;
        }
        else {
            sz = topa.second;
        }
        if (topa.first + topb.first + kuri < 10) {
            if (kuri) {
                ans.emplace_back(make_pair(topa.first + topb.first + kuri, 1));
                kuri = false;
                ans.emplace_back(make_pair(topa.first + topb.first + kuri, sz - 1));
            }
            else {
                ans.emplace_back(make_pair(topa.first + topb.first, sz));
            }
        }
        else {
            ans.emplace_back((topa.first + topb.first + kuri) % 10, 1);
            kuri = true;
            ans.emplace_back((topa.first + topb.first + kuri) % 10, sz - 1);
        }
    }
    if (a.size()) {
        for (int i = a.size() - 1; i >= 0; i--) {
            if (kuri) {
                if (a[i].first == 9) {
                    ans.emplace_back(make_pair(0, a[i].second));
                }
                else {
                    ans.emplace_back(make_pair(a[i].first + 1, 1));
                    ans.emplace_back(make_pair(a[i].first, a[i].second - 1));
                    kuri = false;
                }
            }
            else {
                ans.emplace_back(a[i]);
            }
        }
    }
    else {
        for (int i = b.size() - 1; i >= 0; i--) {
            if (kuri) {
                if (b[i].first == 9) {
                    ans.emplace_back(make_pair(0, b[i].second));
                }
                else {
                    ans.emplace_back(make_pair(b[i].first + 1, 1));
                    ans.emplace_back(make_pair(b[i].first, b[i].second - 1));
                    kuri = false;
                }
            }
            else {
                ans.emplace_back(b[i]);
            }
        }
    }
    if (kuri)ans.emplace_back(make_pair(1, 1));
    reverse(ALL(ans));
    anss.emplace_back(ans[0]);
    for (int i = 1; i < ans.size(); i++) {
        if (ans[i].second == 0)continue;
        if (anss[anss.size() - 1].first == ans[i].first)anss[anss.size() - 1].second += ans[i].second;
        else anss.emplace_back(ans[i]);
    }
    cout << anss.size() << endl;
    REP(i, anss.size()) {
        cout << anss[i].first << " " << anss[i].second << endl;
    }
}

実装がへたくそすぎてコード長が長いのがアレ。

JOI2010 春合宿Day1-2 戦国時代(sengoku)

問題

https://www.ioi-jp.org/camp/2010/2010-sp-tasks/2010-sp-day1_20.pdf

解法

x字を\と/に分解して足し、重なった部分を引くことを考える。重なった時の判定は、偶奇の和と差をうまく使うことによって計算することができる。

ACコード

LL l, n, x, y;
 
int main() {
    vector<LL> u, v, odd, even;
    cin >> l >> n;
    REP(i,n) {
        cin >> x >> y;
        u.emplace_back(x + y);
        v.emplace_back(y - x);
    }
    sort(ALL(u));
    sort(ALL(v));
    UNIQUE(u);
    UNIQUE(v);
    LL ans = 0;
    REP(i,u.size()) {
        if (u[i]<l) ans += u[i] + 1;
        else ans += 2 * l - u[i] - 1;
        if (u[i] % 2) odd.emplace_back(u[i]);
        else even.emplace_back(u[i]);
    }
    REP(i,v.size()) {
        if (v[i]>0) ans += l - v[i];
        else ans += l + v[i];
    }
    REP(i,v.size()) {
        LL p = 2 * l - max(v[i], -v[i]) - 2;
        LL q = max(v[i], -v[i]);
        if (v[i] % 2 != 0) {
            ans -= upper_bound(odd.begin(), odd.end(), p) - lower_bound(odd.begin(), odd.end(), q);
        }
        else {
            ans -= upper_bound(even.begin(), even.end(), p) - lower_bound(even.begin(), even.end(), q);
        }
    }
    cout << ans << endl;
}

yukicoder No.679 不思議マーケット

しばらく考えてわからなかったので解説を読みました

不思議マーケット [yukicoder No.679] - はまやんはまやんはまやん

問題

https://yukicoder.me/problems/no/679

解説

商品の関係性を有向グラフにして、入次数が0の頂点は購入が可能というふうにします。入次数が0の頂点を削除していき、新たに入次数が0の頂点が現れたらそれも購入可能になります。

ACコード

int n, m;
vector<int>G[505];
int indeg[505];

int main() {
    cin >> n >> m;
    REP(i, m) {
        int g, r;
        cin >> g >> r;
        REP(j, r) {
            int h;
            cin >> h;
            G[h].emplace_back(g);
            indeg[g]++;
        }
    }
    queue<int> que;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (indeg[i] == 0)que.push(i);
    }
    while (que.size()) {
        int cur = que.front();
        que.pop();
        ans++;
        REP(i, G[cur].size()) {
            indeg[G[cur][i]]--;
            if (indeg[G[cur][i]] == 0)que.push(G[cur][i]);
        }
    }
    cout << ans << endl;
}

誰かが言っていた「じつはグラフで解ける」という形の問題は、こういう問題のことをさしていたのかもしれない

yukicoder No.396 クラス替え

こういうのを解くのがすごく苦手。数字と10分くらいにらめっこしてしまった。

問題

No.396 クラス替え - yukicoder

解説

順位を0-indexedにすると考えやすい。2mで割った余りについて考える(余りがm以上の時は計算をしてm未満の時の同じ値にする)

ACコード

int n, m, x, y;

int main() {
    cin >> n >> m >> x >> y;
    int mx = (x - 1) % (2 * m);
    int my = (y - 1) % (2 * m);
    if (mx >= m)mx = (2 * m - mx - 1) % m;
    if (my >= m)my = (2 * m - my - 1) % m;
    cout << (mx == my ? "YES" : "NO") << endl;
}

yukicoder No.490 yukiソート

問題

No.490 yukiソート - yukicoder

解説

愚直にソートすればよい

ACコード

int n;
int a[2020];

int main() {
    cin >> n;
    REP(i, n) {
        cin >> a[i];
    }
    REP(i, 2 * n - 3) {
        for (int p = 0; p <= i; p++) {
            int q = i - p;
            if (p < q&&p < n&&q<n&&a[p]>a[q])swap(a[p], a[q]);
        }
    }
    REP(i, n) {
        if (i)cout << " ";
        cout << a[i];
    }
    cout << endl;
}

yukicoder No.490 yukiソート

問題

No.490 yukiソート - yukicoder

解説

愚直にソートすればよい

ACコード

int n;
int a[2020];

int main() {
    cin >> n;
    REP(i, n) {
        cin >> a[i];
    }
    REP(i, 2 * n - 3) {
        for (int p = 0; p <= i; p++) {
            int q = i - p;
            if (p < q&&p < n&&q<n&&a[p]>a[q])swap(a[p], a[q]);
        }
    }
    REP(i, n) {
        if (i)cout << " ";
        cout << a[i];
    }
    cout << endl;
}

yukicoder No.48 ロボットの操縦

問題

No.48 ロボットの操縦 - yukicoder

解説

まず、yが負のときは2回回転が必要です。次に、xが0以外の時は1回回転が必要です。それらに、⌊x/l⌋と⌊y/l⌋を加えたものが答えとなります。

ACコード

int x, y, l;

int main() {
    cin >> x >> y >> l;
    int cnt = 0;
    if (y < 0)cnt += 2;
    else if (x)cnt++;
    y = abs(y);
    cnt += y / l + (y%l ? 1 : 0);
    x = abs(x);
    cnt += x / l + (x%l ? 1 : 0);
    cout << cnt << endl;
}