理想的な生成器の判定
正整数kが「理想生成器」であるとは、任意の整数n（n ≥ k）が、長さkの回文配列の要素和として表現可能な場合を指す。回文配列とは、配列aがa1からakまでとakからa1までが同一となる配列である。例として、k=1は理想生成器である（nは[n]で表現可能）が、k=2は非理想（3を表現不可能）。
解法: kが奇数の場合のみ理想生成器となる。偶数の場合、配列和が奇数値を取り得ないため。
実装例
#include <iostream>
using namespace std;
int main() {
int test_cases;
cin >> test_cases;
while (test_cases--) {
int generator;
cin >> generator;
cout << (generator % 2 ? "YES" : "NO") << endl;
}
return 0;
}高価な数字の最適化
正整数nの「コスト」はnを各桁の和で除算した値と定義される。nから任意の桁を除去し（先頭ゼロ許容）、残りの数字でコストを最小化せよ。
解法: 最下位の非ゼロ桁を保持し、それより高位の全桁を除去する。これによりコスト1を達成可能。
実装例
#include <cstdio>
#include <cstring>
int main() {
int cases;
scanf("%d", &cases);
while (cases--) {
char digits[200];
scanf("%s", digits);
int length = strlen(digits);
int trailing_zeros = 0;
bool non_zero_found = false;
for (int i = length - 1; i >= 0; i--) {
non_zero_found |= (digits[i] != '0');
trailing_zeros += (non_zero_found && digits[i] == '0');
}
printf("%d\n", length - trailing_zeros - 1);
}
return 0;
}素数生成の単純な反復
数字xをk回繰り返して生成された数yが素数か判定せよ（例: x=52, k=3 → y=525252）。
解法: k>1かつx≠1の場合、yは合成数。x=1かつk=2の場合のみ素数（y=11）。
実装例
#include <iostream>
using namespace std;
bool is_prime(long num) {
if (num <= 1) return false;
for (long i = 2; i * i <= num; i++)
if (num % i == 0) return false;
return true;
}
int main() {
int tests;
cin >> tests;
while (tests--) {
long base;
int repetitions;
cin >> base >> repetitions;
if (base == 1 && repetitions == 2) {
cout << "YES\n";
} else if (repetitions > 1) {
cout << "NO\n";
} else {
cout << (is_prime(base) ? "YES" : "NO") << "\n";
}
}
return 0;
}再帰的なテーブル埋め
2n×2nテーブルを再帰的に4分割し、特定順序で1から22nまで埋める。クエリに応じて座標→値または値→座標を回答。
解法: 再帰的に領域を4分割し、各領域のオフセットとサイズを管理。値計算には累積加算を、座標計算には再帰探索を適用。
実装例
#include <cstdio>
typedef long long ll;
void locate_value(ll value, int &row, int &col, int size) {
if (!size) return;
ll segment = (ll)size * size;
if (value < segment) {
locate_value(value, row, col, size >> 1);
} else if (value < 2 * segment) {
value -= segment;
row += size;
col += size;
locate_value(value, row, col, size >> 1);
} else if (value < 3 * segment) {
value -= 2 * segment;
row += size;
locate_value(value, row, col, size >> 1);
} else {
value -= 3 * segment;
col += size;
locate_value(value, row, col, size >> 1);
}
}
ll compute_value(ll row, ll col, ll start_r, ll start_c, ll size) {
if (!size) return 0;
ll end_r = start_r + size, end_c = start_c + size;
if (row < end_r && col < end_c) {
return compute_value(row, col, start_r, start_c, size >> 1);
} else if (row >= end_r && col >= end_c) {
return size * size + compute_value(row, col, end_r, end_c, size >> 1);
} else if (row >= end_r) {
return 2 * size * size + compute_value(row, col, end_r, start_c, size >> 1);
}
return 3 * size * size + compute_value(row, col, start_r, end_c, size >> 1);
}
int main() {
int tests;
scanf("%d", &tests);
while (tests--) {
int dim, queries;
scanf("%d %d", &dim, &queries);
ll grid_size = 1LL << (dim - 1);
while (queries--) {
char op;
scanf(" %c", &op);
if (op == '?') {
ll x, y;
scanf("%lld %lld", &x, &y);
x--; y--;
printf("%lld\n", compute_value(x, y, 0, 0, grid_size) + 1);
} else {
ll num;
scanf("%lld", &num);
int r = 0, c = 0;
locate_value(num - 1, r, c, grid_size);
printf("%d %d\n", r + 1, c + 1);
}
}
}
return 0;
}サブアレイ分割とMEX最大化
配列をk個の連続サブアレイに分割し、各サブアレイのMEX（最小非負整数）の最小値を最大化せよ。
解法: 二分探索で目標MEX値を設定。達成可能かは貪欲法で検証：左からサブアレイを形成し、MEXが目標値以上なら分割。
実装例
#include <iostream>
#include <vector>
using namespace std;
bool can_achieve(vector<int> &data, int segments, int target) {
vector<bool> exists(target + 2, false);
int current = 0, count = 0;
for (int i = 0; i < data.size(); i++) {
if (data[i] <= target && !exists[data[i]]) {
exists[data[i]] = true;
if (++current == target) {
current = 0;
count++;
fill(exists.begin(), exists.end(), false);
}
}
}
return count >= segments;
}
int main() {
int tests;
cin >> tests;
while (tests--) {
int n, k;
cin >> n >> k;
vector<int> arr(n);
for (int i = 0; i < n; i++) cin >> arr[i];
int low = 0, high = n;
while (low < high) {
int mid = (low + high + 1) >> 1;
if (can_achieve(arr, k, mid)) low = mid;
else high = mid - 1;
}
cout << high << endl;
}
return 0;
}文字列配列変換の最小操作
空白配列を目標配列aに変換する最小操作数を求めよ。操作：ニューラルネットワークiを選択し、空白位置にbi,jを挿入、または任意位置を空白に戻す。
解法: 各位置でajと一致するbi,jが存在必須。最適戦略：aと最も一致するbiを選択後、不一致位置を個別修正。
実装例
#include <iostream>
#include <vector>
using namespace std;
int main() {
int tests;
cin >> tests;
while (tests--) {
int len, nets;
cin >> len >> nets;
vector<string> target(len);
vector<vector<string>> neural_outs(nets, vector<string>(len));
vector<bool> feasible(len, false);
for (int i = 0; i < len; i++) cin >> target[i];
for (int i = 0; i < nets; i++) {
for (int j = 0; j < len; j++) {
cin >> neural_outs[i][j];
feasible[j] = feasible[j] || (neural_outs[i][j] == target[j]);
}
}
for (int i = 0; i < len; i++) {
if (!feasible[i]) {
cout << "-1\n";
goto next_test;
}
}
int max_match = 0;
for (int i = 0; i < nets; i++) {
int matches = 0;
for (int j = 0; j < len; j++)
matches += (neural_outs[i][j] == target[j]);
max_match = max(max_match, matches);
}
cout << 3 * len - 2 * max_match << endl;
next_test:;
}
return 0;
}美しいサブアレイの最短長
配列からXOR美麗値（任意要素対のXOR最大値）がk以上となる最短サブアレイの長さを求めよ。
解法: 各要素を右端とするサブアレイで、美麗値k以上を達成する最左端を二分探索。永続トライ木で効率的にXOR最大値計算。
実装例
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
struct PersistentTrie {
struct Node {
int ch[2] = {0, 0};
int cnt = 0;
};
vector<Node> nodes;
vector<int> roots;
int ncnt = 1;
void init() {
nodes.resize(1);
roots.push_back(0);
}
void insert(int val) {
roots.push_back(ncnt++);
nodes.resize(ncnt);
int cur = roots.back(), prev = roots[roots.size()-2];
for (int i = 30; i >= 0; i--) {
int bit = (val >> i) & 1;
nodes[cur].ch[!bit] = nodes[prev].ch[!bit];
nodes[cur].ch[bit] = ncnt++;
nodes.resize(ncnt);
cur = nodes[cur].ch[bit];
prev = nodes[prev].ch[bit];
nodes[cur].cnt = nodes[prev].cnt + 1;
}
}
int max_xor(int l, int r, int val) {
int res = 0, left = roots[l], right = roots[r];
for (int i = 30; i >= 0; i--) {
int bit = (val >> i) & 1;
if (nodes[nodes[right].ch[!bit]].cnt - nodes[nodes[left].ch[!bit]].cnt > 0) {
res |= (1 << i);
left = nodes[left].ch[!bit];
right = nodes[right].ch[!bit];
} else {
left = nodes[left].ch[bit];
right = nodes[right].ch[bit];
}
}
return res;
}
};
int main() {
int tests;
scanf("%d", &tests);
while (tests--) {
int n, k;
scanf("%d %d", &n, &k);
vector<int> arr(n);
for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
if (k == 0) {
printf("1\n");
continue;
}
PersistentTrie trie;
trie.init();
trie.insert(0);
for (int num : arr) trie.insert(num);
int ans = INT_MAX;
for (int r = 1; r < n; r++) {
int l = 0, pos = r;
while (l <= r) {
int mid = (l + r) / 2;
if (trie.max_xor(mid, r + 1, arr[r]) >= k) {
ans = min(ans, r - mid + 1);
l = mid + 1;
} else {
r = mid - 1;
}
}
}
printf("%d\n", ans == INT_MAX ? -1 : ans);
}
return 0;
}