A - ABC400 Party
O(1)
数学の問題です。
A * B = 400
が成立しているか確認します。
この問題ではAが与えられるのでBと余りを求めます。
B = 400 / A
400 / A = x 余り 0
考察が終わりました。
C++
#include <bits/stdc++.h>
#include <atcoder/all>
#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
using namespace std;
using ll = long long;
using P = pair<int,int>;
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 A;
cin >> A;
if(400 % A == 0){
cout << 400 / A << endl;
}else{
cout << -1 << endl;
}
return 0;
}
B - Sum of Geometric Series
O(M*M!)
i=0からMの回数だけループをします。
ansにN^iを加算していきます。
N＝2、M＝５の時、
2^0 = 1
2^1 = 2
2^2 = 4
2^3 = 8
2^4 = 16
2^5 = 32
合計は、
1 + 2 + 4 + 8 + 16 + 32 = 63
int型だとオーバーフローを起こします。
ループ内で最初に10^9を超えるタイミングで、終了処理をします。
全ての計算が終わった後だと、オーバーフローしていてif文の分岐処理が上手くいかないからです。
C++
#include <bits/stdc++.h>
#include <atcoder/all>
#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
using namespace std;
using ll = long long;
using P = pair<int,int>;
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, M;
cin >> N >> M;
const ll inf = 1e9;
ll ans = 0;
for(ll i=0; i<=M; i++){
ll x = 1;
for(int j=0; j<i; j++) x *= N;
ans += x;
if(ans > inf){
cout << "inf" << endl;
return 0;
}
}
cout << ans << endl;
return 0;
}
C - 2^a b^2
AtCoderの公式の解説の手法だと、計算量はO(1)になります。
私が理解できた手法の計算量は、O(60^2)です。
数学の問題です。
計算式を理解することが大事です。
2^a * b^2 <= N
である整数(a, b)の組み合わせの数を求める。
N=10^18の時、2^aだけを見て10^18以下になるパターンは、2^0から2^60までである。
これはlong long型が64bitであることから考察できます。
x = N / 2 ^ a
b = \sqrt{x}
の時、1からbまでの値を撮ります。
次は値が重複するパターンを考えましょう。
a = 2
b = 2
2 ^ a * b ^ 2 = 2 * 2 * 2 * 2
a=4、b=1の時と重複しています。
a = 2
b = 6
2 ^ a * b ^ 2 = 2 * 2 * 6 * 6 = 2 * 2 * 2 * 3 * 2 * 3
a=4、b=3の時と重複しています。
a = 2
b = 5
2 ^ a * b ^ 2 = 2 * 2 * 5 * 5
重複するパターンが存在しません。
約数を見ていくと分かりますが、bが奇数の時だけ探索すると答えになります。
C++
#include <bits/stdc++.h>
#include <atcoder/all>
#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
using namespace std;
using ll = long long;
using P = pair<int,int>;
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 ans = 0;
for(ll a=1; a<61; a++){
ll x = N;
for(int i=0; i<a; i++) x /= 2;
ll b = sqrtl(x);
ans += (b + 1) / 2;
}
cout << ans << endl;
return 0;
}
D - Takahashi the Wall Breaker
O(HW)
01BFSの問題です。
ゴールまでの最短経路ではなく、ゴールまでの壁を破壊した最小の数を求めます。
最短経路だとpush_frontができないです。
壁を壊さなくて良い経路を優先的に処理したいので、push_frontで格納します。
壁を壊した経路を後で処理したいので、push_backで格納します。
壁を破壊した数を2次元配列distに格納します。
.の時に、
dist[yy][xx] = dist[y][x]
#の時に、
dist[yy][xx] = dist[y][x] + 1
を行います。
考察が終わりました。
C++
#include <bits/stdc++.h>
#include <atcoder/all>
#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
using namespace std;
using ll = long long;
using P = pair<int,int>;
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 dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
void solive(int H, int W, vector<string>& S, int A, int B, int C, int D){
A--; B--; C--; D--;
deque<pair<int, int>> deq;
deq.emplace_back(A, B);
vector<vector<int>> dist(H, vector<int>(W, 1e9));
dist[A][B] = 0;
vector<vector<bool>> used(H, vector<bool>(W, false));
while(deq.size()){
auto [y, x] = deq.front();
deq.pop_front();
if(used[y][x]) continue;
used[y][x] = true;
for(int i=0; i<4; i++){
int xx = x + dx[i];
int yy = y + dy[i];
if(xx<0 || W<=xx || yy<0 || H<=yy) continue;
if(dist[yy][xx] <= dist[y][x]) continue;
if(S[yy][xx] == '.'){
dist[yy][xx] = dist[y][x];
deq.emplace_front(yy, xx);
}
}
for(int i=0; i<4; i++){
int xx = x;
int yy = y;
for(int j=0; j<2; j++){
xx = xx + dx[i];
yy = yy + dy[i];
if(xx<0 || W<=xx || yy<0 || H<=yy) continue;
if(dist[yy][xx] <= dist[y][x]) continue;
dist[yy][xx] = dist[y][x]+1;
deq.emplace_back(yy, xx);
}
}
}
cout << dist[C][D] << endl;
}
int main() {
int H, W;
cin >> H >> W;
vector<string> S(H);
rep(i, H) cin >> S[i];
int A, B, C, D;
cin >> A >> B >> C >> D;
solive(H, W, S, A, B, C, D);
return 0;
}