Atcoder Beginner Contest 076 参加した。

abc076.contest.atcoder.jp


114514年振りに投下しておく、Cで詰まってD問題考えてるうちに終わった。



A問

かけてひくだけ

#include <cstdio>
 
int r, g;
 
int main(){
    scanf("%d %d", &r, &g);
 
    printf("%d\n", g * 2 - r);
 
    return 0;
}

B問

2倍した場合とK足した場合で増分の小さい方を選んでN回足す

#include <cstdio>
#include <cmath>
 
int n, k;
 
int main(){
    scanf("%d %d", &n, &k);
 
    int ans = 1;
    for(int i = 0; i < n; i++){
        if(ans * 2 < ans + k){
            ans *= 2;
        }else{
            ans += k;
        }
    }
 
    printf("%d\n", ans);
 
    return 0;
}


C問

辞書順を考慮してSの後ろからTと一致する部分を探索する、
(?部分はaで埋めるのでa以外の文字が含まれるかもしれないTはS'の後ろにあった方が都合がいい)

SとTが最大の長さでも調べるのは50×50回なので全部調べても問題なし。

#include <iostream>
#include <string>
 
std::string str, t;
 
int main(){
    std::cin >> str >> t;
 
    int k = -1;
    for(int i = str.size() - 1; i >= t.size() - 1; i--){
        bool flag = true;
        for(int j = t.size() - 1; j >= 0; j--){
            if((str[i + j - t.size() + 1] != t[j]) &&
                str[i + j - t.size() + 1] != '?'){
 
                flag = false;
                break;
            }
        }
 
        if(flag){
            k = i - t.size() + 1;
            break;
        }
    }
 
    if(k == -1){
        std::cout << "UNRESTORABLE\n";
    }else{
        int c = 0;
        for(int i = 0; i < str.size(); i++){
            if(k <= i && i < k + t.size()){
                str[i] = t[c++];
            }else if(str[i] == '?'){
                str[i] = 'a';
            }
        }
 
        std::cout << str << std::endl;
    }
 
    return 0;
}


うんこードを書いた日だった、寝る。