CHR_Virtual_08 解説

CHR_Virtual_08 の感想です。気力があれば upsolve のついでに不定期投稿するかもね。

1. A. Last Letter

_ = input()
s = input()
print(s[-1])

2. B. Go Straight and Turn Right

n = int(input())
dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
pt = [0, 0]  # y, x
t = input()
k = 0
for c in t:
    if c == "S":
        pt[0] += dy[k]
        pt[1] += dx[k]
    else:
        k -= 1
        if k == -1:
            k = 3

# x, y
print(pt[1], pt[0])

3. C. Yamanote Line Game

interactive だった。Python なら print() 時に flush されるが C++ を使ったので endl する必要あり。

int main() {
    int n;
    cin >> n;
    int pos = 1;
    vector<bool> used(n * 2 + 2, false);
    for (int i = 0; i <= n; i++) {
        cout << pos << endl;
        if (i == n) break;
        used[pos] = true;
        int x;
        cin >> x;
        used[x] = true;
        while (used[pos]) {
            pos++;
        }
    }
    int _;
    cin >> _;
    return 0;
}

(3. に関して) ターミナル練習

以下、.py ファイルの名前は main.py であるとします。あなたのファイル名に応じて、適切に読み替えてください。
interactive 問題を解くには、ターミナルを使うべきです。interactive 問題対策として、ターミナルを使ってみましょう。

#!/usr/bin/python3
s = input()
print(s)

上記コードを実行し、その後「oyo」と入力してください。そうすれば、 main.py くんが oyo と返答してくれるはずです。およ～。

$ python3 main.py  # 入力待ち状態になります
oyo  # あなたが入力してくださいね💛
oyo  # main.py くんが出力してくれます

4. D. Swap Hats

group がかなり黒魔術になっていてすいません…

s = list(input().split())
t = list(input().split())
di = {}
for i in range(3):
    di[s[i]] = i
tot = 0
for i in range(3):
    tot += 3 ** i * di[t[i]]
group = [7, 11, 21]
print("Yes" if tot in group else "No")

5. C. Go Home

単調性があったので二分探索をしてしまった。「全ての提出」を見て気付いたが愚直が通る。

二分探索: $O(\log \sqrt n)$
愚直: $O(\sqrt n) = O(10^{4.5})$ ( $\because n = 10^9$ )

x = int(input())
 
ng = 0
ok = int(1e5)
while ok - ng > 1:
    mid = (ok + ng) // 2
    if mid * (mid + 1) // 2 >= x:
        ok = mid
    else:
        ng = mid
print(ok)

int main() {
    using ll = long long;
    ll x;
    cin >> x;
    ll ng = -1, ok = 1e5;
    auto valid = [&](ll i) {
        return x <= i * (i + 1) / 2;
    };
    // めぐる式二分探索
    while (abs(ok - ng) > 1) {
        ll mid = (ok + ng) / 2;
        (valid(mid) ? ok : ng) = mid;
    }
    cout << ok << '\n';
    return 0;
}

6. D. Between Two Arrays

言われた通りの dp を書くと $O(n \max(b)^2)$ 。
累積和で高速化して $O(n \max(b))$ 。

#include <bits/stdc++.h>
using namespace std;

constexpr int MOD = 998244353;

template <int m>
struct Modular {
   private:
    uint _v;
    using mint = Modular;

