前処理
まさに遅延評価セグメント木の練習問題！！！ 問題へのリンク 問題概要 長さ の文字列 S がある。 最初は のすべての文字が 1 である。以下の 回のクエリに答えよ。 各クエリは整数 が与えられる () の 番目から 番目までをすべて に書き換える を数値とみな…
これは天才！！！ 問題へのリンク 問題概要 一直線上に 個の点が順に並んでいる (座標が )。 個のクエリが与えられる。 各クエリでは区間 () が与えられる 個の点のうち のみを取り出してできる 個の点について以下の問に答えよ 与えられた点集合から、どの …
フローって確かに天才パズルな問題はすごく天才的なんだけど、典型的な問題もたくさんある！ 問題へのリンク 問題概要 下図のような の盤面が与えられる。盤面は通路 ('.') と壁 ('#') がある。いくつかの通路にはコマ ('o') が配置されている。 コマは下方…
この問題に似てた drken1215.hatenablog.com 問題へのリンク editorial 問題概要 の順列 を最適化したい。以下の手順にしたがって、各要素 のスコアが定まる。この 個のスコアの最大値の最小値を求めよ。 値が のいずれかであるような数列 ( 項) が与えられ…
これ好き！楽しい！！ 問題へのリンク 問題概要 長さ の数列 で定義される、全 ステップの操作が与えられる。操作は整数 に対して行うものであり、 回目の操作は次のものである: を % で置き換える 個の整数 それぞれに対して ステップの操作を行って得られ…
確かに、えでゅふぉのラス問にありそう！ 問題へのリンク 問題概要 人の選手が距離 のレースを走る。 人目はデフォルトでは距離 1 走るのに 秒かかる。 スタートから距離が のところにアイテムがある。各アイテムは各選手に対して独立に、確率 で減速 (距離 …
比較的簡単枠だとは思っていたけど、B よりも解かれたのはびっくり！ 問題へのリンク 問題概要 北海道高校には 個の科目があり、それぞれ 1, 2, 3 の 3 段階で成績がつけられる。 各生徒の成績は長さ の文字列で表される 生徒 が生徒 の「上位互換」であると…
いわゆる区間分割する系の DP。こういう系は高速化を要求するタイプの問題が多いけど、今回は素直な二乗 DP で OK！ 問題へのリンク 問題概要 直線上にカツが 個ある。 個目のカツは位置 にあり、その重さは である。これらのカツを、次のようにしてすべて回…
面白かった 問題へのリンク 問題概要 要素からなる正の整数列 が与えられる。以下の 個のクエリに答えよ 各クエリは整数 が与えられる の順に、 という更新を行う 初めて となる瞬間の を求めよ 最終結果が 1 より大きいときは、その値を答えよ 制約 解法 (1…
発想は AtCoder ABC 125 C - GCD on Blackboard (300 点) AtCoder ARC 074 D - 3N Numbers (500 点) とかに似てる。 問題へのリンク 問題概要 長さ の o と x で構成された文字列 が与えられる。 の index から 個選ぶ方法のうち 選んだ index はすべて o で…
実家 DP 苦手すぎる。今回は解法を簡単なものにするにあたって、「区間の左端も右端も単調増加と思って良い」というのが、割と効いてる気がする。 問題へのリンク 問題概要 長さ の数列であって、各要素の値が 以上 未満であるもののうち、以下の 個の条件を…
似たようなことは考えたことがあった。経路復元に関する理解を問う教育的問題！ 問題へのリンク 問題概要 重みなしの有向グラフと、2 頂点 s, t を始点と終点にもつパスが与えられる。今、われわれはナビに沿ってこのパスをたどっている。ナビの仕様は次の通…
ツリー上のパスクエリについての教育的典型題だった 問題へのリンク 問題概要 (意訳) 頂点の重み付きツリーが与えられる。以下の 個のクエリに答えよ。 各クエリは 2 頂点 , と値 が指定され、ツリー上の と とを結ぶパス上の辺の重みの積を求め、それと を…
こういうのを確実に... 問題へのリンク 問題概要 1 以上の整数からなる長さ の数列 が与えられる。この数列に対して、以下の操作を好きな回数だけ好きな順序で行うことで広義単調増加となるようにしたい。最小回数を求めよ。 個の整数から 1 つ選んで -2 倍…
「操作によって出来上がるものが何通りあるか？」という問題では、まず判定問題を考える！(素振り) 問題へのリンク 問題概要 のグリッドがあって、各マスは白または黒に塗られている。以下の操作を好きな順序で好きな回数だけ行った結果得られる盤面が何通り…
包除原理をとても素朴な状態で問いかける問題！！！ 問題へのリンク 問題概要 頂点のツリーが与えられる。ツリーの各辺を白色または黒色に塗る 通りの方法のうち、以下の 個の制約をすべて満たすものの個数を求めよ。 個目の制約は 2 頂点 が指定され、 と …
面白かった！！！こういうのを確実に通せるようにならないと！！！ 問題へのリンク 問題概要 頂点の木が与えられる。木の各辺を のラベルをつける方法のうち、 の値の最大値を求めよ。ただし は、2 頂点 を結ぶパスに含まれる辺の値の集合を考えたときに、そ…
Deque に似てる。けど、Deque と違って、先手と後手がとりうる選択肢は常に一緒 (最初、先手は左から、後手は右からと誤読した)。 問題へのリンク 問題概要 長さ の数列に対し、先手は左から順に、後手は右から順にとっていく。どのターンもとった値の合計値…
勉強になった...けど、これ知らずにできるもんなの！？ 問題へのリンク あと、LCM の最小値バージョンもある！ drken1215.hatenablog.com 問題概要 個の正の整数 が与えられる。これらから 2 個選んで LCM をとってできる 個の整数の最大値を求めよ。 制約 …
200 点問題で最も難しい問題として名高い問題ですね。 これについては、以下の「累積和」について特集した記事で詳しく解説しました！ qiita.com
この Floyd--Warshall は天才すぎる！ 問題へのリンク 問題概要 頂点 辺の重み付き無向単純グラフが与えられる。容量 の燃料タンクがあって、長さ の辺を通ると、タンクの燃料残量が だけ減少する。 各頂点では燃料を補給できて、補給すると満タン (容量 の…
かなり辛いことを頑張ったけど、本当はすごく明快な問題だった！！ 問題へのリンク 問題概要 個の整数 がある。各 に対して、以下の答えを求めよ。 残っている整数から、どの 2 つも互いに異なる 個の整数を選んで抜き取ることを繰り返したい 抜き取れる回数…
区間反転操作問題シリーズ！！！ それにしてもいろんな見方ができる問題な気がする。 問題へのリンク 問題概要 長さ の 'B', 'W' からなる文字列 があたえられる。今この文字列に 回の操作を行う。 まだ選んでいない 2 マス を選んで区間 [ ] の 'B' と 'W' …
すんごく横長な行列に関する問題だけど、実は横の長さを縦の長さ以下にできるというタイプ。 そうすれば の問題に帰着できて、。あとは の bit DP...なのだが、TLE がとれなかった。微妙に詰めが甘かった。。。 問題へのリンク 問題概要 の行列があたえられ…
めるアイコン変換すると良さそうなのはすぐに思い至った。そこから繋げられずに editorial を見た。 問題へのリンク 問題概要 二次元平面上に 個の点がある。このうちの 2 点 が指定されている。その 2 点間のマンハッタン距離を とする。 この 点について「…
すごく典型的な「二乗の木 DP」！！！！！ そして包除原理との組み合わせ。 問題へのリンク 問題概要 を偶数とする。 頂点の木が与えられる。 頂点を 組の 2 つペアにする方法のうち、各ペアを結ぶパスをすべて考えたときに全辺が被覆されるようなものの個数…
これも実はよくある典型問題だったりはする。 問題へのリンク 問題概要 下のような の二次元グリッドが与えられる。 #..#.. .....# ....#. #.#... このグリッドで '#' は壁を表している。ここで '.' マスを 1 つ選んで、そこに光源を置きたい。光源が照らす…
さ、300 点！？ 問題へのリンク 問題概要 個の中からランダムに選ぶ試行を 回行う。それぞれのものが出た回数が 回になる確率を としたとき、 を満たすような最小の を求めよ。 制約 考えたこと 確率を求めること自体は難しくなくて、 で求められる。が、こ…
こういうの素早く解けるようになりたいね。 いわゆる「トポロジカルソート順の数え上げ」という高難易度でたまに見るパターンの問題。 問題へのリンク 問題概要 頂点 辺の無向グラフが与えられる。ここで、辺 が全域木を形成していることが保証されている。 …
昨日の ABC で、「左右両端からの累積和」を使うと良い問題が出たので、その発展的類題の紹介に。 drken1215.hatenablog.com 問題へのリンク 問題概要 を正の整数とする。 個の要素からなる数列 にとおいて、 個の要素を取り除き、残った 個の要素のうち (前…
