折れた心を接着させた男の備忘録です
コンテスト概要
AtCoder Beginner Contest 417
開催日:2025年8月2日 21:00-22:40
A - A Substring
考察
書いてる通りに範囲内を出力すればいい。
言い換えると、0-indexでa番目からn-1-b番目までを出力すればいい。
のに、問題文をよく読んでなかったので1ペナ。
A問題でペナ食らったの久々だな...
最近の不調もあり、若干投げやりムードになる。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
string s;
int n,a,b;
cin >> n >> a >> b >> s;
//a番目からn-b-1番目までを出力。
for(int i=a;i<n-b;i++) cout << s[i];
cout << endl;
}
B - Search and Delete
考察
二分探査とかを使えばスマートなのかもしれない。
ただ、B問題なので制約がかなり小さい。
なので、贅沢に二重ループでシラミつぶしで値を消していく。
eraseを使ってもよかったが、値を-1にして疑似的に消去。
最後に-1を無視して出力。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin >> n >> m;
vector<int>num (n);
for(int i=0;i<n;i++) cin >> num[i];
for(int i=0;i<m;i++){
int x;
cin >> x;
//配列Ａを前から見ていく。
for(int j=0;j<n;j++){
if(num[j] == x){
num[j] = -1;//探している値があったら、-1にする。
break;//一個でもあったら探索終了
}
}
}
for(auto x:num){
if(x == -1) continue;//-1は存在しないので無視。
cout << x << endl;
}
}
C - Distance Indicators
考察
問題文に愚直に従うと、二重ループを回すしかない。
となると計算量は$O(N^2)$になり、制約的にTLEは避けられない。
なので、上手い方法で調べていかなけらばならない。
ここで求める式を変形すると
$j-i=A_i+A_j \Leftrightarrow j-A_j = i+A_i$
となり、それぞれのインデックスごとの式に帰着できる。
なので前から順に$i+A_i$を求めておき、値を配列で管理する。
そして、これまでに$j-A_j$となりうる値が何回あったかを見ればOK。
数学的考察問題の導入としてはちょうどよさそう。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
int n;
cin >> n;
//足し算の最大値は400000なのでそれだけの配列を用意。
vector<int>num (4e5+1,0);
ll sum = 0;
for(int i=1;i<=n;i++){
int x;
cin >> x;
//これまでに足し算の結果が[i-A_i]になった回数を足す
if(i-x >= 0) sum += num[i-x];
//足し算の結果の回数を増やす。
num[i+x]++;
}
cout << sum << endl;
}
D - Takahashi's Expectation
考察
普通にやると毎回シミュレーションしなければいけなさそうに見える。
が、やたら制約が小さい。プレゼントの価値、上り幅ともに500しかない。
となると、テンションが上がるとき、せいぜい価値500、上り幅500で1000にしかならない。
テンションが0～1000スタートの時は、その後どうあがいてもテンションは0~1000までの間でしか変動しない。なので、この範囲は一覧表をDPとかで作れば一瞬で済む。
問題は最初テンションが1000超えていた時。この時、価値が何であれテンションは下がるしかない。なので「プレゼントを渡し続けテンションが1000以下」になったタイミングで表を参照すればいい。そういうのは二分探査が得意。
というわけで、まずは0~1000までにおけるプレゼントを渡した時のテンションの推移をDPで作る。
そしてハイテンションなら、テンションが落ち着くポイントを二分探査で探り、表を参照する。
これでOK。
こういう、頭がよさそうな実装が決まると顔もほころぶ。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
int n;
cin >> n;
vector<vector<int>>num (n,vector<int>(3));
//テンションが下がり続けた場合の下がり幅を、個数ごとに累積和。
vector<int>mns (n+1,0);
for(int i=0;i<n;i++){
for(int j=0;j<3;j++) cin >> num[i][j];
mns[i+1] += mns[i] + num[i][2];
}
//最初のテンションが0~1000の時の遷移をDPで求める。
vector<vector<int>>dp (n+1,vector<int>(1001,-1));
//最後のテンションはその時のテンションの値と同じ。
for(int i=0;i<1001;i++) dp[n][i] = i;
for(int i=n-1;i>=0;i--){
for(int j=0;j<1001;j++){
//それぞれテンションの動いた後のテンションの値に追随する。
if(num[i][0] >= j) dp[i][j] = dp[i+1][j+num[i][1]];
else{
int mn = max(0,j-num[i][2]);
dp[i][j] = dp[i+1][mn];
}
}
}
int q;
cin >> q;
for(int i=0;i<q;i++){
int x;
cin >> x;
if(x <= 1000){
//テンションが1000いないなら最初の表を参照。
cout << dp[0][x] << endl;
}else if(x - mns[n] > 1000){
//全部渡してもテンションが下がりきらないなら最終的な値が答え。
cout << x - mns[n] << endl;
}else{
//二分探査でいつテンションが1000以下になるかを調べる。
int h = 0,t = n;
while(h != t){
int c = (h+t) / 2;
if(x - mns[c] <= 1000) t = c;
else h = c+1;
}
//プレゼントを渡しテンションを下げる。
x -= mns[h];
//そこから先は表を参照。
cout << dp[h][x] << endl;
}
}
}
E - A Path in A Dictionary
考察
ぱっとみダイクストラを使えばよさそうだが、基準となる値がやや曖昧。
普段なら頂点の重みが小さい順に進むが、それが通った順だったらどうするか。
E問題もは全体的に制約が小さい。ならダイクストラにコストとしてvectorを突っ込んでみよう。
c++であれば配列の辞書順の大小を勝手に判断してくれる。
あとは、なのでいつものようにダイクストラを回す。
感想としては「こんなことしていいんだ...」
提出
#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 t;
cin >> t;
for(int i=0;i<t;i++){
int n,m,x,y;
cin >> n >> m >> x >> y;
x--,y--;
//各頂点ごとに通る順を配列で管理。大きい値で初期化。
vector<vector<int>>ans(n,vector<int>(1,n));
//当然スタートはその頂点だけ。
ans[x] = {x};
//パスの作成。
vector<vector<int>>path (n,vector<int>(0));
for(int j=0;j<m;j++){
int a,b;
cin >> a >> b;
path[a-1].push_back(b-1);
path[b-1].push_back(a-1);
}
//優先度付きqueueにvectorを突っ込む。
p_que<vector<int>> que;
que.push({x});
while(!que.empty()){
auto vec = que.top();
que.pop();
int pos = vec.back();
//配列が辞書順でデカいなら見る必要なし。
if(ans[pos] != vec) continue;
for(auto nex:path[pos]){
//今の配列に次行きたいところを挿入。
vec.push_back(nex);
//作った値が辞書順で小さいなら更新。
if(ans[nex] > vec){
ans[nex] = vec;
que.push(vec);
}
//後ろの値は消しておく。
vec.pop_back();
}
}
//ゴールの配列を出力。
int siz = ans[y].size();
for(int j=0;j<siz;j++){
if(j != 0) cout << " ";
cout << ans[y][j]+1;
}
cout << endl;
}
}
F - Random Gathering
考察
期待値苦手なんだよな...
ただ、やることは範囲内の石を合計して、分数が出てもいいのできっちり均等に配りなおすということ。期待値ってそういうものだし。
することは存外単純。範囲の値を更新し、範囲の値の和を高速で取得できればいい。
この特徴は遅延セグメント木ですね！
遅延セグ木よくわかんないんだよな...
ただ、昔見よう見まねで作ったやつがあったのでそれを苦戦しながら改造。
中身は4割ほど理解できてないが通ったのでＯＫ。
完全に理解してたら10分は短縮できた気がする。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll mod = 998244353LL;
ll hf = 499122177LL;//0.5をあらかじめ出しておく。
//区間更新・区間和取得の遅延セグメントツリー。
struct UPDSUM{
int siz;
vector<ll>num,lazy;
//更新すべき値かのチェック
vector<bool>exc;
UPDSUM(int n){
int x = 1;
while(n > x) x <<= 1;
siz = x;
num.resize(siz*2-1,0);
lazy.resize(siz*2-1,0);
exc.resize(siz*2 - 1,false);
}
//初期のデータを設定
void setup(vector<ll> vec){
int now = siz-1;
for(auto x:vec){
num[now] = x;
now++;
}
for(int i=siz - 2;i > -1; i--){
num[i] += num[i*2+1]+num[i*2+2];
num[i] %= mod;
}
}
//遅延評価(何回足す必要があるのかも加味する)
void eval(int k, int l, int r){
//変更フラグがないなら無視
if(!exc[k]) return;
if(r - l > 1){
//下位の要素は半分になる
//変更フラグを立てる
lazy[k*2+1] = lazy[k]*hf;
lazy[k*2+1] %= mod;
exc[k*2+1] = true;
lazy[k*2+2] = lazy[k]*hf;
lazy[k*2+2] %= mod;
exc[k*2+2] = true;
}
num[k] = lazy[k];
//変更フラグをおろす
exc[k] = false;
}
//区間加算
void update_sub(int a,int b,ll x,int k, int l,int r){
eval(k,l,r);
if(a <= l && r <= b){
//値は合計（r-l）個掛けておく
lazy[k] = (r-l)*x;
lazy[k] %= mod;
//フラグも立てておく
exc[k] = true;
eval(k,l,r);
}else if(a < r && l < b){
update_sub(a,b,x,k*2+1,l,(l+r)/2);
update_sub(a,b,x,k*2+2,(l+r)/2,r);
num[k] = num[k*2+1]+num[k*2+2];
num[k] %= mod;
}
}
void update(int a,int b,int x){update_sub(a, b+1, x, 0, 0, siz);}
//区間合計
ll sumval_sub(int a,int b,int k,int l,int r){
eval(k,l,r); //遅延評価があるだけで他はセグメントツリーと変わらない。
if(r <= a || b <= l) return 0;
else if(a <= l && r <= b) return num[k];
else{
ll vl = sumval_sub(a, b, k*2 + 1, l, (r+l) / 2);
ll vr = sumval_sub(a, b, k*2 + 2, (l+r) / 2, r);
ll s = vl + vr;
s %= mod;
return s;
}
}
ll sumval(int a,int b){return sumval_sub(a, b+1, 0, 0, siz);}
};
//逆数の余りを求めるやつ。
//a^-2をフェルマーの小定理を利用して高速取得。
ll inv(ll n){
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;
}
int main(){
int n,m;
cin >> n >> m;
vector<ll>num (n);
for(int i=0;i<n;i++) cin >> num[i];
UPDSUM st(n);
st.setup(num);
for(int i=0;i<m;i++){
int l,r;
cin >> l >> r;
l--,r--;
//範囲内の和を取得し、均等に配分しなおす。
ll sum = st.sumval(l,r);
sum *= inv(r-l+1LL);
sum %= mod;
st.update(l,r,sum);
}
//今ある値が期待値になる。
for(int i=0;i<n;i++){
if(i != 0) cout << " ";
cout << st.sumval(i,i);
}
cout << endl;
}
結果
A(1)BCDE(1)F 6完 2ペナ 100:26
順位 809位
パフォーマンス 1645
レート 1357(+37)
感想
最初、A問題をミスったときはダメかと思った。
逆にその、あきらめが平常心につながったのかもしれない。
緊張しない方法を教えてください。だれか。