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

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

AtCoder ABC 134 A - Dodecagon (灰色, 100 点)

これは本当に言われたとおりにやるだけ! 問題へのリンク 問題概要 整数 の値が与えられるので、 の値を答えてください。 解法 標準入力を用いて r の値を受け取り、3 * r * r の値を出力すれば OK。 #include <bits/stdc++.h> using namespace std; int main() { int r; ci</bits/stdc++.h>…

AtCoder ABC 133 A - T or T (灰色, 100 点)

久しぶりの易しい問題! 問題へのリンク 問題概要 電車を使うと 1 人あたり 円かかります。 タクシーを使うと 人で 円かかります。 人で移動する最小料金はいくらか。 解法 A * N B のうちの小さい方を答えれば OK。関数 min() が使える。 #include <bits/stdc++.h> using n</bits/stdc++.h>…

AtCoder ABC 132 A - Fifty-Fifty (灰色, 100 点)

これはだいぶ難しい問題ですね! 問題へのリンク 問題概要 4 文字の文字列 が与えられる。 がちょうど 2 種類の文字からなり、それらの文字がちょうど 2 個ずつあるかどうかを判定せよ。 解法 色んな解法があると思われる。ここでは、 をアルファベット順に…

AtCoder ABC 131 A - Security (灰色, 100 点)

隣接要素を見る問題。それは何気に結構難しいことだとも思う。 問題へのリンク 問題概要 4 文字の文字列が与えられます。 隣り合う文字が等しい箇所が存在するならば "Bad"、そうでなければ "Good" と答えてください。 解法 次のいずれかを満たせば "Bad" と…

AtCoder ABC 130 A - Rounding (灰色, 100 点)

とても易しい if 文の問題 問題へのリンク 問題概要 整数 が与えられる。 が 未満のときは 0、 以上のときは 10 を出力せよ。 解法 が 未満であることは X < A と表せる。if 文を用いて処理を分岐すれば OK。 #include <bits/stdc++.h> using namespace std; int main() { i</bits/stdc++.h>…

AtCoder ABC 129 A - Airplane (灰色, 100 点)

この頃によくあった 3 個の入力をどうのこうのする系! 問題へのリンク 問題概要 3 つの空港 A, B, C がある。 A-B 間の移動の所要時間は B-C 間の移動の所要時間は A-C 間の移動の所要時間は 今、これらの空港を順に訪れる (たとえば、B → A → C)。最短の所…

AtCoder ABC 128 A - Apple Pie (灰色, 100 点)

ちょっと整理が難しい文章題。 問題へのリンク 問題概要 りんごが 個、りんごの欠片が 個ある。 1 個のりんごを砕くと、りんごの欠片が 個できる 2 個のりんごの欠片を使うと、アップルパイが 1 個できる 今ある材料から、最大で何個のアップルパイが作れる…

AtCoder ABC 127 A - Ferris Wheel (灰色, 100 点)

if 文を上手に使おう! 問題へのリンク 問題概要 ある観覧車の利用料金は年齢に応じて次のとおりである。 13 歳以上は 円かかる。 6 歳以上 12 歳以下は 円の半額がかかる。( は偶数) 5 歳以下は無料 歳の高橋君が観覧車に乗るときの利用料金を求めよ。 解法…

JOIG 春合宿 2023 day2-2 White Light (難易度 8)

セグメント木を用いた DP 高速化! 問題へのリンク editorials 問題概要 'R' と 'G' と 'B' のみからなる長さ の文字列 が与えられる。以下の操作を繰り返し行うことで、"RGB" を繰り返す文字列となるようにしたい。 (操作) 連続する 個以下の文字を消す 目…

AtCodewr ABC 126 A - Changing a Character (灰色, 100 点)

