A - Humidifier 1
O(N)
シミュレートします。
追加する水Vi
経過時間をT[i] - T[i-1]
加湿器の水は0未満にならないので
ans = V[i] + max(0, ans - (T[i] - T[i-1]));
となります。
C++
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
int main() {
int N;
cin >> N;
vector<int> T(N), V(N);
rep(i, N) cin >> T[i] >> V[i];
int ans = V[0];
repx(i, 1, N){
ans = V[i] + max(0, ans - (T[i] - T[i-1]));
}
cout << ans << endl;
return 0;
}
B - Humidifier 2
O(HW * HW * HW)
全探索です。
値が小さいのでO(N^3)でも間に合います。
- 加湿器を置く2マスを全探索します
- 1のループ内で、加湿器を置く2マスと他のマスの距離を探索します
- 2で探索したマスの距離がD以下ならカウントを加算します
- 3の最大値が答えになります
C++
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
int main() {
int H, W, D;
cin >> H >> W >> D;
string S[10];
rep(i, H) cin >> S[i];
int ans = 0;
rep(y1, H) rep(x1, W){
if(S[y1][x1] == '#') continue;
rep(y2, H) rep(x2, W){
if(S[y2][x2] == '#') continue;
if(y1==y2 && x1==x2) continue;
int cnt=0;
rep(i, H) rep(j, W){
if(S[i][j] == '#') continue;
bool ok = false;
if(abs(y1 - i) + abs(x1 - j) <= D) ok=true;
if(abs(y2 - i) + abs(x2 - j) <= D) ok=true;
if(ok) cnt++;
}
ans = max(ans, cnt);
}
}
cout << ans << endl;
return 0;
}
C - Humidifier 3
O(HW)
bfsです。
通常のbfsを異なるのは多始点bfsと呼ばれる、始点が複数あるタイプのbfsです。
最初にHのある座標をqueueに全て格納します。
Hからの距離を探索して答えを出します。
C++
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
int main() {
int H, W, D;
cin >> H >> W >> D;
vector<string> S(H);
rep(i, H) cin >> S[i];
const int INF = 100100100;
vector<vector<int>> dist(H, vector<int>(W, INF));
queue<P> que;
rep(y, H) rep(x, W){
if(S[y][x] == 'H'){
dist[y][x] = 0;
que.push({x, y});
}
}
while(que.size()){
auto [x, y] = que.front();
que.pop();
for(int i=0; i<4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx<0 || W<=nx || ny<0 || H<=ny) continue;
if(S[ny][nx] == '#') continue;
if(dist[ny][nx] != INF) continue;
dist[ny][nx] = dist[y][x] + 1;
que.push({nx, ny});
}
}
int ans = 0;
rep(y, H) rep(x, W) if(dist[y][x] <= D) ans++;
cout << ans << endl;
return 0;
}
D - 9 Divisors
O(N)
エラトステネスの篩の問題です。
「正の約数をちょうど9個持つものの個数」を求めます。
正の約数の数の求め方を考えます。
高校数学Aの単元です。
120を素因数分解すると、
2^3 * 3^1 * 5^1
それぞれの因数に1を加算した値の積が120の約数の数になります。
4 * 2 * 2 = 16
16個であっていますね。
次に約数が9個の場合を変数で考えましょう。
p, qを素数とした時に、
p ^ 2 * q ^ 2の時、((2 + 1) * (2 + 1) = 9)
p ^ 8の時、(8 + 1 = 9)
素数をエラトステネスの篩で求めます。
2 * 2 * 10^6 * 10^6
のパターンを考慮し、エラトステネスの篩で使用する配列は10^6ほど必要です。
求めた素数を使用して、
p ^ 2 * q ^ 2 <= N
p ^ 8 <= N
を判定して探索すると、答えを求めることができます。
C++
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
int main() {
ll N;
cin >> N;
ll INF = 1001001;
bool isPrime[INF];
for(int i=0; i<INF; i++) isPrime[i] = true;
for(ll i=2; i*i<INF; i++){
if(isPrime[i] == false) continue;
for(ll j=i; j*i<INF; j++){
isPrime[j*i] = false;
}
}
vector<ll> primes;
for(int i=2; i<INF; i++){
if(isPrime[i]) primes.push_back(i);
}
ll cnt = 0;
for(auto p1:primes){
for(auto p2:primes){
if(p1 <= p2) break;
if(p1 * p1 * p2 * p2 > N) break;
//cout << p1 * p1 * p2 * p2 << endl;
cnt++;
}
}
for(auto p:primes){
ll x = 1;
rep(i, 8) x *= p;
if(x > N) break;
//cout << x << endl;
cnt++;
}
cout << cnt << endl;
return 0;
}