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

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

ABC-D

新着順 人気順

AtCoder ABC 223 D - Restricted Permutation (1Q, 緑色, 400 点)

順列を題材とした面白い問題。トポロジカルソートの問題でもある。 問題へのリンク 問題概要 の順列であって、以下の 個の条件を満たすもののうち、辞書順最小のものを求めよ。 【 番目の条件】 は よりも先に来る 制約 考えたこと グラフの問題として考えて…

AtCoder ABC 212 D - Querying Multiset (2Q, 茶色, 400 点)

面白かった。priority queue と、「全体に反映させる値を別にもつ」テクニックを学べる問題。 問題へのリンク 問題概要 はじめ、何も入っていない袋がある。次の 回のクエリに答えよ。 クエリタイプ 1:袋に、 と書かれたボールを入れる クエリタイプ 2:袋…

AtCoder ABC 385 D - Santa Claus 2 (1Q, 緑色, 425 点)

難しくはないけど、重たい! 順序付き set の練習問題。 問題へのリンク 問題概要 制約 考えたこと 順序付き set を上手く使う問題。この問題では、次の操作を実現したくなる。ここで、集合 は、初期状態では問題文で与えられる 個の家の座標を格納すること…

AtCoder ABC 342 D - Square Pair (1Q, 緑色, 400 点)

条件を上手に言い換えよう! 問題へのリンク 問題概要 個の整数 が与えられる。 が平方数 という条件を満たすような組 の個数を求めよ。 制約 考えたこと これは「条件の言い換え」を頑張る問題。「 が平方数」という条件を扱いやすいように言い換えよう。こ…

AtCoder ABC 233 D - Count Interval (2Q, 茶色, 400 点)

「区間の値の和」を見たら、累積和をとろう!! 問題へのリンク 問題概要 数列 と整数 が与えられる。 数列の連続する区間であって、その総和が に一致するものが何個あるかを求めよ。 制約 考えたこと 0-indexed で考える。 数列 の累積和を としよう。この…

AtCoder ABC 380 D - Strange Mirroring (1Q, 緑色, 350 点)

実験していくうちにシンプルな構造がわかった。 問題へのリンク 問題概要 英文字からなる長さ の文字列 が与えられる。この文字列に対して、次の操作を 回行ってできる文字列を考える。 【操作】 文字列 に対して、英小文字と英大文字を入れ替えてできる文字…

AtCoder ABC 379 D - Home Garden (2Q, 茶色, 400 点)

「全体に足す」のは難しいから、足す値を別途持っておくというスキル!!! 問題へのリンク 問題概要 以下の 個のクエリに答えよ。 クエリタイプ 1:新たに要素 0 を挿入する(重複もあり) クエリタイプ 2:すでに挿入されているすべての要素に を足す クエ…

AtCoder ABC 378 D - Count Simple Paths (2Q, 茶色, 425 点)

こういう探索系はみんな苦手とするイメージだったけど、結構 Difficulty 低いのね。 問題へのリンク 問題概要 グリッドで、各マスは「空き」または「壁」である。 ある空きマスを出発し、上下左右に隣接するマスへの移動を 回行う方法であって、障害物のある…

AtCoder ABC 333 D - Erase Leaves (2Q, 茶色, 400 点)

問題を言い換えるのが少し難しい 問題へのリンク 問題概要 頂点数 の木が与えられる(頂点番号 )。 この木に対して「葉を 1 つ選んで削除する」という操作を繰り返す。頂点 1 を削除するまでの操作回数の最小値を求めよ。 制約 考えたこと 0-indexed で考え…

AtCoder ABC 283 D - Scope (3Q, 茶色, 400 点)

スタックによるシミュレーション問題! 問題へのリンク 問題概要 整合のとれたカッコ列に対して、英小文字がいくつか挿入されてできる文字列が与えられる (たとえば、"(a(ba))c")。 このような文字列に対して、高橋君が気絶するかどうかを判定したい。次のよ…

AtCoder ABC 060 D - Simple Knapsack (2Q, 水色, 400 点)

面白い。各値に対する答えを予め整理して求めておく手法は頻出! 問題へのリンク 問題概要 個の品物がある。品物 は、重さが であり、価値が である。 いくつかの品物を、総和が 以下となるように選ぶとき、選んだ品物の価値の総和の最大値を求めよ。 制約 …

AtCoder ABC 059 D - Alice&Brown (ARC 072 D) (1D, 青色, 500 点)

面白かった!! 実験で思いつけるかもしれないし、気づいたら証明したい系。 問題へのリンク 問題概要 先手と後手が石取りゲームをする。2 個の山があって、最初それぞれ石が 個積まれている。交互に次の操作をする。 2 個以上の石が積まれている山を 1 つ選…

AtCoder ABC 058 D - 井井井 (ARC 071 D) (2Q, 青色, 400 点)

「x 軸と y 軸を独立に考えられる」と「主客転倒・寄与分解」の合わせ技!! 問題へのリンク 問題概要 座標平面上に、 本の直線 と、 本の直線 がある。 これらの直線のうち 4 本を選んでできる長方形領域は 個あるが、それらの面積の総和を 1000000007 で割…

AtCoder ABC 374 D - Laser Marking (2Q, 茶色, 350 点)

座標平面上の 本の線分の順序を探索して、さらに各線分のどちら側からどちら側になぞるかも探索する。 問題へのリンク 問題概要 座標平面上に 本の線分がある。 本目の線分は、座標 の点と座標 の点を結んでいる。 最初、原点にレーザーがある。レーザーは印…

AtCoder ABC 373 D - Hidden Weights (2Q, 茶色, 400 点)

