Codeforces Round #194 (Div. 1)
茶会。Cは飛ばしたがDが解けたので嬉しい。
A. Secrets
問題文が難しかった。それを理解したのは開始30分後であった。中身は簡単。
問題
$3^n (n \ge 0)$円硬貨のみを持つ国での話。 硬貨の組で、合計額は$n$円より大きいが、$n$円ちょうどを払うことはできないような組がある。 そのような硬貨の組で、合計金額の最小の額の組は、最大何枚の硬貨であるか。
例えば10円に対しては、条件を満たし金額が最小で枚数が最大の組は3円硬貨4枚であり、答は4。
解答
#!/usr/bin/env python3
n = int(input())
while n % 3 == 0:
n = n // 3
print(n // 3 + 1)
B. Chips
解けた。実質的に無視できる制約の多い問題だった。
- 上下左右に動けるが、$n-1$回しか移動できないので、辺から辺へ一直線に移動すると考えてよい。
- 行と列を選び向きを定める問題、と再解釈できる。
- 駒が衝突してはいけないが、全ての駒が盤の中心を軸に時計周り/反時計周りに移動すれば、ちょうど中央の駒を除いて、衝突することはない。
#include <iostream>
#include <set>
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
#define repeat(i,n) repeat_from(i,0,n)
using namespace std;
int main() {
int n, m; cin >> n >> m;
set<int> xs, ys;
repeat (i,m) {
int x, y; cin >> x >> y;
xs.insert(x);
ys.insert(y);
}
xs.insert(1); xs.insert(n);
ys.insert(1); ys.insert(n);
int x = n - xs.size();
int y = n - ys.size();
int p = 0; if (n % 2 == 1 and not xs.count(n/2+1) and not ys.count(n/2+1)) p = -1;
cout << x + y + p << endl;
return 0;
}
D. Characteristics of Rectangles
解けた。$n \le 1000$だったので書いてみた愚直な$O(n^3)$を高速化したら通ってしまった。 editorial曰く、想定解法は$O(n^2 \log n)$。
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cassert>
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
#define repeat(i,n) repeat_from(i,0,n)
using namespace std;
int main() {
int h, w; scanf("%d%d", &h, &w);
vector<vector<int> > a(h, vector<int>(w));
repeat (y,h) repeat (x,w) scanf("%d", &a[y][x]);
vector<int> snd(h);
repeat (y,h) {
vector<int> b = a[y];
sort(b.rbegin(), b.rend());
snd[y] = b[1];
}
int result = 0;
repeat (y1,h) {
if (snd[y1] <= result) continue;
repeat_from (y2,y1+1,h) {
if (snd[y2] <= result) continue;
int z[2] = {};
repeat (x,w) {
int v = min(a[y1][x], a[y2][x]);
if (z[0] < v) {
z[0] = v; // z[0] = max(z[0], v);
if (z[0] > z[1]) swap(z[0], z[1]); // sort(z, z+2);
}
}
if (result < z[0]) result = z[0]; // result = max(result, z[0]);
}
}
printf("%d\n", result);
return 0;
}
今回に限らず一般のテストケースでもcolumn -t
使うといいのではと気付いた