E - 数字の和で割り切れる数

この問題では、与えられた正整数 \(N\) 以下の自然数のうち、その桁の和で割った余りが 0 となる数を求める必要があります。

通常の桁 DP では、剰余を状態として維持するのは容易ですが、今回のように「剰元の基準（桁の和）」自体が変化する場合、直接的な DP では困難になります。そこで、桁の和（モジュロ）を先に見積もるアプローチを取ります。

\(N\) が最大 14 桁であることを考えると、桁の和の最大値は \(9 \times 14 = 126\) です。これは比較的小さい範囲であるため、すべての可能性（1 から 126）に対して独立して計算を行い、集計することができます。各固定された総和 \(S\) について、桁 DP を実行し、最終的に桁和が \(S\) に一致し、かつ \(S\) で割り切れれば有効な数としてカウントします。

long long memo[16][130][130];
int target_sum;
int digits_list[20];

// pos: 現在の桁位置，sum: これまでの桁和，rem: 現在の数値 % target_sum, is_limit: N の制限があるか
long long solve_dp(int pos, int sum, int rem, bool is_limit) {
    if (pos < 0) {
        return (rem == 0 && sum == target_sum) ? 1 : 0;
    }
    if (!is_limit && memo[pos][sum][rem] != -1) {
        return memo[pos][sum][rem];
    }

    long long total = 0;
    int limit_digit = is_limit ? digits_list[pos] : 9;

    for (int d = 0; d <= limit_digit; ++d) {
        // 新合計：sum + d, 新剰余：(rem * 10 + d) % target_sum
        total += solve_dp(pos - 1, sum + d, (rem * 10 + d) % target_sum, is_limit && (d == limit_digit));
    }

    if (!is_limit) {
        memo[pos][sum][rem] = total;
    }
    return total;
}

int main() {
    long long N;
    cin >> N;
    
    // 桁分解
    int len = 0;
    string strN = to_string(N);
    for(char c : strN) digits_list[len++] = c - '0';
    reverse(digits_list, digits_list + len); // 下位から扱うように調整が必要かもしれないが、ここでは上から処理する想定
    
    // 配列リセット
    // 注意：通常 Digits DP は上位から処理するため、インデックス操作に注意
    // ここでは簡略化のため、文字列からの直接アクセスや再帰構造を工夫する
    
    // 実際の実装では、digits_list のインデックス管理を慎重に行う必要がある
    // 簡易的な桁分解の例として
    
    memset(memo, -1, sizeof(memo));
    long long ans = 0;
    
    // 桁の和の取り得る値 1 ~ 9*18 (18 桁想定)
    for (int s = 1; s <= 150; ++s) {
        target_sum = s;
        fill(&memo[0][0][0], &memo[0][0][0] + sizeof(memo)/sizeof(long long), -1);
        ans += solve_dp(strN.size()-1, 0, 0, true);
    }
    
    cout << ans << endl;
    return 0;
}

計算量は、状態数 \(16 \times 130 \times 130\) に遷移回数 10 を掛けたもので十分に収まります。

F - グリッドの回転と双方向探索

初期配置の行列を目標配置に変える最小手数を求めます。操作中には指定された部分行列を回転させることができます。1 回の手数は 4 通りあり、最大 20 回まで操作可能です。

単純な探索を行う場合、状態空間は \(4^{20}\) となり巨大です。ここで、出発点から深さ 10、目標点から逆方向へ深さ 10 ずつ探索を行う「Meet-in-the-middle（双方向探索）」を適用します。双方の状態集合が交差する点を検出することで、全体の手数を見つけます。

行列の状態を効率的に管理するために、ハッシュ関数を用います。行列全体を 1 つのシークエンスと見なし、多項式ロールハッシュなどで一意な値を生成し、到達距離をマップに記録します。

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

typedef long long ll;
struct GridState {
    vector cells;
};

const ll MOD_HASH = 1e9 + 7;
const ll BASE = 313;

ll compute_hash(const GridState& g, int R, int C) {
    ll h = 0;
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            h = (h * BASE + g.cells[i][j]) % MOD_HASH;
        }
    }
    return h;
}

GridState perform_rotate(const GridState& g, int R, int C, int r_offset, int c_offset) {
    GridState nxt = g;
    // サブ行列の定義に従い回転処理を実装
    // 具体的な回転ロジックは問題文の条件に基づくが、一般的に中心対称または 90 度回転とする
    // ここではサンプルコードのロジックに近い形式で記述
    for (int i = 1; i < R; ++i) {
        for (int j = 1; j < C; ++j) {
             // 変換則: 対角線に沿った入れ替えなど
             int src_r = R - i + r_offset; 
             int src_c = C - j + c_offset;
             if(src_r >= 0 && src_r < R && src_c >= 0 && src_c < C) {
                 nxt.cells[i + r_offset][j + c_offset] = g.cells[src_r][src_c];
             }
        }
    }
    return nxt;
}

void solve_problem_F() {
    int H, W;
    if (!(cin >> H >> W)) return;

    GridState start_s, goal_s;
    start_s.cells.resize(H, vector<int>(W));
    goal_s.cells.resize(H, vector<int>(W));

    for(int i=0; i> start_s.cells[i][j];
            goal_s.cells[i][j] = i * W + j + 1;
        }
    }

    queue<GridState> q_start, q_goal;
    unordered_map dist_start, dist_goal;

    q_start.push(start_s);
    q_goal.push(goal_s);
    dist_start[compute_hash(start_s, H, W)] = 0;
    dist_goal[compute_hash(goal_s, H, W)] = 0;

    int max_depth = 10;

    while(!q_start.empty() && !q_goal.empty()) {
        // 開始側展開
        GridState cur = q_start.front();
        q_start.pop();
        ll h_val = compute_hash(cur, H, W);
        
        if(dist_goal.count(h_val)) {
            cout << dist_start[h_val] + dist_goal[h_val] << endl;
            return;
        }
        
        if(dist_start[h_val] < max_depth) {
             for(int dx=0; dx<=1; ++dx) {
                 for(int dy=0; dy<=1; ++dy) {
                     GridState next_s = perform_rotate(cur, H, W, dx, dy);
                     ll nh = compute_hash(next_s, H, W);
                     if(dist_start.find(nh) == dist_start.end()) {
                         dist_start[nh] = dist_start[h_val] + 1;
                         q_start.push(next_s);
                     }
                 }
             }
        }

        // 目標側展開
        cur = q_goal.front();
        q_goal.pop();
        h_val = compute_hash(cur, H, W);

        if(dist_start.count(h_val)) {
            cout << dist_start[h_val] + dist_goal[h_val] << endl;
            return;
        }

        if(dist_goal[h_val] < max_depth) {
             for(int dx=0; dx<=1; ++dx) {
                 for(int dy=0; dy<=1; ++dy) {
                     GridState next_s = perform_rotate(cur, H, W, dx, dy);
                     ll nh = compute_hash(next_s, H, W);
                     if(dist_goal.find(nh) == dist_goal.end()) {
                         dist_goal[nh] = dist_goal[h_val] + 1;
                         q_goal.push(next_s);
                     }
                 }
             }
        }
    }

    cout << -1 << endl;
}