「添え字を分かりやすく」を心に誓った男の備忘録です
コンテスト概要
AtCoder Beginner Contest 400
開催日:2025年4月5日 21:00-22:40
A - ABC400 Party
考察
400祭りだね。
Aが400で割り切れなければ-１。そうでなければ$N/A$が答え。
シンプルでうれしい。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
if(400%n == 0) cout << 400/n << endl;
else cout << "-1" << endl;
}
B - Sum of Geometric Series
考察
数がデカくてオーバーフローが怖い問題。
こういうのは等比数列の公式を使うことが多いが、数がデカすぎるので愚直にやる。
$N^0,N^1,N^2...N^{M-1},N^M$を順番に足していく。で、$10^9$を越えたら打ち切る。
シンプルな問題だが添え字をミスって２ペナ。
添え字わかりやすく。これ大事。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
ll n,m;
cin >> n >> m;
ll lim = 1000000000LL;
ll sum = 1,now = n;
for(ll i=1;i<=m;i++){
if(now > lim){
cout << "inf" << endl;
return 0;
}
sum += now;
if(sum > lim){
cout << "inf" << endl;
return 0;
}
now *= n;
}
cout << sum << endl;
}
C - 2^a b^2
考察
400祭じゃなくて数学祭じゃないか！
1個ずつやると間違いなくTLEしそう。なので計算で何とか個数を求めたい。
まずは基本的な方針を考える。
とりあえず$2^a$を固定する。この時$b^2$は$N/{2^a}$以下である必要がある。なので$b^2$の個数は$\sqrt{N/{2^a}}$個。
これをN以下の$2^a$で行うと...ちょっと多いみたい。
というのも例えば$2^1\times6^2$と$2^3\times3^2$は両方72である。にもかかわらずそれぞれ別の数としてカウントをしてしまっている。
要するにbに2の素因数を持っているとカウントが重複してしまう。だったらbは奇数のみカウントすればよい。
$b^2$の個数を$\sqrt{N/{2^a}}/2$個にすれば万事解決。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// n以下の平方数の個数を返す関数
ll num(ll n){
ll h = 0,t = (1<<30);
while(h != t){
ll c = (h+t)/2LL;
if(c*c > n) t = c;
else h = c+1LL;
}
return t-1LL;
}
int main(){
ll n;
cin >> n;
ll ans = 0,now = 2LL;
while(true){
// N/(2^i)以下の"奇数の"平方数の数
ll c = (num(n/now)+1)/2LL;
//もう平方数がないならおしまい。
if(c==0) break;
ans += c;
now <<= 1;
}
cout << ans << endl;
}
D - Takahashi the Wall Breaker
考察
毛色違いすぎるって。ウナギ？前蹴り？
ややこしそうだがBFSを適切に使えばOKな問題。
全てのマスにおいてそこに行くまでに必要な前蹴りの回数を考える。
今いるマスの前蹴り回数をKとしたとき。行くべきマスが道なら回数はK。壁ならK＋１とする。壁の時さらに1マス進めるのでそこの回数もK＋１とする。
こんな感じで優先度付きキューを使ってBFSすれば終了。
なんか一番解きやすかったかも。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<typename T> using p_que = priority_queue<T,vector<T>,greater<T>>;
int main(){
int h,w;
cin >> h >> w;
vector<vector<char>>mp (h,vector<char>(w));
for(int i=0;i<h;i++){
for(int j=0;j<w;j++) cin >> mp[i][j];
}
int sx,sy,gx,gy;
cin >> sx >> sy >> gx >> gy;
sx--,sy--,gx--,gy--;
int lim = 1e9;
//cnt[x][y] = (x,y)に行くまでに必要な前蹴り回数。とりあえずデカい値で初期化
vector<vector<int>>cnt (h,vector<int>(w,lim));
//当然スタート地点の回数は０。
cnt[sx][sy] = 0;
p_que<pair<int,int>>que;
//少し横着して座標を1つの整数で表しておく
que.push({0,sx*10000+sy});
while(!que.empty()){
auto [cst,now] = que.top();
int x = now/10000,y = now%10000;
que.pop();
///すでに別の値に更新されていたら飛ばす
if(cst > cnt[x][y]) continue;
for(int i=-1;i<2;i+=2){
if(x+i<h && x+i>-1){
if(mp[x+i][y] == '#'){
//一歩先が壁の時
if(cnt[x+i][y] > cnt[x][y] + 1){
//より少ない回数なら更新
cnt[x+i][y] = cnt[x][y] + 1;
que.push({cnt[x+i][y],(x+i)*10000+y});
}
if(x+i+i<h && x+i+i>-1){
//もう1マス先も見ておく
if(cnt[x+i+i][y] > cst + 1){
cnt[x+i+i][y] = cst + 1;
que.push({cnt[x+i+i][y],(x+i+i)*10000+y});
}
}
}else{
//壁じゃないなら回数は増やさない
if(cnt[x+i][y] > cst){
cnt[x+i][y] = cst;
que.push({cst,(x+i)*10000+y});
}
}
}
//横方向でも同じことをする
if(y+i<w && y+i>-1){
if(mp[x][y+i] == '#'){
if(cnt[x][y+i] > cst + 1){
cnt[x][y+i] = cst + 1;
que.push({cst+1,x*10000+y+i});
}
if(y+i+i < w && y+i+i > -1){
if(cnt[x][y+i+i] > cst + 1){
cnt[x][y+i+i] = cst + 1;
que.push({cst+1,x*10000+y+i+i});
}
}
}else{
if(cnt[x][y+i] > cst){
cnt[x][y+i] = cst;
que.push({cst,x*10000+y+i});
}
}
}
}
}
//ゴールの値を出力
cout << cnt[gx][gy] << endl;
}
E - Ringo's Favorite Numbers 3
考察
また数学じゃないか！
なんとなくの直感で当てはまる数字は多くなさそう。なので当てはまる数を全部列挙できればあとはウイニングランっぽい。
条件より$(a^i\times b^j)^2\leqq10^{12}\Leftrightarrow a^i\times b^j\leqq10^{6}$なので個数も$10^6$以下で間違いなさそう。
$10^6$以下の素数を高速に列挙しa,bに順に代入すれば全列挙可能。当てはまる数字はsetに突っ込んでおく。あとはlower_boundを使えば値は簡単に出てくる。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int>pri;
//素数を高速に列挙
void rpp(){
pri.resize(0);
vector<bool>num (1e6,false);
for(int i=2;i<1e6;i++){
if(num[i])continue;
pri.push_back(i);
for(int j=2;i*j<1e6;j++) num[i*j]= true;
}
return;
}
int main(){
rpp();
set<ll>st;
int siz = pri.size();
//素数を順にaに当てはめる
for(int i=0;i<siz;i++){
ll now = pri[i];
while(now <= 1e6){
//素数を順にbに当てはめる
for(int j=i+1;j<siz;j++){
ll c = pri[j];
//10^6を超えたら打ち切り
if(now*c > 1e6) break;
while(now*c <= 1e6){
//現在の値を2乗したものが欲しい
st.insert(now*now*c*c);
//指数を1つ増やす
c *= pri[j];
}
}
//指数を一つ増やす
now *= pri[i];
}
}
st.insert((1LL<<60));
int n;
cin >> n;
for(int i=0;i<n;i++){
ll x;
cin >> x;
//超える数の1つ前の値を出力
cout << *(prev(st.upper_bound(x))) << endl;
}
}
結果
AB(2)CDE 5完 75:23
順位 953位
パフォーマンス 1578
感想
記念すべき400回目。B問題がWAだったときは絶望していた。
が、結果はまさかの1000位切り。正直1時間超えたので1500位代だと思っていた。
やっぱり数学問題が多いと波乱が起きるなぁ。
貯蓄ができたので良しとする。