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

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

緑色diff

AtCoder ABC 146 D - Coloring Edges on Tree (緑色, 400 点)

軽めの構築問題!! 今回は「最大次数」というのが割と明らかだけど、しっかり構築法踏まえて証明する練習をすると、高難易度問題にも繋がりそう! 問題へのリンク 問題概要 頂点の木が与えられる。 本の辺に色を塗っていきたい。ただし、どの頂点についても…

AtCoder ABC 156 D - Bouquet (緑色, 400 点)

二項係数を使いこなすっ!!! 問題へのリンク 問題概要 種類の花束から何個か選ぶ方法のうち、それが 個でも 個でもないようなものが何通りあるかを 1000000007 で割ったあまりを求めよ。 制約 考えたこと 結局、 個のものからいくつか選ぶ方法 ( 通りある)…

AtCoder ABC 160 D - Line++ (緑色, 400 点)

すごく色んな考え方ができる問題ですね! 問題へのリンク 問題概要 個の頂点を持つ無向グラフ がある。 の辺集合は と とを結ぶ辺 頂点 と頂点 とを結ぶ辺 とで構成されている。各 に対して、最短距離が であるような頂点対が何個あるかを求めよ。 制約 考え…

AtCoder ABC 163 D - Sum of Large Numbers (緑色, 400 点)

「作れる数が連続する整数になる」というの、実は結構よくある!! 問題へのリンク 問題概要 個の整数 がある。 これらから 個以上の整数を選んで合計して得られる整数としてありうるものの個数を 1000000007 で割ったあまりを求めよ。 制約 考えたこと まず…

AtCoder ABC 045 C - たくさんの数式 (ARC 061 C) (緑色, 300 点)

AtCoder 版蟻本に bit 全探索の最初の例題として、この問題を挙げていたので。 問題へのリンク 問題概要 "231" といった 1〜9 の数値で構成された、長さ の文字列 が与えられる。文字列の隙間に '+' を挿入する方法は 通りある。そのそれぞれについての計算…

AtCoder ABC 079 D - Wall (緑色, 400 点)

Floyd--Warshall と、あとグリッド上の各マスは独立に考えて OK。 問題へのリンク 問題概要 のグリッドがあって、各マスには -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 のいずれかの数値が書かれている。目的は -1 以外のマスをすべて 1 に変えることである。 各マ…

AtCoder AGC 017 A - Biscuits (緑色, 200 点)

これ、知らなくても解ける制約設定だけど、結構大変やね 問題へのリンク 問題概要 個の正の整数 が与えられる。これらからいくつか選ぶ方法のうち、総和を 2 で割ったあまりが となる方法が何通りあるかを求めよ。 制約 考えたこと 一般に 総和が奇数 ⇔ 和の…

AtCoder AGC 016 A - Shrinking (緑色, 300 点)

一瞬コーナーケースがないかと怖くなる 問題へのリンク 問題概要 長さ の文字列 が与えられる。この文字列に対し、以下の操作を好きな回数だけ行うことができる。文字列を「単一の文字からなる状態」にするのに必要な操作回数の最小値を求めよ。 文字列の各…

AtCoder ABC 161 D - Lunlun Number (緑色, 400 点)

この手の DFS、一時期全然見なかったけど、最近復活してきた! 問題へのリンク 問題概要 1 以上の整数であって、隣り合う桁の値の絶対値が 1 以下であるような数をルンルン数とよぶ。 番目に小さいルンルン数を求めよ。 制約 考えたこと さて、「 番目に小さ…

AtCoder AGC 018 A - Getting Difference (緑色, 300 点)

操作の仕方が Euclid の互除法そのものになっているタイプの問題。 問題へのリンク 問題概要 要素数 の数列 が与えられる。これに対して以下の操作を好きな回数だけ行うことができる: 整数を 2 つ選び、その差の絶対値をとり、それを数列に新たに挿入する 整…

AtCoder AGC 043 A - Range Flip Find Route (緑色, 400 点)

「予め盤面をいじることができる」という設定の問題にはある程度の定石があるように思う! 問題へのリンク 問題概要 の盤面が与えられ、左上から右下まで行きたい。'#' マスは壁を表し、'.' マスは通路を表す。 予め盤面に以下の操作を行うことができる。最…

AtCoder Petrozavodsk Contest 001 C - Vacant Seat (緑色, 500 点)

インタラクティブ...でも問題自体は「単調性が成り立たなくても二分探索できるよ!」という教育的なものだった! 問題へのリンク 問題概要 円形状に並んだ 個の椅子がある ( は奇数)。各椅子は 男性がいる 女性がいる 空席 のいずれかである。どの隣り合う 2…

AtCoder Petrozavodsk Contest 001 B - Two Arrays (緑色, 300 点)

面白かった。間違いやすいけど、このくらいなら!!! 問題へのリンク 問題概要 長さ の正の整数からなる二つの数列 、 が与えられる。以下の操作を好きな順序で好きな回数だけ行える。 と が一致するようにすることは可能か? の要素を一つ選んで する の要…

CODE FESTIVAL 2017 qual C C - Inserting 'x' (緑色, 400 点)

少しでも実装を楽にしたい 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。以下の操作を最小回数行って回文にしたい。その最小回数を求めよ。不可能な場合は -1 を出力せよ。 のどこかに 'x' を挿入する 制約 考えたこと まず可…

AtCoder ABC 062 C - Chocolate Bar (ARC 074 C) (緑色, 400 点)

最適解の形を丁寧に場合分けして考える系 問題へのリンク 問題概要 の板チョコレートを 3 つの長方形に割りたい。そのときの 3 つの長方形の面積の最大値と最小値の差の最小値を求めよ。 制約 考えたこと まず思ったのは、 のうちの少なくとも一方が 3 の倍…