   public:
    constexpr Modular() : _v(0) {}
    constexpr Modular(long long v) {
        v %= 1ll * m;
        _v = v < 0 ? v + m : v;
    };
    mint &operator++() {
        if (++_v == umod()) _v = 0;
        return *this;
    }
    mint &operator--() {
        if (_v == 0) _v = umod();
        return _v--, *this;
    }
    mint operator++(int) {
        mint res = *this;
        return ++*this, res;
    }
    mint operator--(int) {
        mint res = *this;
        return --*this, res;
    }
    constexpr mint operator-() { return mint() - *this; }
    mint operator+(const mint &rhs) { return mint(*this) += rhs; }
    mint operator-(const mint &rhs) { return mint(*this) -= rhs; }
    mint operator*(const mint &rhs) { return mint(*this) *= rhs; }
    mint operator/(const mint &rhs) { return mint(*this) /= rhs; }
    mint &operator+=(const mint &rhs) {
        _v += rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    mint &operator-=(const mint &rhs) {
        _v -= rhs._v;
        if (_v >= umod()) _v += umod();
        return *this;
    }
    mint &operator*=(const mint &rhs) {
        _v = 1ll * _v * rhs._v % umod();
        return *this;
    }
    mint &operator/=(const mint &rhs) { return *this = *this * rhs.inv(); }
    friend mint operator+(const mint &lhs, const mint &rhs) { return mint(lhs) += rhs; }
    friend mint operator-(const mint &lhs, const mint &rhs) { return mint(lhs) -= rhs; }
    friend mint operator*(const mint &lhs, const mint &rhs) { return mint(lhs) *= rhs; }
    friend mint operator/(const mint &lhs, const mint &rhs) { return mint(lhs) /= rhs; }
    bool operator==(const mint &rhs) { return this->_v == rhs._v; }
    bool operator!=(const mint &rhs) { return this->_v != rhs._v; }
    static constexpr int mod() { return m; }
    constexpr uint val() const { return _v; }
    mint pow(long long n) const {
        mint x = *this, res = 1;
        while (n) {
            if (n & 1) res *= x;
            x *= x, n /= 2;
        }
        return res;
    }
    mint inv() const { return pow(umod() - 2); }
    friend istream &operator>>(istream &is, mint &x) {
        long long _v;
        return is >> _v, x = _v, is;
    }
    friend ostream& operator<<(ostream& os, const mint& x) { return os << x.val(); }

   private:
    static constexpr uint umod() { return m; }
};
using mint = Modular<MOD>;
constexpr mint operator""_M(unsigned long long x) { return mint(x); }

int main() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    const int MX = 3020;
    vector<mint> cur(MX, 0_M);
    cur[0] = 1_M;
    for (int i = 0; i < n; i++) {
        vector<mint> cur_acc(MX, 0_M);
        for (int j = 0; j < MX; j++) {
            cur_acc[j] = j ? cur_acc[j - 1] + cur[j] : cur[j];
        }
        vector<mint> nxt(MX, 0_M);
        for (int x = a[i]; x <= b[i]; x++) {
            nxt[x] = cur_acc[x];
        }
        swap(cur, nxt);
    }
    mint ans = 0_M;
    for (int i = 0; i < MX; i++) {
        ans += cur[i];
    }
    cout << ans << '\n';
    return 0;
}

7. E. King Bombee

自力 AC。制約がやけに小さいので愚直に違いない、と考えた。愚直でいいことに気付けば、愚直 dp するだけ。

#include <bits/stdc++.h>
using namespace std;

constexpr int MOD = 998244353;

template <int m>
struct Modular {
   private:
    uint _v;
    using mint = Modular;

