けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

グリッド

AOJ ???? Numbers on Papers (KUPC 2020 B)

DP 高速化系問題 問題へのリンク 問題概要 のグリッドが与えられる。各マス には数値 が書かれている。 各行から 1 個ずつ数値を選んで行順に並べてできる数列を考える。そのような数列は 通り考えられるが、そのうち広義単調増加なものが何通りあるか、1000…

AOJ 2679 Decoding Ancient Messages (JAG 春コン 2014 C) (700 点)

多倍長整数を活用した、重み付き二部マッチング 問題へのリンク editorial 問題概要 のグリッドが与えられる。各マスにはアルファベット (英大文字と英小文字) が描かれている。今、次の条件を満たすように 個の文字を抜き出す 各行から選ぶマスはちょうど 1…

AOJ 1618 池のある庭園 (ICPC 国内予選 2017 C) (150 点)

この手の、単純だけど for 文ネストがエグい全探索、案外 AtCoder で見ないかもしれない 問題へのリンク 問題概要 の二次元グリッドが与えられる。各グリッドには 0 以上 9 以下の整数値が書かれている。 グリッド上で、以下の条件を満たす長方形領域を考え…

AOJ 2953 Hokkaido University Hard (HUPC 2019 day2-B)

テスターだった。 簡単枠の Easy ヴァージョンに対して「制約あげられるね」と提案して、正式に問題セットになった! 問題へのリンク editorial 問題概要 のグリッドがあって、各マスは '.' か 'B' から成っている。'B' マス間のマンハッタン距離として考え…

HHKB プログラミングコンテスト 2020 D - Squares (青色, 400 点)

これ、「重なるものを数える」という風に考えれば、縦方向と横方向を独立に考えれば良いことに気付けるかが結構ポイントっぽい 問題へのリンク 問題概要 整数 が与えられます。 辺の長さが の白い正方形を座標平面の に 4 頂点が重なるように置きます。 次に…

HHKB プログラミングコンテスト 2020 E - Lamps (水色, 500 点)

これを思い出した drken1215.hatenablog.com 問題へのリンク 問題概要 のグリッドが与えられる。あるマスは壁 ('#') になっていて、あるマスは通路 ('.') になっている。通路マスが 個あるとして、すべての「通路マスの部分集合」 ( 通りある) に対して、以…

ACL Contest 1 C - Moving Pieces (青色, 600 点)

フローって確かに天才パズルな問題はすごく天才的なんだけど、典型的な問題もたくさんある! 問題へのリンク 問題概要 下図のような の盤面が与えられる。盤面は通路 ('.') と壁 ('#') がある。いくつかの通路にはコマ ('o') が配置されている。 コマは下方…

AtCoder ABC 179 F - Simplified Reversi (青色, 600 点)

早速遅延セグ木があればできる問題来た!! AC Library の出番かと思った!!! 問題へのリンク 問題概要 縦 マス、横 マスのグリッドがあり、はじめグリッドの中央 マスには黒い石が 1 個ずつ置いてあり、下辺と右辺の計 マスには白い石が 1 個ずつ置いてあ…

AtCoder ABC 175 E - Picking Goods (水色, 500 点)

最初、同じ行の「連続する 3 個」しか選べないのだと誤読してしまった... 問題へのリンク 問題概要 二次元座標平面上で、(1, 1) から (R, C) へと格子点を辿って最短経路で進みたい (上か右にしか行けない)。 K 個の座標 () に価値 のアイテムがある。通った…

AtCoder ABC 145 D - Knight (緑色, 400 点)

この問題のおかげで、僕の二項係数記事が一躍広く普及することになったのだった。 問題へのリンク 問題概要 二次元グリッドの原点 にチェスのナイトの駒がある。 ナイトの駒はマス にあるとき か のどちらかのマスにのみ動かすことができる。 ナイトの駒をマ…

JOI 二次予選 2020 D - テンキー (AOJ 0675, 難易度 7)

