グリッド
面白かった 問題へのリンク 問題概要 の盤面の各マスを 0 か 1 かで埋めたい。すでに 個のマスについては数字が埋まっている。以下の条件を満たすように残り マスを埋める方法は何通りあるか、998244353 で割ったあまりで求めよ。 一辺の長さが 2 以上な部分…
最適解の形を丁寧に場合分けして考える系 問題へのリンク 問題概要 の板チョコレートを 3 つの長方形に割りたい。そのときの 3 つの長方形の面積の最大値と最小値の差の最小値を求めよ。 制約 考えたこと まず思ったのは、 のうちの少なくとも一方が 3 の倍…
見るからに最小カットだけど、こういうの意外と詰め切るのに時間がかかるイメージがある... 問題へのリンク 問題概要 の二次元グリッドが与えられる。各マスは 'S' のマス：カエルがいる 'T' のマス：カエルがそこにいきたい 'o' のマス：葉っぱがある '.' …
800 点埋めをしていく！！！ 問題見て、コーナーケース怖い系かな...と思ったけど、ちゃんと一発で通せてよかった 問題へのリンク 問題概要 行 列のマス目があって、以下の条件を満たすように各マスに整数値を書き込みたい (整数値を とする): どのマスの数…
枝刈り探索が根本的に計算量改善することを示せることがある！！！ 有名な例は最大独立集合問題に対する のアルゴリズムかなと。 指数時間アルゴリズム入門 from Yoichi Iwata www.slideshare.net 問題へのリンク 問題概要 下図 (公式解説より) のように な…
今日の会社のバチャでやった。面白かった。 問題へのリンク 問題概要 のグリッドに 'A', 'B', 'C' の各文字を書き込む。以下の条件を満たすものを一つ求めよ。 以下のような に対して である: 隣接する 2 マスの組であって一方が 'A' で他方が 'B' であるも…
マトロイドだ！！！！！！！ 問題へのリンク 問題概要 のボード上の 個のコマがあってそれぞれ重みがつけられている。同じマスに複数のコマが置かれていることもある。 今、各行から 1 個以下のコマを取り去る。次に各列から 1 個以下のコマを取り去る。 最…
確かに、ついこの間の ABC 131 F の類題だね 問題へのリンク 問題概要 のグリッドがあって、 マス分が黒く塗られている 長方形の三頂点状に並んだ黒マスの組を選んで、残りの頂点に相当する位置を黒く塗る (コスト 0) 黒くないマスを一つ選んで黒く塗る (コ…
ちょっと話題になった超典型フロー 問題へのリンク 問題概要 のグリッドがあります。各マスは白黒に塗られています。今、白いマスにできるだけ多くのコマを置きたいです。 各マスに 1 個のみ コマを置けるのは白いマスのみ 隣り合う白マスの双方にコマを置く…
これも実はよくある典型問題だったりはする。 問題へのリンク 問題概要 下のような の二次元グリッドが与えられる。 #..#.. .....# ....#. #.#... このグリッドで '#' は壁を表している。ここで '.' マスを 1 つ選んで、そこに光源を置きたい。光源が照らす…
ちょっとした構築系問題という感じかな... 問題へのリンク 問題概要 二次元平面上の二点 が与えられる。 はすべて整数である。 今、 から出発して「上下左右に 1 秒に 1 だけ動く」という動作を繰り返しながら に行き、またそこから出発して に戻り、さらに…
当時は解けなかったけど、二項係数を扱うスキルを格段に高めた今なら解ける！！！ というのは罠で、「経路数に帰着する」という考え方をこの問題で学んだ ^^; 問題へのリンク 問題概要 個の正の整数値のペア が与えられる。 の値を 109 + 7 で割ったあまりを…
好き！ 確かに天才系問題だけど、実験を積み上げると見えて来る感じが最高！！！ 問題へのリンク 問題概要 × の盤面に何個かのコマが置かれている。先手と後手が交互に、以下のいずれかの動作を繰り返す: コマを 1 つ選び、それを 1 マス左か下に動かす (た…
嘘貪欲は一瞬脳裏によぎり、それを振り払って問題を解いてた。発想はこれの「後ろから解く」のに似ている。 drken1215.hatenablog.com 問題へのリンク 問題概要 × のグリッドのあるマスにロボットが置かれている。先手と後手はそれぞれ長さ の自分の文字列 …
また一つ、教育的 & 典型的な BFS 問が誕生した！！！ 問題へのリンク 問題概要 × のグリッドがあって、各マスは「白」「黒」に塗られている。 1 秒ごとに、各黒マスに対し、その上下左右に隣接したマスが存在するならば、そのマスを黒く上塗りしていく。全…
こどふぉにありそうな雰囲気の問題かな 問題へのリンク 問題概要 × のグリッドの各マスをちょうど一回ずつ訪れたい。ただし スタートとゴールは異なるマスでよい 毎回の移動は、上下左右斜めの 8 方向への移動は禁止 (飛車の移動も角の移動も禁止) を満たす…
ちょっと考えればできる 問題へのリンク 問題概要 × のグリッドグラフの左上から右下への最短路が 1 つ与えられる。この最短路と辺を共有しない最短路を一つ求めよ (頂点で重なるのは OK) 制約 考えたこと 対角線に沿って反転すれば OK #include <iostream> #include <sstream> </sstream></iostream>…
各地点に早くたどり着いておくに越したこと無い系問題！！ atcoder.jp 問題概要 のグリッドがあってスタートからゴールへと行きたい。壁のあるマスは通れない。 ただし毎秒ごとに移動できる方向に制限がある。 で割ったあまりがそれぞれの場合についてどの方…
高校の頃とかに「グリッドの左上から右下まで行く最短路が何通りあるか」みたいな問題に親しんでいれば、自然に思えるかもしれない 問題へのリンク 問題概要 のグリッドがあって、最初は駒は左上隅に置かれていた。 駒が上下左右に動きながら右下隅まで移動…
mod. p での連立一次方程式の練習などに！！！ 問題へのリンク 問題概要 × のマス目があり、そのうちの マスについては既に 以上 以下の数値が入れられている。残りの マスに 以上 以下の数値を入れる方法のうち どの行の和と、どの列の和をとっても、その一…
こういうの超苦手系だけど、苦手なりに解法を詰められたのは成長の証で嬉しい！ olphe たん、ナンさんとチームを組んでいて、olphe たんに考察を話して、詰めてくれて、爆弾周りの見落としがあって詰まって、みんなでデバッグして...とチーム戦ならではの考…
グリッド上をスタートからゴールまで行く系の問題において、しばしばある 盤面に対し、何らかの形でコストを払ったりスコアを獲得したりしながら変更を加えられる という設定の問題。その設定が加わると難しい問題になることも多いが、この問題は比較的素直…
燃やす埋めるを本気で整理する！！！ すごく面白い問題だった！！！ 問題へのリンク 問題概要 × の二次元ボードが与えられる。以下のような "#" のところを最小個数の長方形で敷き詰めよ。例えば 4 10 ########## ....#..... ....#..... .......... は下のよ…
めちゃ面白い！ 問題へのリンク 問題概要 オセロにおいて、黒石が 1 個だけない状態からスタートする。 ........ ........ ........ ...ox... ....o... ........ ........ ........ ここから通常のオセロルールでプレイする。今、 個のクエリが投げられ、各…
燃やす埋めるは今度こそちゃんとマスターする！！！ 問題へのリンク 問題概要 × の各格子点に電球がある。 が偶数となるような について、 を頂点とする正方形の中心に装置があって、各装置を押すことで四隅の電球を点灯することができる。 ただし、装置を起…
一目見て、データ構造げーかな...と思ってしまった。そういう先入観を持つと危ない。実際は好みな考察で解ける問題だった。 問題へのリンク 問題概要 正の整数 と からなる順列が与えられる。いま、この順列を下図左のようにピラミッドの最底辺に書き込む。…
こういうのを爆速で書けるようになりたい。問題としては マンハッタン距離に関する問題では x 軸方向と y 軸方向とで独立に考えればよいことになるケースが多い (マンハッタンに限らず、各要素ごとに独立にならないかを考察することは重要) の最小値を与える…
座圧に見えてしまった 問題へのリンク 問題概要 のグリッドがあります。グリッドのうち マスに壁があって壁の位置は で与えられます。壁のあるマスには行けません。 マス からマス へと至る最短経路が何通りあるか、 で割ったあまりを求めよ。 制約 考えたこ…
これ好き！！！本番中に通せれば 問題へのリンク 問題概要 のマス目に から までの数値を 個ずつ書きたい。 つの数列 と が与えられて 行目の最大値が 列目の最大値が という性質を満たすものが何通りあるか、1000000007 で割ったあまりで求めよ。 制約 考え…
DP とかメモ化再帰とか考え出すとドツボにはまる...素直な考察が大事だね。 問題へのリンク 問題概要 H × W のグリッドが与えられる。各マスは白か黒で塗られている。「黒」マスと「白」マスのペアであって、 黒マスから出発して、隣接するマスを辿っていく…
