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

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

AtCoder400点

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

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

AtCoder ABC 049 D - 連結 (ARC 065 D) (青色, 400 点)

Union-Find を上手に使うと解けるいい練習問題ですね。 問題へのリンク 問題概要 個の都市があって、都市間を 本の「道路」と 本の「鉄道」が結んでいる。各道路と各鉄道は、結んでいる都市間を双方向に移動することができる。 各都市 に対して、以下の条件…

AtCoder ABC 075 D - Axis-Parallel Rectangle (水色, 400 点)

古き良き全探索問題!! 問題へのリンク 問題概要 二次元平面上に 個の点があります。 番目の点の座標を とします。 この二次元平面上で各辺が X 軸・Y 軸に平行であるような長方形であって、 個の点のうち 個以上の点を内部および周に含むようなものを考え…

AtCoder ABC 091 C - 2D Plane 2N Point (ARC 092 C) (水色, 400 点)

とても教育的かつ典型的な貪欲法の問題ですね。 問題へのリンク 問題概要 二次元平面上に、赤い点と青い点が 個ずつあります。 個目の赤い点の座標は であり、 個目の青い点の座標は です。 赤い点と青い点は、 座標と 座標がともに赤い点よりも青い点の方が…

AtCoder ABC 206 D - KAIBUNsyo (緑色, 400 点)

今や Union-Find やるだけだと茶色 diff (下手したら灰色 diff) だけど、ちゃんと考察要素を入れるとやっぱり緑色 diff になるのね。 問題へのリンク 問題概要 正の整数からなる整数列 が与えられる。以下の操作を好きなだけ行うことによって、 個の値がすべ…

AtCoder AGC 053 A - >< again (水色, 400 点)

自明な上界を達成できるパターンだった! 問題へのリンク 問題概要 長さ の非負整数列 が与えられる。この数列はどの隣接する二項も値が異なる。 この数列をなるべく多くの 項の非負整数列へと分解せよ。分解とは 分解された各非負整数列の各項を足すと、も…

AtCoder ARC 115 B - Plus Matrix (茶色, 400 点)

「決めてから、整合性を確認する」というタイプの問題の典型例ですね! 問題へのリンク 問題概要 の非負整数を成分とする行列 が与えられる。 すべての について を満たすような非負整数列 と の組が存在するか判定し、存在するなら一つ出力せよ。 制約 考え…

AtCoder ABC 193 D - Poker (緑色, 400 点)

発想や考え方はそんなに難しくないんだけど、すごく頭がこんがらがってしまう問題だね... 問題へのリンク 問題概要 が表に書かれたカードが 枚ずつ、計 枚のカードがあります。 これらのカードをランダムにシャッフルして、高橋くんと青木くんにそれぞれ、4 …

AtCoder ABC 187 D - Choose Me (茶色, 400 点)

ペア の大きい順にソートする嘘貪欲にハマってしまった方が多そうだった 問題へのリンク 問題概要 青木君と高橋君が選挙を行う。 個の町があり、 番目の町では 青木派が 人いる 高橋派が 人いる ということがわかっている。高橋君はいくつかの町で選挙活動を…

AtCoder ABC 170 D - Not Divisible (緑色, 400 点)

数列をヒストグラム化することで解決できるタイプの問題!特に今回みたいに、数値の値も 以下と小さい場合はすごくそれっぽい! 問題へのリンク 問題概要 長さが の正の整数からなる数列 が与えられる。以下の条件を満たす の個数を求めよ。 なる任意の に対…

AtCoder ABC 137 D - Summer Vacation (水色, 400 点)

これは難しい!!! 誘惑されそうな嘘解法がたくさんある!! 問題へのリンク 問題概要 件の日雇いアルバイトがあります。 件目の日雇いアルバイトを請けて働くと、その 日後に報酬 が得られます。 あなたは、これらの中から 1 日に 1 件まで選んで請け、働…

AtCoder ABC 136 D - Gathering Children (茶色, 400 点)

「大体こういう感じ」というところまではすぐに見えるけど、細かいところを詰めるのが大変な問題かもしれない。 問題へのリンク 問題概要 マスがあって、各マスには "L" または "R" が書かれている (左端は "R" で右端は "L" であることが保証される)。また…

AtCoder ABC 134 D - Preparing Boxes (緑色, 400 点)

一見すると かかるように思えるかもしれない。でも実は になる。 問題へのリンク 問題概要 個の整数 が与えられる (それぞれ 0 または 1)。このとき、 個の 0-1 変数 の値を、以下の条件を満たすように定めよ。 各 に対して、 を 2 で割ったあまりが に一致…

AtCoder ABC 186 D - Sum of difference (茶色, 400 点)

いろんな方法が考えられそう! 問題へのリンク 問題概要 個の整数 が与えられる。 を満たすすべての の組に対する の総和を求めよ。 制約 考えたこと 絶対値のままだと厄介。ちょっと工夫する。まず、数列 の並びを入れ替えたとしても答えが変わらないことに…

AtCoder ABC 185 D - Stamp (茶色, 400 点)

番兵を入れるとかすれば、怖いケースをあらかじめ除去できそう 問題へのリンク 問題概要 左右方向一列に 個のマスが並んでいます。 この 個のマスのうち、マス の 個のマスは青色で、それ以外のマスは白色です。 あなたは一回だけ、正整数 を一つ選んで幅 の…

AtCoder ARC 110 B - Many 110 (茶色, 400 点)