本選参加のボーダーとなった問題らしい!それにしても JOI は実装が重たい...!!! 問題へのリンク 類題とか drken1215.hatenablog.com 問題概要 初期状態では下図のようなテンキーの「0」のところにカーソルがある。 上下左右への移動 ボタンを押す (315 …

AtCoder ABC 079 D - Wall (緑色, 400 点)

Floyd--Warshall と、あとグリッド上の各マスは独立に考えて OK。 問題へのリンク 問題概要 のグリッドがあって、各マスには -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 のいずれかの数値が書かれている。目的は -1 以外のマスをすべて 1 に変えることである。 各マ…

AtCoder ABC 042 D - いろはちゃんとマス目 (ARC 058 D) (青色, 400 点)

これが青パフォ!!!!! 時代の進化を感じるところ!!! 問題へのリンク 問題概要 のマス目が与えられる。左上から右下へ進む最短経路のうち、 下から マス以内、かつ 左から マス以内 の範囲内には来ないようなものの個数を、1000000007 で割ったあまり…

AtCoder AGC 004 C - AND Grid (黄色, 700 点)

こういうの大好き! 問題へのリンク 問題概要 の盤面 A が与えられる。各マスは白か黒かのいずれかである。次の条件を満たす、同じ大きさの白黒の二つの盤面の組 (S, T) を構築せよ S の黒マスはすべて縦横に連結である T の黒マスはすべて縦横に連結である …

AtCoder ABC 159 E - Dividing Chocolate (水色, 500 点)

制約が縦方向の bit 管理を要求している感満載 問題へのリンク 問題概要 のグリッドがあって各マスに 0 か 1 が書き込まれている。これに対し、縦横にラインでカットして、部分長方形区域に分けたい。どの区域も 1 の個数が 以下になるようにする。 これを実…

AtCoder AGC 043 A - Range Flip Find Route (緑色, 400 点)

「予め盤面をいじることができる」という設定の問題にはある程度の定石があるように思う! 問題へのリンク 問題概要 の盤面が与えられ、左上から右下まで行きたい。'#' マスは壁を表し、'.' マスは通路を表す。 予め盤面に以下の操作を行うことができる。最…

AtCoder AGC 003 F - Fraction of Fractal (銅色, 1700 点)

頭がゴチャゴチャしてきて、詰め切るのがとても大変だった。 でも整理し切った後に出てくる性質は、至極単純なものだった。面白い。 問題へのリンク 問題概要 のグリッドが与えられ、各マスは白黒に塗られている。この盤面をレベル 1 のフラクタルとする。 …

フォルシアゆるふわ競プロオンサイト #3 F - Yet Another Cake Division locked

面白かった 問題へのリンク 問題概要 の盤面の各マスを T, M, N, P の四色に塗る方法のうち、以下の条件を満たすものが何通りあるか、1000000007 で割ったあまりを求めよ。 どの T マスと M マスについても、M マスは T マスから見て strict に右にあるか、s…

CADDi 2018 F - Square (橙色, 900 点)

面白かった 問題へのリンク 問題概要 の盤面の各マスを 0 か 1 かで埋めたい。すでに 個のマスについては数字が埋まっている。以下の条件を満たすように残り マスを埋める方法は何通りあるか、998244353 で割ったあまりで求めよ。 一辺の長さが 2 以上な部分…

キーエンス プログラミング コンテスト 2020 F - Monochromization (銅色, 1100 点)

「操作によって出来上がるものが何通りあるか?」という問題では、まず判定問題を考える!(素振り) 問題へのリンク 問題概要 のグリッドがあって、各マスは白または黒に塗られている。以下の操作を好きな順序で好きな回数だけ行った結果得られる盤面が何通り…

AtCoder ABC 062 C - Chocolate Bar (ARC 074 C) (緑色, 400 点)

最適解の形を丁寧に場合分けして考える系 問題へのリンク 問題概要 の板チョコレートを 3 つの長方形に割りたい。そのときの 3 つの長方形の面積の最大値と最小値の差の最小値を求めよ。 制約 考えたこと まず思ったのは、 のうちの少なくとも一方が 3 の倍…

AtCoder ARC 074 F - Lotus Leaves (黄色, 800 点)

見るからに最小カットだけど、こういうの意外と詰め切るのに時間がかかるイメージがある... 問題へのリンク 問題概要 の二次元グリッドが与えられる。各マスは 'S' のマス:カエルがいる 'T' のマス:カエルがそこにいきたい 'o' のマス:葉っぱがある '.' …

CODE FESTIVAL 2016 qual C D - Friction (黄色, 800 点)

気持ち良く詰められた 問題へのリンク 問題概要 のオブジェに対し いずれかの列を選び、その列を一段沈める (このとき最下段ブロックは消える) という操作を 回繰り返してオブジェを完全に消し去りたい。1 回の操作に要するコストは、そのブロックがその時点…

CODE FESTIVAL 2016 qual A D - マス目と整数 / Grid and Integers (橙色, 800 点)

800 点埋めをしていく!!! 問題見て、コーナーケース怖い系かな...と思ったけど、ちゃんと一発で通せてよかった 問題へのリンク 問題概要 行 列のマス目があって、以下の条件を満たすように各マスに整数値を書き込みたい (整数値を とする): どのマスの数…

AOJ 2574 Magical Switches (JAG 模擬地区 2013 J) (900 点)

枝刈り探索が根本的に計算量改善することを示せることがある!!! 有名な例は最大独立集合問題に対する のアルゴリズムかなと。 指数時間アルゴリズム入門 from Yoichi Iwata www.slideshare.net 問題へのリンク 問題概要 下図 (公式解説より) のように な…

AtCoder ABC 151 D - Maze Master (緑色, 400 点)

面白かった。BFS したり、Warshall--Floyd したり。 問題へのリンク 問題概要 の盤面が与えられる。各マスは '.' か '#' のいずれかである。それぞれ「通路」と「壁」を表している。 「通路を 2 箇所 指定したときの、上下左右に通路のみをたどって から へ…

KUPC 2019 G - ABCのG問題

今日の会社のバチャでやった。面白かった。 問題へのリンク 問題概要 のグリッドに 'A', 'B', 'C' の各文字を書き込む。以下の条件を満たすものを一つ求めよ。 以下のような に対して である: 隣接する 2 マスの組であって一方が 'A' で他方が 'B' であるも…

第一回日本最強プログラマー学生選手権-予選- E - Card Collector (橙色, 800 点)

マトロイドだ!!!!!!! 問題へのリンク 問題概要 のボード上の 個のコマがあってそれぞれ重みがつけられている。同じマスに複数のコマが置かれていることもある。 今、各行から 1 個以下のコマを取り去る。次に各列から 1 個以下のコマを取り去る。 最…

Codeforces 500 DIV1 B. Chemical table (R1900)

確かに、ついこの間の ABC 131 F の類題だね 問題へのリンク 問題概要 のグリッドがあって、 マス分が黒く塗られている 長方形の三頂点状に並んだ黒マスの組を選んで、残りの頂点に相当する位置を黒く塗る (コスト 0) 黒くないマスを一つ選んで黒く塗る (コ…

SoundHound 2018 予選 C - 広告 (400 点)

「二部グラフの最大安定集合問題」について知っていれば典型問題ですね。 問題へのリンク 問題概要 のグリッドがあります。各マスは白黒に塗られています。今、白いマスにできるだけ多くのコマを置きたいものとします。 各マスに 1 個のみコマを置ける コマ…