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

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

水色diff

AtCoder ARC 171 B - Chmax (水色, 600 点)

順列をどうのこうのする系、最近多いかもしれない。 問題へのリンク 問題文 考えたこと 操作の内容を解釈するのに少し苦労した。 順列 から誘導される Functional Graph を考えた。このグラフ上で、頂点 から出発して頂点番号が大きくなる限り進んでいったと…

AtCoder ARC 167 B - Product of Divisors (水色, 500 点)

面白かった! 問題へのリンク 問題概要 以上の整数 と非負整数 が与えられる。 の正の約数の総積が で最大何回割れるかを 998244353 で割った余りで求めよ。 制約 考えたこと 一般に、2 以上の整数 の正の約数の総積は、 の約数の個数を とすると となる。た…

AtCoder ABC 328 F - Good Set Query (水色, 525 点)

重み付き Union-Find そのもの。もしくは、列挙可能 Union-Find 使ってマージテクでも。 問題へのリンク 問題概要 個の整数値 に関する制約条件が 個与えられる。 番目の制約条件では 3 つの整数の組 が与えられ、 という形をしている。ここで、次のクエリに…

AtCoder ABC 327 E - Maximize Ratin (水色, 475 点)

式がいかめしくて戸惑うけど、DP 自体は比較的単純 問題へのリンク 問題概要 個の値 が与えられる。 これらの中から順序を保っていくつか選ぶ。選び方のスコアは、 個の整数 を選んだとしたとき、 で与えられる。このスコアの最大値を求めよ。 制約 考えたこ…

AtCoder ABC 325 D - Printing Machine (水色, 450 点)

とてもややこしくてハマってしまった......。とても教育的な Greedy 問題。 問題へのリンク 問題概要 個の商品がベルトコンベアで運ばれてくる。 番目の商品は、時刻 から時刻 の間 (両端含む) に点字できる。 点字マシンは 1 秒あたり 1 個の商品にしか点字…

AtCoder ABC 034 D - 食塩水 (試験管水色)

とても典型的な「平均値の最大化」→「二分探索」の問題! 問題へのリンク 問題概要 個の食塩水がある。 番目の食塩水は、重さが グラムであり、濃度 パーセントである。 これらの食塩水から 個選んで混ぜてできる食塩水の濃度の最大値を求めよ。 制約 考えた…

AtCoder ABC 323 F - Push and Carry (水色, 525 点)

怒りの場合分け。ちょっと苦手系だけど一発 AC できてよかった。 問題へのリンク 問題概要 高橋君は現在 にいて、荷物は にあり、荷物を目的地 に届けたい。 高橋君は荷物のある位置に入ることはできず、荷物と隣接した状態から荷物の方向に移動すると、荷物…

AtCoder ABC 323 E - Playlist (水色, 450 点)

よくある区間分割の DP だけど、それでよいことに思い至るのが難しいかもしれない。 問題へのリンク 問題概要 曲あって、それぞれの曲の長さは である。 今、時刻 0 から開始して「曲を一様ランダムに流し、それが終わったらまた一様ランダムに曲を選択して…

AtCoder ABC 322 D - Polyomino (水色, 400 点)

最近、実装重たい全探索問題多いね! 問題へのリンク 問題概要 下図のようなポリオミノが 3 個与えられる。いずれも 4 × 4 グリッドにおさまるサイズであり、入力は 4 × 4 グリッドで与えられる。文字 '#' に対応する部分が与えられるポリオミノに対応する。…

AtCoder ABC 256 E - Takahashi's Anguish (水色, 500 点)

最近話題の Functional Graph の問題! 問題へのリンク 問題概要 人 がいる。各人 には 1 人ずつ嫌いな人 がいる。 今、彼らに順番にキャンディーを配る。ただし、各 について、もし人 よりも先に にキャンディーを配ると、不満度が だけ加算される。 キャン…

AtCoder ABC 311 E - Defect-free Squares (水色, 475 点)

有名な DP をするか、二次元累積和 + 二分探索をするか 問題へのリンク 問題概要 のグリッドが与えられる。グリッドの各マスのうち、指定された 個のマスには穴があいている。その他のマスは穴があいていない。 グリッドに含まれる正方形であって、その内部…

AtCoder ABC 270 D - Stones (水色, 400 点)

いわゆる「得点差を最大化したい」というゲーム DP!! 問題へのリンク 問題概要 個の石が積まれた山を使って石取りゲームをします。先手と後手は交互に次の操作を行います。 個のいずれかの個数の石を取り除きます ただし、 が残っている石の個数よりも小さ…

AtCoder ABC 201 D - Game in Momotetsu World (水色, 400 点)

慣れないと頭がごっちゃになるけど、一度慣れればもう機械的に解ける系!! 問題へのリンク 問題概要 のグリッドがある。各マスには '+' か '-' のいずれかの文字が書かれている。 最初、左上マスにコマが置かれている。高橋君と青木君は交互に、次の操作を…

AtCoder ABC 310 D - Peaceful Teams (水色, 400 点)

再帰関数を使った全探索が書けるかどうかが試される! 問題へのリンク 問題概要 人のスポーツ選手を 個のグループに分けたい。 ただし、仲の悪いスポーツ選手の組が 組ある。任意の に対して、選手 と選手 を同じグループに属させてはならない。 この制約を…

AtCoder ABC 305 F - Dungeon Explore (水色, 525 点)