   public:
    constexpr Modular() : _v(0) {}
    constexpr Modular(long long v) {
        v %= 1ll * m;
        _v = v < 0 ? v + m : v;
    };
    mint &operator++() {
        if (++_v == umod()) _v = 0;
        return *this;
    }
    mint &operator--() {
        if (_v == 0) _v = umod();
        return _v--, *this;
    }
    mint operator++(int) {
        mint res = *this;
        return ++*this, res;
    }
    mint operator--(int) {
        mint res = *this;
        return --*this, res;
    }
    constexpr mint operator-() { return mint() - *this; }
    mint operator+(const mint &rhs) { return mint(*this) += rhs; }
    mint operator-(const mint &rhs) { return mint(*this) -= rhs; }
    mint operator*(const mint &rhs) { return mint(*this) *= rhs; }
    mint operator/(const mint &rhs) { return mint(*this) /= rhs; }
    mint &operator+=(const mint &rhs) {
        _v += rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    mint &operator-=(const mint &rhs) {
        _v -= rhs._v;
        if (_v >= umod()) _v += umod();
        return *this;
    }
    mint &operator*=(const mint &rhs) {
        _v = 1ll * _v * rhs._v % umod();
        return *this;
    }
    mint &operator/=(const mint &rhs) { return *this = *this * rhs.inv(); }
    friend mint operator+(const mint &lhs, const mint &rhs) { return mint(lhs) += rhs; }
    friend mint operator-(const mint &lhs, const mint &rhs) { return mint(lhs) -= rhs; }
    friend mint operator*(const mint &lhs, const mint &rhs) { return mint(lhs) *= rhs; }
    friend mint operator/(const mint &lhs, const mint &rhs) { return mint(lhs) /= rhs; }
    bool operator==(const mint &rhs) { return this->_v == rhs._v; }
    bool operator!=(const mint &rhs) { return this->_v != rhs._v; }
    static constexpr int mod() { return m; }
    constexpr uint val() const { return _v; }
    mint pow(long long n) const {
        mint x = *this, res = 1;
        while (n) {
            if (n & 1) res *= x;
            x *= x, n /= 2;
        }
        return res;
    }
    mint inv() const { return pow(umod() - 2); }
    friend istream &operator>>(istream &is, mint &x) {
        long long _v;
        return is >> _v, x = _v, is;
    }
    friend ostream& operator<<(ostream& os, const mint& x) { return os << x.val(); }

   private:
    static constexpr uint umod() { return m; }
};
using mint = Modular<MOD>;
constexpr mint operator""_M(unsigned long long x) { return mint(x); }

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, m, k, s, t, x;
    cin >> n >> m >> k >> s >> t >> x;
    s--, t--, x--;
    vector<vector<int>> edges(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        edges[--a].push_back(--b);
        edges[b].push_back(a);
    }
    vector<vector<mint>> cur(2, vector<mint>(n, 0));
    cur[0][s] = 1;
    for (int _ = 0; _ < k; _++) {
        vector<vector<mint>> nxt(2, vector<mint>(n, 0));
        for (int v1 = 0; v1 < n; v1++) {
            for (auto v2 : edges[v1]) {
                for (int bit = 0; bit < 2; bit++) {
                    nxt[bit ^ (v2 == x)][v2] += cur[bit][v1];
                }
            }
        }
        swap(cur, nxt);
    }
    mint ans = cur[0][t];
    cout << ans << '\n';
    return 0;
}

8. D. Anything Goes to Zero

snuke さんの解説見ました。mod の値が s_pcnt ± 1 の 2 種にしかならないことに気付けば、綺麗に差分更新できる。コーナーケースに注意する。

#include <bits/stdc++.h>
using namespace std;

template <class T>
T modpow(T x, T n, T m) {
    x %= m;
    T res = 1;
    while (n) {
        if (n & 1) res = res * x % m;
        x = x * x % m;
        n /= 2;
    }
    return res;
}
int main() {
    using ll = long long;
    ll n;
    string s;
    cin >> n >> s;
    ll s_pcnt = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '1') s_pcnt++;
    }
    vector<ll> tot_base(2);
    for (int adds = 0; adds < 2; adds++) {
        ll mod = adds ? s_pcnt + 1 : s_pcnt - 1;
        if (mod <= 0) continue;
        for (int i = 0; i < n; i++) {
            tot_base[adds] = (tot_base[adds] * 2 + (s[i] == '1')) % mod;
        }
    }
    auto parse = [&](ll idx) -> ll {
        bool adds = s[idx] == '0';
        ll mod = adds ? s_pcnt + 1 : s_pcnt - 1;
        if (mod == 0) return -1;
        ll tot = 0;
        // tot_base から差分更新して tot を算出
        if (adds) {
            tot = (tot_base[adds] + modpow(2ll, n - 1 - idx, mod)) % mod;
        } else {
            tot = (tot_base[adds] - modpow(2ll, n - 1 - idx, mod) + mod) % mod;
        }
        return tot;
    };
    auto calc = [&](auto self, ll x) -> ll {
        if (!x) return 0ll;
        return self(self, x % __builtin_popcountll(x)) + 1;
    };
    for (int i = 0; i < n; i++) {
        ll x = parse(i);
        // コーナーケース
        if (x == -1) {
            cout << 0 << '\n';
            continue;
        }
        cout << calc(calc, x) + 1 << '\n';
    }
    return 0;
}

1. A. Last Letter

2. B. Go Straight and Turn Right

3. C. Yamanote Line Game

(3. に関して) ターミナル練習

4. D. Swap Hats

5. C. Go Home

6. D. Between Two Arrays

7. E. King Bombee

8. D. Anything Goes to Zero

関連する記事

ABC247 解説的なやつ

CHR_Virtual_10の解説的なやつ

ARC120-F解説

ICPC2020参加記

ブログの更新をお知らせ