30分心を落ち着かせた男の備忘録です
コンテスト概要
AtCoder Beginner Contest 428（Promotion of AtCoderJobs）
開催日:2025年10月18日 21:30-23:10
A - Grandma's Footsteps
考察
150点問題。ケアレスミスでペナ付けがち。なので丁寧にやる。
愚直にやるなら、MIN(A,残り時間)走る、MIN（B,残り時間)休む。を繰り返す。これを残り時間が無くなるまでやればよい。
とはいえこの方針はミスりやすいのでもっとわかりやすくする。
行動は(A+B)秒でループするので、まずX秒で何ループできるかを考える。
そして、余った時間でどれだけ走れるかを調べる。
ちょっとめんどくさい。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int s,a,b,x;
cin >> s >> a >> b >> x;
int ans = 0;
//何ループできるか、最後にどれだけ余るか？
int t = x/(a+b),k = x%(a+b);
//最後の残り時間でどれだけ走れるか？
k = min(k,a);
//ループの回数だけA秒走る。
ans += s*a*t;
//余った時間だけ走る。
ans += s*k;
cout << ans << endl;
}
B - Most Frequent Substrings
考察
まあ言われた通りにやってくださいと言われればそこまでの問題。
ただ、最大のものを探したりするのがやや面倒。
まず、方針として
1:全てのK文字の文字列を抜き出す。
2:そして抜き出したものをmapで管理して出てきた回数だけカウントを増やす。
3:mapを参照しながら出現回数が最も多かったものをvectorに収める。
4:ソートをかけて出力。
改めてやるだけだが、めんどくさいね。
面倒すぎて1,2,3をまとめて実装しちゃった。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
string s;
int n,k;
cin >> n >> k >> s;
//暫定の答えを格納する。
vector<string>ans (0);
//今の最大個数。
int mx = 0;
map<string,int>mp;
for(int i=0;i+k<=n;i++){
//文字列からK文字抜き取る。
string str = s.substr(i,k);
mp[str]++;
if(mp[str] > mx){
//最大値を更新した場合。
mx = mp[str];//更新
ans.clear();//暫定の答えは全削除
ans.push_back(str);//新たに答えを格納
}else if(mp[str] == mx){
//最大値と同じばい
ans.push_back(str);//暫定リストに格納
}
}
//最大値を出力。
cout << mx << endl;
//ソート
sort(ans.begin(),ans.end());
//暫定リストを出力。
for(auto x:ans) cout << x << endl;
}
C - Brackets Stack Query
考察
正直カッコ列にはいい思い出はない。
正しいカッコ列の見分け方はいろいろとある。今回は次のもので考える。
( を+1、) を-1として前から順に足した時
〇総和が0である。
〇一度も合計が負の値になったことがない。
この２つを満たすとき、正しいカッコ列になる。
これが確認できるように実装すればいい。
正直総和は愚直に計算すればいい。
負の値は少し面倒、負になった回数を別途持っておけば何とかなる。
やっぱりカッコ列めんどくさい。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
//今までの値を格納。
stack<int>st;
//総和を管理
int sum = 0;
//負になった回数を管理
int mn = 0;
for(int i=0;i<n;i++){
int c;
cin >> c;
if(c == 1){
char x;
cin >> x;
if(x == '('){
//(なら足す
sum++;
st.push(1);
}else{
//)なら引く
sum--;
st.push(-1);
}
//今負の値ならカウントを増やす
if(sum < 0) mn++;
}else{
//今の最後尾を取り出す。
int x = st.top();
st.pop();
//今負の値ならカウンターを減らす
if(sum < 0) mn--;
sum -= x;
}
//正しいカッコ列かをチェック。
if(sum == 0 && mn == 0){
cout << "Yes" << endl;
}else{
cout << "No" << endl;
}
}
}
D - 183184
考察
今日１番めんどくさかった問題。
数学はあまり得意じゃないんだよ。
まず、思いつくのは平方数を列挙する方法。もし上限が$10^9$位だったら３万個くらいしかないので列挙も悪くない手。
しかし、今回の値の上限は2000000005200000000。この値以下の平方数はざっくり$10^9$個なので到底間に合わない。なんとかしたい。
さて、別の問題を考える。例えば、130以上5000以下の平方数はいくつあるかを考える。
まず5000以下の平方数は$[\sqrt{5000}]$個ある。外側はガウス記号(小数以下切り捨て)
次に130未満の平方数は$[\sqrt{129}]$個ある。
両端の個数が出たので答えは$[\sqrt{5000}]-[\sqrt{129}]$個である。
これで何が言いたいかといえば、直接考えるのは難しいが範囲内の個数であれば比較的に簡単に求まる、ということ。
では具体例で方針を追ってみる。
C=130、D=50000とする。この時C+xは$131 \leq C+x \leq 50130$となる。
この時桁が上がるとトータルの桁も上がるので各桁ごとに考えると。
$f(C,C+x)$の取りうる範囲は、
130131~130999,1301000~1309999,13010000~13050130
の3つの範囲とわかる。あとは範囲ごとに平方数の数を求めればOK。
数学は方針を閃いた時の気持ちよさはあるんですがね。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll cnt(ll x){
//今回は2分探査で検索。
ll h = 0,t = (1LL<<31);
//Xを超える平方数を探る。
while(h != t){
ll c = (h+t)/2LL;
if(c*c > x) t = c;
else h = c + 1LL;
}
//値より1つ下が答え。
h--;
return h;
}
int main(){
int t;
cin >> t;
//範囲をあらかじめvectorに入れておく
vector<ll>lp (11,1),rp (11,9);
for(int i=0;i<10;i++) lp[i+1] = lp[i] * 10LL;
for(int i=0;i<10;i++) rp[i+1] = rp[i] * 10LL + 9LL;
for(int p=0;p<t;p++){
ll c,d;
cin >> c >> d;
//C+xの最大値と最小値
ll mn = c+1,mx = c+d;
ll ans = 0;
for(int i=0;i<10;i++){
//桁が小さいなら飛ばす。
if(mn > rp[i]) continue;
//桁が大きいならもう調べない。
if(mx < lp[i]) break;
ll x = lp[i],y = rp[i];
//最小値,最大値が範囲内にあるなら更新
if(lp[i] <= mn && mn <= rp[i]) x = mn;
if(lp[i] <= mx && mx <= rp[i]) y = mx;
//桁数分繰り上げて足す。
x += c * lp[i+1];
y += c * lp[i+1];
x--;
//範囲内の平方数を数える。
ll cl = cnt(x),cr = cnt(y);
ans += cr - cl;
}
cout << ans << endl;
}
}
E - Farthest Vertex
考察
何だったら今回一番素直な問題。いやそうでもないか。
まず直感的にある頂点から一番遠いところは木の端っこでありそう。
そして、いろいろと言っているが結局答えの候補になるのは木の直径の両端しかない。
「答えが複数ある場合一番大きい数」というのが少々厄介だが、左端の一番大きい数、右端の一番大きい数を求めてしまえばほぼ終わり。
後は答えの候補からBFSとかで距離を求め、より遠かったスタート地点が答えになる。
難易度が逆転するの心臓に悪いんでやめてください。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<vector<int>>path;
int inf = (1<<30);
//ある頂点からの距離を求める。
int pt(int p,vector<int> &vec){
vec[p] = 0;
queue<int> que;
que.push(p);
while(!que.empty()){
int x = que.front();
que.pop();
for(auto nex:path[x]){
if(vec[nex] == inf){
vec[nex] = vec[x] + 1;
que.push(nex);
}
}
}
//ついでに一番遠いところも求める
int mx = 0,ans = -1;
for(int i=0;i<vec.size();i++){
if(mx <= vec[i]){
mx = vec[i];
ans = i;
}
}
return ans;
}
int main(){
int n;
cin >> n;
path.resize(n,vector<int>(0));
for(int i=0;i<n-1;i++){
int x,y;
cin >> x >> y;
path[x-1].push_back(y-1);
path[y-1].push_back(x-1);
}
vector<int>len1 (n,inf),len2 (n,inf),len3 (n,inf);
//頂点1から一番遠い場所が候補１。
int l = pt(0,len1);
//候補1から一番遠い場所が候補2。
int r = pt(l,len2);
//候補2からの距離も求める。
pt(r,len3);
l++,r++;
for(int i=0;i<n;i++){
//候補1のほうが遠いなら候補1が答え。
if(len2[i] > len3[i]) cout << l << endl;
//候補2のほうが遠いなら候補2が答え。
if(len2[i] < len3[i]) cout << r << endl;
//同じ距離なら番号が大きいほうが答え。
if(len2[i] == len3[i]) cout << max(l,r) << endl;
}
}
結果
ABCDE 5完 71:25
順位 605
パフォーマンス 1731
レート 1416(+41)
感想
激めんど回にもかかわらず、まさかの歴代最高成績。
全体的に得意だったわけでもないんですが。
やはり30分の精神統一タイムがあったのが良かったのかも。
心の平穏これ大事。