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

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

黄色diff

新着順 人気順

AtCoder ABC 181 F - Silver Woods (黄色, 600 点)

条件反射で二分探索してしまった!!!この問題めっちゃ面白くて好き!!! 問題へのリンク editorial 問題概要 平面上に 2 直線 で囲まれた通路がある。この通路の中の の部分に 本の大きさの無視できる釘が打たれており、 本目の釘の座標は である。 高橋…

AtCoder ABC 213 F - Common Prefixes (3D, 黄色, 500 点)

これを機会に SA-IS を整備した! 問題へのリンク 問題概要 2 つの文字列 に対して「先頭何文字が一致しているか」を と表すことにします。 長さ の文字列 が与えられます。 の 文字目以降のみからなる部分文字列を と表すことにします。 のそれぞれに対して…

Tenka1 2019 D - Three Colors (2D, 黄色, 600 点)

お 見た目とても面白そう 問題へのリンク 問題概要 要素からなる数列 があたえられる。各要素を「赤」「緑」「青」の三色のいずれかに塗る方法のうち、各色の合計値を として三辺の長さが となるような三角形が存在するようなものを数え上げよ。998244353 で…

AtCoder ABC 127 F - Absolute Minima (2D, 黄色, 600 点)

超絶苦手系。でもこういうのパッとできるようにせな。 問題へのリンク 問題概要 関数 があります。 はじめ、これは定数関数 です。 個のクエリが与えられるので、順番に処理してください。クエリは 2 種類あり、入力形式とクエリの内容は以下の通りです。 更…

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

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

AtCoder ABC 266 G - Yet Another RGB Sequence (黄色, 600 点)

すごく楽しかった。解析的に式で求められるのね。 問題へのリンク 問題概要 個の文字 R、 個の文字 G、 個の文字 B を並べてできる文字列のうち、部分文字列として含まれる RG がちょうど 個であるようなものの個数を 998244353 で割ったあまりを求めよ。 制…

AtCoder ABC 009 D - 漸化式 (2D, 試験管黄色)

AND と XOR は、それぞれ「掛け算」と「足し算」に対応するので、行列累乗が使える! 問題へのリンク 問題概要 個の整数の組 と が与えられる。 数列 は次の漸化式で定義される。 () AND XOR AND XOR ... XOR AND () の値を求めよ。 制約 考えたこと AND は…

AtCoder ABC 250 F - One Fourth (2D, 黄色, 600 点)

くしらっちょ君と一緒に解いた! 実装が辛い。 問題へのリンク 問題概要 頂点数が である凸多角形が与えられる。この凸多角形の面積を とする。 今、凸多角形の隣接しない 2 頂点を結ぶ直線によって凸多角形を 2 つの多角形に分ける。そして、2 つの多角形う…

AtCoder ABC 307 F - Virus 2 (3D, 黄色, 550 点)

セグ木上二分探索使ったというコメントをよく見たけど、僕の方針でも使うことになった 問題へのリンク 問題概要 頂点数 、辺数 の単純な重み付き無向グラフが与えられる。 日目、 個の頂点 がウィルスに感染した。一度ウィルスに感染した頂点はずっと感染し…

AtCoder ABC 318 G - Typical Path Problem (3D, 黄色, 575 点)

点素パスのパッキング系の問題、出ないな〜〜と思っていたら出た! 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。3 頂点 が指定される。 2 頂点 を端点とする単純パスであって、頂点 を通るものが存在するかどうか判定せよ。 制約 …

AtCoder ABC 369 G - As far as possible (3D, 黄色, 600 点)

Euler Tour して、遅延評価セグ木(区間加算 + 区間 min)に乗せて......という解法を考えていたところに、あまりにもシンプルな想定解法を目にして、感動した! 問題へのリンク 問題概要 頂点数 の重み付き木が与えられる。 に対して、次の問に答えよ。 個…

AtCoder ABC 373 G - No Cross Matching (3D, 黄色, 600 点)

すごく面白かった! 問題へのリンク 問題概要 二次元平面上に点 と という 個の点がある。同一直線上に 3 点が乗ることはない。 の順列 であって、次の条件を満たすものが存在するかどうかを判定し、存在するならば 1 つ示せ。 【条件】 に対して、2 点 , を…

AtCoder ARC 188 C - Honest or Liar or Confused (3D, 黄色, 700 点)

面白かった!! 問題へのリンク 問題概要 人がいて、それぞれ正直者であるか、嘘つきであるかのいずれかである。また、各人は混乱していないか、混乱しているかのいずれかである。 混乱していない正直者は、常に正しいことをいう 混乱している正直者は、常に…

AtCoder ARC 190 B - L Partition (3D, 黄色, 800 点)

「二項係数の和」は結構なんとかなることを学んだ! 備忘録程度に書く。 問題へのリンク 問題概要 下の図のように、 グリッドを、レベル の L 字で隙間なく埋め尽くす (レベル の L 字の定義は問題文参照)。 マス を指定したとき、次の 回のクエリに答えよ。…

AtCoder ARC 189 D - Takahashi is Slime (3D, 黄色, 700 点)

で解けた! 同じ値が連続する場合の対処に苦慮した。 問題へのリンク 問題概要 強さが のスライムが一列にこの順に並んでいる。 に対して、次の問に答えよ。 【問】 初期状態で左から 番目にいるスライムが高橋君である。高橋君が下記の行動を好きな回数だけ…

AtCoder AGC 070 A - Multiples in the String (3D, 黄色, 600 点)

