やりごたえがあって面白かったです。全体的にかんたんな問題が多いと思いきや、しっかり難しい問題も混ざっておりとても楽しめました。 # A - Welcome to Teracoder 問題: https://mofecoder.com/contests/teracoder2024/tasks/teracoder2024_a FA狙いでテストをチェックせずに投げましたがFA取れず。ループを書くだけです。 [提出](https://mofecoder.com/contests/teracoder2024/submissions/18960) ```c++ #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を引いてあげると第何回かが計算できます。 [提出](https://mofecoder.com/contests/teracoder2024/submissions/18991) ```cpp 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で。 [提出](https://mofecoder.com/contests/teracoder2024/submissions/19005) ```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$の長さ)。全体はそれぞれ求めたものを足し合わせれば求まります。 [提出](https://mofecoder.com/contests/teracoder2024/submissions/19031) ```cpp #define rep(i, n) for (int i = 0; i < (int)(n); i++) void solve() { int n, m, o; vector 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$と比較すればよいです。[提出](https://mofecoder.com/contests/teracoder2024/submissions/19050) ```cpp #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。 [提出](https://mofecoder.com/contests/teracoder2024/submissions/19064) ```python 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$番目の星の場所が分かれば逆算して何番目かを求めることができるので、これを頑張って実装するとこの問題が解けます。 ```cpp 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)$で求められるので、これを用いることでこの問題が解けます。[提出](https://mofecoder.com/contests/teracoder2024/submissions/19084) ```cpp 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 不幸度が最小となるような訪問順を順列全探索によって求めればよいです。[提出](https://mofecoder.com/contests/teracoder2024/tasks/teracoder2024_i) ```Cpp void solve() { int n; cin >> n; int p[n][n]; rep(i, n) rep(j, n) cin >> p[i][j]; vector 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ペナ。 [提出](https://mofecoder.com/contests/teracoder2024/submissions/19229) ```cpp #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 一番難しかった。要するに閉路を検出した上で、すべての閉路を列挙する必要があります。このときに、例えば ``` 4 5 1 2 2 3 3 1 2 4 4 3 ``` のような入力があった時に、1→2→3の閉路が検出されて記録されるのは良いものの、その後1→2→3→4の閉路が検出されずに終わってしまうというバグと戦っていました。これを解消するために、「すでに閉路検出された頂点/閉路検出された頂点から伸びてきた頂点であるか」という配列を持っておき、そのような頂点から訪問済みの頂点に到達した場合は追加で閉路検出するというなかなか大変な実装になってしまいました... この問題の想定解が気になるところです。[提出](https://mofecoder.com/contests/teracoder2024/submissions/19371) ```cpp void dfs(vector> &g, int p, vector &history, vector &seen, vector &fin, set &ans, vector &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> g(n); rep(i, m) { int u, v; cin >> u >> v; u--; v--; g[u].push_back(v); } set ans; vector seen(n, false), fin(n, false), state(n, false); vector 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|$)で十分高速にシミュレーションできます。 [提出](https://mofecoder.com/contests/teracoder2024/submissions/19217) ```cpp void solve() { int n; cin >> n; vector s(n); set 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 -1" << endl; else if(p[0] > p[1]) cout << "Terako " << p[0] << endl; else cout << "TerakoA " << 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 -1" << endl; else if(p[0] > p[1]) cout << "Terako " << p[0] << endl; else cout << "TerakoA " << 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)$となり、これは十分高速なので、この問題が解けました。 [提出](https://mofecoder.com/contests/teracoder2024/submissions/19340) ```cpp 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; } ``` --- 大変取り組みやすく楽しいコンテストでした。来年も楽しみです。

TeraCoder2024