2021/2/27

競プロ E - Young Maids Caddi Programming Contest 2021(AtCoder Beginner Contest 193) - AtCoder Kaggle Tabular Playground Series - Feb 2021 | Kaggle

2021/2/26

競プロ E - Both Sides Merger D - Teleporter Kaggle Tabular Playground Series - Feb 2021 | Kaggle

2020/2/25

競プロ Problem - D - Codeforces D - Reversed LCS 組み合わせ最適化 Kaggle Tabular Playground Series - Feb 2021 | Kaggle

2021/2/24

競プロ E - Snuke Line Dashboard - Codeforces Round #559 (Div. 1) - Codeforces Kaggle Tabular Playground Series - Feb 2021 | Kaggle

2022/2/23

競プロ Dashboard - Codeforces Round #539 (Div. 1) - Codeforces Dashboard - Codeforces Round #704 (Div. 2) - Codeforces F - Minimum Bounding Box

2020/2/22

競プロ E - Stop. Otherwise...

2021/2/21

競プロ TechFUL AtCoder Regular Contest 113 - AtCoder

2021/2/20

競プロ D - Digit Sum E - Avoiding Collision E - M's Solution AtCoder Beginner Contest 192 - AtCoder Kaggle

2021/2/19

競プロ Dashboard - 2020 China Collegiate Programming Contest, Weihai Site - Codeforces Kaggle

2021/2/18

競プロ E - Weights on Vertices and Edges E - Or Plus Max 組み合わせ最適化 5.3 Codeforces Round #703 (Div. 2)に出た Kaggle

2021/2/17

毎日の進捗をのこします 競プロ D - Orientation B - Row to Column E - Bichrome Tree Kaggle Data Visualization 3 Tabular Playground Series - Feb 2021

Codeforces Round #700 (Div. 1)

A interactiveなので二分法を考えると、極小値が存在する区間を半分ずつ絞れることがわかる B1 数列を順番を保ったまま二つに分解し、それぞれランレングス圧縮した後の長さのmaxを求めればよい とりあえず適当な貪欲を書く 順位表を見て反例がありそうな気…

AtCoder Beginner Contest 189

C N^2未満の解法はぱっと思い浮かばない lごとに累積minを持ちながらl,rを全探索、でになるが、ABC-Cで10^8は見たことが無い の意図がよくわからない を見てxの全探索を考える xの値ごとに、全ての要素がx以上であるような区間の長さのmaxを求めればよい xを…

Codeforces Round #696 (Div. 2)

A 桁数を大きく→左の桁から数を大きく の順に貪欲にやる、いつもの B p,qを素数として、p^3かpqの形しかない p

キーエンス プログラミング コンテスト 2021

風呂の時計は10分進んでいるんですね~と思ってゆっくり風呂に入っていたら知らない間に風呂の時計が直っていて、10分遅刻(は?) A aとbの累積maxの積? より、となるのはb_iを使う場合のみ →aの累積maxを持ってDP B 小さい数からバケツに積んでいくことを…

Codeforces Round #695 (Div. 2)

A 98765...(一敗)(適当すぎ) 前の桁の数を貪欲に大きくしたいのでs[0]は9 このときs[1]は0か8になる、8の方がよい このときs[2]は7か9になる、9の方がよい →後ろが定まる 簡単枠でも考察の道筋はちゃんと意識しましょう() B 昔のAtCoderの問題で見たこと…

Codeforces Round #694 (Div. 1)

A セグ木を使えばできることはわかるが、流石に使わない楽な解法がありそうなので探す →思いつかなかったのでそのまま書く kが大きい人から順に、使えるうち最小のプレゼントを採用すればよいので、indexを持ったpairでRmQ+INFに更新 ソート済みの数列におい…

Codeforces Round #693 (Div. 3)

コンテストごとに書くことにします B n個の数を総和の等しい2つのグループに分割できること、簡単な必要十分条件があった気がするんだけど思い出せず... 知識があやふやで速度が落ちていてよくない D AとBのどちらかを選ぶ→Aを全て選ぶことにし、B-Aを選ぶ…

