座標ごとに情報を整理するのは頻出！ 問題へのリンク 問題概要 x-y 座標平面上に 人がいる。それぞれ座標 の位置にいて、左右いずれかを向いている（各人が左右どちらを向いているかは文字列 で与えられる）。 各人が、その位置から、向いている方向に向かっ…

set を上手に使う系の問題 問題へのリンク 問題概要 のグリッドがあり、最初は各マスに壁がある。このグリッドに次の 回のクエリを実行したあとの、残っている壁の個数を求めよ。 【クエリ】 マス のある位置に爆弾を落とす。 もしこのマスに壁があるなら、…

データを上手に持って、差分更新する系の問題 問題へのリンク 問題概要 のグリッドがあって、各マスは文字 '#' か '.' のいずれかが書かれている。先手は '#' の個数が得点となり、後手は '.' の個数が得点となる。双方得点を最大化したい。 先手は行を 1 つ…

次の問題にとても似ていた！ drken1215.hatenablog.com 問題へのリンク 問題概要 のグリッドが与えられる。各マスには文字 'o' または 'x' が描かれている。これらのマスから 3 個選ぶ方法であって、 3 マスに書かれた文字はすべて 'o' である 3 マスのうち…

黒マスを避けながら、長方形領域の値の総和を最大化する問題として解いた！ 問題へのリンク 問題概要 のグリッドがあって、各マス には正の整数 が書かれている。 グリッドに含まれる長方形領域のうち、「長方形領域に含まれる値の総和」と「長方形領域に含…

これが ABC の C 問題だったとは...！！！ 典型90問の問 4 が結構近いと思った。 drken1215.hatenablog.com 問題へのリンク 問題概要 のグリッド (メモリにおさまらない規模) が与えられる。そのうちの 個のマスには飴が置いてある。 次の条件を満たすマスの…

「横移動 + 縦移動」で行けるところをすべて求めるのは簡単だし、「縦移動 + 横移動」で行けるところをすべて求めるのも簡単。しかし、両方の方法で行けるマスの扱いが難しい。 問題へのリンク 問題概要 のグリッドがあり、そのうちの 個のマスは壁になって…

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

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

めるアイコン変換すると良さそうなのはすぐに思い至った。そこから繋げられずに editorial を見た。 問題へのリンク 問題概要 二次元平面上に 個の点がある。このうちの 2 点 が指定されている。その 2 点間のマンハッタン距離を とする。 この 点について「…

これも実はよくある典型問題だったりはする。 問題へのリンク 問題概要 下のような の二次元グリッドが与えられる。 #..#.. .....# ....#. #.#... このグリッドで '#' は壁を表している。ここで '.' マスを 1 つ選んで、そこに光源を置きたい。光源が照らす…

こういうのを爆速で書けるようになりたい。問題としては マンハッタン距離に関する問題では x 軸方向と y 軸方向とで独立に考えればよいことになるケースが多い (マンハッタンに限らず、各要素ごとに独立にならないかを考察することは重要) の最小値を与える…

とりあえず 1 問目やってみた！累積和の典型題 問題へのリンク 問題概要 以下のような J, O, I で構成される の盤面があたえられる。以下の条件を満たすような 3 マスの組が何個あるか求めよ。 3 マスはそれぞれ J, O, I である J の右側 (行は一緒) に O が…

グリッドの縦方向の情報と横方向の情報を前処理するのは典型ですね！！ 問題へのリンク editorial 類題とか drken1215.hatenablog.com 問題概要 のグリッドの各マス目に数値が書かれている。 各マス に対して、「そのマスと行または列が等しいマスの数値の総…