水色diff
これの応用問題って感じだった！！ drken1215.hatenablog.com 問題へのリンク 問題概要 頂点数 の木が与えられる。 番目の辺は頂点 と頂点 とを結んでいる。はじめ、各頂点には、値 0 が書き込まれている。以下の 個のクエリを処理したあとの、各頂点に書き…
これは難しい！！！ 誘惑されそうな嘘解法がたくさんある！！ 問題へのリンク 問題概要 件の日雇いアルバイトがあります。 件目の日雇いアルバイトを請けて働くと、その 日後に報酬 が得られます。 あなたは、これらの中から 1 日に 1 件まで選んで請け、働…
実は双対性が深く絡んでるけど、割と素直な Greedy でも解ける 問題へのリンク 問題概要 要素からなる整数列 が与えられる。これらの要素をいくつかの色に塗り分けたい。ただし、同じ色で塗られた要素は狭義単調増加になるようにしなければならない。 このよ…
マージテクを知らなくても雰囲気で通せるのかもしれない 問題へのリンク 問題概要 人の生徒がそれぞれクラス に所属している。 各生徒はそれぞれの家から出発したあと、他の生徒と合流を繰り返しながら学校へ向かう。一度合流した生徒が分かれることはない。…
一次合同方程式を解く問題です！ 問題へのリンク 問題概要 円周上に 個の椅子が並べられています。そのうち 1 つは玉座です。 高橋君は最初、玉座から時計回りに数えて 個隣の椅子に座っており、次の行動を繰り返します。 行動：いま座っている椅子から時計…
LCS (Longest Common Subsequence) によく似た DP！！ 問題へのリンク 問題概要 (意訳) 長さ の整数列 と、長さ の整数列 が与えられる。これらに以下の操作を繰り返すことで、要素数が等しくなるようにしたい。 A の要素を 1 つ選んで削除する B の要素を 1…
誤読したーーーーー 問題へのリンク 問題概要 頂点数 、辺数 の連結な無向グラフが与えられる (多重辺はありうるが、自己ループはない)。各辺には色がついていて、色は 以上 以下の整数値で与えられる。 各頂点に 以上 以下の色を割り振りたい。このとき、「…
おおむね BFS だけど、ちょっとだけ TLE に注意。。。 問題へのリンク 問題概要 のグリッドが与えられる。"." は通路マス、"#" は壁で侵入不能マス、"S" はスタート、"G" はゴールである。さらに英小文字で表された各マス間は 1 手で自由にワープで行き来可…
最初、「期待値の線形性」を使うのかなと思って迷走した... D は DP の D だった。 問題へのリンク 問題概要 袋の中に金貨が 枚、銀貨が 枚、銅貨が 枚入っている。袋の中にあるいずれかの種類の硬貨が 100 枚になるまで以下の操作を繰り返す。 操作：袋の中…
まさかの超典型な半分全列挙！！！(蟻本にもほぼ同じ問題あり！！) 問題へのリンク 問題概要 個の正の整数 と、正の整数 が与えられる。 個の整数の中からいくつか選んで総和をとる。その値が より大きくならない範囲内での、その値の最大値を求めよ。 制約 …
三乗の解法はすぐに出てくるので、それを上手に高速化する！ 問題へのリンク 問題概要 のグリッドが与えられる。"." マス (通路) には行けるが "#" マス (壁) には行けない。左上のマスから右下のマスへと行きたい。毎回のターンで以下のいずれかの行動をと…
こういうの苦手すぎるので、素早く綺麗に実装できるようになりたい 問題へのリンク 問題概要 AtCoder に参加している幼児が 人おり、 から の番号が付けられている。また、幼稚園 がある。幼児 のレートは であり、はじめ幼稚園 に所属している。 これから …
しゃくとり法のいい練習問題！！ 問題へのリンク 問題概要 長さ の正の整数列 が与えられる。 整数列の連続する部分列のうち、「同じ数値が 2 箇所以上登場しない」という条件を満たす最大長を求めよ。 制約 考えたこと 今回の問題には、次のような著しい構…
二次元累積和のいい感じの練習問題！！ ただこれ水色って...茶色くらいに感じるので、昔の問題の色感覚はやっぱりバグる。 問題へのリンク 問題概要 市松模様に塗られた のマス目があって、各マスには整数値が書かれている。以下の条件を満たす長方形領域の…
面白かった 問題へのリンク 問題概要 の行列 と、整数 が与えられる。この行列は、 をちょうど一つずつ要素に含む。 sigma くんは、以下の 2 種類の操作を、好きな順序で 好きな回数 行えます。 全ての について を満たす を選び、行列の 列目をswapする 全…
結構難しい！！ 問題へのリンク 問題概要 正の整数 に対して、 := を二進法表現したときの各桁の総和を として を で割ったあまり := を で置き換える操作を繰り返したときに、何回で 0 になるか として定める。たとえば のとき、, より、 となる。 今、二進…
面白かった 問題へのリンク 問題概要 文字列 がアンバランスであるとは、 の中の文字のうち、過半数が同じ文字 であることを指すものとする。長さ の文字列 が与えられたとき、 の連続する部分文字列であって、アンバランスなものがあるかどうかを判定せよ。…
面白かった 問題へのリンク 問題概要 以下の条件を満たすような 個の区間 ( 番目を とする) を構築したい。 はすべて互いに相異なる整数 これらの区間の中から「どの 2 個も交差しないように最大で何個の区間を選べるか」という問題に対して、高橋君と青木君…
TSP だ！！ 問題へのリンク 問題概要 3 次元空間内に 個の都市、都市 1 から 都市 N がある。 座標 の都市から の都市に移動する際には のコストがかかる。 都市 1 からスタートし、全ての都市を 1 度以上巡って都市 1 に戻るまでの最小コストを求めよ。 制…
これを思い出した drken1215.hatenablog.com 問題へのリンク 問題概要 のグリッドが与えられる。あるマスは壁 ('#') になっていて、あるマスは通路 ('.') になっている。通路マスが 個あるとして、すべての「通路マスの部分集合」 ( 通りある) に対して、以…
LIS を求める in-place DP を応用すればできる！ でも、400 点問題で「DP 配列をセグ木に乗せて」「in-place に更新することで高速化する」という問題が出るとは思わなかった！ in-place DP に馴染みのない方は先にこっちを qiita.com 問題へのリンク 問題概…
えーーー、300 点！？ 問題へのリンク 問題概要 二次元平面上に 点が与えられる。これらの点の x 座標、y 座標を抽出すると、それらは の順列となっている。 各 に対して、点 から 自分よりも x 座標と y 座標がともに大きな点 自分よりも x 座標と y 座標が…
DP 高速化系問題。こういうのが緑 diff になるようになったんかーー (水色 diff にアップグレードした！) 問題へのリンク 問題概要 マスからなるマス目が与えられる。また、 個の互いに disjoint な区間 が与えられる。この区間に属する整数からなる集合を …
異様に難しかった！！ 問題へのリンク 問題概要 の順列が与えられる。 順列の中の i から P[ i ] へ移動するとき、C[ P[ i ] ] だけスコアが加算される。 出発点を自由に選んで 回以上 回以下の移動を行うとき、得られるスコアの最大値を求めよ。 制約 考え…
最初、同じ行の「連続する 3 個」しか選べないのだと誤読してしまった... 問題へのリンク 問題概要 二次元座標平面上で、(1, 1) から (R, C) へと格子点を辿って最短経路で進みたい (上か右にしか行けない)。 K 個の座標 () に価値 のアイテムがある。通った…
未証明でも確信持てる系。でも、こういう風に「作れるものは連続している」というのはたまに見るパターン。そういう問題には「とりうる状態が連結」というタグをつけているので是非に！！ drken1215.hatenablog.com 問題へのリンク 問題概要 個の整数 を次の…
まさかの既出！！！しかも割と最近の ABC-E！！！ drken1215.hatenablog.com 問題へのリンク 問題概要 から までの数字のみからなる文字列 が与えられる。 の連続する区間であって、 の倍数であるものが何個あるのかを求めよ。 制約 考えたこと 実は完全にマ…
考え方自体は典型的ではある 問題へのリンク 問題概要 個の整数 が与えられる。 これらから 2 個選んで XOR をとって得られる整数 ( 個ある) の総和を 1000000007 で割ったあまりを求めよ。 制約 考えたこと XOR をみたら、とにかく「各桁ごとに考える」とい…
「平均値が A」という制約は上手に扱うテクニックがある。 今回はそれを思いつかなくても解けるけど、思いつくと計算量が落ちる。 問題へのリンク 問題概要 個の整数 からいくつか選ぶ方法のうち、その平均値がちょうど となるものが何通りあるかを求めよ。 …
よくある桁DPとはまた違うけれど、桁DPの応用問題としてよくあるやつを試せる問題ですね！ 問題へのリンク 問題概要 "013?42???2??" のような、'?' と数値で構成された、長さ の文字列が与えられる。 この '?' を埋めて数値を作る方法のうち、13 で割ったあ…