大文字小文字の扱いを考える。 問題へのリンク 問題概要 文字 'A'、'B'、'C' のみからなる長さ の文字列 が与えられる。 この文字列の 文字目を小文字にした文字列を出力せよ。 解法 文字目は S[K-1] と表せる。 文字 S[K-1] が 'A', 'B', 'C' のいずれかで…

AtCoder ABC 125 A - Biscuit Generator (灰色, 100 点)

という表現が何を言っているんだ......と戸惑うかもしれない。これは、要は「ちょうど 秒後」も含むよということを言っている。 問題へのリンク 問題概要 ビスケット起動装置を起動してから、 秒後にそれぞれビスケットを 枚生成する。 起動してから 秒間の…

AtCoder ABC 123 A - Five Antennas (灰色, 100 点)

ちょっと数学的な部分が難しい問題かもしれない。 問題へのリンク 問題概要 5 つのアンテナがこの順に一直線上に並んでいて、それぞれ座標値は () である。 2 つのアンテナは、距離が 以内であるとき、通信できる。 これらのアンテナの組であって、通信でき…

AtCoder ABC 122 A - Double Helix (灰色, 100 点)

文字の問題 問題へのリンク 問題概要 A, C, G, T のいずれかの文字が与えられる。 A と T、C と G がそれぞれ対になる。 与えられた文字に対して、対となる文字を出力せよ。 解法 if 文を使って処理しよう。 #include <bits/stdc++.h> using namespace std; int main() { ch</bits/stdc++.h>…

JOIG 春合宿 2023 day2-1 Smartphone (難易度 8)

JOI ではお馴染みの「 個の区間を扱う問題」。ただし実装がしんどかった。僕は区間を set で管理する方法で実装した。 問題へのリンク editorials 問題概要 制約 考えたこと いかにも貪欲法の香りが漂っている問題ですね。この手の問題では、 個の区間を終端…

JOIG 2024 A - 三連続 (難易度 2)

for 文の練習問題! 問題へのリンク 問題概要 o と x からなる長さ の文字列 が与えられる。 の中に o が 3 つ連続している箇所があれば "Yes" を出力し、そうでなければ "No" を出力せよ。 制約 考えたこと for 文を用いて判定しよう。具体的には、各 i に…

JOIG 2024 E - 名前 (難易度 9)

いかにも JOI にありがちな添字の持ち方をする DP! 問題へのリンク 問題概要 英小文字と英大文字からなる長さ の文字列 と、長さ の文字列 が与えられる。また 0 以上 3 以下の整数 が与えられる。 次の条件を満たす文字列 の長さの最小値を求めよ。 は、英…

JOIG 2024 C - 座席 2 (難易度 6)

色んな解法が考えられそうな問題で、ドツボにハマりやすくて危険な問題だったと思う。落ち着いて整理してシンプルに考える力が問われる。実は、二分探索などは必要ない問題である。 問題へのリンク editorial 問題概要 人の選手 がいる。選手 の出身国は で…

AtCoder ARC 167 E - One Square in a Triangle (銅色, 800 点)

天才構築ゲー。これ完全自力で一発 AC できて嬉しかった!! 問題へのリンク 問題概要 正の整数 が与えられる。次の条件を満たす三角形が存在するかどうかを判定し、存在すれ場合は 1 つ求めよ。 頂点がすべて格子点であり、座標値は 以上 以下である すべて…

AtCoder ARC 171 D - Rolling Hash (黄色, 600 点)

コンテスト後に解いた。こっちの方が解きやすかった。 問題へのリンク 問題概要 制約 考えたこと 最初は の指数を気にするのかな......などと考えていたが、考えていくうちに の値など、ただの飾りであることがわかってきた。 まず、問題の条件を言い換える…

AtCoder ARC 171 C - Swap on Tree (黄色, 600 点)

備忘録として。解説よりもおそらく面倒な DP をした。 問題へのリンク 問題概要 考えたこと 基本的に木 DP のノリで考えることにした。 根を 1 つとったとき、異なる部分木間で交換される頂点はただだか 1 個以内である。そこで次の DP をした。 dp[v][k] ← …

