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

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

水色diff

AtCoder ABC 161 F - Division or Substraction (水色, 600 点)

めちゃくちゃ面白かった!!! 問題へのリンク 問題概要 整数 が与えられる。以下の条件を満たす 以上 以下の整数 の個数を求めよ。 整数 を用いて、 に対して操作を行っていく が で割り切れるならば を で置き換えて、そうでない場合には を に置き換える…

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

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

AtCoder AGC 003 B - Simplified mahjong (水色, 400 点)

微妙なコーナーケースに注意 問題へのリンク 問題概要 の書かれたカードがそれぞれ 枚ある。以下の条件を満たすようにペアリングしていくとき、最大で何組できるか? ペアとなるカードの数値の差は 1 以下 制約 考えたこと 一瞬、 値が等しいペアを作れるだ…

AtCoder ABC 157 E - Simple String Queries (水色, 500 点)

一瞬、「更新がある」「種類数」ということで、Wavelet Matrix が必要かとびびった 問題へのリンク 問題概要 長さ の文字列 が与えられる。以下の 個のクエリに答えよ タイプ 1: の 文字目を に変更する タイプ 2: の区間 に含まれる文字の種類数を答える …

AtCoder ABC 157 D - Friend Suggestions (水色, 400 点)

とても教育的な Union-Find!!! 問題へのリンク 問題概要 人がいて、 組の友達関係と、 組のブロック関係がある (いずれも双方向的)。 各人について、 直接的な友達関係ではない ブロック関係でもない 友達の友達の...とたどっていくと到着できる ような人…

AtCoder ABC 154 E - Almost Everywhere Zero (水色, 500 点)

DP しなくても間に合うけど、桁 DP 的な考え方が役に立つ! 問題へのリンク 問題概要 100 桁以下の整数 が与えられる。 以上 以下の整数であって、十進法表記で 0 以外の数値がちょうど 個であるようなものが何個あるのかを求めよ。 制約 の桁数 考えたこと …

AtCoder ABC 153 F - Silver Fox vs Monster (水色, 600 点)

区間加算に対応したデータ構造の出番! 問題へのリンク 問題概要 体のモンスターがいて、それぞれ座標 にいて、HP は である。すべてのモンスターを倒したい。 1 回の魔法で、座標 を指定して、[ ] の範囲内にいるモンスターの HP をすべて ずつ減少すること…

AtCoder ABC 152 E - Flatten (水色, 500 点)

