kwm_t

kwm_tのメモ

ABC346

■A - Adjacent Product はい ■B - Piano 開始地点全探索 ■C - Σ setで管理しながら適当に ■D - Gomamayo Sequence dp[i][j][k]:=iまでみた、最後がj、iとi+1が一致するものがk個 ■E - Paint 後ろから見る ■F - SSttrriinngg in StringString にぶたん、して…

ARC174

■A - A Multiply 累積和 ■B - Bought Review 賄賂のパターンは3通り ■C - Catastrophic Roulette dp[i] = p0 * dp[i-1] +p1*(1+dp[i-1])+p2*(1 +dp[i]) + p3*(dp[i-2]) ■D - Digit vs Square Root 実験 ■E - Existence Counting 上手に数え上げ

ABC345

■A - Leftrightarrow 作れ ■B - Integer Division Returns やれ ■C - One Time Swap s[i]!=s[j]な数と s[i] == s[j]なものが存在するか ■D - Tiling 左上からおいていく 未使用のものをbitで管理 ■E - Colorful Subsequence top2だけ持っておけばいいという…

Starters 125 Division 1 (Rated till 6-Stars)

■Binary Minimal 1の数を数えて適当に ■Bucket Game 実験コード書いてエスパー 1があればそれを取るのが最善 あとは残りの偶奇で決まる ■Operating on A 操作順は関係ないという大胆予想を立てる 前から貪欲でOK ■Manhattan Xor 区間Xorをライブラリにして…

ABC344

■A - Spoiler substrで適当に ■B - Delimiter whileで適当に ■C - A+B+C 全探索してset ■D - String Bags dp[i][j]:=袋iまで見たj文字目まで作った ■E - Insert or Erase 双方向リストを適当に作る ■F - Earn to Advance 所持金を増やすの箇所のP[i][j]は単…

ABC343

■A - Wrong Answer 0か1か ■B - Adjacency Matrix 適当 ■C - 343 全部試す ■D - Diversity of Scores mapでガチャガチャ ■E - 7x7x7 面倒枠 一つ固定して残りの2つの位置関係をすべて試す ■F - Second Largest Query セグ木にそのまま乗る。 ■G - Compress …

Codeforces Round 929 (Div. 3)

■A. Turtle Puzzle: Rearrange and Negate Σabs(a) ■B. Turtle Math: Fast Three Task 一個消すかaddを2回するか ■C. Turtle Fingers: Count the Values of k 適当にやる ■D. Turtle Tenacity: Continual Mods gcdで割って1が2つ以上あればng ■E. Turtle vs.…

ABC342

■A - Yay! map ■B - Which is ahead? map ■C - Many Replacement それぞれの文字の初期->終了を ■D - Square Pair サンプルが優しい 素因数分解して肩に奇数が乗ってるものを取り出す ■E - Last Train ダイクストラっぽく ■F - Black Jack 遅延セグ木区間加…

Educational Codeforces Round 162 (Rated for Div. 2)

■A. Moving Chips 後ろから貪欲 ■B. Monsters Attack! 攻撃はstockしておく ■C. Find B 区間内の1の数*2と区間内の1以外の数の和と比べる ■D. Slimes 二分探索。 322222みたいなときに注意 ■E. Count Paths ABC340-Gの簡単版

ARC172

■A - Chocolate 再帰的に考えていく ■B - AtCoder Language 連続するn-(k-1)文字はすべて異ならないといけない ■C - Election 実験をすると、開票結果の結果列の振る舞いがわかる ■D - Distance Ranking これはなに? ■E - Last 9 Digits これはなに?

ABC341

■A - Print 341 for ■B - Foreign Exchange 前から ■C - Takahashi Gets Lost 開始位置全探索 ■D - Only one of two 二分探索 ■E - Alternating String セグ木 ■F - Breakdown ナップサック ■G - Highest Ratio CHTと二分探索。傾きが単調なので動的に扱える…

Codeforces Round 924 (Div. 2)

■A. Rectangle Cutting // a,b->a/2,2b // a,b->2a,b/2 ■B. Equalize 重複消してsortしてlower_bound ■C. Physical Education Lesson // (2k-2)* m + x = n // (2k-2)*m+(2k-2)-x = n; 適当に ■D. Lonely Mountain Dungeons 分割数固定して均等に分ける 面倒…

ABC340

■A - Arithmetic Progression while ■B - Append vector ■C - Divide and Divide メモ化再帰 ■D - Super Takahashi Bros. ダイクストラ ■E - Mancala 2 遅延セグ木 ■F - S = 1 拡張gcd ■G - Leaf Color 木dpとマージテク 演算的にばf(a,b)=(a+1)*(b+1)-1

ARC171

■A - No Attacking ルークの置く場所を考える ■B - Chmax セグ木とdsu持ち出したが不要っぽい? 挿入dpの要領 ■C - Swap on Tree 頂点ごとに独立に考えられる 2乗の木dpみたくなる ■D - Rolling Hash 累積和っぽくしょりすればいいのはなんとなくわかったが…

焼きなましテンプレート

#include <bits/stdc++.h> //#include <atcoder/all> //using namespace std; //using namespace atcoder // 時間管理 class TimeKeeperDouble { private: std::chrono::high_resolution_clock::time_point start_time_; double time_threshold_; double now_time_ = 0; public: TimeKeep</atcoder/all></bits/stdc++.h>…

