TEPLONE

九理化B3　主に石や大学の記録用
AtCoder始めました12/6～普段はpythonです
Algo緑

[TEPLONE @tepl0ne]

宝石や鉱物の記録用としてアカウント作りました～
あくまで趣味の範疇なのでお手柔らかに

[TEPLONE @tepl0ne]

#abc466
ABCDE5完(驚異の8ペナ???)
C インタラクティブやめてください
二分探索で質問回数足りずRE*2
尺取りでAC
D 逆から見てRもCもはじめての値ならそれを使う
使わないやつもちゃんと値を両方とも記録しよう(2ペナ)
E B-Aの配列を準備して重ならないように区間をK個選んだときの総和のmax
DPをした

[TEPLONE @tepl0ne]

#abc465
ABCD4完
E悲しみの5分over
Cはcollections.dequeで左にいれるか右にいれるかを繰り返す
D x,yのそれぞれで大きい方をKで切り捨てることを繰り返して2つが一致したときの操作回数
E 左からメモ化再帰で頑張った
使った数字を10bitで持ったらTLE、前計算で次の状態を全通り計算しといたらAC

[TEPLONE @tepl0ne]

ICPC緊張してきたー

[TEPLONE @tepl0ne]

#abc464

EってDFSでいいじゃーん
本番中に気付ければ...

[TEPLONE @tepl0ne]

#abc464

ABCD4完
最近実装が下手すぎる

B わけわからん計算量が軽い解法にして時間を浪費
制約小さいんやからさっさと書けばよいのに
C 毎時間ごとに色ごとの数を記録したらMLE
nextdpみたいにしたらAC
D DPをする
E 逆から処理するんだがTLE
解説のimos法は天才過ぎる

実装力がほしい

[TEPLONE @tepl0ne]

#abc463
ギリギリABCDE5完！
C 後ろからHの最大値を記録しといてLがTよりでかい要素のうちHの最大値を答える
D 実装下手すぎる、二分探索+区間スケジューリング
別のコード間違えて出して1ペナ
E ワープ用の頂点つくってダイクストラ

個人的に難易度E<D

[TEPLONE @tepl0ne]

#abc462
負けof負け
ABCD激遅4完

C Xが小さい順に見てyが最小を更新する回数<-遅い
D 0.5単位時間ごとの人数をimos法で記録、人数が2以上の区間について答えを加算<-WA
解法変えて[l, r-d]が被る区間を見てAC<-遅い
E 無駄な往復が必要となるケースを考えておらず時間切れ

精進が足りぬ...

[TEPLONE @tepl0ne]

@yiwiy9 ノ
https://t.co/DAiFKA74sT

[けんちょん@競プロ @drken_procon]

【告知・拡散希望】
ついに！ AtCoder NoviSteps 上で

・問題集「セグメント木」
https://t.co/aOlmyoeqdY

・問題集「Unioin-Find」
https://t.co/40rf9SgbGu

をリリースしました！！

ABC で頻出のテーマです
ぜひ易しい問題から難しい問題まで段階的に練習して、ABC で勝ちましょう！
#novisteps

[TEPLONE @tepl0ne]

#abc461
E 問題SortedMultiSetでACできた
誤読さえなければ...

[TEPLONE @tepl0ne]

#abc461
ABCD4完でした
C　実装沼りすぎた各色から最大値をM個取ったあとにpriority queueで残りを取る
D　O(H^2 *W)は通らないと思って時間を浪費
E　最終的な黒マスの数かと思ってた
クエリごとでした

ダメ元でD出したのは偉い

[TEPLONE @tepl0ne]

@rapca0 おめでとうございます！

[TEPLONE @tepl0ne]

#abc460
やったーー5完だーー！！
B (r1-r2)^2<=dist^2<=(r1+r2)^2
C 重いやつから順番に
D １回操作を行ったあと黒マスからの最短距離が偶数なら白奇数なら黒
最初の操作し忘れてペナ
E yの桁数をlとしてxの個数はn*gcd(m, 10^l -1)//m
高校数学では合同式とか整数が一番得意なのに遅いの反省

[TEPLONE @tepl0ne]

#abc459
ABCD4完でした
C ムズすぎておもろい
SortedMultisetで頑張った
D heapqで多い文字数から順に配置
連続はダメ
E 葉から順に根に向かってcombをかけていくだけではあるが実装終わらず

[TEPLONE @tepl0ne]

#abc458
Eは高校数学をまだ覚えてたから解けたけど、そのうちできなくなりそう
↓一般項

[TEPLONE @tepl0ne]

#abc458
A-E5完！　初めて5完したー
CはCの左と右の文字数のminを足す
Dは優先度キューを2本使って左半分の最大値と右半分の最小値を持つ。
Eムズくないすか
一般項出したけどホントかこれ？
(-1)^k * (y+1, k)(x-k+y, y)(z-k+y, y)
をk=0~min(x,y+1,z)まで足す
pythonのpowが逆元も計算できて助かった

[TEPLONE @tepl0ne]

#arc219
初参加ARCはAB2完でした
Aは10進表記したSのうち無い数字のbitを反転したものが答え

BはPの先頭が1,2,...kとなっているとき1<=i<=kについてN-iの総和が答え
Bはちゃんと証明できてないけど合ってたからまあよし

[TEPLONE @tepl0ne]

@rapca0 ありがとうございます！
共にARC頑張りましょう！
0完で茶色に戻る可能性もあるので不安ですが...

[TEPLONE @tepl0ne]

#abc457
入緑だー！
明日のARCに間に合ったー！

[TEPLONE @tepl0ne]

#abc457
24分ABCD4完で早解き成功！
初めての水パフォで入緑しました！！！

Dは答えで二分探索して必要な操作回数がK以下かどうか
Eは左端をSとする右端の最大値と右端をTとする左端の最小値で判定すればよいはずだが実装終わらず

考察あってそうだし実装できなかったの悔しいな