ABC245F サイクルに到達出来る頂点の個数を求める． そうでない，無駄な頂点を省いていく． 具体的にサイクルを求めたりする必要はなく， 出次数が 1以上の頂点だけ通り続ければサイクルになる． 出次数が 0の頂点 \(v\) に到達しても，サイクルには到達でき…

\( \def \ra {\rightarrow} \) ABC257F テレポータの行き先を超頂点 \(X \not\in N\) とおく． \(X\) を頂点として加えたグラフを考える． これにより，テレポータの行き先を保留した状態でグラフを構成できる． \(X\) の行き先を \(i\) としたいときは， コ…

ABC252F 切り方は tree に対応する． つまり，最適な切り方を探すのは，最適な tree を探すことに対応する． しかし，tree 全体は探索しても間に合わない． Tree の葉に値を割り振って，parent に child の値を足していくと考える． すると，葉を除いた頂点…

ABC248F 状態をまとめて DP． 連結しているかどうかが重要． 今 i番目の コ の字の部分を決めようとしているとする． つまり，左側は既に決まっているとする． 上の頂点と下の頂点が，左側において連結しているかどうかだけが， 今後に影響する． \(dp_{i,k}…

ABC254F 長方形領域における GCD を求める問題． 2次元の計算を 1次元に落とす． 気持ちとしては，和や差によって GCD が変わらないことを利用して， 左上を基準のマスとして，残りは差分で計算したい． 行と列の差分を別々に計算することで，計算量を減らす…

ABC315F スキップした頂点が多いほどペナルティが大きくなる． スキップできる箇所はそんなに多くないのがポイント． スキップしないで頂点を通った場合，最大で \(2^{1/2} 10^{4}*n \leq 1.5 \cdot 10^{8}\). ペナルティがこれよりも大きい場合，ペナルティ…

ABC315参加． 2週間連続でやらかしてレーティングが合計100減った． これなら試験に参加しなければよかったと感じる． ランクが上がったところで気持ちよく終わっていればよかった． 勉強を続けても，試験は受けないほうが精神面でプラスだった． AtCoder の…

ABC315D あまり綺麗な解法がない．全探索によるシュミレーションを高速化する問題． 基本は， 何を全探索するか． 升目の全探索は，削除の処理を考えると TLE である． たとえば，aaaaabccccbdeeebdfghのような形が最悪ケース． 対策：色が 26種類と少ないこ…

ABC315E トポロジカルソート． 本問題は DFS, BFS どちらでも可能である． どちらでも良いときは，DFS の方が実装が軽いケースが多い． DFS のトポロジカルソートは，帰りがけ順で vertex を並べて， 最後に reverse. 試験本番では BFS で実装した． どこが…