「〜の最小値を求めてください」「ただし 1000000007 で割ったあまりで」 ...この設定の歪さを見ると、不思議な気持ちになる 問題へのリンク 問題概要 個の正の整数 が与えられる。以下の条件を満たす正の整数列 をすべて考えたときの、 の最小値を求めよ (1…

AtCoder ABC 151 E - Max-Min Sums (水色, 500 点)

こういう系の「個別要素に分解して考える」という問題が三連発だ!!!!! これもあれも! drken1215.hatenablog.com drken1215.hatenablog.com 問題へのリンク 問題概要 個の整数 が与えられる。これらから 個を選ぶ 通りの方法についての 「選んだ 個の整…

AtCoder ABC 150 D - Semi Common Multiple (水色, 400 点)

面白かった!!! 「2 で何回割れるのか」に着目するのはあるあるだけど、400 点としては難しめな感じかな。 問題へのリンク 問題概要 個の正の整数 と整数 が与えられる。以下の条件を満たす整数 が何個あるか求めよ。 任意の に対して、ある 0 以上の整数 …

第5回 ドワンゴからの挑戦状 予選 2018 B - Sum AND Subarrays (水色, 400 点)

最初、罠に引っかかった 問題へのリンク 問題概要 長さ の数列 が与えられる。これらの連続する区間の総和を書き出していく ( 個ある)。 これらの中から 個選んで AND をとった値として考えられる最大値を求めよ。 制約 嘘貪欲 とりあえず なので、 個の整数…

AtCoder ABC 142 E - Get Everything (水色, 500 点)

個人的には bitDP は「順列を全探索するもの」というイメージがあるけど、今回はそれとはまた違う bitDP という感じ! 問題へのリンク 問題概要 個の宝箱がある。宝箱を開けるための鍵が 個あって、それぞれの鍵はいくつかの宝箱に対応している。鍵 を用いる…

AtCoder ABC 054 C - One-stroke Path (水色, 300 点)

グラフの探索を頑張る問題。現代の AtCoder であまり見ないけど、教育的な全探索問題!!! 問題へのリンク 問題概要 頂点数 、辺数 の無向グラフが与えられる。このグラフ上で頂点 1 から出発するハミルトンパスが何本あるかを数え上げよ。 なおハミルトン…

AtCoder ABC 141 E - Who Says a Pun? (水色, 500 点)

もう文字列は怖くないっ!!! 文字列検索に関するライブラリが充実していれば怖いものがない。でも文字列のことを知らなくても実は DP でも解ける!!! Suffix Array Z-algorithm (editorial 解) ロリハ + 二分探索 「ロリハ + 二分探索」の高速化 (editor…

AtCoder ABC 133 E - Virus Tree 2 (水色, 500 点)

木の走査って 根の方から情報を配っていく 子ノードたちの情報を引っ張ってくる (いわゆる木 DP) という二つの方向性があって、状況に応じてうまいこと使い分けるとよいイメージがある。 問題へのリンク 問題概要 頂点の木があたえられる。木の各頂点を 色に…

AtCoder ABC 131 E - Friendships (水色, 500 点)

順位表メタ読みスキルも大事かもしれない。「たくさん通しているのだから、きっと単純な方法があるに違いない」という感じの 問題へのリンク 問題概要 頂点の連結な無向グラフのうち、その間の最短経路長が 2 となっているような二頂点の組がちょうど 組であ…

diverta 2019_2 C - Successive Subtraction (水色, 500 点)

復元つらい 問題へのリンク 問題概要 黒板に 個の整数 が書かれている。 書かれている数字から 2 個選んで として、これらを消して を新たに書き加える という操作を 回行って最後に残る整数の最大値を求めよ。またそれを達成する操作列を復元せよ ( を毎タ…

AtCoder ABC 128 D - equeue (水色, 400 点)

こういう全探索が意外と出てこないという意見はよく聞くよね。 同時に「複数種類の操作を行える問題では、操作の流れを単純化する」という典型思考を試す問題でもある。 問題へのリンク 問題概要 あなたは誕生日プレゼントとして友人から dequeue D を貰いま…

AtCoder ABC 129 E - Sum Equals Xor (水色, 500 点)

まさにこの考え方で解ける問題 drken1215.hatenablog.com 今回の問題も桁 DP でもよいのだが、実は桁 DP しなくても解ける。 問題へのリンク 問題概要 正整数 が二進数表記で与えられます。 以下の条件を満たす非負整数 の組がいくつ存在するか求めてくださ…

AtCoder ABC 126 D - Even Relation (水色, 400 点)

とても教育的なツリーの探索問題。 問題へのリンク 問題概要 頂点の重み付き無向グラフが与えられる。このグラフの各頂点を白黒に塗る方法であって 同色に塗られた 2 頂点はどれを選んでも、その間のパスの長さは偶数である という条件を満たすものを求めよ…

AtCoder ABC 126 E - 1 or 2 (水色, 500 点)

これまた Union-Find を用いる教育的問題!!!!! 問題へのリンク 問題概要 枚のカードがあって、それぞれ 1 か 2 の数値が書かれている。 枚のカードの数値 をすべて当てたい。 現在、以下の形式をした条件が 個与えらている: 整数 に対して、 は偶数であ…

AtCoder AGC 002 C - Knot Puzzle (水色, 500 点)

気づけばすぐな感じかな 問題へのリンク 問題概要 本のロープがあってそれぞれの長さは で与えられる。最初、ロープ の右端とロープ の左端が結ばれている。今、 長さが 以上のひとつながりのロープを選び、その中に結び目があればどれか 1 つ選んでほどく …

AtCoder AGC 003 C - BBuBBBlesort! (水色, 600 点)

楽しかった 問題へのリンク 問題概要 長さ の数列 が与えられる。どの 2 要素も互いに相異なることが保証される。これに対し 隣り合う 2 要素を swap する 連続する 3 要素を反転する という操作を行ってソートしたい。ただし、1 の使用回数を最小にしたい。…

AtCoder ABC 114 D - 756 (水色, 400 点)

editorial は「75」という整数の特徴をフル活用している。 そして 75 という整数の特徴を活用しない DP による方法もあると説いている。 ここでは 75 という整数の特徴も活用せず、DP もしない (といっても DP への改良は容易) 愚直な全探索でも通った。 問…

AtCoder AGC 033 B - LRUD Game (水色, 600 点)

嘘貪欲は一瞬脳裏によぎり、それを振り払って問題を解いてた。発想はこれの「後ろから解く」のに似ている。 drken1215.hatenablog.com 問題へのリンク 問題概要 × のグリッドのあるマスにロボットが置かれている。先手と後手はそれぞれ長さ の自分の文字列 …

AtCoder ABC 113 D - Number of Amidakuji (水色, 400 点)

あみだくじ 問題へのリンク 問題概要 縦棒の個数が 、横棒が縦方向に 刻みのあみだくじであって、 番目からスタートすると 番目に到着するようなものを数え上げよ。 制約 考えたこと いかにも DP という感じではあるね。 dp[ i ][ j ] := 縦棒を上から i 刻…

AtCoder ABC 122 D - We Like AGC (水色, 400 点)

こういうの素早く書けるようになるにはどうしたらいいんだろう... 問題へのリンク 問題概要 'A', 'G', 'C', 'T' のみからなる長さ の文字列のうち、「どの隣接した 2 文字を swap しても "AGC" を連続部分列として含まないもの」が何通りあるか求めよ。 制約…

AtCoder ABC 123 D - Cake 123 (水色, 400 点)

priority_queue で動的に 個出力する問題作りたいな〜と思ってぼんやりストックしてた問題と一緒だった!!!!!! 問題へのリンク 問題概要 個の要素からなる数列 個の要素からなる数列 個の要素からなる数列 が与えられる。 からそれぞれ 1 個ずつとりだ…

AtCoder AGC 032 B - Balanced Neighbors (水色, 700 点)

三角形、四角形、、、と順に作って行って、五角形の場合を作るのに苦労した!!! 問題へのリンク 問題概要 頂点番号が な単純無向であって、以下の条件を満たすものを 1 つ構築せよ: どの頂点についても、その頂点に隣接している頂点の番号の和が等しい 制…

AtCoder AGC 031 B - Reversi (水色, 700 点)

これは安定感のある思考過程を経て解けた気がするので共有したい気持ち!!! 問題へのリンク 問題概要 長さ の数列 が与えられる。各 は 以上 以下の整数値である。今、以下のような操作を何回でも行うことができる: となるような < を選んで、 と との間の…