sA_3

競プロ初心者 Atcoder🟩 Python C++(少し)

[sA_3 @dpDKH]

やることリスト

[sA_3 @dpDKH]

初青パフォ！！！！！

sA_3さんのキーサイト・テクノロジープログラミングコンテスト（AtCoder Beginner Contest 454）での成績：996位
パフォーマンス：1612相当
レーティング：997→1075 (+78) :)
#AtCoder #キーサイト・テクノロジープログラミングコンテストABC454 https://t.co/GyF0Q42g0y

[sA_3 @dpDKH]

E:
A+Bが偶数かNが奇数の場合No
それ以外Yes
Aが奇数の場合は横向き、偶数の場合は縦向きに進み、(A,B)にぶつかる列だけ蛇行して進む

[sA_3 @dpDKH]

#ABC454 ABCDE5完！久々大勝ち！
A:
R-L+1
B:
len(F)==len(set(F))
len(set(F))==M
C:
A→Bの有向グラフを作って行ける場所を走査
D:
A,Bともに括弧を無くし、一致するか判定
xxでセパレートして、stackで管理
末尾が()になったら削除する事を繰り返し、xxを戻す

[sA_3 @dpDKH]

#ABC447
E:
削除する辺の最大値を最小化すればよい
Unionfindで管理して、大きい辺から順に繋げていく
連結成分が2個になったら、それ以下の辺は同じグループのもののみ繋げ、残りは削除対象

[sA_3 @dpDKH]

#ABC447 ABCDE5完！
A:
(N+1)//2 >= M
B:
Counterで出現回数を調べて、最大のものを削除
C:
A以外の出現を調べる
出現順が同じなら可能
出現の前後のAの個数の差を足す
D:
ABCそれぞれindexで管理し後ろから見ていく
Cの最後尾より後ろは使わなくなるので削除

[sA_3 @dpDKH]

#ABC444
ABCDE5完
A:
len(set(N))
B:
1からNまで
C:
答えはmax(A)かA[0]+A[-1]の2択なので両方やる
最長と最短でペアを作る
D:
桁をリストにしimos法で各桁で足される数を求める
下の桁から1桁だけ取り、残りを上の桁に渡すことを繰り返す
E:
SortedListを使い尺取り法
RはD以上離れているか二分探索

[sA_3 @dpDKH]

sA_3さんのAtCoder Beginner Contest 441 (Promotion of Engineer Guild Fes)での成績：2544位
パフォーマンス：1209相当
レーティング：1056→1073 (+17) :)
#AtCoder #ABC441(PromotionofEngineerGuildFes) https://t.co/TAsf3Ma3Qx

[sA_3 @dpDKH]

#ABC441 ABCDE5完！
A:
X<=P+100にして1ペナ
B:
片方だけの文字が使われてるか判定
C:
ソートして小さい方からK個を酒とし、量が多い順に飲んでいく
D:
BFSでコストと回数を合わせて管理
L回目でS<=cost<=Tのときの到達点を記録
E:
ABCを1,-1,0として累積和
右から見て自身より小さいものをカウント

[sA_3 @dpDKH]

#ABC440
ABC3完
A:
X×2^Y
B:
idx付けてソート
C:
2Wで割った余りを連続するW個選ぶ
累積和を取ってW個の和を計算

[sA_3 @dpDKH]

#ABC439 ABCD4完
A:
やるだけ
B:
ループするまで繰り返す
C:
x,yそれぞれN^0.5までやる
D:
数の出現場所をdefaultdictで管理
j番目は5の倍数であり、その前後を考える
jの前後でj//5*7とj//5*3の個数を二分探索で調べ、それぞれ掛ける
E:
dp全然わからなかった、衰え

[sA_3 @dpDKH]

新年一発目ぞい！

[sA_3 @dpDKH]

#ABC436 ABCDE5完
A:
N-len(S)分だけ付ける
B:
書いてあるとおり
C:
置けたら置く、置けなかったら置かない
D:
BFS
ワープは別配列でアルファベット毎に管理
同じワープを通らなくていいことにずっと気づけなかった
E:
swapしたときに片方が揃うペアをUnionFindで結合し、同じグループのペアの個数が解

[sA_3 @dpDKH]

#ABC435
ABCD4完、これ3桁パフォまじ？
A:
N(N+1)//2
B:
全探索
C:
A[i+1]をmax(A[i+1],A[i]-1)で更新して、1になったら終了
D:
逆向きのグラフを管理して、黒になった点からの到達可能点をDFSで求める
到達可能点が塗られたときpassできるの気づかずペナ
E:
N<=10^9に気付かず遅延セグ木を頑張ってた

[sA_3 @dpDKH]

sA_3さんのＳｋｙ株式会社プログラミングコンテスト2025（AtCoder Beginner Contest 434）での成績：1873位
パフォーマンス：1181相当
レーティング：1119→1126 (+7) :)
#AtCoder #Ｓｋｙ株式会社プログラミングコンテスト2025（ABC434） https://t.co/U9icJsuY3c

[sA_3 @dpDKH]

てかEぜんぶUFでよかったじゃん

[sA_3 @dpDKH]

E:
存在しうる座標の種類を調べ、各ウサギが飛ぶ場所が他の誰とも重ならない場合はその場所に飛ぶ
場所が重なるウサギはUnionfindで管理し、各グループの匹数と座標の種類数の小さい方を採用

[sA_3 @dpDKH]

#ABC434
ABCD4完（22:44にE問題AC）
A:
1000*W/B
B:
各鳥の匹数と大きさの合計をそれぞれ管理
C:
次の目標の時間まででいける最高と最低を求め、目標を超えている場合は揃える
D:
二次元累積和で雲の重なりを見て、重なり1以外を全て消し、もう一度累積和を取って、各雲の中の重なり1の個数を調べる

[sA_3 @dpDKH]

あああああああああああああああああ
あと5分あれば

[sA_3 @dpDKH]

D見た瞬間にキツそうだと思って飛ばして大正解

[sA_3 @dpDKH]

E:
登場する整数をカウントし、セグ木に乗せる
(登場する整数×その個数)のリストも別のセグ木に乗せる

[0,L)は上のセグ木で和×L

[L,R)は下のセグ木で和

[R,500000)は上のセグ木和×R

[sA_3 @dpDKH]

#ABC432
ABCE4完久しぶりの勝ち‼️
A:
降順でソート
B:
先頭が0以外の最小数であとは昇順
C:
全員に小さい飴を配ったときの重さが全てmod(Y-X)で合同、かつ、このときの最大値に合わせたときに飴の個数が足りればOK
あとは大きい飴を増やせるだけ増やす