AtCoder ABC 153 E - Crested Ibis vs Monster (緑色, 500 点)

個数制限なしナップサック!!!!!!! 問題へのリンク 問題概要 種類の魔法を駆使して、HP が のモンスターを倒したい。 番目の魔法は、魔力を だけ消費して、モンスターの HP を だけ減らすことができる モンスターの HP を 0 以下にするのに消費する魔…

CODE FESTIVAL 2016 qual A C - 次のアルファベット / Next Letter (緑色, 400 点)

辞書順最小の教育的例題!!! 問題へのリンク 問題概要 長さ の文字列 が与えられる。この文字列に以下の操作をちょうど 回行う。行った結果得られる文字列の辞書順最小なものを求めよ。 の文字を 1 つ選んで、1 文字進める。ただし 'z' は 'a' になる 制約…

AtCoder ABC 152 D - Handstand 2 (緑色, 400 点)

こういうのをスパッと解けるようになりたい 問題へのリンク 問題概要 以上 以下の整数の組 であって、 の最上位の値と の一の位の値が等しい の最上位の値と の一の位の値が等しい という条件を満たすものが何個あるかを求めよ。 制約 考えたこと ペアリング…

キーエンス プログラミング コンテスト 2020 B - Robot Arms (緑色, 200 点)

区間スケジューリング問題そのものだった!!! ...とはいえ 200 点というのは衝撃!!! 問題へのリンク 問題概要 ある工場では、 数直線上に 個のロボットが設置されている。 ロボット は座標 に設置されていて、左右に長さ のアームを伸ばしている。 これ…

AtCoder ABC 151 D - Maze Master (緑色, 400 点)

面白かった。BFS したり、Warshall--Floyd したり。 問題へのリンク 問題概要 の盤面が与えられる。各マスは '.' か '#' のいずれかである。それぞれ「通路」と「壁」を表している。 「通路を 2 箇所 指定したときの、上下左右に通路のみをたどって から へ…

AtCoder AGC 023 A - Zero-Sum Ranges (緑色, 200 点)

200 点問題で最も難しい問題として名高い問題ですね。 これについては、以下の「累積和」について特集した記事で詳しく解説しました! qiita.com

AtCoder ABC 148 E - Double Factorial (緑色, 500 点)

じゅぴろ君が「これは中受典型」と言いそうな雰囲気がありますね。 問題へのリンク 問題概要 以上の整数 が与えられる。 を計算した値において、末尾に何個の 0 がつくのかを求めよ。 制約 考えたこと これとよく似た形で、たとえば の末尾に 0 が何個つくか…

AtCoder ABC 102 C - Linear Approximation (ARC 100 C) (緑色, 300 点)

| x - a | + | x - b | + | x - c | + ... の最小値を求める問題には定石があるぞいぞい 問題へのリンク 問題概要 長さ の整数列 が与えられます。整数 をいろいろ変えたときの の最小値を求めてください。 制約 考えたこと 非本質だけど、 って普通「変数」…

AtCoder ABC 111 C - /\/\/\/ (ARC 103 C) (緑色, 300 点)

意外と罠にはまりやすい問題かもしれない!!! この手の問題は「最適解の形を考える」という意識で解くと良さそう。 そして、コーナーケースがサンプルにあるのが親切。 問題へのリンク 問題概要 長さ ( は偶数) の数列 が /\/\/\/ であるとは 任意の に対…

AtCoder ABC 147 C - HonestOrUnkind2 (緑色, 300 点)

とても教育的な問題でしたね!!! ここにまとめました! drken1215.hatenablog.com 以下のような問題です。bit 全探索とよばれているもので、 通りの選択肢をすべて調べ上げる手法を用います。 問題概要 人がいて、それぞれ「正直者」であるか、「不親切な…

AtCoder ABC 142 D - Disjoint Set of Common Divisors (緑色, 400 点)

すごく楽しくて教育的な整数問題 問題へのリンク 問題概要 2 つの正の整数 が与えられる。 の公約数から何個か整数を選ぶことを考える。 選んだ整数からどの 2 つをとっても、それらが互いに素になるようにしたい。 選べる個数の最大値を求めよ。 制約 考え…

AtCoder ABC 057 C - Digits in Multiplication (緑色, 300 点)

整数に関する問題でまずは直面する典型的な事柄を学べる教育的問題!!! 例えば整数 が素数かどうかを判定するのは、実は から まで順に試し割りすればよいという話など。 問題へのリンク 問題概要 正の整数 が与えられる。 を満たす正の整数 の組をすべて…

AtCoder ABC 061 C - Big Array (緑色, 300 点)

「k 番目を求める」に関する典型的な処理を要求される問題。 問題へのリンク 問題概要 空集合 に対して、以下の 回の操作を行う: に整数 を 個挿入する 回の操作後の S において 番目に小さな値を求めよ。 制約 考えたこと この問題の注意点として、 を具体…

AtCoder ABC 141 D - Powerful Discount Tickets (緑色, 400 点)

問題を読み替えつつ Greedy!!! 問題へのリンク 問題概要 個の品物があって、それぞれ 円で売られている。今 枚の魔法の割引券があって、品物を買う際に割引券を好きな枚数使うことができる。 円の品物を買う際に 枚の割引券を使った場合、その品物を 円で…

AtCoder ABC 133 D - Rain Flows into Dams (緑色, 400 点)

時々こういうの見る気がする。とりあえず求めたい値を と置いてみる感じ。 問題概要 を奇数とする。整数 が与えられるので ... を満たすような を求めよ。 制約 は奇数 考えたこと 問題の構造として 「 を決めると、残りが芋づる式にすべて決まってしまう」 …