ビットベクターで高速化するのは、いつも見落としてしまう！ 問題へのリンク 問題概要 円環状に 個の魔法石があり、 番目の魔法石は、価値が 、色が である。色は 1 以上 50 以下の整数で表される。 今、これらの魔法石に対して、隣り合う魔法石の色の差が …

壁にぶつかるまで動く設定の迷路問題！ 問題へのリンク 問題概要 のグリッドがある。各マスは壁 (文字 '#') か通路 (文字 '.') かのいずれかである。グリッドの外周のマスはすべて壁であることが保証されている。 プレイヤーは最初、マス にいる (0-indexed)…

迷路の最短路問題なので BFS でやりたくなるが、まともにやると で TLE してしまう！！ 頂点の持ち方を工夫して 0-1 BFS で解く！ 別解として枝刈り BFS も。 drken1215.hatenablog.com 問題へのリンク 問題概要 のグリッドが与えられます。各マスは通路 (文…

DIjkstra をするときに、直前の頂点ももつ系 問題へのリンク 問題概要 頂点数 、辺数 の重み付き無向グラフが与えられる。頂点 の座標は となっている。 頂点 1 から頂点 2 へと至る経路のうち、鋭角に曲がる箇所がないようなものを考える (頂点 の前の頂点…

いかにも ABC-E にありあそうな DP！！ ジャッジへのリンク 問題文へのリンク これとか似てる atcoder.jp 問題概要 個の店がある。 日間にわたって、いずれか 1 つの店で買い物をする。 日目に 番目の店で買い物をしたときの値段は で与えられる (10 の倍数)…

三乗の解法はすぐに出てくるので、それを上手に高速化する！ 問題へのリンク 問題概要 のグリッドが与えられる。"." マス (通路) には行けるが "#" マス (壁) には行けない。左上のマスから右下のマスへと行きたい。毎回のターンで以下のいずれかの行動をと…

部分文字列の遷移は愚直に求めた。。。 問題へのリンク 問題概要 長さ の文字列 c と、短い文字列 s, t が与えられ、'a'〜'z' と '?' からなっている。'?' を埋める方法のうち、 c の連続する部分文字列として s を含む箇所の個数から c の連続する部分文字…

あみだくじ 問題へのリンク 問題概要 縦棒の個数が 、横棒が縦方向に 刻みのあみだくじであって、 番目からスタートすると 番目に到着するようなものを数え上げよ。 制約 考えたこと いかにも DP という感じではあるね。 dp[ i ][ j ] := 縦棒を上から i 刻…

こういうの素早く書けるようになるにはどうしたらいいんだろう... 問題へのリンク 問題概要 'A', 'G', 'C', 'T' のみからなる長さ の文字列のうち、「どの隣接した 2 文字を swap しても "AGC" を連続部分列として含まないもの」が何通りあるか求めよ。 制約…