A - ポスター (Poster)

回転の後塗り直すのと, 塗り直した後回転するのではコストは変わらない
最初に回転した後塗り直すものとして良い
回転するのは2回まででよい
各回転について塗り直す時間を求め, 最小を取る
計算量は $O(N^2)$

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, b) for(ll i = a; i < b; i++)
template<class T> bool chmin(T& a, const T& b){ if(a > b){ a = b; return 1; } return 0; }
const ll INF = 0x1fffffffffffffff;


void rotate(vector<vector<char>>& a){ // 回転
    ll n = a.size();
    vector<vector<char>> b = a;
    rep(i, 0, n) rep(j, 0, n) a[i][j] = b[j][n - 1 - i];
}
ll cost(const vector<vector<char>>& a, const vector<vector<char>>& b){ // 塗り分けにかかる時間
    ll n = a.size(), ans = 0;
    rep(i, 0, n) rep(j, 0, n) ans += a[i][j] != b[i][j];
    return ans;
}
int main(){
    ll n;
    cin >> n;
    vector<vector<char>> s(n, vector<char>(n)), t(n, vector<char>(n));
    rep(i, 0, n) rep(j, 0, n) cin >> s[i][j];
    rep(i, 0, n) rep(j, 0, n) cin >> t[i][j];
    ll ans = INF;
    chmin(ans, cost(s, t));
    rotate(s);
    chmin(ans, cost(s, t) + 1);
    rotate(s);
    chmin(ans, cost(s, t) + 2);
    rotate(s);
    chmin(ans, cost(s, t) + 1);
    cout << ans << endl;
}

B - いちご (Strawberry)

少なくとも1番遠いいちごのところまで往復する時間はかかる
行き際に収穫しても帰り際に収穫しても答えは変わらないから, 帰り際に収穫するものとしていい
帰り際にまだ熟していなかったらその分待つ必要がある
計算量は $O(N)$

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, b) for(ll i = a; i < b; i++)
template<class T> bool chmin(T& a, const T& b){ if(a > b){ a = b; return 1; } return 0; }
template<class T> bool chmax(T& a, const T& b){ if(a < b){ a = b; return 1; } return 0; }
const ll INF = 0x1fffffffffffffff;


int main(){
    ll n;
    cin >> n;
    ll ans = 0;
    rep(i, 0, n){
        ll a, t;
        cin >> a >> t;
        chmax(ans, a + a); // 往復分
        chmax(ans, a + t); // まだ熟してなかったら待つ
    }
    cout << ans << endl;
}

C - 桁和 (Digit Sum)

"操作をすると $N$ になる整数を探す" のは難しいが, "操作したあとの整数を求める" のは簡単
$X$ が操作して $N$ になるかと $X + d(X)$ が操作して $N$ になるかは同じ
$dp[i] = i$ に操作を続けて $N$ にできるか
計算量は $O(N\log N)$

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll digit_sum(ll a){
    ll ans = 0;
    while(a){
        ans += a % 10;
        a /= 10;
    }
    return ans;
}
int main(){
    ll n;
    cin >> n;
    vector<bool> dp(1000100);
    dp[n] = 1;
    for(ll i = n; --i; ) dp[i] = dp[i + digit_sum(i)];
    cout << accumulate(dp.begin(), dp.end(), 0) << endl;
}

D - テンキー (Tenkey)

表示されている数を $M$ で割った余りを $R$ にしたいんだから, $M$ で割った余りでまとめてDP(？)ができる
$cost[i][j]=$ カーソルが $i$ で、表示されている数を $M$ で割った余りが $j$ にするための最小操作回数
~~Dijkstra法を使って計算~~ BFSで十分
計算量は $O(M\log M)$ (定数倍10倍くらい)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, b) for(ll i = a; i < b; i++)
template<class T> bool chmin(T& a, const T& b){ if(a > b){ a = b; return 1; } return 0; }
template<class T> bool chmax(T& a, const T& b){ if(a < b){ a = b; return 1; } return 0; }
const ll INF = 0x1fffffffffffffff;


