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

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

2021-08-11から1日間の記事一覧

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

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

AtCoder ABC 213 D - Takahashi Tour (茶色, 400 点)

DFS (深さ優先探索) の動きをシミュレーションする問題。 問題へのリンク 問題概要 頂点番号が であるような木が与えられます。 今このグラフにおいて、頂点 1 から出発して、次の動きを繰り返します。 いまいる頂点に隣接する頂点のうち、まだ訪れたことが…

AtCoder ABC 213 C - Reorder Cards (茶色, 300 点)

一見いかめしい問題だけど、単に座標圧縮するかどうかだと気づけるかですね。 問題へのリンク 問題概要 のグリッドが与えられます。数 はそれぞれマス に書かれています。それ以外の マスには何も書かれていません。 このグリッドに対して、次の操作を可能な…

AtCoder EDPC W - Intervals

まさに、「DP 配列をセグメント木に載せる」というセグ木上の in-place DP ですね!!! 一部の競プロ界隈では、俗に実家 DP などと呼ばれてたりしていたものです。 問題へのリンク 問題概要 0 と 1 のみからなる長さ の文字列を 0-1 文字列と呼ぶことにしま…

AtCoder EDPC Q - Flowers

まさに重み付き LIS ともいうべき問題ですね。 問題へのリンク 問題概要 本の花が横一列に並んでいます。 左から 番目の花の高さは で、美しさは です。 太郎君は何本かの花を抜き去ることで、次の条件が成り立つようにしようとしています。 「残った花を左…