グリッド
迷路の最短路問題なので BFS でやりたくなるが、まともにやると で TLE してしまう！！ 頂点の持ち方を工夫して 0-1 BFS で解く！ 別解として枝刈り BFS も。 drken1215.hatenablog.com 問題へのリンク 問題概要 のグリッドが与えられます。各マスは通路 (文…
EDPC C - Vacation と良く似た問題だと思う！！ あと、幅が狭いグリッドでは DP が疑われることが結構多い！ 問題へのリンク 問題概要 長さが の数列が 2 つ ( と ) 与えられます。 各 に対して、 と のいずれかを選ぶことで、新たに数列 を作ります。 こう…
かの有名な「器物損壊！高橋君」の類題ですね。 drken1215.hatenablog.com 問題へのリンク 問題概要 のグリッドがあって、各マスは通路マス (.) か壁マス (#) のいずれかです。 今、左上のマス から右下のマス へと移動したいです。上下左右に移動することが…
一見いかめしい問題だけど、単に座標圧縮するかどうかだと気づけるかですね。 問題へのリンク 問題概要 のグリッドが与えられます。数 はそれぞれマス に書かれています。それ以外の マスには何も書かれていません。 このグリッドに対して、次の操作を可能な…
通称 0-1 BFS と呼ばれるアルゴリズムが使える問題ですね。 問題へのリンク 問題概要 のマス目で表現された地図が与えられます。 . は通路、# は壁を表します。s マスから出発して、上下左右への移動を繰り返しながら g マスへと到達したいとします。. マス…
これが ABC の C 問題だったとは...！！！ 典型90問の問 4 が結構近いと思った。 drken1215.hatenablog.com 問題へのリンク 問題概要 のグリッド (メモリにおさまらない規模) が与えられる。そのうちの 個のマスには飴が置いてある。 次の条件を満たすマスの…
グリッドの縦方向の情報と横方向の情報を前処理するのは典型ですね！！ 問題へのリンク editorial 類題とか drken1215.hatenablog.com 問題概要 のグリッドの各マス目に数値が書かれている。 各マス に対して、「そのマスと行または列が等しいマスの数値の総…
結構アドホックで難しいと思った！ 問題へのリンク 問題概要 マスが横一列に並んだすごろくが与えられる ( と番号づけされている)。すごろくの各マスは . と x と # のいずれかである。 マス とマス は X である 他のマスは長さ の文字列 で与えられる X は…
「横移動 + 縦移動」で行けるところをすべて求めるのは簡単だし、「縦移動 + 横移動」で行けるところをすべて求めるのも簡単。しかし、両方の方法で行けるマスの扱いが難しい。 問題へのリンク 問題概要 のグリッドがあり、そのうちの 個のマスは壁になって…
めっちゃフラクタルな問題だ！ ジャッジページへのリンク 問題文へのリンク 類題とか drken1215.hatenablog.com 問題概要 JOI のロゴは、下図のようになっている (問題文より)。 レベル のロゴは 1 × 1 のグリッドで "J" のみからなる レベル のロゴは、 の…
面白かった。単純にやると なので、そこから計算量オーダーを 1 つ落とすことを考える。 ジャッジページへのリンク 問題文へのリンク 問題概要 のグリッドが与えられる。各マスには 0, 1, 2 のうちのいずれかの値が描かれている。 これらの 個のマスのうちの…
一見すると典型的な「座標圧縮」+「二次元いもす法」なのだが、それだと TLE / MLE してしまう。 ジャッジへのリンク 問題文へのリンク 問題概要 のグリッド上に 枚の長方形の紙を敷いていく。 枚目の紙は を満たす座標 を覆う領域に配置される。最も多くの…
いかにも ABC-E にありあそうな DP！！ ジャッジへのリンク 問題文へのリンク これとか似てる atcoder.jp 問題概要 個の店がある。 日間にわたって、いずれか 1 つの店で買い物をする。 日目に 番目の店で買い物をしたときの値段は で与えられる (10 の倍数)…
これ好き！ 問題へのリンク 問題概要 のグリッドがあって、"." と "O" と "X" のいずれかが描かれている。"O" または "X" の描かれているマス目の個数を とする。 今、いくつかのマスに対して、"O" または "X" のマス目の "OX" を入れ替える操作を行う。それ…
幅が小さいので、幅についての 通りの探索が間に合う！ 問題へのリンク 問題概要 のマス目がある。各マスの値は 0 または 1 である。次の操作を好きな順序で好きな回数だけ行うことができる。 ある行を選択して、その行の数値をすべてひっくり返す (0 を 1 …
ハニカムつらい 問題へのリンク editorial 問題概要 下図で表されるようなハニカム状のグリッドが与えられる (図は問題文より)。 黒色マスは建物があるマスを表している。赤太線は、「外側」から見て見える外壁を表している。 このような のマップが与えられ…
J, O, I の 3 人しかいないと、意外と bit DP を発想しづらいかもしれない。でもこういうのめっちゃ見るね。 問題へのリンク 類題とか drken1215.hatenablog.com 問題概要 J 君と、O 君と、I 君の 3 人が所属する部活動がある。 日間の活動が行われる。それ…
ちょっと実装大変だった。差分のみ更新していく系の問題。 問題へのリンク editorial 問題概要 のグリッドがあって、各マスには "J"、"O"、"I" が書かれている。 またこれとは別に、2 × 2 の "J", "O", "I" のパターンが与えられる ( 通りありうる)。 今、与…
おおむね BFS だけど、ちょっとだけ TLE に注意。。。 問題へのリンク 問題概要 のグリッドが与えられる。"." は通路マス、"#" は壁で侵入不能マス、"S" はスタート、"G" はゴールである。さらに英小文字で表された各マス間は 1 手で自由にワープで行き来可…
三乗の解法はすぐに出てくるので、それを上手に高速化する！ 問題へのリンク 問題概要 のグリッドが与えられる。"." マス (通路) には行けるが "#" マス (壁) には行けない。左上のマスから右下のマスへと行きたい。毎回のターンで以下のいずれかの行動をと…
二次元累積和のいい感じの練習問題！！ ただこれ水色って...茶色くらいに感じるので、昔の問題の色感覚はやっぱりバグる。 問題へのリンク 問題概要 市松模様に塗られた のマス目があって、各マスには整数値が書かれている。以下の条件を満たす長方形領域の…
グリッドグラフは二部グラフ！！！ 問題へのリンク 問題概要 のマス目に整数値 (マス には ) が書かれている。 各マスについて、「元の整数値のままにする」または「元の整数値に 1 を足したもの」をすることによって、どの隣接する 2 マスの値も互いに相異…
これは天才パズル！！！ 問題へのリンク 問題概要 のグリッドに 0, 1 の数値を書き込む方法であって、 どの行をみても、それに含まれる 0 の個数と 1 の個数のうちの小さい方の個数が どの列をみても、それに含まれる 0 の個数と 1 の個数のうちの小さい方の…
場合分けやコーナーケース回避がエグい問題！ 問題へのリンク 問題概要 .#..#.. のような長さ のマス目が与えられる。"#" は岩を表す。初期状態では、すぬけ君は マス目に、ふぬけ君は マス目にいる ()。 今、「2 人のうちのいずれかを選んで 1 マス右か 2 …
構築楽しかった 問題へのリンク editorial 問題概要 のグリッド上に のドミノを互いに重ならないように配置していく。 どの行・列を見ても、その行・列上にある のドミノの個数が互いに等しいような配置を求めよ。存在しない場合は "-1" を出力せよ。 制約 …
状態空間を上手に削減する系の問題 問題へのリンク editorial 問題概要 種類の長方形形状 () をしたスタンプがある (それぞれ「赤」「緑」「青」の 3 種類がある)。 これらを使って 4 × 4 のグリッド上に所望の模様を作りたい。グリッドからはみ出して押して…
から落とせる気がまったくしなかった... 問題へのリンク 問題概要 個の広義単調増加数列 が与えられる。 それぞれの数列から、先頭から 個ずつとってきた値の総和の最大値を求めよ。ただし でなければならないものとする。 制約 考えたこと 個数に関する con…
コンテスト本番はこの問題から解いた！！確信を持つのに時間かかった 問題へのリンク editorial 問題概要 0 と 1 と 2 のみからなる の行列 がある。そのうちの と の値のみがわかっている。他のマスの値は、 に対して = mex() と定められている。 全体の 0,…
山登り法で見つかった！スコアが下がっていくのを眺めるの快感！ 問題へのリンク 問題概要 のグリッドに以下の条件を満たすように英小文字を入れよ。 横方向、縦方向に連結しているマス目を抜き出してできる文字列は 個ある そのすべてが互いに相異なる これ…
DP 高速化系問題 問題へのリンク 問題概要 のグリッドが与えられる。各マス には数値 が書かれている。 各行から 1 個ずつ数値を選んで行順に並べてできる数列を考える。そのような数列は 通り考えられるが、そのうち広義単調増加なものが何通りあるか、1000…
