けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

応用的な探索

AtCoder ABC 280 Ex - Substring Sort (銅色, 600 点)

Suffix Tree 上で DFS した。デバッグがめっちゃ大変だった! 問題へのリンク 問題概要 個の英小文字からなる文字列 が与えられる。 これら 個の文字列について、連続する部分文字列をすべて考える。重複を除かずに考えると 個ある。 これら 個の文字列を辞…

AtCoder ABC 077 D - Small Multiple (ARC 084 D) (橙色, 700 点)

これほどシンプルな問題がグラフ最短路問題になるのは感動的ですね! 問題へのリンク 問題概要 の正の倍数をすべて考えたときの、各桁の和として考えられる最小値を求めてください。 制約 うまく数字を並べるゲームと捉える の倍数をひたすら試す方法をまず…

JOI 二次予選 2021 E - スパイ 2 (難易度 10)

面白かった。 問題へのリンク 問題概要 人がいて、それぞれ「スパイ」か「非スパイ」かのどちらかである。 人のうち、何人かについてはスパイかどうかが予めわかっている ( で与えられる)。 個の証言がある。各証言は人 が証言者によってなされ、「人 はスパ…

AtCoder ABC 175 F - Making Palindrome (橙色, 600 点)

こういう重たい実装を確実にこなせるように...なりたい! 問題へのリンク 問題概要 個の文字列 が与えられる。これらを好きな順序で好きな回数だけ concat して回文を作りたい。ただし 番目の文字列を使用するコストは 1 回あたり である。 回文を作れるかど…

CADDi 2018 E - Negative Doubling (黄色, 800 点)

こういうのを確実に... 問題へのリンク 問題概要 1 以上の整数からなる長さ の数列 が与えられる。この数列に対して、以下の操作を好きな回数だけ好きな順序で行うことで広義単調増加となるようにしたい。最小回数を求めよ。 個の整数から 1 つ選んで -2 倍…

AtCoder ABC 153 F - Silver Fox vs Monster (水色, 600 点)

区間加算に対応したデータ構造の出番! 問題へのリンク 問題概要 体のモンスターがいて、それぞれ座標 にいて、HP は である。すべてのモンスターを倒したい。 1 回の魔法で、座標 を指定して、[ ] の範囲内にいるモンスターの HP をすべて ずつ減少すること…

yukicoder No.974 最後の日までに

めちゃくちゃ面白い!!! 問題へのリンク 問題概要 (意訳) 思いを寄せている先輩に 週後に告白したいので、その日までに先輩の好感度を最大化しておきたいです。最初、「所持金」と「好感度」はともに 0 です。毎週、以下のいずれかの行動を起こすことがで…

AOJ 2574 Magical Switches (JAG 模擬地区 2013 J) (900 点)

枝刈り探索が根本的に計算量改善することを示せることがある!!! 有名な例は最大独立集合問題に対する のアルゴリズムかなと。 指数時間アルゴリズム入門 from Yoichi Iwata www.slideshare.net 問題へのリンク 問題概要 下図 (公式解説より) のように な…

AtCoder ABC 142 F - Pure (青色, 600 点)

色んな方法がありそう。 問題へのリンク 問題概要 頂点数 、辺数 の単純な有向グラフが与えられる。なお各有向辺の向きをなくして得られる無向グラフも単純であるとする (有向辺 (u, v) があったら辺 (v, u) はない)。 このグラフの有向サイクルであって、有…

Codeforces Round #586 (Div.1 + Div.2) E. Tourism (R2200)

結構好き...だけど、完全既出だったらしい 問題へのリンク 問題概要 頂点 辺の連結な単純無向グラフが与えられる。各頂点 には重み が付いている。頂点 を始点としたウォークであって、ウォーク上のどの辺 に対してもその直後が ではない (直前に通った辺を…

Codeforces Round #584 (Div. 1 + Div. 2) F. Koala and Notebook (R2600)

勉強になった!!!!! 「辺番号または頂点番号が辞書順最小な最短路」を求める考え方が炸裂する感じ。 最短路として使われうる辺を列挙しておく (この考え方自体が典型) その辺をうまいこと活用しながら探索する という典型の流れになっている。 問題への…

MUJIN 2018 D - うほょじご (400 点)

いかにもよくわからない操作問題なので、難しいことは考えずに探索に走るべきな雰囲気 atcoder.jp 問題概要 正の整数 に対し、 で を 10 進表記してできる文字列を反転したものを 10 進表記に持つ整数を表す。 正の整数 が与えられる。 なる整数の組 であっ…