Translation Notice
This article was machine-translated using DeepSeek-R1.

Original Version: Authored in Chinese by myself

Accuracy Advisory: Potential discrepancies may exist between translations

Precedence: The Chinese text shall prevail in case of ambiguity

Feedback: Technical suggestions regarding translation quality are welcomed

Long time no write-up. Here’s a quick one.

A - Job Interview

Problem Summary

Given a string $S$ of length $N$ consisting of o, -, and x.

Determine if $S$ satisfies:

Contains at least one o.
Contains no x.

$1\le N\le 100$

Approach

Straightforward simulation.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


#include <cstdio>
using namespace std;

int main()
{
    while(getchar() != '\n');
    char c;
    bool ok = false;
    while((c = getchar()) != '\n')
    {
        if(c == 'x')
        {
            puts("No");
            return 0;
        }
        if(c == 'o')
            ok = true;
    }
    puts(ok? "Yes": "No");
    return 0;
}

Python ~~quick pass~~ one-liner

1
2
3


input()
s = input()
print('Yes' if 'o' in s and 'x' not in s else 'No')

Saved 208 characters (~~flees~~

B - Coloring Matrix

Problem Summary

Given two $N\times N$ binary matrices $A$ and $B$.

Rotate $A$ by 0°, 90°, 180°, or 270°, then check if for every cell where $A_{i,j}=1$, $B_{i,j}=1$.

$1\le N\le 100$

Approach

Simulate all four rotations as described in the problem statement.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


#include <cstdio>
#define maxn 105
using namespace std;

int a[maxn][maxn], b[maxn][maxn], c[maxn][maxn];

int main()
{
    int n;
    scanf("%d", &n);
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            scanf("%d", a[i] + j);
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            scanf("%d", b[i] + j);
    for(int x=0; x<4; x++)
    {
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                c[i][j] = a[i][j];
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                a[i][j] = c[n - 1 - j][i];
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                if(a[i][j] && !b[i][j])
                    goto bad; // Avoid using goto (old habit), don't learn this
        puts("Yes");
        return 0;
        bad:;
    }
    puts("No");
    return 0;
}

C - Cards Query Problem

Problem Summary

Process $Q$ queries on $N$ boxes:

Insert card with number $i$ into box $j$.
Output all cards in box $i$ in sorted order (duplicates allowed).
Output all boxes containing card $i$ in sorted order (no duplicates).

$1\le N,Q\le 2\times 10^5$

Approach

Maintain a multiset per box for query type 2.
Maintain a set per card for query type 3.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


#include <cstdio>
#include <set>
#define maxn 200005
using namespace std;

multiset<int> box[maxn];
set<int> has[maxn];

int main()
{
    int n, q;
    scanf("%d%d", &n, &q);
    while(q--)
    {
        int op, i;
        scanf("%d%d", &op, &i);
        if(op == 1)
        {
            int j;
            scanf("%d", &j);
            box[j].insert(i);
            has[i].insert(j);
        }
        else if(op == 2)
        {
            for(int x: box[i])
                printf("%d ", x);
            putchar('\n');
        }
        else if(op == 3)
        {
            for(int x: has[i])
                printf("%d ", x);
            putchar('\n');
        }
    }
    return 0;
}

D - Writing a Numeral

Problem Summary

Maintain a string $S$ (initially “1”) through $Q$ operations:

Append digit $x$ to $S$.
Remove the first character of $S$.
Output $S$ modulo $998244353$.

$1\le Q\le 6\times 10^5$

Approach

Maintain the current value modulo $P=998244353$ and track $10^{|S|}\bmod P$ to handle removals efficiently.

Code

Implementation 1: Using atcoder::modint and deque

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


#include <cstdio>
#include <deque>
#include <atcoder/modint>
using namespace std;

using modint = atcoder::modint998244353;

int main()
{
    deque<int> s;
    s.push_back(1);
    int q;
    scanf("%d", &q);
    modint ans = 1;
    while(q--)
    {
        int op;
        scanf("%d", &op);
        if(op == 1)
        {
            int x;
            scanf("%d", &x);
            s.push_back(x);
            ans = ans * 10 + x;
        }
        else if(op == 2)
        {
            int x = s.front(); s.pop_front();
            ans -= x * modint(10).pow((int)s.size());
        }
        else printf("%d\n", ans.val());
    }
    return 0;
}

Implementation 2: Manual modular arithmetic with queue

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


#include <cstdio>
#include <queue>
#define MOD 998244353
using namespace std;

int main()
{
    int Q;
    scanf("%d", &Q);
    queue<int> q;
    q.push(1);
    int ans = 1, p = 1;
    while(Q--)
    {
        int op;
        scanf("%d", &op);
        if(op == 1)
        {
            int x;
            scanf("%d", &x);
            q.push(x);
            ans = (ans * 10LL + x) % MOD;
            p = p * 10LL % MOD;
        }
        else if(op == 2)
        {
            ans -= (long long) q.front() * p % MOD; q.pop();
            p = p * 299473306LL % MOD; // 299473306 is inverse of 10 modulo MOD
            if(ans < 0) ans += MOD;
        }
        else printf("%d\n", ans);
    }
    return 0;
}

E - Unfair Sugoroku

Problem Summary

Two players move on a board of $N$ cells. Takahashi starts at $A$, Aoki at $B$. Takahashi’s die has $P$ faces, Aoki’s has $Q$ faces. Compute Takahashi’s winning probability modulo $998244353$.

$2\le N\le 100$

Approach

DP with states $f_{i,j}$ (Takahashi’s turn) and $g_{i,j}$ (Aoki’s turn). Transition by averaging over possible dice outcomes.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47


#include <cstdio>
#include <algorithm>
#define MOD 998244353
#define maxn 105
using namespace std;

using LL = long long;
inline LL inv(LL x)
{
    int y = MOD - 2;
    LL res = 1LL;
    while(y)
    {
        if(y & 1) (res *= x) %= MOD;
        (x *= x) %= MOD, y >>= 1;
    }
    return res;
}

inline void add(int& x, int y)
{
    if((x += y) >= MOD)
        x -= MOD;
}

int f[maxn][maxn], g[maxn][maxn];

int main()
{
    int n, a, b, p, q;
    scanf("%d%d%d%d%d", &n, &a, &b, &p, &q);
    for(int i=0; i<n; i++)
        f[n][i] = g[n][i] = 1, f[i][n] = g[i][n] = 0;
    LL prob_p = inv(p), prob_q = inv(q);
    for(int i=n-1; i>=a; i--)
        for(int j=n-1; j>=b; j--)
        {
            for(int k=1; k<=p; k++)
                add(f[i][j], g[min(i + k, n)][j]);
            f[i][j] = f[i][j] * prob_p % MOD;
            for(int k=1; k<=q; k++)
                add(g[i][j], f[i][min(j + k, n)]);
            g[i][j] = g[i][j] * prob_q % MOD;
        }
    printf("%d\n", f[a][b]);
    return 0;
}

F - Rook Score

Problem Summary

Given $N$ non-zero grid cells, compute the maximum sum of a row and column (minus overlap) for any chosen cell.

$1\le N\le 2\times 10^5$

Approach

Track row sums and column sums. Use a max-heap to maintain column contributions adjusted for overlaps.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52


#include <cstdio>
#include <vector>
#include <set>
#include <unordered_map>
using namespace std;

using LL = long long;
using pii = pair<int, int>;

unordered_map<int, vector<pii>> rows;
unordered_map<int, LL> col_sum;

template <typename T>
class MaxSet {
private:
    multiset<T> s;
public:
    inline void insert(const T& x) { s.insert(x); }
    inline void update(const T& old, const T& New) {
        s.erase(s.find(old));
        s.insert(New);
    }
    inline T max() { return *s.rbegin(); }
};

int main()
{
    int n;
    scanf("%d", &n);
    while(n--)
    {
        int x, y, v;
        scanf("%d%d%d", &x, &y, &v);
        rows[x].emplace_back(y, v);
        col_sum[y] += v;
    }
    MaxSet<LL> s;
    for(auto [_, sum]: col_sum)
        s.insert(sum);
    LL ans = 0LL;
    for(auto& [x, v]: rows)
    {
        for(auto [y, val]: v)
            s.update(col_sum[y], col_sum[y] - val);
        LL cur = s.max();
        for(auto [y, val]: v)
            s.update(col_sum[y] - val, col_sum[y]), cur += val;
        if(cur > ans) ans = cur;
    }
    printf("%lld\n", ans);
    return 0;
}

G - Strawberry War

Problem Summary

Partition a $H\times W$ grid into $T+1$ rectangles via $T$ cuts. Minimize the difference between maximum and minimum strawberry counts.

$1\le H,W\le 6$

Approach

Dynamic programming tracking minimal maximum value for each subrectangle and cut count. Enumerate all possible minimum values.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61


#include <bits/stdc++.h>
using namespace std;
const long long INF = 1000000000000000000;
int main(){
  int H, W, T;
  cin >> H >> W >> T;
  vector<vector<long long>> s(H, vector<long long>(W));
  for (int i = 0; i < H; i++){
    for (int j = 0; j < W; j++){
      cin >> s[i][j];
    }
  }
  vector<vector<vector<vector<long long>>>> sum(H, vector<vector<vector<long long>>>(H + 1, vector<vector<long long>>(W, vector<long long>(W + 1, 0)));
  vector<long long> x;
  for (int i = 0; i < H; i++){
    for (int j = i + 1; j <= H; j++){
      for (int k = 0; k < W; k++){
        for (int l = k + 1; l <= W; l++){
          for (int m = i; m < j; m++){
            for (int n = k; n < l; n++){
              sum[i][j][k][l] += s[m][n];
            }
          }
          x.push_back(sum[i][j][k][l]);
        }
      }
    }
  }
  int cnt = x.size();
  long long ans = INF;
  for (int i = 0; i < cnt; i++){
    vector<vector<vector<vector<vector<long long>>>>> dp(T + 1, vector<vector<vector<vector<long long>>>>(H, vector<vector<vector<long long>>>(H + 1, vector<vector<long long>>(W, vector<long long>(W + 1, INF)))));
    for (int j = H - 1; j >= 0; j--){
      for (int k = j + 1; k <= H; k++){
        for (int l = W - 1; l >= 0; l--){
          for (int m = l + 1; m <= W; m++){
            if (sum[j][k][l][m] >= x[i]){
              dp[0][j][k][l][m] = sum[j][k][l][m];
            }
            for (int n = j + 1; n < k; n++){
              for (int o = 0; o < (n - j) * (m - l); o++){
                for (int p = 0; p < (k - n) * (m - l) && o + p < T; p++){
                  dp[o + p + 1][j][k][l][m] = min(dp[o + p + 1][j][k][l][m], max(dp[o][j][n][l][m], dp[p][n][k][l][m]));
                }
              }
            }
            for (int n = l + 1; n < m; n++){
              for (int o = 0; o < (k - j) * (n - l); o++){
                for (int p = 0; p < (k - j) * (m - n) && o + p < T; p++){
                  dp[o + p + 1][j][k][l][m] = min(dp[o + p + 1][j][k][l][m], max(dp[o][j][k][l][n], dp[p][j][k][n][m]));
                }
              }
            }
          }
        }
      }
    }
    ans = min(ans, dp[T][0][H][0][W] - x[i]);
  }
  cout << ans << endl;
}