二部グラフ判定を書いたことがあれば、その要領で解ける! 問題へのリンク 問題概要 頂点数 、辺数 の重み付き有向グラフが与えられる。各頂点 に値 を書き込む方法であって、どの辺 に対しても を満たすようなものを 1 つ求めよ (そのようなものが存在する…

AtCoder ABC 243 D - Moves on Binary Tree (2Q, 茶色, 400 点)

まともに計算すると桁数がとんでもないことになるので、「LU で消す」「RU で消す」を活用しよう! 問題へのリンク 問題概要 頂点数が十分多い完全二分木が与えられる。根の番号は 1 であり、一般に頂点 の左子頂点の番号は 、右子頂点の番号は である。 最…

AtCoder ABC 055 D - Menagerie (ARC 069 D) (2Q, 水色, 500 点)

「いくつかの値を決めると、残りが決まっていくので、最後に整合性を check する」というのは、頻出の典型テクニック! 問題へのリンク 問題概要 円環状に動物 がこの順に並んでいる。各動物は羊 ('S') か狼 ('W') である。ただし、各動物がいずれであるかが…

AtCoder ABC 372 D - Buildings (1Q, 緑色, 400 点)

この手のスタックの問題はもうすっかり常識と化した! 問題へのリンク 問題概要 ビル がこの順に並んでいる。ビル の高さは である。 各 に対して、ビル の間にビル より高いものがないような () の個数を求めよ。 制約 考えたこと いかにもスタックを使いそ…

AtCoder ABC 053 D - Card Eater (ARC 068 D) (3Q, 緑色, 400 点)

きちんとした手続きを経て求めたいところ 問題へのリンク 問題概要 個の整数からなる数列 が与えられる。この数列に次の操作を繰り返して、数列の項がすべて相異なるようにしたい。できあがる数列の項数の最大値を求めよ。 【操作】 数列から 3 個の整数を選…

AtCoder ABC 050 D - Xor Sum (ARC 066 D) (3D, 橙色, 600 点)

繰り上がりがあるから、ただの「桁 DP」よりは難しい。でも少しの工夫で解ける! 問題へのリンク 問題概要 1 個の正の整数 が与えられる。次の条件を満たす整数 が存在するような整数の組 の個数を 1000000007 で割った余りを求めよ。 xor = 制約 考えたこと…

AtCoder ABC 047 D - 高橋君と見えざる手 (ARC 063 D) (1Q, 水色, 400 点)

が関係ないやんけ! 問題へのリンク 問題概要 高橋君は街 の順に訪れる。街 ではりんごの価値は 円である。 高橋君は街 で 円でりんごを好きな数だけ買うことができて、 を満たす街 でそのりんごを好きな数だけ 円で売ることができる。ただし、高橋君はりん…

AtCoder ABC 046 D - AtCoDeerくんと変なじゃんけん (ARC 062 D) (2Q, 水色, 300 点)

一見、 の DP に見えたが、その必要はなかった。 問題へのリンク 問題概要 グーとパーしか出せないジャンケンを 回する。相手が各回に何を出すかが予めわかっている。ただし、どの時点でも (それまでに出したグーの回数) (それまでに出したパーの回数) を満…

AtCoder ABC 045 D - すぬけ君の塗り絵 (ARC 061 D) (2Q, 青色, 400 点)

グリッドが幅広いが、黒色マスの周辺でしか「3 x 3 内部に黒色マスがある」という状況が発生しないことを活用する! 問題へのリンク 問題概要 グリッドの各マスは白色または黒色である。 個のマスが黒色である(座標が与えられる)。 このグリッド内部の各 3…

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

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

AtCoder ABC 370 D - Cross Explosion (1Q, 緑色, 400 点)

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

AtCoder ABC 306 D - Poisonous Full-Course (2Q, 茶色, 400 点)

とっても教育的な DP の問題!!! 問題へのリンク 問題概要 高橋君の前に 個の料理が順に配られる。高橋君はその都度「食べる」「下げてもらう」を選択することができる。 番目の料理は、 のとき、解毒剤入りの、美味しさが の料理 のとき、毒入りの、美味…

AtCoder ABC 361 D - Go Stone Puzzle (1Q, 水色, 425 点)

よくある、パズルの最小手数を求める問題! この手の問題では、まず「あり得る状態」がどれだけあるかを見積もろう! 問題へのリンク 問題概要 マスがあって、最初、前から マスには白石か黒石のいずれかが置かれている。置かれ方は文字列 で表される。後ろ …

AtCoder ABC 240 D - Strange Balls (3Q, 茶色, 400 点)

スタックを活用する系の問題! 問題へのリンク 問題概要 値 の書かれたボールをこの順に筒に挿入していく。 挿入された際に、同じ数 が 個連続したら、それらがすべて消えるものとする。 個目のボールが挿入された瞬間の、筒内のボールの個数を逐次答えよ。 …

AtCoder ABC 307 D - Mismatched Parentheses (3Q, 茶色, 400 点)

カッコ列に関連してシミュレーションしていく問題! 問題へのリンク 問題概要 英小文字と文字 '('、')' からなる長さ の文字列 が与えられる。この文字列に対して、次の操作を繰り返す。 「文字 '(' と ')' に挟まれた部分文字列であって、カッコ文字を含ま…

AtCoder ABC 357 D - 88888888 (1Q, 緑色, 350 点)

面白かった! 問題へのリンク 問題概要 整数 が与えられる。 整数 の十進法表記を 個 concat してできる整数を 998244353 で割った余りを求めよ。 制約 考えたこと まず、整数 が 桁だとしよう! このとき、求めたい値は次のように表現できる。 よって、 と…