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

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

ABC-C

AtCoder ABC 184 C - Super Ryuma (茶色, 300 点)

これ難しいと思った! あと、どうやら (1, 1, 1, 6) を 3 回にする嘘解法が AC になったらしい 問題へのリンク 問題概要 以下の動きのできる駒がある。駒をマス からマス へ移動させるのに必要な手数の最小値を求めよ。 制約 考えたこと まず、スタートとゴ…

AtCoder ABC 183 C - Travel (灰色, 300 点)

C++ なら next_permutation() を使うことで 通りの全探索ができる! 問題へのリンク 問題概要 個の都市 がある。都市 と都市 とは距離が だけ離れている。 都市 から出発して各都市をちょうど一度ずつ訪問して都市 に戻ってくる方法のうち、その移動距離の総…

AtCoder ABC 181 C - Collinearity (灰色, 300 点)

幾何っぽい問題。確かに数学ゲーではあるのだけど、平行判定は「計算幾何」の知見として習得してしまっても良さそう。 問題へのリンク 問題概要 二次元平面上に 個の点 () が与えられる。 これらのうちの 3 点であって、同一直線上にあるものが存在するかど…

AtCoder ABC 043 C - いっしょ (ARC 059 C) (茶色, 200 点)

本当にただ全探索するだけ!!! でも意外とこういうのが思いつかれにくいかもしれない。 問題へのリンク 問題概要 (意訳) 長さ の整数列 が与えられる。今、整数 を 1 つ選ぶ。そして整数列をすべて に書き換える。それに要するコストは で与えられる。適切…

AtCoder ABC 042 C - こだわり者いろはちゃん (ARC 058 C) (緑色, 300 点)

記念すべき新体制 AtCoder になってからの初の rated ABC の C 問題!!! 問題のリンク 問題概要 以上の整数のうち、 種類の数値 のいずれも含まない最小のものを求めよ。 制約 考えたこと 真っ先に思い浮かぶ方法は、単純に と順々に試していって「 をいず…

AtCoder ABC 180 C - Cream puff (灰色, 300 点)

完全に約数列挙!!!!! 問題へのリンク 問題概要 正の整数 が与えられる。 の正の約数をすべて出力せよ。 制約 考えたこと 約数列挙問題そのものだった!!!!! まったくそのまんまなものを次の記事の「3. 約数列挙」のところで書いた! qiita.com 計算…

HHKB プログラミングコンテスト 2020 C - Neq Min (灰色, 300 点)

mex!!!それにしても、ならし計算量解析系が来たのびっくり! 問題へのリンク 問題概要 長さ の数列 が与えられる。 各 に対して、0 以上の整数で のいずれとも等しくない値のうち最小値を求めよ。 制約 考えたこと とりあえず次のような配列を用意したく…

AtCoder ABC 177 C - Sum of product of pairs (灰色, 300 点)

茶色 diff にはなると思ったけど、灰色 diff だった...「/2」が必要と感じて詰まる人も多いと思ったのに... 問題へのリンク 問題概要 個の整数 が与えられる。 を満たすすべての に対しての の総和を 1000000007 で割ったあまりを求めよ。 制約 考えたこと …

AtCoder ABC 176 C - Step (灰色, 300 点)

Greedy の一番簡単なパターン 問題へのリンク 問題概要 人が 1 列に並んでおり、前から 番目の人の身長は です。 それぞれの人の足元に、高さが 0 以上の踏み台を設置し、全ての人が次の条件を満たすようにしたいです。 条件:踏み台を込めて身長を比較した…

AtCoder ABC 178 C - Ubiquity (茶色, 300 点)

包除原理!!!C 問題としては難しめですね。 問題へのリンク 問題概要 0 以上 9 以下の整数値からなる長さ の数列 であって、 数列中に 0 が含まれる 数列中に 9 が含まれる という条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。 制約 考え…

ACL Beginner Contest C - Connect Cities (茶色, 300 点)

Union-Find の練習問題という雰囲気ながら、DFS や BFS でも解ける 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。これに最小本数の辺を追加することで全体が連結となるようにしたい。その最小本数を求めよ。 制約 考えたこと 全体…

AtCoder ABC 179 C - A x B + C (灰色, 300 点)

でもできる! 問題へのリンク 問題概要 正の整数 が与えられる。 を満たすような正の整数 の組の個数を求めよ。 制約 考えたこと こういう整数問題は、実のところ本当に整数論的考察を必要とするパターンは少なくて、大抵は探索ベースの解法が有効になる!!…

AtCoder ABC 175 C - Walking Takahashi (茶色, 300 点)

ちょっと場合分けが怖い問題だけど、最後の動きは「ちょうどゴールにならないと、上がれないすごろく」を思い出すと納得できそう! 問題へのリンク 問題概要 現在、座標 にいる。以下のいずれかの操作をちょうど 回行う。 座標 にいるとき、 に移動する 座標…

AtCoder ABC 171 C - One Quadrillion and One Dalmatians (茶色, 300 点)

これは、、、桁和を求めるタイプの問題の応用ではある 問題へのリンク 問題概要 数値を文字列に置き換える。ただしそのルールは 1,2,⋯,26 は、その順に a, b, ..., z 27,28,29,⋯,701,702 は、その順に aa, ab, ac, ..., zy, zz 703,704,705,⋯,18277,18278 は…