2020/12/28

AGC50 B 500なので区間DPを考える 操作によってできる列を観察すると、 flip対象となる連続する3つのマスは、同じ状態である必要がある →flipできる区間は、長さが3の倍数かつ、全て同じ状態 dp[色][l][r]:=[l,r)がすべてある色で塗られている状態から始めた…

2020 12/4~12/10 ポエム

kkt89.hatenablog.com ↑に触発されて自分も書くことにした。 12/3 16時起床(え?) 24時締切のAD変換レポートがそこそこ残っていたので、朝ご飯を食べて進める。 興味のある音声合成処理に関連した話で、内容自体は面白いんだけど、グラフ作成とデータ処理…

異常mod まとめ

この記事は Competitive Programming (1) Advent Calendar 2020 7日目の記事です。 ネタ記事です。 プログラミングコンテストでは、場合の数を大きな素数で割った余りを求める問題がしばしば出題されます。 ほとんどの場合、10^9+7や998244353などの素数が用…

2020/12/1

CF 1455 E 各点が正方形のどの位置に来るかを固定する(4!通り) 左下を(a,b)、正方形の長さをnとすると、 |a-x1|+|a+n-x2|+|a-x3|+|a+n-x4|+|b-y1|+|b-y2|+|b+n-y3|+|b+n-y4|の最小化になる nを固定すると、a,bは中央値にすればよい(いつもの絶対値の和の形、…

2020/11/30

CF1456 C リセットがない場合、大きい数を先に使うべき(寄与分が大きくなるので) k回リセットがある場合 →k+1個の0を用意しておき、一番大きい物に足すことにすればよい(priority_queueで管理)

2020/11/25

CF 1454 F 左側の右端lを固定する→maxが決まる →左側に入っていない[0,mx)を全て覆えるまで右側の左端rを伸ばす →右側のmaxが足りない場合、さらに伸ばす 真ん中のminが条件を満たしていればok 座圧してパケットを作る、indexを入れておく lを昇順に探索する…

2020/11/24

2020-2021 ACM-ICPC Brazil Subregional Programming Contest C hashにして考える Aの文字列を全てsetに入れておく Aの各文字列についてprefixを列挙する setに列挙したprefixがある場合、残った部分→対応する二つの文字列のidのmappingを作る Bについてもsu…

2020/11/17

CF 1447 D Aの部分文字列CとBの部分文字列Dを取り、(C,Dの最長共通部分列)*4-|C|-|D|を最大化したい 左端を固定したときの良い性質を探す 部分列の左右がLCSに含まれない限り、左右は削ってよい →でもあまりうれしくない、貪欲には手詰まり感があるのでDPを…

2020/11/15

CF 1446 A l=ceil(w/2)として、 l<=w_i<=wを満たすiが存在する→このiを使う そうでない時→w_i>wのものは無視し、w_i

2020/11/14

AGC37 B 取り方に人を割り当ててよい(あとでN!を掛けることにし、RGBの取り方を一番左で区別することにする) 制約の大きさからDPは厳しそう→貪欲を考える 左から漸次決定していく、S_1はaとして使うしかない S_1=S_2のとき→S_2はaとして使うしかない S_1!=…

2020/11/13

CF 1438 C 市松模様が条件を満たすことに思いを馳せると、偶奇で市松模様を作ればよい adhocにやろうとして迷走しすぎた CF 1438 D 0,1で考えると不可能条件は明らか 操作手順の構成に時間がかかりすぎた、変なことをしようとしてはまっていた感がある(惰性…

2020/11/11

第4回PAST O 最短経路問題やフローに落ちるのでは? グラフを書いてみる、(i+1)からiに辺を張って重なる区間を処理するテクが使えそう →負辺をなくしたい →負辺を使う状況を考えると、RmQでDPをすればよいことに気づく 頑張ると負辺のない最短経路問題に落ち…