AtCoder ARC 171 B - Chmax (水色, 600 点)

順列をどうのこうのする系、最近多いかもしれない。 問題へのリンク 問題文 考えたこと 操作の内容を解釈するのに少し苦労した。 順列 から誘導される Functional Graph を考えた。このグラフ上で、頂点 から出発して頂点番号が大きくなる限り進んでいったと…

AtCoder ARC 171 A - No Attacking (茶色, 400 点)

慎重に解いた。ノーペナで解けたのは収穫。 問題へのリンク 問題概要 のグリッドに、以下の条件を満たすように 個のルークと 個のポーンを配置することが可能かどうかを判定せよ (ルークとポーンを合わせて駒と呼ぶ)。 どのルークについても、それと同じ行・…

AtCoder ARC 167 B - Product of Divisors (水色, 500 点)

面白かった! 問題へのリンク 問題概要 以上の整数 と非負整数 が与えられる。 の正の約数の総積が で最大何回割れるかを 998244353 で割った余りで求めよ。 制約 考えたこと 一般に、2 以上の整数 の正の約数の総積は、 の約数の個数を とすると となる。た…

AtCoder ARC 167 A - Toasts for Breakfast Party (灰色, 300 点)

面白かった! 問題へのリンク 問題概要 個の正の整数 を 個のグループに分ける。ただし、どのグループの要素数も 1 個以上 2 個以下でなければならない。 最適なグループ分けをしたときの、各グループの要素の総和の二乗の総和の最小値を求めよ。 制約 考え…

AtCoder ARC 167 D - Good Permutation (黄色, 700 点)

モノグサでバチャやって、なんとか通した! 問題へのリンク 問題概要 の順列 が与えられる。この順列に対して「2 個の要素を選んで swap する」という操作を実行して、 「順列から誘導される Functional Graph の連結成分の個数が 1 個」 という状態を実現し…

AtCoder ABC 338 G - evall (橙色, 600 点)

人目見て「頑張れば解けそう」と思えたので、コンテスト中になんとか頑張って通した! 問題へのリンク 問題概要 "1+2*34" のような文字列が与えられる。 この文字列の連続する部分文字列をすべて考えて 数式として成立しているなら、その数式を計算した値 数…

AtCoder ABC 121 A - White Cells (灰色, 100 点)

過去に似た問題があった。その応用問題と言える。 問題へのリンク 問題概要 の白色のマス目がある。 行と 列を選んで、すべて黒色に塗った。 白色のマス目は何個残るか。 解法 白い部分をかき集めると、 の長方形となる。 #include <bits/stdc++.h> using namespace std; in</bits/stdc++.h>…

AtCoder ABC 120 A - Favorite Sound (灰色, 100 点)

if 文を使ってもいいし、関数 max() を使ってもいい 問題へのリンク 問題概要 買いたいものがある。 円で 1 個買うことができる。 円持っている。 ただし、 個以上は要らない。何個買えるか。 解法 最後の「 個以上は要らない」がなければ、B / A が答えとな…

AtCoder ABC 119 A - Still TBD (灰色, 100 点)

これは戸惑った人も多いと思う。実は単純に考えて OK! 問題へのリンク 問題概要 日付データが yyyy/mm/dd 形式の文字列で与えられる (ex:"2019/04/30")。 与えられた日付が、2019 年 4 月 30 日以前であるかどうかを判定せよ。 解法 文字列を string 型で…

AtCoder ABC 118 A - B +/- A (灰色, 100 点)

倍数判定は演算子「%」を用いる! 問題へのリンク 問題概要 2 つの正の整数 が与えられる。 が の約数ならば の値を出力し、そうでないならば の値を出力せよ。 解法 が の約数 (言い換えると、 が で割り切れる) であるかどうかは、 if (B % A == 0) という…