ABC 253 参加記
88分6完(5ペナ)で493位、パフォーマンスは1843でした。レートが1700を超えました!(次の日のARCで落ちましたが…)
A Median?
問題
整数$a, b, c$が与えられます。$b$がこれらの整数の中央値かどうか判定してね。
- $1 \leq a, b, c \leq 100$
提出コード
int main(){
vector<int> T(3); rep(i, 3) cin >> T[i];
auto S = T;
sort(all(S));
YesNo(S[1] == T[1]);
}
B Distance Between Tokens
問題
$H$行$W$列のマス目があって、$2$つの異なるマスに駒が置かれてるよ。一方を上下左右の隣接マスに動かしてもう一方と同じマス目に移動するためには最小で何手必要?
- $2 \leq H, W \leq 100$
- $S_i(1 \leq i \leq H)$は
o
(コマ)か-
(何も置かれてないマス)- ちょうど$2$つ
o
が存在するよ
提出コード
int main(){
ll H, W; cin >> H >> W;
vector<string> A(H); for(int i = 0; i < H; i++) cin >> A[i];
vpll B;
rep(i, H) rep(j, W) if(A[i][j] == 'o'){
B.pb({i, j});
}
ll ans = abs(B[0].fi - B[1].fi) + abs(B[0].se - B[1].se);
cout << ans << '\n';
}
C Max - Min Query
問題
整数の多重集合$S$があって、最初$S$は空です。$Q$個のクエリをさばいてね。
1 x
: $S$に$x$を1つ追加2 x c
: $S$から$x$を$\min(c, (Sに含まれるxの個数))$個削除3
: ($S$の最大値) $-$ ($S$の最小値) を出力- $1 \leq Q \leq 2 \times 10^5$
- $0 \leq x \leq 10^9$
- $1 \leq c \leq Q$
3
のクエリを処理するとき、$S$は空でない
考察
multiset
でもできるかもしれないけど大変そうなのでmap
で値と個数を持つようにします。こうすると頑張るとできます。
提出コード
int main(){
ll Q; cin >> Q;
map<int, int> S;
while(Q--){
int t; cin >> t;
if(t == 1){
int x; cin >> x;
S[x]++;
}elif(t == 2){
int x, c; cin >> x >> c;
S[x] -= c;
if(S[x] <= 0) S.erase(x);
}else{
auto min = S.begin();
auto max = S.end(); max--;
cout << abs(max->fi - min->fi) << endl;
}
}
}
どっちが大きいのかわすれちゃったからとりあえずabs
をしちゃいました 先頭が小さくて後ろが大きいです。
D FizzBuzz Sum hard
問題
$1$以上$N$以下の整数で$A$の倍数でも$B$の倍数でもないものの総和をもとめてね。
- $1 \leq N, A, B \leq 10^9$
考察
総和じゃなくて個数だとだいぶ有名な気がします。個数で考えて適当に総和にするとよいです。
$f(x) = \cfrac{x(x+1)}{2}$としたとき、答えは$f(N) - Af(N/A) - Bf(N/B) + \text{lcm}(A, B) f(N/\text{lcm}(A, B))$(割り算は切り捨て)
となります。ベン図を考えるとわかりやすいです。$\text{lcm}(A, B)$を$A \times B$としてしまい1ペナ…
提出コード
/*最大公約数*/
ll gcd(ll x, ll y){
if (x < y) swap(x, y);
while (y > 0){
ll r = x % y;
x = y;
y = r;
}
return x;
}
/*最小公倍数*/
ll lcm(ll x,ll y){
return x * y / (gcd(x, y));
}
ll su(ll n){
return n * (n+1) / 2;
}
int main(){
ll N, A, B; cin >> N >> A >> B;
ll ans = 0;
ans += su(N);
ans -= A * su(N / A);
ans -= B * su(N / B);
ans += lcm(A, B) * su(N / lcm(A, B));
cout << ans << '\n';
}
E Distance Sequence
問題
長さ$N$の整数からなる数列$A = (A_1, \cdots, A_N)$であって、以下の条件をすべて満たすものは何通りありますか?
- $1 \leq A_i \leq M~(1 \leq i \leq N)$
- $|A_i - A_{i+1}| \geq K~(1 \leq i \leq N-1)$
ただし、答えは大きくなるので$998244353$で割ったあまりを求めてね
- $2 \leq N \leq 1000$
- $1 \leq M \leq 5000$
- $0 \leq K \leq M-1$
考察
DPしてねって問題に書いてあるのでDPします。普通にやるとやばいのでうまい感じにやります。僕は累積和を使いました。
$K=0$の時は壊れちゃうので別で処理を書きましょう。これを忘れて1ペナしました。
提出コード
// https://github.com/Kyo-s-s/Kyo_s_s_Library/blob/main/md/Modint.md
// https://github.com/Kyo-s-s/Kyo_s_s_Library/blob/main/md/CumulativeSum.md
int main(){
ll N, M, K; cin >> N >> M >> K;
vector<Mint> dp(M, 1);
if(K == 0){
auto m = Mint(M);
m = m.pow(N);
cout << m << endl;
exit(0);
}
rep(n, N - 1){
vector<Mint> pd(M, 0);
CumulativeSum Cum(dp);
Mint Sum = sum(dp);
Cum.build();
rep(m, M){
ll low = max(m - K + 1, 0LL);
ll hig = min(M, m + K);
pd[m] = Sum - Cum.sum(low, hig);
}
swap(dp, pd);
}
Mint ans = sum(dp);
cout << ans << endl;
}
F Operations on a Matrix
問題
縦$N$行横$M$列の行列があり、はじめすべての成分は$0$です。以下のクエリを$Q$個さばいてね。
1 l r x
: $l, l+1, \cdots, r$列目の成分すべてに$x$を足す2 i x
: $i$行目の成分すべてを$x$で書き換える3 i j
: $(i, j)$成分を出力する- $1 \leq N, M, Q \leq 2 \times 10^5$
- $1 \leq l \leq r \leq M$
- $1 \leq i, j \leq N$
- $1 \leq x \leq 10^9$
考察
最後にクエリ2が来てから何が足されたかを見ることによって$(i, j)$成分についての値を答えることができます。
クエリを逆から読んでいきます。クエリ2を読んだときにその行のそれ以前のクエリ3についての答えが確定します。これをやります。最初に2 i 0
($1 \leq i \leq N$)があることにしておくと実装が楽です。クエリ1は区間加算なので遅延セグ木を持ってきます。
提出コード
#include <atcoder/all>
using namespace atcoder;
struct q {
int t, l, r, i, j, x;
};
using S = long long;
using F = long long;
const S INF2 = 8e18;
S op(S a, S b){ return std::max(a, b); }
S e(){ return -INF2; }
S mapping(F f, S x){ return f+x; }
F composition(F f, F g){ return f+g; }
F id(){ return 0; }
int main(){
ll N, M, Q; cin >> N >> M >> Q;
vector<q> Query;
rep(i, N){
q add;
add.t = 2;
add.i = i + 1;
add.x = 0;
Query.pb(add);
}
rep(u, Q){
q add;
cin >> add.t;
if(add.t == 1) cin >> add.l >> add.r >> add.x;
elif(add.t == 2) cin >> add.i >> add.x;
else cin >> add.i >> add.j;
Query.pb(add);
}
reverse(all(Query));
vector<pll> Ans; // idx, val
vector<S> v(M + 10, 0);
lazy_segtree<S, op, e, F, mapping, composition, id> seg(v);
vector<vector<tuple<ll, ll, ll>>> Index(N + 10); // i行列に対し、<j列目でidxでその時の遅延セグ木のval> の行列
ll idx = Q + 1;
for(auto que: Query){
if(que.t == 1){
seg.apply(que.l, que.r+1, que.x);
}elif(que.t == 2){
for(auto [j, in, va]: Index[que.i]){
ll val = seg.get(j);
ll an = val - va + que.x;
Ans.pb({in, an});
}
Index[que.i].resize(0);
}else{
ll val = seg.get(que.j);
Index[que.i].pb({que.j, idx, val});
}
idx--;
}
sort(all(Ans));
for(auto [in, an]: Ans) cout << an << "\n";
}
バグらせそうだったので1-indexedで書きました。焦って書いたのでぐちゃぐちゃです…
Comment is disabled to avoid unwanted discussions from 'localhost:1313' on your Disqus account...