int main(){
    ll m, r;
    cin >> m >> r;
    const vector<vector<ll>> g = {{1}, {0, 2, 4}, {1, 3, 5}, {2, 6}, {1, 5, 7}, {2, 4, 6, 8}, {3, 5, 9}, {4, 8}, {5, 7, 9}, {6, 8}}; // 隣のキー
    vector<vector<ll>> cost(10, vector<ll>(m, INF));
    queue<pair<ll, ll>> q;
    cost[0][0] = 0;
    q.push({0, 0});
    while(q.size()){
        ll at, r;
        tie(at, r) = q.front();
        q.pop();
        ll next = (r * 10 + at) % m;
        if(chmin(cost[at][next], cost[at][r] + 1)) q.push({at, next}); // キーを押す
        for(auto& i : g[at]) if(chmin(cost[i][r], cost[at][r] + 1)) q.push({i, r}); // 隣に移動
    }
    ll ans = INF;
    rep(i, 0, 10) chmin(ans, cost[i][r]);
    cout << ans << endl;
}

E - じゃんけん式 (Rock-Scissors-Paper Expression)

まさか構みやつ構文解析が出るとは思わなかったなー
構造分析はパターンがあるので1度解いておくと良さげ
私のパターン : (部分文字列の範囲) → 計算結果の関数を作る
対応するカッコを調べておくとオーダーが落ちる
R → {1, 0, 0} , S → {0, 1, 0} , P → {0, 0, 1} , ? → {1, 1, 1} と変換して各演算子を実装する
勝ち負け, 演算子の定義, 計算順序に気をつけて計算していくと解けるただの実装問

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, b) for(ll i = a; i < b; i++)
template<class T> bool chmin(T& a, const T& b){ if(a > b){ a = b; return 1; } return 0; }
template<class T> bool chmax(T& a, const T& b){ if(a < b){ a = b; return 1; } return 0; }
const ll INF = 0x1fffffffffffffff;
const ll MOD = 1000000007;


struct janken{
    ll R, S, P;
    janken(ll R, ll S, ll P): R(R % MOD), S(S % MOD), P(P % MOD){}
    janken operator+(janken x){
        ll r = R * x.R + R * x.S + S * x.R;
        ll s = S * x.S + S * x.P + P * x.S;
        ll p = P * x.P + P * x.R + R * x.P;
        return {r, s, p};
    };
    janken operator-(janken x){
        ll r = R * x.R + R * x.P + P * x.R;
        ll s = S * x.S + S * x.R + R * x.S;
        ll p = P * x.P + P * x.S + S * x.P;
        return {r, s, p};
    };
    janken operator*(janken x){
        ll r = R * x.R + S * x.P + P * x.S;
        ll s = S * x.S + P * x.R + R * x.P;
        ll p = P * x.P + R * x.S + S * x.R;
        return {r, s, p};
    };
};
string s;
vector<ll> close;
janken parse(ll l, ll r){
    if(l + 1 == r){ // 1文字なら変換
        if(s[l] == 'R') return {1, 0, 0};
        if(s[l]=='S') return {0, 1, 0};
        if(s[l]=='P') return {0, 0, 1};
        return {1, 1, 1};
    }
    vector<janken> a;
    vector<char> b;
    rep(i, l, r){ // カッコがあったら再帰しながら分解
        if(s[i] == '('){
            a.push_back(parse(i + 1, close[i] - 1));
            i = close[i] - 1;
        }
        else if(s[i] >= '?') a.push_back(parse(i, i + 1)); // '*' < '+' < '-' < '?' < 'P' < 'R' < 'S'
        else b.push_back(s[i]);
    }
    vector<janken> c = {a.front()}; // * だけ計算
    vector<char> d;
    rep(i, 0, b.size()){
        if(b[i] == '*') c.back() = c.back() * a[i+1];
        else{
            c.push_back(a[i + 1]);
            d.push_back(b[i]);
        }
    }
    janken ans = c.front(); // + - を計算
    rep(i, 0, d.size()){
        if(d[i] == '+') ans = ans + c[i + 1];
        else ans = ans - c[i + 1];
    }
    return ans;
}
int main(){
    ll n;
    char c;
    cin >> n >> s >> c;
    close.resize(n);
    vector<ll> q;
    rep(i, 0, n){ // 対応するカッコを調べる
        if(s[i] == '(') q.push_back(i);
        else if(s[i] == ')'){
            close[q.back()] = i + 1;
            q.pop_back();
        }
    }
    janken ans = parse(0, n);
    if(c == 'R') cout << ans.R << endl;
    else if(c=='S') cout << ans.S << endl;
    else cout << ans.P << endl;
}