ei1333の日記

ぺこい

えー

さいきんコンテスト中に解けなかった解くべき問題への知見です.

不定期で更新するかも(これは更新しないことを表していて

自分用のメモなので期待しないでね. 過激な主張が含まれている可能性があります.

AtCoder

AGC026 D - Histogram Coloring

制約をゆるくする方にDPを更新する

AGC025 D - Choosing Points

最大安定集合を求める問題
→ 二部グラフしかない(重要)

2つの二部グラフの重ね合わせみたいなのは効率的に求まる. それぞれの二部グラフで彩色すれば  {2 \times 2 = 4} パターンの塗り分けが表れる. 特に最も多いものは  {\frac N 4} 以上.

AGC024 E - Sequence Growing Hard

以下の根付き木の構成するための操作列の個数を求める問題に帰着される.

  • ある木の頂点に対し, その頂点に書かれた値よりも大きい値が書かれた頂点を接続する.

これはボトムアップに木を構築するDPで求めることが可能.

値が小さい方から dp[頂点数 i][根の値 j] = Σ dp[i - k][j] * C(i - 2, k - 1) * (Σ dp[k][l(>j)])

なにをしているかというと, 新たな根をつくるとする. この根より厳密に小さい値が書かれた部分木を, 新たな根の子にしている. 複数の子を根につなぐ可能性があるのでいい感じに更新.

AGC023 B - Find Symmetries

えーこれなんで解けなかったんだろうね.

500点問題なのでせいぜいシミュレーションに何かをする程度で.

AGC023 C - Painting Machines

ちょうど  {K} 回 =  {K} 回以下 -  {K - 1} 回以下.

AGC022 B - GCD Sequence

構築ゲー(素振り)

2 と 3 は素なのですべての最大公約数は 1. あとは 2 と 3 のみを素因数に持つやつから選んできて, 和が 6 の倍数になるようにする. → 乱択が楽

AGC023 C - Remainder Game

コストが  {2^k} で最小コストを求めるやつは, 上位bitから決めていくしかなくて.

AGC021 C - Median Sum

それぞれの部分集合には対応する補集合がある. どちらかは総和の 1/2 を超えるため.

AGC019 B - Reverse and Compare

えーこれうくだね.

区間の操作なんですが, 両端だけみればよい.

AGC018 A - Getting Difference

ほんまに300点問題か?

gcd(全体)を構成できるなあと思うとできる.

AGC018 C - Coins

なんかひいてみて, 利益みたいなのをかんがえる.

AC015 C - Nuske vs Phantom Thnook

それぞれの連結成分を木とすると, 頂点数 - 辺数 = 木の数なんですね

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

 {\sum_{i=0}^{n} {}_n \mathrm{ C }_i x^i = \sum_{i=0}^{n} {}_n \mathrm{ C }_i x^i 1^{n-i} = (x+1)^n} なんですよね, 初見さん.

#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

変な制約がついている → ラグランジュ緩和したいなあという気持ちになり二分探索