A - ヒーローからゼロへ
シミュレーション問題です。
kで割れる場合は直接kで割り、そうでない場合は余りを引きます。
コードを見る
#include
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while(t--) {
long long n, k;
cin >> n >> k;
long long count = 0;
while(n > 0){
if(n % k == 0){
n /= k;
count++;
}
else{
long long rem = n % k;
count += rem;
n -= rem;
}
}
cout << count << "\n";
}
return 0;
}
B - オーバーフローをキャッチ！
スタックを利用して各操作の合計を維持します。`end`に遭遇した際には、直前の`for`からの合計を取り出し、そのループ回数を乗じます。オーバーフローが発生すれば即座に終了します。
コードを見る
#include
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
long long limit = (1LL << 32) - 1;
stack st;
vector> loops;
for(int i=0;i> cmd;
if(cmd == "add"){
st.emplace(1, i);
}
else if(cmd == "for"){
int a;
cin >> a;
loops.emplace_back(a, i);
}
else{
long long sum = 0;
while(!st.empty() && st.top().second >= loops.back().second){
sum += st.top().first;
st.pop();
}
auto [multiplier, _] = loops.back();
loops.pop_back();
if(sum * multiplier > limit){
cout << "OVERFLOW!!!" << endl;
return 0;
}
st.emplace(sum * multiplier, i);
}
}
long long total = 0;
while(!st.empty()){
total += st.top().first;
if(total > limit){
cout << "OVERFLOW!!!" << endl;
return 0;
}
st.pop();
}
cout << total << endl;
return 0;
}
C - 電化
列挙アルゴリズムを使用します。
|a_i - x|はa_iとxの距離を表します。この場合、k+1番目に近い距離を見つける必要があります。これにより、先頭k個の点はxを中心に連続した区間となります。
コードを見る
#include
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while(t--){
int n, k;
cin >> n >> k;
vector<int> a(n);
for(auto &x : a) cin >> x;
int result = -1, min_distance = INT_MAX;
for(int i=k;i D - 配列分割
数学的アプローチを使用します。
S_kをkからnまでの後方和とし、p_iをi番目のサブ配列の開始インデックスとします。目的はS_p_1 + S_p_2 + ... + S_p_kを最大化することです。
コードを見る
#include
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<int> a(n);
for(auto &x : a) cin >> x;
vector<long long> suffix_sum(n);
suffix_sum[n-1] = a[n-1];
for(int i=n-2;i>=0;i--){
suffix_sum[i] = suffix_sum[i+1] + a[i];
}
sort(suffix_sum.begin()+1, suffix_sum.end(), greater<long long>());
long long answer = suffix_sum[0];
for(int i=1;i E - 最小セグメントカバー
倍増法を使用します。
f_{i,k}はiから2^kステップ移動した際に到達可能な最も遠い距離を示します。
コードを見る
#include
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
int max_r = 0;
vector> segments(n);
for(auto &[l, r] : segments){
cin >> l >> r;
max_r = max(max_r, r);
}
sort(segments.begin(), segments.end());
vector<int> f(max_r+1, -1);
int ptr = 0;
for(int i=0;i<=max_r;i++){
while(ptr < n && segments[ptr].first <= i){
f[i] = max(f[i], segments[ptr].second);
ptr++;
}
}
int log_max = log2(max_r)+1;
vector dp(max_r+1, vector<int>(log_max+1, -1));
for(int i=0;i<=max_r;i++) dp[i][0] = f[i];
for(int j=1;j<=log_max;j++) for(int i=0;i<=max_r;i++) if(dp[i][j-1]!=-1) dp[i][j] = dp[dp[i][j-1]][j-1];
while(m--){
int l, r;
cin >> l >> r;
if(r > max_r){
cout << "-1\n";
continue;
}
int steps = 0, current = l;
for(int j=log_max;j>=0;j--){
if(dp[current][j] != -1 && dp[current][j] < r){
steps += (1<= r){
steps++;
}
cout << (current >= r ? steps : -1) << "\n";
}
return 0;
}
F - 部分順列の数
XORハッシュを使用します。
[l,r]の範囲が1からr-l+1までの並びになる条件を満たすには、全ての要素が重複せず、最大値がr-l+1である必要があります。
コードを見る
#include
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for(auto &x : a) cin >> x;
vector<unsigned long long> xor_hash(n+1);
for(int i=1;i<=n;i++) xor_hash[i] = rng(), xor_hash[i] ^= xor_hash[i-1];
long long answer = 0;
auto process = [&](vector<int> &arr)->void{
vector<int> prefix_hash(n+1);
int max_val = 0;
for(int i=0;i= max_val && (prefix_hash[i+1] ^ prefix_hash[i+1-max_val]) == xor_hash[max_val]){
answer++;
}
}
};
process(a);
reverse(a.begin(), a.end());
process(a);
answer -= count(a.begin(), a.end(), 1);
cout << answer << "\n";
return 0;
}