危険地帯に確認して飛び込んだ男の備忘録です
コンテスト概要
Polaris.AI プログラミングコンテスト 2025（AtCoder Beginner Contest 429）
開催日:2025年10月25日 21:00-22:40
A - Too Many Requests
考察
久々のHTTPステータスコード問題。次はABC451かな？
100点問題らしく言われた通りに比べればOK。
むしろ英単語の書き間違いのほうがミスしやすそう。
英単語は無難にコピペしよう。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin >> n >> m;
//1-indexにして問題通りに比較できるようにする。
for(int i=1;i<=n;i++){
//mを超えたらToo～。
if(i > m) cout << "Too Many Requests" << endl;
//そうでなければOK。
else cout << "OK" << endl;
}
}
B - N - 1
考察
最近では珍しく理解しやすいB問題。
制限が小さいので、1つずつ足さない数を決めて総和がMになるかを確かめたとしても余裕で間に合う。
ややスマートな方法も考えてみる。
数列の合計値Sは足せば出る。そこから値Xを引いて目標値Mにする。
ということは言い換えれば合計値Sから目標値Mを引いたものが値Xとなる。
式でいうなら$S-X=M \Leftrightarrow S-M=X $となる。
ここまで出ればあとは値Xが数列内にあったかを確かめればOK。
B問題は愚直にもスマートにも解けるから好き。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin >> n >> m;
//値が出現したかを管理。
vector<bool>num (101,false);
int sum = 0;
for(int i=0;i<n;i++){
int x;
cin >> x;
//メモを「あり」に変える。
num[x]=true;
//合計値も求める。
sum += x;
}
//そもそも目標に足りてないなら失敗。
if(sum < m) cout << "No" << endl;
else{
//ほしい値があったかを確認。
if(num[sum - m]) cout << "Yes" << endl;
else cout << "No" << endl;
}
}
C - Odd One Subsequence
考察
今回のコンテスト全体的に問題文が短くて手が付けやすい。
さて、$i<j<k$なんて制約がついていると考えづらい。これをないものにしたい。
問題は「３つの数字のうち2つが同じになる組み合わせの数」を聞いている。となれば数列の中から適当に同じ数を2つ選び、違う数字を1つ選べばいい。
$i<j<k$の制約だが選んだ後にそう並べればいいだけ。なので実質この制約はないものとして扱えそう。
というわけで問題を分かりやすく改変すると
箱の中に数字の書かれた区別できるボールがN個あります。
ここからボールを3つ取り出した時、ボールに書かれた2つだけが同じになる取り出し方は全部で何通りですか？
という高校数学っぽいものになった。あとは解くだけ。
こういうのは片方を先に決め打つと数えやすい。今回は2つのほうを決め打つ。
値Xのボールを2つ取り出すとする。もし、値XのボールがB個あるなら取り出し方は$\frac{B\times(B-1)}{2}$通り。
そして値Xではないボールは$N-B$個あるのでトータルで$\frac{B\times(B-1)}{2}\times(N-B)$通りになる。
あとはこれをすべての値について計算して足し上げればOK。
ABCって意外と高校数学も大事なんですよね。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
int n;
cin >> n;
//数ごとに個数をメモ。
vector<ll>num (n,0);
for(int i=0;i<n;i++){
int x;
cin >> x;
num[x-1]++;
}
ll ans = 0;
for(auto x:num){
//X個ある数字からを2つ選ぶ場合。
//残りの選択肢はn-x通り。
ll rem = n - x;
//2つの選び方
ll ptn = x*(x-1)/2LL;
//かけたものを足す。
ans += rem * ptn;
}
cout << ans << endl;
}
D - On AtCoder Conference
考察
425点のD問題はもれなくめんどくさい。
まず初めに、何m歩けばC人以上の人と会えるかを高速で求めたい。こういうのは二分探査が得意。
あらかじめ配列にそれぞれの人の位置を入れてソート。そのあと、人数がC人を超えるポイントを探せばいい。
ただこの配列。1周分だと小屋をまたぐ時をうまく処理できない。なので2周分作ってバグを防ぐ。
距離がわかればその間にいる人数も二分探査とかで求まる。
これを0~M-1まで順番にやっていけばOK...ではない。
もちろんMが$10^5$くらいであれば問題ないが、今回は$10^{12}$。ちまちまやってる暇はない、どうしよう？
ここで、今回聞かれているのは人数の合計というところがポイント。
例えば人が全然いない区間があったする。その左側から始めようが、右側から始めようがC人以上になるポイントは変わらない。だってその間、人がいないから。
ということで、人がいない区間は答えが同じになるのでそこは掛け算でパパっと出せる。
こうすれば人のいるポイントだけで計算するので高々$N$回の計算で済む。今回の$N$は$5\times10^5$なので間に合う。
制約を見る癖ってホント大事。
提出(※添え字が適当すぎたので手直しあり)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
ll n,m,c;
cin >> n >> m >> c;
//それぞれの人がいる場所をメモ
vector<ll>pos (1,0);
//人がいる地点のリストを出す。
set<ll>st;
//両端を入れてバグ防止。
st.insert(0);
st.insert(m);
for(int i=0;i<n;i++){
ll x;
cin >> x;
//Mを足した2周分チェック。
pos.push_back(x);
pos.push_back(x+m);
st.insert(x);
}
//ソートも忘れない。
sort(pos.begin(),pos.end());
vector<ll>che (0);
for(auto x:st) che.push_back(x);
int siz = che.size() - 1;
ll ans = 0;
for(int i=0;i<siz;i++){
//スタート地点
ll now = che[i];
ll h = 0LL,t = m+1;
//スタート地点より前にいる人数。
ll fr = upper_bound(pos.begin(),pos.end(),now) - pos.begin();
while(h != t){
ll md = (h+t) / 2LL;
//進んだ地点より前にいる人数。
ll bc = upper_bound(pos.begin(),pos.end(),now+md) - pos.begin();
if(bc-fr >= c) t = md;
else h = md + 1LL;
}
//人がいない区間分まとめて計算
ll mr = che[i+1] - che[i];
//進んだ距離までにいた人数。
ll cnt = upper_bound(pos.begin(),pos.end(),now+h) - pos.begin() - fr;
//まとめて足す。
ans += mr * cnt;
}
cout << ans << endl;
}
E - Hit and Away
考察
E問題って「上級知識の基礎」って感じだから、知ってればD問題よりとっつきやすいんだよね。
問題文は安全地帯基準だが実装しづらいので言い換えたい。
ある危険地帯を基準として、異なる2か所の安全地帯に行くときの最短距離が答えになる。
となれば直感的に「一番目に近い安全地帯までの距離」+「二番目に近い安全地帯までの距離」が最短経路になりそう。これを実装したい。
「一番近い安全地帯までの距離」は多始点BFSでもすればすぐ求まる。が、今回は2番も欲しい。
なので、多始点BFSを2つの値管理できるように改造して実装する。
それぞれの頂点について、「一番近い距離」と「二番目に近い距離」の二つを適切に管理できれば。あとは足し算だけでＯＫ。
1番と2番が同じ頂点を刺さないかだけに注意。
自分は「注意するぞ！」と決意して実装し忘れました。
ここの5分は痛い。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
int n,m;
cin >> n >> m;
//辺を管理。
vector<vector<int>>path (n,vector<int>(0));
for(int i=0;i<m;i++){
int x,y;
cin >> x >> y;
x--,y--;
path[x].push_back(y);
path[y].push_back(x);
}
int lim = (1<<30);
//各頂点の安全地帯までの距離を2位まで管理。
//{1位の距離,1位のスタート},{2位の距離,2位のスタート}
vector<vector<pair<int,int>>>stp (n,{{lim,-1},{lim,-1}});
//que{現在の距離,{現在地,スタート地点}}
queue<pair<int,pair<int,int>>>que;
//危険地帯をメモ
vector<int>ans (0);
for(int i=0;i<n;i++){
char x;
cin >> x;
if(x == 'S'){
//一番近い安全地帯は自分
stp[i][0] = {0,i};
que.push({0,{i,i}});
}else{
ans.push_back(i);
}
}
while(!que.empty()){
auto [cst,aaa] = que.front();
auto [now,ord] = aaa;
que.pop();
//cst:現在の距離,now:現在地点,ord:スタート地点
for(auto nex:path[now]){
//2位の距離を塗り替えられるとき。
if(stp[nex][1].first > cst + 1){
//すでにスタート地点から来たことあるなら飛ばす。
if(stp[nex][1].second == ord || stp[nex][0].second == ord)continue;
//2位を更新
stp[nex][1] = {cst+1,ord};
//1位になれるなら交換しておく。
if(stp[nex][0].first > stp[nex][1].first) swap(stp[nex][0],stp[nex][1]);
que.push({cst+1,{nex,ord}});
}
}
}
for(auto x:ans){
//1位の距離と2位の距離を足す。
cout << stp[x][0].first + stp[x][1].first << endl;
}
}
結果
ABCDE(1) 5完 1ペナ 53:19
順位 653位
パフォーマンス 1665
レート 1444(+27)
感想
凡ミスはあったものの、今回も早解きを達成することができた。
過去問の水diff埋めが効いているかもしない。
今年度中に青色になれるとうれしいが、調子に乗るとよくないので気を引き締めます。