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

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

AtCoder300点

ACL Contest 1 A - Reachable Towns (300 点)

えーーー、300 点!? 問題へのリンク 問題概要 二次元平面上に 点が与えられる。これらの点の x 座標、y 座標を抽出すると、それらは の順列となっている。 各 に対して、点 から 自分よりも x 座標と y 座標がともに大きな点 自分よりも x 座標と y 座標が…

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 ARC 060 C - 高橋君とカード (300 点)

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

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

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

AtCoder ARC 061 C - たくさんの数式 (300 点)

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

AtCoder AGC 019 A - Ice Tea Store (300 点)

丁寧に簡潔に 問題へのリンク 問題概要 合計で グラム買いたい。 0.25 グラフで 円のセット 0.5 グラムで 円のセット 1 グラムで 円のセット 2 グラムで 円のセット がある。これらのセットを組み合わせて グラム買うための最小金額を求めよ。 考えたこと 0.…

AtCoder AGC 016 A - Shrinking (300 点)

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

AtCoder ABC 161 C - Replacing Integer (300 点)

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

AtCoder AGC 018 A - Getting Difference (300 点)

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

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

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

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 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 以上の整数 が与えられる。 以上の最小の素数を求めよ。 制約 素数判定 整数 が素数かどうかを判定するのは、整数論的アルゴリズムで最初くらいに学ぶものです…

AtCoder ABC 148 C - Snack (300 点)

結構、そのまんまな問題が来ましたね。 問題へのリンク 問題概要 2 つの正の整数 が与えられる。 でも でも割り切れる正の整数のうち、最小の値を求めよ。 制約 考えたこと すごくそのまんまですね。 と の最小公倍数を求めよ、という問題。実は と の最大公…

AtCoder ARC 100 C - Linear Approximation (300 点)

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

AtCoder ARC 103 C - /\/\/\/ (300 点)

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

AtCoder ABC 147 C - HonestOrUnkind2 (300 点)

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

AtCoder ABC 143 C - Slimes (300 点)

区間ごとに分割していく処理は、ものすごく大事な典型処理なので、是非ともテンプレ化してノータイムで書けたらすごくいい感じ!!!!! 問題へのリンク 問題概要 "aabbbbccbaaa" のような長さ N の文字列 S が与えられる。同じ文字が連続している区間が何…

AtCoder ABC 142 C - Go To School (300 点)

この問題で要求している処理を「前処理」として要求する問題はたくさんある!!! というわけで教育的な問題かもしれない。 問題へのリンク 問題概要 人の生徒がいて、出席番号 の生徒はそれぞれ、全体で 人目に登校していることがわかっている。 これらの情…

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

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