Atcoder Beginner Contest 076 参加した。
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; }
うんこードを書いた日だった、寝る。