A - Baloon Trip
問題要約
$W[kg] < nB[g]$となるような最小のnを求めよ。
解法
nを全探索する。
$1 \leq W \leq 100$の制約から、$B=1$のケースでもnは$10001$を超えることがないとわかるため、計算が間に合う。
コード例
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
int main() {
int W, B;
cin >> W >> B;
rep(n, 1e9) {
if (n * B > W * 1000) {
cout << n << endl;
return 0;
}
}
}
B - Bird Watching
問題要約
数列$A$、$B$が与えられる。( $|A| = |B| = N$)
すべての$k = 1, 2, .., M$について、$A_i = k$である$i$について$B_i$の平均値を求めよ。
解法
$A_i=j$である要素についての総和$sum[j]$と個数のカウント$counts[j]$を作り、最後に平均値を計算して出力する。
ちなみに全探索の$O(NM)$でも間に合う。
コード例
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(ll i=0;i<(n);i++)
int main() {
ll N, M;
cin >> N >> M;
vector<ll> counts(M, 0);
vector<ll> sum(M, 0);
rep(i, N) {
ll A, B;
cin >> A >> B;
--A; // 0-indexedに変換
counts[A]++;
sum[A] += B;
}
rep(i, M) {
// 整数値同士の演算だと小数点以下が切り捨てられてしまうのでdoubleにシフトしてから計算する
cout << double(sum[i]) / double(counts[i]) << endl;
}
}
C - Flapping Takahashi
問題要約
１秒あたり座標を$-1 \leq ∆x \leq 1$の範囲で変化させられる。$N$個の条件: 「時刻$t_i$において$l_i \leq x \leq u_i$を達成する」をすべて満たす方法はあるか判定せよ。
解法
まず、目標を時間の順にソートする。
そして、次の目標を達成し、かつ、そこにいることが達成可能な座標の範囲を毎回計算し、範囲を満たす値がなくなったらNoと判定し、そうでなければ最後にYes。
コード例
マルチテストケースを楽に処理するために、solve関数を導入した。
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(ll i=0; i<(n); i++)
void solve() {
ll N, H;
cin >> N >> H;
vl t(N), l(N), u(N);
rep(i, N) cin >> t[i] >> l[i] >> u[i];
ll ok_highest = H;
ll ok_lowest = H;
rep(i, N) {
ok_highest = ok_highest + t[i] - (i == 0 ? 0 : t[i-1]);
ok_lowest = max(0ll, ok_lowest - (t[i] - (i == 0 ? 0 : t[i-1])));
// 目標を達成できるか
if (ok_highest < l[i] || ok_lowest > u[i]) {
cout << "No" << endl;
return;
}
// 目標の範囲と重なる部分にする
ok_highest = min(ok_highest, u[i]);
ok_lowest = max(ok_lowest, l[i]);
}
cout << "Yes" << endl;
}
int main() {
ll T;
cin >> T;
while (T--) { // T回だけ繰り返す
solve();
}
}
D - Clouds
問題要約
2000x2000のグリッドにおいて、矩形範囲が$N$個ある。各$k=1,2,...,N$について、矩形範囲$k$のみを取り除いた状態でどの矩形範囲にも覆われていないマスの数を数えよ。
解法
H,Wをそれぞれグリッドの縦方向の数、横方向の数とする。
まず、各マス目においていくつの範囲が重なっているかを数える。これは2次元imos法によって$O(N+HW)$で求められる。
次に、どの範囲にも覆われていないマスの数を数える。これは$O(HW)$である。
そして、範囲が1つのみ重なっているマス目の数を二次元累積和で計算しておく。これも$O(HW)$である。
最後に、各矩形範囲について、その範囲に含まれる「範囲が1つのみ重なっているマス目の数」+「どの範囲にも覆われていないマスの数」を答える。これは以前に構築したテーブルを活用することで合計$O(N)$で求められる。
解法が成り立つ理由
各矩形範囲に含まれる「範囲が1つのみ重なっているマス目」は、必ずその矩形範囲のみが重なっているため、その矩形範囲を取り除くと必ずどの範囲にも覆われていない状態になるし、その矩形範囲以外を取り除いてもその矩形範囲に覆われたままの状態であるから。
コード例
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(ll i=0; i<(n); i++)
#define vc vector
int main() {
vc<vc<ll>> cs(2000, vc<ll>(2000, 0)); // imos
ll N;
cin >> N;
vc<tuple<ll,ll,ll,ll>> clouds(N);
rep(i, N) cin >> get<0>(clouds[i]) >> get<1>(clouds[i]) >> get<2>(clouds[i]) >> get<3>(clouds[i]);
rep(i, N) {
--get<0>(clouds[i]);
--get<1>(clouds[i]);
--get<2>(clouds[i]);
--get<3>(clouds[i]);
}
// 2次元imos法: 登録
rep(i, N) {
auto [u, d, l, r] = clouds[i];
++cs[u][l];
if (d+1 < 2000) --cs[d+1][l];
if (r+1 < 2000) --cs[u][r+1];
if (d+1 < 2000 && r+1 < 2000) ++cs[d+1][r+1];
}
// 2次元imos法: 累積和の計算
rep(i, 2000) {
rep(j, 2000-1) {
cs[i][j+1] += cs[i][j];
}
}
rep(j, 2000) {
rep(i, 2000-1) {
cs[i+1][j] += cs[i][j];
}
}
ll zero_count = 0; // 範囲が0個のマス目の数
vc<vc<ll>> one_counts(2000, vc<ll>(2000, 0)); // 範囲が1個のマス目の累積和
rep(i, 2000) {
rep(j, 2000) {
if (cs[i][j] == 0) ++zero_count;
if (cs[i][j] == 1) ++one_counts[i][j];
}
}
// 累積和を取る
rep(i, 2000) {
rep(j, 2000-1) {
one_counts[i][j+1] += one_counts[i][j];
}
}
rep(j, 2000) {
rep(i, 2000-1) {
one_counts[i+1][j] += one_counts[i][j];
}
}
// 答える
rep(i, N) {
auto [u, d, l, r] = clouds[i];
ll now_one_cnt = one_counts[d][r];
if (u > 0) now_one_cnt -= one_counts[u-1][r];
if (l > 0) now_one_cnt -= one_counts[d][l-1];
if (u > 0 && l > 0) now_one_cnt += one_counts[u-1][l-1];
cout << now_one_cnt + zero_count << endl;
}
}