ABC339

■A - TLD はい ■B - Langton's Takahashi 実装面倒系。 ■C - Perfect Bus シュミレーションして最小が負になるなら補正 ■D - Synchronized Players dpをする ■E - Smooth Subsequence セグ木 ■F - Product Equality 解けるわけ無いだろこれと思ってboost使っ…

ABC338

■A - Capitalized? やる ■B - Frequency やる ■C - Leftover Recipes 料理Aを作れる個数を全探索する ■D - Island Tour どの橋を壊すと最短と比べてどれだけコストが掛かるかを考える imosでいいが面倒なので遅延セグ木で ■E - Chords 典型90のNo17を引っ張…

AHC短期メモ

AHC短期メモ 解説記事を読んだ上での改善含むので自力ではない ■AtCoder Heuristic Contest 002 時間:004:00 概要:フィールド上を与えられた初期位置移動してポイント稼ぎ perf:3512(1位) やったこと:焼きなまし 初期解をdfsをすることで発見する 初期解…

ARC170

■A - Yet Another AB Problem 貪欲にペアを決めていく ■B - Arithmetic Progression Subsequence 左端を固定したとき最低どこまで伸ばせば等差数列が作れるかを考える ■C - Prefix Mex Sequence これ解けないの駄目 dp[i][j]:=iまでみた、j種類使ったでdp

ABC337

■A - Scoreboard 足す ■B - Extended ABC 空文字でもいいらしい ランレングス圧縮の要領 ■C - Lining Up 2 vectorで適当に ■D - Cheating Gomoku Narabe 2d累積和 ■E - Bad Juice 有名問題 ■F - Usual Color Ball Problems 適当に管理すると解ける ■G - Tree…

Educational Codeforces Round 161 (Rated for Div. 2)

■A. Tricky Template 各文字を確かめる ■B. Forming Triangles xxxかxyyみたいになる ■C. Closest Cities 累積和 ■D. Berserk Monsters シミュレーションをする 左右のindexを持っておいて更新があったものだけ次のターンでシミュレーション ■E. Increasing …

Codeforces Round 920 (Div. 3)

■A. Square 長さの種類は2つ ■B. Arranging Cats 01と10の多い方 ■C. Sending Messages dp ■D. Very Different Array ソートして適当に ■E. Eat the Chip O(1)算数 ■F. Sum of Progression 丁寧に斜めimos

ABC336

■A - Long Loong はい ■B - CTZ ライブラリ ■C - Even Digits 5進数 ■D - Pyramid やる ■E - Digit Sum Divisible 桁dp ■F - Rotation Puzzle 半分全列挙 ■G - 16 Integers BEST theorem 有向グラフに含まれるオイラー閉路の数え上げ 閉路なのがポイントで順…

Codeforces Round 919 (Div. 2)

■A. Satisfying Constraints 適当にlower_boundとかで ■B. Summation Game どこまでアリスが消し去るかを全探索 ■C. Partitioning the Array 差のgcd ■D. Array Repetition 操作2の回数は60回もすれば1e18を超えるので丁寧に ■E. Counting Binary Strings d…

ABC335

あけおめ ■A - 2023 はい ■B - Tetrahedral Number 全探索 ■C - Loong Tracking 逆順を持っておく ■D - Loong and Takahashi ぐるぐる ■E - Non-Decreasing Colorful Path unionfindして閉路けしてdp ■F - Hop Sugoroku 平方分割 ■G - Discrete Logarithm Pr…

2023年

■AtCoder AGCを何回かサボった 青に落ちても黄色にはすぐ戻れるようにはなった。 2200(国内アクティブ200位程度)ぐらいになりたいね■yukicoder できるだけリアルタイム参加 一時期過去問埋めまくってたけど飽きちゃった■Codeforces 薄橙になったのをいいこと…

ABC334

ここ100年で一番体調が悪かった ■A - Christmas Present if ■B - Christmas Trees 頭が回ってないのでceilとfloorを負にも対応して関数化したのを忘れるなど ■C - Socks 2 頭が回ってないので重実装をする ■D - Reindeer and Sleigh upper_boundは頭回ってな…

ABC333

■A - Three Threes for ■B - Pentagon 比較 ■C - Repunit Trio 想定がよくわからない next_permutationを3発 ■D - Erase Leaves 木dp ■E - Takahashi Quest 後ろからシミュレーションして 前からもシミュレーション ■F - Bomb Game 2 dp[i][j]:=i人残りj番…

Starters 112 Divison 1 (Rated till 6 Stars)

■Maximise Sum 1が連続してるなら最後以外はIDK 0が一人でもいればNO ■Cursed Indices ちょっとだけ難しい 前から可能な限り最適に作る ■Yet Another Array Game s=0 取れる要素が決まる s=1 取る個数を全部試す ■Permutation Construction 実験すると 7のと…

ABC332

■A - Online Shopping if ■B - Glass and Mug 問題文通りにやる ■C - T-shirts やる ■D - Swapping Puzzle next_permutationを二重に ■E - Lucky bag dp[i][j]:=集合iをj個の集合に分けた時の分散の最小値 遷移はO(3^n)で自明。 なんと本質は、浮動小数点誤…