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