TeraCoder2024 | ardririyの足跡

やりごたえがあって面白かったです。全体的にかんたんな問題が多いと思いきや、しっかり難しい問題も混ざっておりとても楽しめました。

A - Welcome to Teracoder

問題: https://mofecoder.com/contests/teracoder2024/tasks/teracoder2024_a
FA狙いでテストをチェックせずに投げましたがFA取れず。ループを書くだけです。
提出

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
void solve() {
    int n;
    cin >> n;
    rep(i, n) cout << "TeraCoder" << endl;
}

B - Big Shout Terakosan

2023と2024のときに注意しつつ、丁寧に場合分けします。2013-2022のときは2012を引いてあげると第何回かが計算できます。
提出

void solve() {
    // hogehoge
    int n;
    cin >> n;
    if (n >= 2013 && n <= 2022) cout << n - 2012 << endl;
    else if (n == 2024) cout << 11 << endl;
    else cout << "Not Held" << endl;
}

C - Substring

部分文字列の判定はPythonだとかんたんに書けるのでPythonで。
提出

input()
s = input()
t = input()

print("Yes" if t in s else "No")

D - Only One Canpas

\(P\) に対するindexの数列 \(S\) と \(L\) が与えられるので、 \(\sum_{i=1}^M P_{S_i}\) と \(\sum_{i=1}^O P_{L_i}\) をそれぞれ求めればよいです( \(M\) , \(O\) はそれぞれ \(S\) , \(L\) の長さ)。全体はそれぞれ求めたものを足し合わせれば求まります。
提出

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
void solve() {
    int n, m, o;
    vector<int> p, s, l;

    cin >> n;
    rep(i, n) {
        int t; cin >> t;
        p.push_back(t);
    }

    cin >> m;
    rep(i, m) {
        int t; cin >> t;
        t--;
        s.push_back(t);
    }
    cin >> o;
    rep(i, o) {
        int t; cin >> t;
        t--;
        l.push_back(t);
    }

    int a = 0, b = 0;
    rep(i, m) {
        a += p[s[i]];
    }
    rep(i, o) {
        b += p[l[i]];
    }
    cout << a << " " << b << " " << a + b << endl;
}

E - Sum Odd

\(N\) が最大で \(4\times 10^4\) と小さいので、愚直に全部足してから \(M\) と比較すればよいです。提出

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
void solve() {
    int n, m;
    cin >> n >> m;
    int sum = 0;
    rep(i, n) {
        sum += i*2+1;
    }
    if(sum>=m) cout << "Yes" << endl;
    else cout << "No" << endl;
}

F - TeraCoderString

こういう判定は相変わらずPythonが楽です。"TeraCoder"に文字が含まれているかどうかを愚直に判定すればOK。提出

n = int(input())
s = input()

for c in s:
    if not c in "TeraCoder":
        print("No")
        exit(0)
print("Yes")

G - Astronomical observation

ぼくは算数が苦手なので一番最後に回しました。
一等星と二等星の場所が初めて同じになるのがどこかが分かれば、間隔は \(\text{lcm}(D_1, D_2)\) なので \(K\) 番目の星がどこにあるかがわかります。そして、 \(K\) 番目の星の場所が分かれば逆算して何番目かを求めることができるので、これを頑張って実装するとこの問題が解けます。

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    int d1, d2;
    cin >> d1 >> d2;
    long long interval = lcm(d1, d2);

    long long start = max(n, m);
    while ((start - n) % d1 != 0 || (start - m) % d2 != 0) {
        start++;
    }

    int res = start + (k-1) * interval;
    int addr = (res - n) / d1 + 1;
    cout << addr << endl;
}

H - Wreker Terako

答えるべきは

\[\sum_{i=A}^N i^3 = \sum_{i=1}^N i^3 - \sum_{i=1}^{A-1} i^3\]

です。 \(\sum_{i=1}^{N} i^3 = (\frac{1}{2}N(N+1))^2\) と \(O(1)\) で求められるので、これを用いることでこの問題が解けます。提出

int MOD = 998244353;
int power(int t, int n) {
    int x = t % MOD;
    int result = 1;
    while (n > 0) {
        if ((n & 1) == 1) {
            result *= x;
            result %= MOD;
        }
        x *= x;
        x %= MOD;
        n >>= 1;
    }
    return result;
} 

void solve() {
    // hogehoge
    int a, n;
    cin >> a >> n;
    int sum = n * (n+1) / 2;
    int sum2 = (a-1) * a / 2;
    sum = power(sum, 2);
    sum2 = power(sum2, 2);

    cout << (sum - sum2 + MOD) % MOD << endl;
}

I - Lunch

不幸度が最小となるような訪問順を順列全探索によって求めればよいです。提出

void solve() {
    int n;
    cin >> n;
    int p[n][n];
    rep(i, n) rep(j, n) cin >> p[i][j];

    vector<int> q;
    rep(i, n) {
        q.push_back(i);
    }

    int ans = 1ll << 60;
    do {
        int cnt = 0;
        rep(i, n) {
            cnt += p[q[i]][i];
        }
        chmin(ans, cnt);
    } while( next_permutation(all(q)));
    cout << 1000000000 - ans << endl;
}

J - radix-N conversion