本番 14 分かけたのは反省。 問題へのリンク 問題概要 "110" という文字列を 10000000000 個連結してできる文字列を とする。 長さ の文字列 が与えられる。 の中に が連続する部分文字列としていくつ含まれるかを求めよ。 制約 考えたこと こういう、端の処…

AtCoder ABC 182 D - Wandering (茶色, 400 点)

累積和の累積 max 問題へのリンク 問題概要 数列 が与えられます。 この数列は負の要素を含むかもしれません。 数直線上の座標 0 に置かれているロボットが、以下の動作を順に行います。 正の向きに 進む。 正の向きに 進み、正の向きに 進む。 正の向きに …

AtCoder ARC 109 B - log (茶色, 400 点)

二分探索でやればよさそう。本当は でもできるのかも。 問題へのリンク 問題概要 正の整数 が与えられる。 整数 のうち、いくつか選んだものが以下の条件を満たすようにしたい。そのような選び方のうち、選ぶ個数の最小値を求めよ。 選んだ整数はいくつかの…

AtCoder ARC 108 B - Abbreviate Fox (茶色, 400 点)

カッコ列系の問題! 問題へのリンク 問題概要 長さ の文字列 が与えられる。文字列に対して、以下の処理を繰り返し行う。操作の結果得られる文字列の長さの最小値を求めよ。 文字列中の "fox" を削除する 制約 考えたこと カッコ列でよく似た問題はすごく有…

AtCoder ABC 184 D - increment of coins (水色, 400 点)

最初、「期待値の線形性」を使うのかなと思って迷走した... D は DP の D だった。 問題へのリンク 問題概要 袋の中に金貨が 枚、銀貨が 枚、銅貨が 枚入っている。袋の中にあるいずれかの種類の硬貨が 100 枚になるまで以下の操作を繰り返す。 操作:袋の中…

AtCoder ABC 183 D - Water Heater (茶色, 400 点)

条件反射でいもす法!!! 問題へのリンク 問題概要 人がいる。 人目の人は、時刻 から時刻 の間で、毎分 リットルずつお湯を使う。 どの時刻においても、使用されているお湯の合計量が、毎分 リットル以内におさまるかどうかを判定せよ。 制約 考えたこと …

AtCoder AGC 049 A - Erasing Vertices (青色, 400 点)

面白い。ただ初手で強連結成分分解 (SCC) したくなるのが罠すぎる。SCC 自体は考察過程としては悪くなさそうだけど、SCC して DP...と考えると大変。 問題へのリンク 問題概要 頂点の単純有向グラフが与えられる。以下の操作をグラフが空になるまで繰り返す…

AtCoder AGC 036 A - Triangle (緑色, 400 点)

ちょっと面白い感じの構築問題! 問題へのリンク 問題概要 正の整数 が与えられる。 以下の条件を満たす 3 つの格子点 の組を一つ求めよ。 座標値はすべて 以上 以下の整数値 3 つの格子点からなる三角形の面積を 2 倍すると に一致 制約 考えたこと 仮に 1 …

AtCoder AGC 034 A - Kenken Race (茶色, 400 点)

場合分けやコーナーケース回避がエグい問題! 問題へのリンク 問題概要 .#..#.. のような長さ のマス目が与えられる。"#" は岩を表す。初期状態では、すぬけ君は マス目に、ふぬけ君は マス目にいる ()。 今、「2 人のうちのいずれかを選んで 1 マス右か 2 …

AtCoder ABC 181 D - Hachi (茶色, 400 点)

整数 を 8 で割ったあまりは、 の下三桁を 8 で割ったあまりに等しい! 問題へのリンク 問題概要 整数 が長さ の文字列として与えられる ( は '1'〜'9' のみで構成される)。 の各文字を並び替えてできる整数の中に、8 の倍数となるものが存在するかどうかを…

AtCoder ARC 107 B - Quadruple (茶色, 400 点)

半分全列挙した! 問題へのリンク 問題概要 正の整数 と整数 が与えられる。以下の条件を満たす正の整数 の組の個数を求めよ。 制約 考えたこと 愚直な方法としては、次のように 4 重ループをする解法が考えられるかもしれない。しかしこれでは の計算量を要…

AISing Programming Contest 2020 D - Anything Goes to Zero (水色, 400 点)

結構難しい!! 問題へのリンク 問題概要 正の整数 に対して、 := を二進法表現したときの各桁の総和を として を で割ったあまり := を で置き換える操作を繰り返したときに、何回で 0 になるか として定める。たとえば のとき、, より、 となる。 今、二進…

AtCoder ABC 043 D - アンバランス (ARC 059 D) (水色, 400 点)

面白かった 問題へのリンク 問題概要 文字列 がアンバランスであるとは、 の中の文字のうち、過半数が同じ文字 であることを指すものとする。長さ の文字列 が与えられたとき、 の連続する部分文字列であって、アンバランスなものがあるかどうかを判定せよ。…

AtCoder ARC 106 B - Values (茶色, 400 点)

問題へのリンク 問題概要 頂点数 、辺数 の無向グラフが与えられる。各頂点 には値 が書かれている。以下の操作を好きな順序で好きな回数だけ行うことで、各頂点 の数値が であるような状態にすることが可能かどうかを判定せよ。 辺 を選んで、以下のいずれ…

AtCoder ABC 180 D - Takahashi Unevolved (茶色, 400 点)

2 種類の操作がある系の問題!こういうのは操作の手順を単純化して考えられる場合が多い 問題へのリンク 問題概要 正の整数 が与えられる。これに対して以下の 2 種類の操作のいずれかを繰り返し行なっていく を 倍する に を足す が 以上となってはならない…