AtCoder ABC 169 C - Multiplication 3 (茶色, 300 点)

誤差は怖い!!!!!!! 問題へのリンク 問題概要 整数 と、"x.yz" のフォーマットで与えられる実数 が与えられる。 の小数点以下を切り捨て、結果を整数として出力せよ。 制約 考えたこと 数値誤差が怖いというテーマの問題は、パナソニックコンでもあっ…

AtCoder ABC 168 C - : (Colon) (灰色, 300 点)

余弦定理を使うか、座標を求めるか、、、いずれにしても三角関数の素養を要求する問題。 問題へのリンク 問題概要 時計の時針と分針があって、それぞれ長さは , となっている。 時 分の段階において、時針の先端と分針の先端との距離がどのようになっている…

AtCoder ABC 144 C - Walk on Multiplication Table (灰色, 300 点)

約数列挙!!! 問題へのリンク 問題概要 正の整数 が与えられる。 を満たすような正の整数 の組をすべて考えたときの、 の最小値を求めよ。 制約 考えたこと これはまさに約数列挙の問題!!! 以下の記事の「3. 約数列挙」のところで、本質的に同じ問題の…

AtCoder ABC 044 C - 高橋君とカード (ARC 060 C) (水色, 300 点)

「平均値が A」という制約は上手に扱うテクニックがある。 今回はそれを思いつかなくても解けるけど、思いつくと計算量が落ちる。 問題へのリンク 問題概要 個の整数 からいくつか選ぶ方法のうち、その平均値がちょうど となるものが何通りあるかを求めよ。 …

AtCoder ABC 162 C - Sum of gcd of Tuples (Easy) (灰色, 300 点)

素直に for 文を回して全部足せば OK!!! なお、3 つの整数の最大公約数の求め方に注意。 問題概要 を満たすすべての整数 の組に対しての、 の総和を求めよ。 制約 考えたこと 素直に 通りの組について、GCD を求めて合計しても間に合う。なお、3 つの整数…

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

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

AtCoder ABC 161 C - Replacing Integer (灰色, 300 点)

これは問題文がいかめしいけど、ちょくだいさんのこのツイートが全てかなと思う! C問題、数学の問題といえばそうなんだけど、「無限に長いすごろくがあります。ゴールまでの距離がxです。Kマスずつ進めますが、ゴールを通り過ぎてしまう場合は折り返します…

AtCoder ABC 157 C - Guess The Number (300 点)

全探索した! 整数を string 型にするのに手こずってしまった。 問題へのリンク 問題概要 以下の条件を満たす整数があれば、それを出力し、存在しなければ -1 を出力せよ。 ちょうど 桁である 左から数えて 桁目は である。() 制約 考えたこと 存在しない場…

AtCoder ABC 154 C - Distinct or Not (灰色, 300 点)

こういう「どの値が何個ありますか」的な処理方法は典型パターンが 2 つあると思う std::set や std::map などの連想配列を用いて管理する ソートしてソート順に処理していく 問題へのリンク 問題概要 個の整数 が与えられる。この整数列のどの 2 つの要素も…

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

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

AtCoder ABC 153 C - Fennec vs Monster (灰色, 300 点)

な場合に注意。。。 問題へのリンク 問題概要 個の正の整数 が与えられる。以下の操作を 回まで行うことができる: 整数を 1 つ選んで、0 にする 操作を行った後の、整数の総和として考えられる最小値を求めよ。 制約 考えたこと 素朴に考えれば、 が大きい順…

AtCoder ABC 152 C - Low Elements (灰色, 300 点)

for 文って、本当に 1 回回すだけでいろんな処理ができる!!! 問題へのリンク 問題概要 の順列 が与えられる。 が の最小値となっている という条件を満たす が何個あるかを数えよ。 制約 考えたこと つまり「先頭から 個もってきたときに、 番目が最小値…

AtCoder ABC 151 C - Welcome to AtCoder (灰色, 300 点)

間違わないように、正確に、シミュレーションする問題。 C、大好き!!!!!!「言われたことを正確にこなせるか」というシミュレーション問題なんだけど、題材が面白い上に、配列か連想配列で情報を管理することを要求したり、少し注意力も要求する感じが…

AtCoder ABC 150 C - Count Order (茶色, 300 点)

next_permutation の練習になりそう。DFS でも。 問題へのリンク 問題概要 の順列 が与えられます。 が の順列のうち辞書順で何番目か が の順列のうち辞書順で何番目か を求め、それらの差を答えよ。 制約 考えたこと 制約が小さいので、 通りの順列をすべ…

AtCoder ABC 146 C - Buy an Integer (茶色, 300 点)

二分探索の教育的問題ですね! 問題へのリンク 問題概要 正の整数 が与えられる。正の整数 に対して を の桁数とする。このとき を満たす最大の正の整数 を求めよ。 制約 考えたこと わけわからない式だし、二分探索に決まってるやろ!!!という雰囲気があ…

AtCoder ABC 149 C - Next Prime (灰色, 300 点)

C 問題で整数系のアルゴリズムを確認する問題を出すの良さそうやね。 問題へのリンク 問題概要 2 以上の整数 が与えられる。 以上の最小の素数を求めよ。 制約 素数判定 整数 が素数かどうかを判定するのは、整数論的アルゴリズムで最初くらいに学ぶものです…