さいきんコンテスト中に解けなかった解くべき問題への知見です.
不定期で更新するかも(これは更新しないことを表していて
自分用のメモなので期待しないでね. 過激な主張が含まれている可能性があります.
AtCoder
AGC029 E - Wandering TKHS
全頂点について答えを求める → 親の頂点と子頂点の答えの差を求めたい
AGC028 C - Min Cost Cycle
円の種類数は3通り.
AGC027 C - ABland Yard
AABB型の閉路を探したくなるんですが, 1頂点を4頂点に増やして閉路検出あるいは条件を満たさない頂点を再帰的に削る
AGC026 E - Synchronized Subsequence
辞書順最大化→後ろから
AGC026 D - Histogram Coloring
制約をゆるくする方にDPを更新する
AGC025 E - Walking on a Tree
葉を削って1個小さい問題へ
AGC025 D - Choosing Points
最大安定集合を求める問題
→ 二部グラフしかない(重要)
2つの二部グラフの重ね合わせみたいなのは効率的に求まる. それぞれの二部グラフで彩色すれば パターンの塗り分けが表れる. 特に最も多いものは
以上.
AGC024 E - Sequence Growing Hard
以下の根付き木の構成するための操作列の個数を求める問題に帰着される.
- ある木の頂点に対し, その頂点に書かれた値よりも大きい値が書かれた頂点を接続する.
これはボトムアップに木を構築するDPで求めることが可能.
値が小さい方から dp[頂点数 i][根の値 j] = Σ dp[i - k][j] * C(i - 2, k - 1) * (Σ dp[k][l(>j)])
なにをしているかというと, 新たな根をつくるとする. この根より厳密に小さい値が書かれた部分木を, 新たな根の子にしている. 複数の子を根につなぐ可能性があるのでいい感じに更新.
AGC023 F - 01 on Tree
縮約しても損しない頂点同士から縮約していく(setとかでがんばる)
AGC023 B - Find Symmetries
えーこれなんで解けなかったんだろうね.
500点問題なのでせいぜいシミュレーションに何かをする程度で.
AGC023 C - Painting Machines
ちょうど 回 =
回以下 -
回以下.
AGC022 E - Median Replace
観察→条件を列挙
AGC022 B - GCD Sequence
構築ゲー(素振り)
2 と 3 は素なのですべての最大公約数は 1. あとは 2 と 3 のみを素因数に持つやつから選んできて, 和が 6 の倍数になるようにする. → 乱択が楽
AGC023 C - Remainder Game
コストが で最小コストを求めるやつは, 上位bitから決めていくしかなくて.
AGC021 C - Median Sum
それぞれの部分集合には対応する補集合がある. どちらかは総和の 1/2 を超えるため.
AGC019 B - Reverse and Compare
えーこれうくだね.
区間の操作なんですが, 両端だけみればよい.
AGC018 A - Getting Difference
ほんまに300点問題か？
gcd(全体)を構成できるなあと思うとできる.
AGC018 C - Coins
なんかひいてみて, 利益みたいなのをかんがえる.
AGC012 E - Camel and Oases
左から&右からDPする
AGC011 D - Half Reflector
周期性
AGC004 E - Salvage Robots
んーなんだこれ
AGC003 E - Sequential operations on Sequence
後ろから考える
変化する点をmapで持つと計算量が落ちる (x に対して mod a_i を順に log x 回とると0になる(a_i > x は無視).
AGC002 F - Leftmost Ball
えーこれ簡単だと思うんですが
DAGをかんがえてトポロジカルソートだと思うと終わり.
AGC002 E - Candy Piles
グリッド上の移動に帰着して, 各格子点の勝敗を観測するといい感じの構造になっている.
AGC001 F - Wide Swap
隣接swap辞書順最小化のときに、交換してはダメなペアに辺を張ると辞書順最小トポロジカルソートに帰着される
AGC001 E - BBQ Hard
複数の経路数の計算をDPでまとめるテク
ARC101 E - Ribbons on Tree
普通のDPを定義できても計算量は減らせない 包除原理をすることによって計算量が減ることがある
ARC101 F - Robots and Exits
とりあえず図にプロットしてみる
ARC099 E - Independence
貪欲では無理そうなときはDPを考える.
ARC098 F - Donation
逆から考える(重要).
上手く条件を言い換えると, 最小全域木っぽいなにかに帰着される.
ARC097 F - Monochrome Cat
不要な葉は, 前処理で削っておく.
一周まわるやつから, あるパスを削る問題に帰着できる.
ARC095 F - Permutation Tree
えーなんかこういうの直径しかなさそう(偏見).
ARC094 F - Normalization
自明な条件は mod 3 が一致する. それを踏まえて実験.
ARC093 E - Bichrome Spanning Tree
こういう意味不明なのは, 辺を何種類かのタイプに分類するしかないね.
SoundHound Inc. Programming Contest 2018 -Masters Tournament- E - + Graph
DFS木をつくって矛盾をチェックすると楽そう.
codeFlyer （bitFlyer Programming Contest）本選 D - 数列 XOR
自由度的なものを求めたくなる, xor → 行列
CODE FESTIVAL 2017 Final E - Combination Lock
えー意味不明なものでも階差をとってみることは重要で.
Codeforces
#505 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final) F. Disjoint Triangles
日本語でぐぐる
#493 (Div. 1) C. Sky Full of Stars
なんですよね, 初見さん.
#488 by NEAR (Div. 1) D. Compute Power
平均値の最小化 → 解の二分探索
x 以下にできるか → a/b を a-bx としたときに総和みたいなのが0以下になるか判定
DPするためにソートしたら嬉しくならないか.
Avito Code Challenge 2018 E. Addition on Segments
bool 値DPを戻したいみたいな気持ち → 適当に mod とりながら組み合わせの数を求める DP
あるいはセグメント木で log n 個に分解して高速化
#475 (Div. 1) D. Frequency of String
なんかよくわからないけど√にならないか疑う
CSA
#82 Water Supply
変な制約がついている → ラグランジュ緩和したいなあという気持ちになり二分探索
