{%hackmd Gkxun6TZTIGjCpqKlW4NMA %}

# 2025/04/25 期中考

## Scoreboard

:::spoiler scoreboard
:::

## problems

### url for each problem

* [Translated Statement by SA](https://hackmd.io/@sa072686/SyFSC6w1ex/%2F%40sa072686%2FAtCoder_abc174_c)

* [pA - AtCoder abc174_c - Repsept](https://atcoder.jp/contests/abc174/tasks/abc174_c)
* [pB - AtCoder joi2025_yo2_b - ビリヤード (Billiards)](https://atcoder.jp/contests/joi2025yo2/tasks/joi2025_yo2_b)
* [pC - AtCoder abc301_c - AtCoder Cards](https://atcoder.jp/contests/abc301/tasks/abc301_c)
* [pD - AtCoder abc247_d - Cylinder](https://atcoder.jp/contests/abc247/tasks/abc247_d)

### pA

:::success
Simpled Statement

給 $K$ 使得 $\overbrace{7777\ldots777}^{ans}$ 被 $K$ 整除
求最小的 $ans$
假如 $ans$ 不存在則輸出 "-1"
:::

:::warning
Solution

$7, 77, \ldots, \overbrace{7777\ldots777}^n \pmod{K}$
理論上應該會形成一個循環節
不論是 $1 \to 2 \to 3 \to \ldots \to 0 \to 1$
或者是 $1 \to 2 \to 4 \to 1$
終究會停止，且透過仔細的觀察會發現
此循環節的長度不超過 $K$
所以我們可以透過 $f(n) = f(n-1) \times 10 + 7$ 來快速轉移到 $\overbrace{7777\ldots777}^n$
只要轉移超過 $K$ 次後，沒找到答案則無解

過程中要小心 $\overbrace{7777\ldots777}^n$ 會超過 `long long` 儲存的範圍
但我們發現，我們要判斷的只是 $\overbrace{7777\ldots777}^n \pmod{K}$
所以可以透過同餘定理，每次計算都取模避免溢位
:::

:::spoiler code

#include <iostream>
using namespace std;
int main() {
    int k; cin >> k;
    int ans = -1;
    for(int i = 1, now = 7%k; i <= k; i++, now = (now*10+7)%k) {
        if(!now) {
            ans = i;
            break;
        }
    }
    cout << ans << '\n';
}

:::

:::info
Thoughts

比賽的時候第一直覺是同餘最短路
然後隨便想一想就出來了

但是判斷有沒有重複的時候
為了拚首殺，選擇了一個實作超輕鬆，但超吃毒的寫法
直接開 `map` 下去砸
慢了超級多倍www
:::

### pB

:::success
Simpled Statement

給 $X$
長度為 $N$ 的陣列 $A = \{A_1, A_2, \ldots, A_N\}$
長度為 $N$ 的陣列 $P = \{P_1, P_2, \ldots, P_N\}$
假設一個長度為 $K$ 的陣列 $B$
$1 \le B_i (1 \le i \le K) \le N$
使得 $A_{B_1} + A_{B_2} + \ldots + A_{B_K} \le X$
且符合 $P_{B_i} = -1 \vee P_{B_i} \in B \space \forall \space 1 \le i \le N$
求 $B_K$ 最大能多少
:::

:::warning
Solution

我們可以把這題想像成一張圖 ($N$ 點 $\sum^{N}_{i = 1}{P_i \neq -1}$ 邊)
則我們可以 greedy 的假設答案一定是這張圖上的一條鍊
且這條鍊上的總和不超過 $X$

而簡單的觀察下，我們會發現在環上的點肯定不能當作答案
我們可以使用 top down 或者 bottom up 的方式遍歷
在 DAG 的順序上做就可以得出答案了

> 用陣列紀錄答案下，其實概念上就有些 dynamic programming 的技巧
> 只是是單一轉移點的 DP 而已

這題因為存在環，所以個人認為 bottom up 的方式做會更好
:::

:::spoiler code

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
	int n; long long x;
	cin >> n >> x;
	vector<int> v(n); for(auto &d : v) cin >> d;
	vector<vector<int> > g(n);
	vector<long long> sum(n);
	queue<int> qq;
	for(int i = 0; i < n; i++) {
		int a; cin >> a;
		if(a != -1) g[a-1].push_back(i);
		else if(v[i] <= x) {
			sum[i] = v[i];
			qq.push(i);
		}
	}
	int ans = -1;
	while(qq.size()) {
		int id = qq.front();
		qq.pop();
		ans = max(ans, id+1);
		for(auto &d : g[id]) if(sum[id] + v[d] <= x) {
			sum[d] = sum[id] + v[d];
			qq.push(d);
		}
	}
	cout << ans << '\n';
}

:::

:::info
Thoughts

因為這題是 JOI 的題目，所以果斷放棄
回來想的時候一直覺的是 DP，然後隨便做一做就過了
:::

### pC

:::success
Simpled Statement

給兩字串 $s, t$
$@$ 可以變換為 $\{a, t, c, o, d, e, r\}$ 其中一個
你可以隨便換 $t$ 的順序
問是否可以使得 $s = t$
:::

:::warning
Solution

排序其實根本沒必要
因為更換 $t$ 的順序 $=$ 更換 $s$ 的順序
所以我們只要看字母是否可以匹配上就行了
:::

:::spoiler code

#include <iostream>
#include <algorithm> // count
using namespace std;
int alp[128];
int main() {
	string a = "atcoder";
	string s, t; cin >> s >> t;
	for(char &c : s) alp[c]++;
	bool ok = true;
	int cnt = 0;
	for(char &c : t) if(c != '@') {
		if(alp[c]) alp[c]--;
		else if(!count(a.begin(), a.end(), c)) // c not in a
			ok = false;
	} else cnt++;
	for(char i = 'a'; i <= 'z'; i++)
		if(!count(a.begin(), a.end(), i) && alp[i]) // i not in a
			ok = false;
		else {
			cnt -= alp[i];
			if(cnt < 0) ok = false;
		}
	cout << (ok ? "Yes\n" : "No\n");
}

:::

:::info
Thoughts

超多細節的一題
一直吃WA超躁
最後隨便喇一喇突然就過了 :-1:
:::

### pD

:::success
Simpled Statement

$Q$ 筆操作

兩種操作
1. 將 $c$ 個數字 $x$ 丟到右邊
2. 將左邊 $c$ 個東西拿出來，問總和
:::

:::warning
Solution

簡單的 STL 題目
:::

:::spoiler code

#include <iostream>
#include <queue>
using namespace std;
int main() {
    int q; cin >> q;
    deque<pair<int, int> > dqq; // x, c
    while(q--) {
        int op; cin >> op;
        if(op == 1) {
            int x, c; cin >> x >> c;
            dqq.push_back({x, c});
        } else {
            int c; cin >> c;
            long long ans = 0;
            while(c) {
                auto &[a, b] = dqq.front();
                int mn = min(c, b);
                c -= mn;
                ans += 1ll*a*mn;
                if(b == mn) dqq.pop_front();
                else b -= mn;
            }
            cout << ans << '\n';
        }
    }
}

:::

:::info
Thoughts

挺簡單的，沒啥心得
:::

## Conclusion

這次比賽的難度我覺得算有一點點超綱
pA 想法上我是直接以同餘最短路出發，所以我個人感覺這題反而是全部題目裡面來想法算難的題目
pB 牽涉到圖論上的想法，所以對新手比較不友善 (雖然作法上沒有涉及到圖論)
pC 單純是我不喜歡那種瘋狂找反例的題目 :angry:
pD 水題

但相對於裸題來說，這種吃點想法的題目對於目前競程生態來說是好的