"142857" はエニアグラムやっていたら毎日目にする。エニアグラムは競プロの役に立つ! 問題へのリンク 問題概要(output only) 正整数 と文字列 の組であって以下の条件を全て満たすものを 1 つ挙げよ。 は 0 から 9 までの数字からなる長さ 5000 以下の文…

AtCoder ARC 076 E - Connected? (2D, 黄色, 700 点)

面白かった! 交差数に関する問題に帰着される。 問題へのリンク 問題概要 座標平面上に、4 頂点の座標が であるような長方形があり、その長方形の周上または内部に、 とラベルのついた 個の点がある(どの 2 点も相異なる)。 について、同じラベル の 2 点…

AtCoder ABC 044 D - 桁和 (ARC 060 D) (1D, 黄色, 500 点)

で場合分けする系! 問題へのリンク 問題概要 正の整数 が与えられる。次の条件を満たす最小の整数 ()を求めよ。(存在しない場合は -1。) 【条件】 を 進法表記したときの桁の和が である 制約 考えたこと が小さい範囲は愚直に調べればよさそうだ。 があ…

AtCoder ABC 359 G - Sum of Tree Distance (3D, 黄色, 600 点)

いろんな解法あり。 問題へのリンク 問題概要 頂点数 の無向木が与えられる。各頂点 には色 が塗られている。 このグラフにおいて、 であるような頂点組 () についての、2 点 間の距離の総和を求めよ。 制約 考えたこと マージテクで考えた。例によって頂点 …

AtCoder ABC 356 F - Distance Component Size Query (3D, 黄色, 525 点)

苦手系の問題だけど、解けてよかった。 問題へのリンク 問題概要 正の整数 が与えられる。はじめ空である集合 が与えられるので、次のクエリに答えよ。 クエリタイプ 1 x:集合 に整数値 がない場合は挿入し、ある場合は削除する クエリタイプ 2 x:集合 に…

AtCoder ABC 205 E - White and Black Balls (2D, 黄色, 500 点)

カタラン数をわかっていればできる! 問題へのリンク 問題概要 正の整数 が与えられる。黒いボール 個と、白いボール 個を一列に並べる方法のうち、次の条件を満たすものの個数を 1000000007 で割った余りを求めよ。 【条件】 どの についても、列の左から …

AtCoder ARC 176 C - Max Permutation (3D, 黄色, 700 点)

これは面白かった。 問題へのリンク 問題概要 の順列であって、以下の 個の条件を満たすものの個数を 998244353 で割った余りを求めよ。 について、 である 制約 考えたこと グラフの問題として考えることにした。つまり、0-indexed で表現すると 頂点数 、…

AtCoder ABC 350 G - Mediator (3D, 黄色, 600 点)

本当に色んな解法がある問題っぽい!! 問題へのリンク 問題概要 頂点 の 頂点からなる無向グラフがあり、最初は辺がない。以下の 2 種類のオンラインクエリに答えよ。 クエリタイプ 1:頂点 間に辺を結ぶ クエリタイプ 2:頂点 の双方に隣接する頂点がある…

AtCoder ABC 347 F - Non-overlapping Squares (3D, 黄色, 525 点)

面白かった。JOI でもありそうな問題。長方形を 3 枚並べるのは典型らしい。 問題へのリンク 問題概要 のグリッドがあって、各マス には数値 が描かれている。 このグリッド上で の正方形を重ならないように 3 枚並べるとき、これらの正方形に覆われたマスの…

AtCoder ARC 171 D - Rolling Hash (黄色, 600 点)

コンテスト後に解いた。こっちの方が解きやすかった。 問題へのリンク 問題概要 制約 考えたこと 最初は の指数を気にするのかな......などと考えていたが、考えていくうちに の値など、ただの飾りであることがわかってきた。 まず、問題の条件を言い換える…

AtCoder ARC 171 C - Swap on Tree (黄色, 600 点)

備忘録として。解説よりもおそらく面倒な DP をした。 問題へのリンク 問題概要 考えたこと 基本的に木 DP のノリで考えることにした。 根を 1 つとったとき、異なる部分木間で交換される頂点はただだか 1 個以内である。そこで次の DP をした。 dp[v][k] ← …

AtCoder ARC 167 D - Good Permutation (3D, 黄色, 700 点)

モノグサでバチャやって、なんとか通した! 問題へのリンク 問題概要 の順列 が与えられる。この順列に対して「2 個の要素を選んで swap する」という操作を実行して、 「順列から誘導される Functional Graph の連結成分の個数が 1 個」 という状態を実現し…

AtCoder ABC 325 G - offence (3D, 黄色, 575 点)

o......f...(.....)... のようなパターンで、(.....) の中身が消せるような場合を最初見落とした。 問題へのリンク 問題概要 長さ の文字列 に対して、次の操作を好きな回数だけ行える。操作後の文字列の長さとして考えられる最小値を求めよ。 が連続する部…

AtCoder ARC 026 D - 道を直すお仕事 (試験管黄色)

「平均値の最小化」に基づく二分探索 + 最小全域問題 問題へのリンク 問題概要 (意訳) 頂点数 、辺数 の重み付き単純無向グラフが与えられる。各辺 は、重みが であり、長さが である。 グラフの辺集合のうち、すべての頂点を連結にするものを考える。そのよ…

AtCoder ABC 320 F - Fuel Round Trip (3D, 黄色, 550 点)

少し重たかった。でもいい問題。JOI にありそう。 問題へのリンク 問題概要 数直線上に 箇所の燃料補給所がある。 番目の補給所は次のようになっている。 座標 にある 補給すると、現在の HP が であるとき、HP が になる (コストとして を支払う) 今、高橋…