たれながし

色々雑多に書きます

緑diff精進 その3 (1/25)

解いた問題

  • ABC052 D - Walk and Teleport
  • ABC053 D - Card Eater
  • ABC239 E - Subtree K-th Max
  • ABC276 E - Round Trip
  • ABC177 E - Coprime
  • ABC115 D - Christmas
  • ABC194 E - Mex Min

ABC052 D - Walk and Teleport

atcoder.jp

感想 (解答中に考えたこと)

  1. 貪欲かDP。DPは制約的に無理そうなので貪欲の方針にする。
  2. 1------2-3-4 みたいな町で B = A + 3くらいの条件で考えてみると、234のまとまりにテレポートした方が良い。また、3にテレポートして 3 -> 2 -> 3(経由) -> 4とすると2 -> 3(経由)分が無駄になるので、一番近い場所にテレポートするのが良い。
  3. よって \rm{dist}_{i} = X_{i} - X_{i-1}として、 \sum_{i=2}^{N} \min \left\{\rm{dist}_{i} \times A, B\right\}で良さそう。

提出コード

atcoder.jp

ABC053 D - Card Eater

atcoder.jp

感想 (解答中に考えたこと)

  1. 何を消すかを管理すれば良い？
  2. 同じカードの枚数が偶数ならば2枚、奇数ならば1枚残る。
    • 操作の対象はカードの枚数を Mとして M \geq 3であって、操作1回につき2枚ずつ減るので
    • この時の操作の回数は \lfloor \frac{M-3}{2} \rfloor + 1 \; \left(M \geq 2\right)
  3. 偶数枚あるカードの種類の数を Lとする。
    1. Lが奇数のときは1枚まで減らせるため、残った1枚を最小あるいは最大とできるように3枚を選択すれば良いので、操作回数は \lfloor \frac{L}{2} \rfloor + 1。
    2. Lが偶数の時は2枚まで減らせる。ここでこの2枚を同時消しできる可能性があるので、偶数枚あるカードのうち最小値 L_{\rm{min}}および最大値 L_{\rm{max}}を残すように選択する。 \left(L_{\rm{min}}, L_{\rm{max}}\right)に含まれる奇数枚のカードが存在すれば操作回数は \lfloor \frac{L}{2} \rfloor。存在しなければ \lfloor \frac{L}{2} \rfloor + 1
  4. 操作回数を Kとすれば、 N - K \times 2が残るカードの枚数。

提出コード

atcoder.jp

ABC239 E - Subtree K-th Max

atcoder.jp

感想 (解答中に考えたこと)

  1. Kの制約がそこまでキツくないので、部分木を O(1)で出力できれば十分そう。
  2. 木はとりあえずlist[set[int]]で管理し、根からBFSで子 -> 親のパスを消し飛ばしておく。
    • これは不要で、DFSの引数に親を追加し、親 = 子の場合にcontinueすれば良い。
  3. DFSで根から探索し、各ノードに上位20件の数字のリストを持たせていく。
    • つまり葉であれば[X[n]]を返し、そうでなければ子ノードの返り値とX[n]を合わせて降順ソート & limit = 20で良い
  4. あとは O(1)で答えが出る。テーブルの構築にはDFSでの構築部分とクエリ部分で O(Q + NK\log K)かかってると思う(たぶん)。

提出コード

部分木といえばオイラーツアーがあったなと反省……。 atcoder.jp

ABC276 E - Round Trip

atcoder.jp

感想 (解答中に考えたこと)

  1. BFSでvisitedがTrueのものがあればYes? しかし戻るパターンを除去するのが面倒くさい。
  2. だらだら実装してサンプルが合わないので解説を少しだけ読む。色分けかぁ……これは思いつきたい。
  3. visitedをbooleanではなく数値で管理し、Sを#扱いにして4方向にBFSするだけになった。

提出コード

atcoder.jp

ABC177 E - Coprime

atcoder.jp

感想 (解答中に考えたこと)

  1. setwise coprimeはgcd(*A) == 1で一発で判定可能。つまりpairwise coprimeの判定が肝になる。
  2. 当然のことながら全探索は無理。ところで、 \gcd{\left(a, b\right)} =1って \frac{a}{b}が既約分数なので、共通の素因数を持たないと解釈できそう。
  3. つまり集合 Aの素因数を全部調べて重複があるかを判定すれば良い。
  4. エラトステネスの篩をつかって \max{\left\{A_i\right\}}\left(=A\right)までの素数を列挙し、素数をkeyとしてkeyが素因数として出てきたかを持つboolをvalueとして持つHashMapを用意する。素因数分解は O(\sqrt{N})のものを使う。素因数分解については指数の要素はいらないので、素因数の集合を返すように改造しておく。
  5. あとは出てきた素因数をHashMapに記録し、既にTrueのものがあればpairwiseになる。
  6. これ計算量 O(N\sqrt{A})で 10^9じゃないですか？落ちそう -> ACした。

提出コード

エラトステネスの篩で素数を列挙している途中で、 D\left[n\right]:=nを落とした素数とすることで試し割り(2 ~ \sqrt{N}まで割る方法)をする必要がないので O(\log A)でできるらしい。天才では？？？？ atcoder.jp

ABC115 D - Christmas

atcoder.jp

感想 (解答中に考えたこと)

  1. 明らかに再帰関数の実装を求めていそうな問題。とはいえバーガーの高さとパティの枚数は普通に漸化式を解けば O(1)で出る。
  2. レベル nバーガーをg[n]、バンズをB、パティをPとすればレベル nバーガーはBg[n-1]Pg[n-1]Bと書ける。
  3. レベル nバーガーに対して、 Xが下部のレベル n-1バーガーの領域を超えている場合のみその分のパティを加え、その分の高さを Xから引いていけば求まる。
    • レベル kバーガーの区切りが良いところから始める必要があるので。真ん中のパティを特別に扱わないとバグる。
    • パティが存在する領域よりも高い Xである場合、レベル0バーガーの探索を終えても Xは0よりも大きくなるので、ループの条件に レベル >= 0が必要 (1敗)

提出コード

正直上記の説明じゃ何も伝わってないと思う……説明難しい……。 atcoder.jp

ABC194 E - Mex Min

atcoder.jp

感想 (解答中に考えたこと)

  1. しゃくとりっぽく、区間をずらした際に出ていく数字・入る数字を管理すれば高速で \rm{mex}求められそうじゃない？(根拠なし)
  2. 使える数字をSortedListで管理し、区間にある数字をHashMapで管理する。区間にある数字について、個数が0になったものがあればSortedListにその数字を追加し、個数が1以上になったものがあればSortedListからdiscardする。
  3. あとはSortedListの先頭をchminすれば良い。これで計算量は O(N\log N)なはず。定数倍の遅さにビビりながらsubmit。

提出コード

atcoder.jp