A. Image Scaling
簡単な問題。矩形の幅と高さを求め、それらの最大公約数で割って互いに素にするだけ。
コードを表示
#include <cstdio>
#include <cstring>
int n, m, x1, y1, x2, y2;
char grid[505][505];
int gcd(int a, int b) {
while (b) {
int t = b;
b = a % b;
a = t;
}
return a;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
scanf("%s", grid[i] + 1);
// 最初の 'x' を探す
for (int i = 1; i <= n && !x1; ++i)
for (int j = 1; j <= m; ++j)
if (grid[i][j] == 'x') { x1 = i; y1 = j; break; }
// 最後の 'x' を探す
for (int i = n; i >= 1 && !x2; --i)
for (int j = m; j >= 1; --j)
if (grid[i][j] == 'x') { x2 = i; y2 = j; break; }
int h = x2 - x1 + 1, w = y2 - y1 + 1;
int d = gcd(w, h);
w /= d; h /= d;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j)
putchar('x');
putchar('\n');
}
return 0;
}
B. Break Sequence
面白い問題のため、別途詳細な解説記事を書きました（コメント付き）。こちらを参照。
I. Interesting Numbers
問題：数値を中央で二つに分割したとき、両方の数が平方数であるような数を [L, R] の中で数えよ。
コンテスト中は問題を読み間違えて積や和だと思っていました。累積和の考え方を使えば、f(x) = [1, x] 内の条件を満たす個数として、f(R) - f(L-1) で求められます。
数値は偶数桁 N 桁とし、左右の半分は独立なので別々に考えます。右端 R の左右を R1, R2、現在の数を X としてその左右を X1, X2 とします。分割後は最大30桁なので __int128 で扱えます（最大38桁）。
場合1：X1 < R1 のとき、X2 は自由に取れる：
- X1：⌊√(R1-1)⌋ + 1 通り（0を含むため+1）
- X2：⌊√(10^{N/2} - 1)⌋ + 1 通り
従って (⌊√(R1-1)⌋ + 1) * (⌊√(10^{N/2} - 1)⌋ + 1) 通り。
場合2：X1 = R1 のとき（R1が平方数でなければ該当なし）：
- X1 は1通り
- X2 は ⌊√R2⌋ + 1 通り
合計 ⌊√R2⌋ + 1 通り。
これらを足して f(R) を得ます。f(L-1) も同様に、L1 はそのまま、L2 を1減らしてから計算します（L2=0の特別処理に注意）。
コードを表示
#include <cstdio>
int n;
char L[105], R[105];
__int128 isqrt(__int128 x) {
if (x < 0) return -1;
__int128 lo = 0, hi = 1e15 + 1;
while (lo + 1 < hi) {
__int128 mid = (lo + hi) >> 1;
if (mid * mid <= x) lo = mid;
else hi = mid;
}
return lo;
}
__int128 pow10(int e) {
__int128 res = 1;
for (int i = 0; i < e; ++i) res *= 10;
return res;
}
__int128 count_up_to(int n, __int128 r1, __int128 r2) {
__int128 half = n >> 1;
__int128 max_r2 = pow10(half) - 1;
__int128 ways = (isqrt(r1 - 1) + 1) * (isqrt(max_r2) + 1);
ways += (isqrt(r1) - isqrt(r1 - 1)) * (isqrt(r2) + 1);
return ways;
}
void print128(__int128 x) {
if (x) {
char buf[40];
int len = 0;
while (x) { buf[len++] = '0' + (x % 10); x /= 10; }
for (int i = len - 1; i >= 0; --i) putchar(buf[i]);
} else putchar('0');
}
int main() {
scanf("%d%s%s", &n, L + 1, R + 1);
__int128 l1 = 0, l2 = 0, r1 = 0, r2 = 0;
int half = n >> 1;
for (int i = 1; i <= half; ++i) {
l1 = l1 * 10 + (L[i] - '0');
r1 = r1 * 10 + (R[i] - '0');
}
for (int i = half + 1; i <= n; ++i) {
l2 = l2 * 10 + (L[i] - '0');
r2 = r2 * 10 + (R[i] - '0');
}
__int128 ans = count_up_to(n, r1, r2) - count_up_to(n, l1, l2 - 1);
print128(ans);
putchar('\n');
return 0;
}
K. Kill The Monsters
貪欲法。毎回最大の値に対して操作2（kで割る）を適用し、操作1の回数はその時点での最大値と等しくなる。優先度付きキューで最大値を取り出しながらシミュレートし、各時点での 現在の最大値 + 既に行った操作の回数 の最小値を取る。ただし、全てを操作2だけで済ませられる場合も考慮し、最終的な操作回数 alr でも答えを更新する。
操作1回で値を1/kにするため、全体の計算量は O(N logk max ai)。k=1の場合は操作2が不可能なので、そのまま最大値を出力。
コードを表示
#include <cstdio>
#include <queue>
#include <algorithm>
int n;
long long k, a[100005];
std::priority_queue<long long> pq;
int main() {
scanf("%d%lld", &n, &k);
for (int i = 0; i < n; ++i) {
scanf("%lld", &a[i]);
pq.push(a[i]);
}
if (k == 1) {
printf("%lld\n", pq.top());
return 0;
}
long long ans = 1e18, cnt = 0;
while (!pq.empty()) {
long long cur = pq.top(); pq.pop();
ans = std::min(ans, cur + cnt);
cur /= k;
if (cur > 0) pq.push(cur);
++cnt;
}
ans = std::min(ans, cnt);
printf("%lld\n", ans);
return 0;
}