ケアレスミスを無くせない男の備忘録です
コンテスト概要
AtCoder Beginner Contest 405（Promotion of AtCoder Career Design DAY）
開催日:2025年5月10日 21:00-22:40
A - Is it rated?
考察
言われた通りに出力するだけ。
どちらかといえば「Div.1とDiv.2を間違えない」「未満と以下を間違えない」とかの注意力を問われる問題。
気を抜くとWA出しがちな問題。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,x;
cin >> n >> x;
if(x == 1){
//Div.1は1600以上3000未満が対象
if(1600 <= n && n < 3000) cout << "Yes" << endl;
else cout << "No" << endl;
}else{
//Div.2は1200以上2400未満が対象
if(1200 <= n && n < 2400) cout << "Yes" << endl;
else cout << "No" << endl;
}
}
B - Not All
考察
おそらくいろいろな解法ができる問題。
前から順に見て行ってM以下の数がすべて出たタイミングを探るとか。
今回は問題文通りに実装。
配列で数字が出た回数を管理。最後まで行ってM以下の数字がすべて出ていなければ数字を消す必要はない。
順番に数字を後ろから消していき、M以下のある数がなくなったら消した回数を出力。
...やっぱり、すべて出たタイミングで引き算したほうが楽ですね。
冷静な考察は大事。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin >> n >> m;
//数字ごとに出てきた回数を管理
vector<int>num (101,0);
stack<int> st;
int cnt = 0;
for(int i=0;i<n;i++){
int x;
cin >> x;
//初めて出てきたM以下の数字ならカウント
if(x <= m && num[x] == 0) cnt++;
num[x]++;
st.push(x);
}
//そもそもM以下の数字がすべて出てないなら消す必要はない
if(cnt != m){
cout << "0" << endl;
return 0;
}
int ans = 0;
//stackで後ろから消していく
while(!st.empty()){
int x = st.top();
st.pop();
num[x]--;
ans++;
//M以下のある数がなくなった終了
if(num[x] == 0 && x <= m) break;
}
cout << ans << endl;
}
C - Sum of Product
考察
もはや準レギュラーのダブルシグマさん。
もちろんすべての$N_i \times N_j$を計算する時間はない。$ \frac{N \times (N-1)}{2}$回(最大で$10^{10}回$くらい)を何とかうまく考えなければならない。
ここでダブルシグマを書き下してみると
$N_1 \times N_2 +N_1 \times N_3+ N_1 \times N_4 + N_1 \times N_5 + ... + N_{n-1} \times N_n$となる。同じ文字が多いのでくくってみると。
$N_1 \times (N_2 + N_3 + N_4 + ... + N_n) + N_2 \times(N_3 + N_4+ ...+N_n)+...+N_{n-1} \times N_n$
という感じに$N_i \times(N_i 以降の和)$と省略できる。
なので、あらかじめ累積和を用意しておけば順に計算するだけでおしまい。
ダブルシグマの入門みたいな問題かも。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
ll n;
cin >> n;
//値を管理する配列と累積和を管理する配列。
vector<ll>num (n),sum(n+1,0);
for(int i=0;i<n;i++){
cin >> num[i];
//累積和を計算
sum[i+1] = num[i] + sum[i];
}
ll ans = 0;
for(int i=0;i<n;i++){
//N_i*(i以降の和)
ans += num[i] * (sum[n] - sum[i+1]);
}
cout << ans << endl;
}
D - Escape Route
考察
何してんだこの高橋。
最短で非常口に向かえる経路をすべてのマスで求める必要がある。
となればBFSの出番。幅優先探索で全マスを順に矢印で埋めればOK。
矢印の向きに気を配りながら実装していく。
...なんですが、なぜか凡ミスをしており20分バグ取に追われる。
continueの乱用ダメ。絶対。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int h,w;
cin >> h >> w;
vector<vector<char>>mp (h,vector<char>(w));
//BFS用のque。座標をメモ。
queue<pair<int,int>>que;
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
cin >> mp[i][j];
//非常口がスタートなのでqueに追加
if(mp[i][j] == 'E') que.push({i,j});
}
}
//スタートから順に見る
while(!que.empty()){
auto [x,y] = que.front();
que.pop();
for(int i=-1;i<2;i+=2){
if(i+x < h && 0 <= i+x){
//まだ行っていないマスの場合
if(mp[i+x][y] == '.'){
if(i < 0) mp[i+x][y] = 'v';//下から来たなら'v'
else mp[i+x][y] = '^';//上から来たなら'v'
que.push({i+x,y}); //queに座標を追加
}
}
if(i+y < w && 0 <= i+y){
if(mp[x][i+y] == '.'){
if(i < 0) mp[x][i+y] = '>';//右から来たなら'>'
else mp[x][i+y] = '<';//左から来たなら'>'
que.push({x,y+i});//queに座標を追加
}
}
}
}
//答えを出力
for(auto x:mp){
for(auto y:x) cout << y;
cout << endl;
}
}
E - Fruit Lineup
考察
非常に簡潔な問題文。苦手な人はとっかかりがなさそう。
順番に果物を置いていく。
まずリンゴはバナナより左に置く必要があるので、この二つは、
リリリリ...リリリリ ババババ...ババババ
と置くしかない。
次にブドウを置きたい。ブドウもリンゴより右に置く必要がある。
なのでバナナが並んでいる間にブドウを適当においていく。ただあまりにも適当にするとオレンジとブドウの位置関係がわかりづらくなる。
分かりやすくするためにブドウの左端を固定しておく。
リリリリ...リリリリ ババババ... バ ブ ババ...ババババ
この時固定したブドウより右側に残りのブドウを、左側にはすべてのオレンジを適当に配置していけばいい。
果物の置ける場所を箱、果物をボールとすれば典型的な「n個のボールをr個の箱に入れるやつ(写像12相)」に落ち着く。
詳しくはこれを見て
今回は箱は区別するがボールは区別しないので二項係数が使える。
ブドウの場所を固定して右側と左側でそれぞれ通りの数を計算すればOK
ただ普通にやると計算量がえぐそうなので、あらかじめ階上の逆数を求めておくと吉。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll mod = 998244353LL;
unordered_map<ll,ll>minv,fnc;
//ある数の逆数をmodで割った余りを求める関数
ll inv(ll n){
//mod p の逆数は n^(p-2)で求まる
ll ans = 1,m = mod - 2LL;
while(m != 0){
if(m%2 == 1) ans *= n;
ans %= mod;
n *= n;
n %= mod;
m >>= 1;
}
return ans;
}
//二項係数を求める関数
ll cmb(ll c,ll k){
//分母を階上メモから引き出す
ll ans = fnc[c+k];
//分子を逆数メモから引き出す
ans *= minv[c];
ans %= mod;
ans *= minv[k];
ans %= mod;
return ans;
}
int main(){
ll apl,bnn,grp,ore;
cin >> apl >> ore >> bnn >> grp;
ll now = 1;
ll lim = 3000001;
//階上と逆数に関して0と1をあらかじめ定義
minv[1] = inv(now);
minv[0] = 1;
fnc[0] = 1;
fnc[1] = 1;
//使いうる最大を前計算
for(ll i=2;i<=lim;i++){
now *= i;
now %= mod;
fnc[i] = now;
minv[i] = inv(now);
}
ll ans = 0;
for(ll i=0;i<=bnn;i++){
//一番後ろのリンゴからi個離れたところに最初のブドウを置く
ll x = cmb(bnn-i,grp - 1); //右側を計算
ll y = cmb(apl+i,ore); //左側を計算
x *= y;
x %= mod;
ans += x;
ans %= mod;
}
cout << ans << endl;
}
結果
ABCDE 5完 69:01
順位 1572位
パフォーマンス 1365
感想
ただのBFSに20分とられたのは痛かった。
ちょっと基礎がおろそかかも。今週は初心に帰ります。