2022-01-01から1年間の記事一覧
AtCoderに出た ABCARCAGCそれぞれ一回サボった 青上位を相変わらずウロウロした どうにか2200ぐらいになりたいもんだけどyukicoderに出た 去年から出てるけど、できるだけリアルタイム参加こどふぉに出るようになった 停滞した。薄橙は青上位なら余裕と聞い…
前半手間取りすぎ ■A. Koxia and Whiteboards priority_queueで一番小さいものを変更する ■B. Koxia and Permutation 10,1,9,2,8,3,7,4,6,5みたくする ■C. Koxia and Number Theory 等しい要素があればNG 4,6,5,7みたいなのがあったときもNG 100以下の素数を…
上級問題 ★は5段階評価 11.★★ 問題の設定を理解するのにめちゃめちゃ時間がかかる 大きいものから考えていく12.★ 2冪で考える 2048枚あったとして96回の操作が経過したところからスタートしたと思えばいい (2^10-1)-9692713.★ 2*2のマスは1999*2001個数ある…
上級問題 ★は5段階評価 1.★★ 合計を二通りの方法で表す。 全員の得点の合計は、試合の結果に関わらず一試合で1なので(0+1,1/2+1/2,0+1) Σai=Binom(n,2) 下位同士での勝ち点の合計はBinom(10,2)であり、これが合計の半分になることより Σ下位=Binom(n-10,2)*…
■A. Joey Takes Money n,1,1,1,1,1, ■B. Kill Demodogs ジグザグが最適 ■C. Even Subarrays 累積xorをmapで管理する ■D. Valiant's New Map ABCでやった気がする。 二分探索 https://atcoder.jp/contests/abc203/tasks/abc203_d ■E. Graph Cost 上から貪欲 ■…
■A - Power ぱわー ■B - First Query Problem くえり ■C - Cash Register やるだけ ■D - Scope 割と面倒セグ木に載せた ■E - Don't Isolate Elements dp[i][j][k]:=iまで見た2つ前は反転かどうか、1つ前が反転かどうか 結構面倒 ■F - Permutation Distance…
Dで勘違いして延々と時間を ■A - Generalized ABC for ■B - Let's Get a Perfect Score bitで持ってpopcountしようとか思ったけど普通に ■C - String Delimiter はい ■D - Make Bipartite 2 問題の意味を勘違いするという酷さ 連結部分ごとに二部グラフ判定…
■A - Count Down はい ■B - Sandwich Number はい ■C - Circular Playlist sumで割ったあまりで適当に ■D - Max Multiple dp[i][j][k]:=i番目まで見た、j個使った、余りがkの最大値 ■E - Least Elements 面倒になったのでセグ木にのせた ■F - Xor Minimizati…
組合せ論の精選 基本問題51 解法メモ 01. 簡単な計算をします02. 丁寧に計算をします03. 二項係数の和が2^nになること 合計が奇数なら奇数が奇数個あること04. 包除原理をします05. 丁寧に計算をします 二問目とほぼ同じ06. 連続する同性をブロックにしてみ…
維持できたからいいや ■A - My Last ABC Problem 操作して減らす必要があるのは? 連続する文字が異なるものの個数。 これを0にする必要がある。 4個以上異なる場所があるときは簡単に2つ減らせる 3個のとき、2個のときは少し場合分けして考える ■B - Arrang…
AGC前に黄色復帰 ■A - Pawn on a Grid 数える ■B - Inverse Prefix Sum 引く ■C - Extra Character 前からチェック ■D - Factorial and Multiple 二分探索した ■E - Critical Hit 期待値dpとてもかんたん ■F - Pay or Receive ダイクストラに毛を生やす ■G -…
プラマイゼロ ■A - wwwvvvvvv かぞえる ■B - LOOKUP std::string find ■C - RANDOM はい ■D - Freefall 傾きを二分探索しました ■E - Cheating Amidakuji 頑張る ■F - BOX dsuで頑張る ■G - At Most 2 Colors 時間なかった dpをする 遷移を考える 頭k項は適…
■A. Doremy's Paint 全部取る ■B. Doremy's Perfect Math Class 最大/gcd ■C. Doremy's City Construction n/2が確実に作れる どこかで分けて完全二部マッチング ■D. Doremy's Pegging Game 得意分野 残る部分の両サイド 最後に取るものの候補 を考える。
青に追い返されました ■A - Seat Occupation 空、埋、空、埋のように埋めていき、最後の2人組が座れなかったらNo ■B - Pass on Path 同じ場所からスタートするのが一番効率がいい ■C - Pivot これ難しいですわ
ratedじゃなくなった瞬間ゴミペナを多発する件について ■A - Shift はい ■B - Misjudge the Time ペナした 適当にシュミレーションする。 ■C - FF mapとsetで管理 ■D - All Assign Point Add mapで管理 ■E - Grid Filling 二次元累積和をn回する ■F - Shirit…
前に書いた入黄の記録 黄色になりました - kwm_t ■黄色に復帰しました(2回目) 復帰しました。 5ヶ月かかりました。 ■やったこと(通算) AtCoder:2874問 codeforces:535問 yukicoder:481問 ■やったこと(ここ一年) codeforcesにでるようになりました。 OMCにで…
修正前の問題文:「a,b,c,dが相異なる」の場合以下の条件を満たす通り数dp[n]を考える 1:n人存在する 2:n人全てが、いずれかの人と赤or青の糸で結ばれている 3:問題の2条件と最終的な状態の条件を満たす。以上を満たすdp[n]が求まれば、元の問題の答え…
■A - ^{-1} やる ■B - Playing Cards Validation 丁寧に ■C - Ladder Takahashi 座圧しました ■D - Takahashi's Solitaire 2周分持って尺取法 ■E - Crystal Switches よく読むと01bfs ■F - Sorting a Matrix 行の入れ替えはeasy 列の入れ替えは? 成約を無視…
■A - Rightmost はい ■B - Adjacency List いつもどおり ■C - Previous Permutation std::prev_permutation というのがあるらしい(は?) ■D - Divide by 2 or 3 e*2^p*3^qとして eが全て一致が必要最小は最小のpqに合わせればいいので ■E - Round Trip なん…
■A - Find Takahashi indexとpairで持ってsort ■B - ABC-DEF mint ■C - Counting Squares 面倒三点固定してごちゃごちゃした ■D - Yet Another Recursive Function メモ化再帰 ■E - Sugoroku 4 やるだけ ■F - Erase Subarrays dp[i][j][k]:=i番目まで見た、…
■A. Factorise N+M n+n ■B. Jumbo Extra Cheese 2 max(a[i],b[i])でsort ■C. Bricks and Bags 適当に分けた ■D. Knowledge Cards 未処理がn*m-4個以下ならOk ■E. Hanging Hearts わかんねぇ 落ち着いてやると木dp
■A. Bestie 難しくないですか? a[i]全ての1からnから任意で選んだもののgcdが1になればいい 後半パートは前計算する でも、3で足りるらしい ■B. Ugu 前から貪欲 ■C1. Sheikh (Easy version) 区間を伸ばしても単調増加することがわかるので セグ木上で二分…
■A - Batting Average 別に誤差とか気にしなくていいらしい ■B - Line Sensor 数える ■C - Ameba グラフ ■D - Robot Arms 2 dp ■E - Booster 巡回セールスマン ■F - Fishing 区間の左端になる物を固定した上でイベントソート ■G - Security Camera 3 方向は…
■A. Cowardly Rooks 愚直を書いたが、初期状態が成立しているのでギャグ ■B. Death's Blessing ΣA+ΣB-maxB ■C. Number Game 制約が緩いのでシュミレーションする。 ■D. Counting Arrays 111111以外駄目 ■E. Cactus Wall 01bfsを行う 壁の建て方は、壁を伝っ…
■A - Equal Hamming Distances s[i]=t[i]なら0でいい 異なるところが奇数個ならNG あとは適当に貪欲 ■B - A 前から管理dsuを使うと楽 ■C - 01 Game Grundy数にそろそろ慣れろ ■D - Binary Representations and Queries Xiが異なるクエリは可換であることがす…
点数の割に難しくない? ■A. Maxmina 1があれば出来る ■B. Rebellion どこかで区切って それより左の0の個数とそれより右の0の個数のmaxのmin ■C. Permutation Operations 絶対作れそうな気がするので貪欲に差を殺していく ■D. Paths on the Tree 単なる木dp…
■A - A Recursive Function はい ■B - Broken Rounding 丁寧に ■C - (K+1)-th Largest Number lower_bound ■D - LRUD Instructions 実装が重たいlower_bound ■E - Notebook 親情報を持った子を持つ木を作っていく。 ■F - Hammer 2 実装重いけどただの区間dp …
■A. Sum sortとかしなくても愚直に ■B. Increasing setで種類数 ■C. Stripes 縦に全部BなのがあればBそうでなければR ■D. Coprime 計算量怪しいけど値で全探索 ■E. Scuza 二分探索 ■F. Smaller sortしていいんだということを読み取るまでに時間がかかる。 A…
■A - Compare T-Shirt Sizes やる ■B. Funny Permutation ans[i] = i + 1 rotate(ans.begin(), ans.begin() + 2, ans.end()); ■C - Minimize the Thickness 最初から何個取るか ■D - Masha and a Beautiful Tree 根っこから頑張る ■E. Sending a Sequence Ov…
■A. Make A Equal to B 違うとこを全部直すか、数を揃えてソートするか ■B. Playing with GCD a[i]とa[i+2]のgcdがa[i+1]を割きる ■C1. Good Subarrays (Easy Version) セグ木上で二分探索しました。 ■D. Equal Binary Subsequences 2つ刻みに考える典型