10進数を経由して頑張って実装します。64bit整数に収めてくれているのは大変ありがたい。
S=0のときに空文字列が出力されており1ペナ。
提出

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
void solve() {
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    reverse(all(s));

    unsigned long long num = 0;
    int base = 1;
    
    int k;
    // n -> 10
    rep(i, s.length()) {
        if(s[i] >= '0' && s[i] <= '9') {
            k = s[i] - '0';
        } else if(s[i] >= 'A' && s[i] <= 'Z') {
            k = s[i] - 'A' + 10;
        } else {
            k = s[i] - 'a' + 36;
        }

        num += base * k;
        base *= n;
    }


    // 10 -> m
    string ans = "";
    while(num != 0) {
        int k = num % m;
        if(k < 10) {
            ans.push_back(k + '0');
        } else if(k < 36) {
            int l = k - 10;
            ans.push_back(l + 'A');
        } else {
            int l = k - 36;
            ans.push_back(l + 'a');
        }
        num /= m;
    }
    reverse(all(ans));
    if(ans == "") ans = "0";
    cout << ans << endl;
}

K - Say!Yes!Kyosan Beam

一番難しかった。要するに閉路を検出した上で、すべての閉路を列挙する必要があります。このときに、例えば

のような入力があった時に、1→2→3の閉路が検出されて記録されるのは良いものの、その後1→2→3→4の閉路が検出されずに終わってしまうというバグと戦っていました。
これを解消するために、「すでに閉路検出された頂点/閉路検出された頂点から伸びてきた頂点であるか」という配列を持っておき、そのような頂点から訪問済みの頂点に到達した場合は追加で閉路検出するというなかなか大変な実装になってしまいました... この問題の想定解が気になるところです。提出

void dfs(vector<vector<int>> &g, int p, vector<int> &history, vector<bool> &seen, vector<bool> &fin, set<int> &ans, vector<bool> &state) {
    seen[p] = true;
    history.push_back(p);

    for(int ni: g[p]) {
        if (state[p] && fin[ni]) {
            for(int i = history.size()-1; i >= 0; i--) {
                if(ans.find(history[i]) != ans.end()) break;
                ans.insert(history[i]);
                state[history[i]] = true;
            }
            continue;
        }
        if(seen[ni] && !fin[ni]) {
            for(int i = history.size()-1; i >= 0; i--) {
                ans.insert(history[i]);
                state[history[i]] = true;
                if (history[i] == ni) break;
            }
            continue;
        }
        if (state[p]) {
            state[ni] = true;
        }
        dfs(g, ni, history, seen, fin, ans, state);
    }
    fin[p] = true;
    history.pop_back();
    return;
}

void solve() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> g(n);

    rep(i, m) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        g[u].push_back(v);
    }

    set<int> ans;
    vector<bool> seen(n, false), fin(n, false), state(n, false);
    vector<int> his;

    dfs(g, 0, his, seen, fin, ans, state);
    if (ans.size() == 0) cout << "Happy" << endl;
    else cout << ans.size() << endl;
}

L - Word Chain Terako

ルールに従って頑張って点数をシミュレーションすればいいです。回文の判定は文字列を反転しても同じかどうかを調べればよく、長さ \(|S|\) の文字列 \(S\) は \(O(|S|)\) で判定できるので、O( \(N|S|\) )で十分高速にシミュレーションできます。
提出

void solve() {
    int n;
    cin >> n;
    vector<string> s(n);
    set<string> set;
    rep(i, n) cin >> s[i];

    string revs;
    int p[2] = {0, 0};
    rep(i, n) {
        if(i!=0) {
            if (s[i-1][s[i-1].size()-1] != s[i][0] || set.find(s[i]) != set.end()) {
                if(p[0] == p[1]) cout << "draw\n-1" << endl;
                else if(p[0] > p[1]) cout << "Terako\n" << p[0] << endl;
                else cout << "TerakoA\n" << p[1] << endl;
                return;
            }
        }
        revs = s[i];
        reverse(all(revs));
        if(revs == s[i]) {
            p[i%2] += 2;
        } else {
            p[i%2] += 1;
        }
        set.insert(s[i]);
    }
    if(p[0] == p[1]) cout << "draw\n-1" << endl;
    else if(p[0] > p[1]) cout << "Terako\n" << p[0] << endl;
    else cout << "TerakoA\n" << p[1] << endl;
}

途中まで問題を「ルールを破ったら負け」と勘違いしており、変なClarを投げて大変申し訳ございませんでした...

M - Like Frobenius

\[\begin{align}\sum_{i=2}^{N-1} \sum_{j=i+1}^N (ij-i-j) &= \sum_{i=2}^{N-1} \sum_{j=i+1}^N\{ j(i-1) - i\} \\&= \sum_{i=2}^{N-1}(\sum_{j=i+1}^N j(i-1) - \sum_{j=i+1}^Ni) \\&= \sum_{i=2}^{N-1} \{(i-1)\times (\frac{1}{2}\frac{n(n+1)}{2} - \frac{1}{2}\frac{i(i+1)}{2}) - i\times(n-i)\}\end{align}\]

というように、1重のループのみの形に書き直すことができます。よって、 \(O(N)\) となり、これは十分高速なので、この問題が解けました。
提出

void solve() {
    int n;
    cin >> n;

    int MOD = 998244353;
    int ans = 0;
    for(int i = 2; i < n; i ++) {
        int k = n - i;
        int x = (i * (i+1) / 2) % MOD;
        ans += (i-1) * ((n * (n+1) / 2) % MOD - x + MOD) % MOD - (k * i) % MOD;
        ans = (ans + MOD) % MOD;
    }
    cout << ans << endl;
}

大変取り組みやすく楽しいコンテストでした。来年も楽しみです。