DFS をちゃんと分かっているかが問われる! DFS の動きをシミュレートする問題 問題へのリンク 問題概要 この問題はインタラクティブ問題である。 頂点数 、辺数 の連結かつ単純な無向グラフがある。ただし最初の入力として与えられるのは の値のみである。 …

AtCoder ABC 235 E - MST + 1 (水色, 500 点)

MST の理解が問われる面白い教育的問題! 問題へのリンク 問題概要 頂点数 、辺数 の連結な重み付き単純無向グラフ が与えられる。なお、各辺の重みはすべて互いに異なることが保証されている。 の最小全域木を とする (一意に定まることが示せる)。 このグ…

AtCoder ABC 302 F - Merge Set (水色, 500 点)

下手を打つと密なグラフになって TLE してしまう!! スーパーノードを作ることでグラフを sparse にするテク! 問題へのリンク 問題概要 以上 以下の整数値からなる 個の有限集合 が与えられる。 以下の操作を最小回数繰り返すことによって、「 と をともに…

AtCoder ABC 016 D - 一刀両断 (試験管水色)

幾何の問題。特に「線分と線分の交差判定」に関する問題! 問題へのリンク 問題概要 凸とは限らない 角形 が与えられる。 番目の頂点の座標は である。 この多角形 の外部に 2 点 , がある。この 2 点を結ぶことによって、多角形 をいくつかのピースに分ける…

AtCoder ARC 160 B - Triple Pair (水色, 500 点)

これ系は好き! これに近いのを ABC-D で最近よく見かける気がする。 問題へのリンク 問題概要 整数 が与えられる。 3 つの整数の組 であって、 がすべて 以下であるようなものの個数を 998244353 で割ったあまりを求めよ。 ケース与えられる。 制約 考えた…

AtCoder ABC 300 E - Dice Product 3 (水色, 500 点)

確率や期待値を計算する DP をするときは、自己ループを除去することが多いね。 問題へのリンク 「EDPC J - ボール」などは類題と言える。先にこの問題を解いておくと、今回の問題も解きやすいかもしれない! qiita.com 問題概要 以上 以下の整数が等確率で…

AtCoder ABC 281 E - Least Elements (水色, 500 点)

よくあるデータ構造問題!! めっちゃ色んな解法がある! 問題へのリンク 問題概要 長さ の整数列 と整数 が与えられる (0-indexed で表している)。 各 に対して、次の問題に答えてください。 個の整数 を小さい順に並び替えたときの先頭 個の総和を求めよ。…

AtCoder ABC 087 D - People on a Line (ARC 090 D) (水色, 400 点)

重み付き Union-Find が有効活用できる問題! 問題へのリンク 問題概要 個の変数 の値を決定したい。 これらの値を決定するための 本の制約条件がある。このうち 個めの情報は 3 つの値 によって与えられ、 であるという制約条件を表す。 これら 本の制約条…

AtCoder ABC 280 E - Critical Hit (水色, 500 点)

EDPC A - Frog 1 とほとんど同じ DP で解けますね! 問題へのリンク 問題概要 体力が であるモンスターが 1 体います。高橋君はモンスターに対し、モンスターの体力が 1 以上残っている限り繰り返し攻撃を行います。 高橋君は 1 回の攻撃で、 の確率でモンス…

AtCoder ABC 250 E - Prefix Equality (水色, 500 点)

とても色んな解法が考えられる問題ですね。ハッシュで殴るのが最も簡単だとは思います。そのほかにもさまざまな解法が考えられます。 問題へのリンク 問題概要 2 つのサイズ の整数列 と が与えられます。 これらの数列に対して 回のクエリが与えられます。…

AtCoder ABC 246 E - Bishop 2 (水色, 500 点)

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

AtCoder ABC 245 E - Wrapping Chocolate (水色, 500 点)

これ!!! ABC 091 C - 2D Plane 2N Point とほとんど同じ!! ただ制約が大きいので、貪欲法を高速化する必要がありますね。 問題へのリンク 問題概要 個のチョコレートと、 個の箱があります。 番目のチョコレートはサイズ であり、 番目の箱はサイズ で…

AtCoder ABC 213 E - Stronger Takahashi (水色, 500 点)

かの有名な「器物損壊!高橋君」の類題ですね。 drken1215.hatenablog.com 問題へのリンク 問題概要 のグリッドがあって、各マスは通路マス (.) か壁マス (#) のいずれかです。 今、左上のマス から右下のマス へと移動したいです。上下左右に移動することが…

AtCoder ARC 005 C - 器物損壊!高橋君 (試験管水色)

通称 0-1 BFS と呼ばれるアルゴリズムが使える問題ですね。 問題へのリンク 問題概要 のマス目で表現された地図が与えられます。 . は通路、# は壁を表します。s マスから出発して、上下左右への移動を繰り返しながら g マスへと到達したいとします。. マス…

AtCoder ABC 075 D - Axis-Parallel Rectangle (水色, 400 点)

古き良き全探索問題!! 問題へのリンク 問題概要 二次元平面上に 個の点があります。 番目の点の座標を とします。 この二次元平面上で各辺が X 軸・Y 軸に平行であるような長方形であって、 個の点のうち 個以上の点を内部および周に含むようなものを考え…

AtCoder ABC 091 C - 2D Plane 2N Point (ARC 092 C) (水色, 400 点)

とても教育的かつ典型的な貪欲法の問題ですね。 問題へのリンク 問題概要 二次元平面上に、赤い点と青い点が 個ずつあります。 個目の赤い点の座標は であり、 個目の青い点の座標は です。 赤い点と青い点は、 座標と 座標がともに赤い点よりも青い点の方が…