AtCoder ABCのコンテスト中にACした解法の実装方針記事化前メモ
ABC279 6完
A:数える
B:連続部分列
C:転置+ソート
D:三分探索+念の為周辺も含めたmin
E:iごとの1の位置をsetで管理、入操作対象のsetに操作番号のiが含まれていたらそれだけ特別扱い
F:ボール集合をUnionFindで、ボール集合の代表が入っている箱を配列で管理して、操作を丁寧にやる
ABC280 4完
A:数える
B:先頭からの和を管理
C:初めて異なる文字が出た箇所
D:素因数分解して素因数ごとに頑張る
E:DPだなと思ったけど漸化式上手く立てられなくて乙
ABC281 4完
A:降順ループ
B:条件を丁寧に書く、数字最上位が0以外である必要があることに注意
C:合計値の余りを取る + 累積和を先頭から舐める
D:i番目までの数字のうちj個を用いた際の余りkのものの最大値でDP
E:計算量をNMから落とせなくて爆死
ABC282 4完
A:ループ
B:全ペア試す
C:"が出現したかをトグルで管理
D:連結成分内は白×黒、他連結成分とは全てペアにしてよい、一つでも二部グラフでない連結成分があったら無条件で0、最後に元々ある辺の数を引くのを忘れない
E:制約からN^2 log(N^2)なら通るとか、前計算N^2で、スコアでソートして貪欲か、などと考えるも確信に至る前にゲームオーバー
ABC 283 4完
A:a^b or a**b(言語によって選択)
B:配列でやる
C:00かどうかを先にチェック
D:「syntax = (syntax) syntax | char syntax | end」みたいなイメージで頑張る
E:(index, prev, cur)のタプルをキーに01bfs(prev, curは反転フラグのbool)まで考察したものの、実装バグらせてサンプル通らず
ABC 284 5完
A: reverse
B: 数えるだけ
C: 横着してUFでグルーピング
D: N^(1/3)まで素数列挙、最小の因数がpかqかで場合分け、sqrtは桁落ちが怖かったので二分探索した
E: dfs、カウントが上限に達したら探索打ち切り
F: ローリングハッシュだなと実装を始めたが間に合わず
ABC 285 4完
A: ×2 or ×2+1
B: 二重ループ
C: 26 ^ lenでIDのオフセット、s × 26 + cで現在のIDを計算して足す
D: T -> Sの遷移を張って後退解析
E: 区間DPぽいなー => 時間切れ
ABC 286 5完
A: 場合分け頑張る
B: 前２つを順に見ていく
C: 0 <= i < NごとにBsumを求め、min(A × i + Bsum)
D: Bを1 + 2 + 4 + … + 端数と分解してAと掛け算した値を値集合とし、boolでDP
E: (経由数, -1 × お土産の価値)でワーシャルフロイド
F: 中国剰余定理だな => 適切な集合を発見できず負け
ABC 287 4完
A: 数えて2倍して比較
B: Tをsetに入れてSの後ろ3文字をチェック
C: 訪問済みに再度来ないことをdfsでチェック(後に嘘解法と知る)
D: 前からと後ろからの、マッチしたかの累積和
E: trieもどきを実装しようとして終了
ABC 288 3完
A: 繰り返して足し算
B: 先頭からK個だけソート
C: UFで接続を管理し、途中で同じグループに属するものが出現した回数をカウント
D: 椅子が温まりました。累積和かな？と思ったらサンプル通らず。
ABC 289 4完
A: やる
B: 連続区間を反転、終わりの余りに注意
C: bit全列挙
D: NGリストを持ったBooleanDP、遷移バリエーションが少ないので素直に
E: n × nの頂点でbfs、遷移グラフを丁寧に作る => のが間に合わず乙
ABC 290 3完
A: 配列のindexとして読む
B: 前からk個のoは残す、残りは全部x
C: 昇順ソートして先頭からk個取る、先頭から見てindexと値が初めて異なる点のindex
D: Range Setが欲しいけど持ってないなぁ、作るか、からのゲームオーバー
ABC 291 5完
A: 先頭から数える
B: ソート、先頭n個末尾n個を削除、平均
C: それまでに訪れた座標をsetで管理
D: 2×2の組み合わせの遷移を先頭からDP、値が同じ場合は遷移できない
E: トポロジカルソートする時に、常に次に選べる候補が1件かチェック
F: 両側からdfsと気付いたときには残り30秒
ABC 292 4完
A: toUpper
B: イエローカードなら+1、レッドカードなら+2、判定は2以上か
C: (iとn-iの約数の個数の積)の合計
D: ufを使ってグループ化、グループの辺の数、チェックの3回ループを回す
E: 無駄に複雑に考えてしまって実装まとまらず
ABC 293 4完
A: 素直にswap
B: 前から順に呼ばれた番号のフラグを下げる
C: 素直にdfs、テストケースに遷移数最大のケースがある
D: UFで連結を管理、既に同じグループならそこでループが出来たと判定
E: v = a ^ (r / 2), v + v * a ^ ((r + 1) / 2)をベースにすればよいことに気づいたのが残り20秒