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

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

2024-04-01から1ヶ月間の記事一覧

AtCoder ABC 228 A - On and Off (6Q, 灰色, 100 点)

これは結構大変! 問題へのリンク 問題概要 高橋君は、毎日 時 0 分に部屋の電気を点け、 時 0 分に部屋の電気を消す。電気をつけている間に日付が変わることもある。 時 30 分に部屋の電気がついているかどうかを判定せよ。 解法 これは整理するのが大変だ…

yukicoder No.254 文字列の構成 (2Q)

yukicoder で「構築」練習することにした! 問題へのリンク 問題概要 英小文字からなる文字列 であって、次の条件を満たすものを求めよ。 文字数は 以下である どの隣接する文字も相異なる の連続する部分文字列であって、回文であるものがちょうど 個存在す…

AtCoder ARC 176 E - Max Vector (5D, 赤色, 800 点)

面白かった!! 上手に変数変換することで「2 変数劣モジュラ関数の和の最小化」になるタイプの問題だった。 問題へのリンク 問題概要 考えたこと 一目見て、2 変数劣モジュラ関数の最小化 (燃やす埋める) っぽいと感じた。値が 500 以下というのも怪しい。 …

AtCoder ARC 176 D - Swap Permutation (4D, 橙色, 700 点)

行列累乗した。デバッグに手こずった。 問題へのリンク 問題概要 の順列 が与えられる。以下の操作を 回行う。 を選んで と を swap する 操作列は 通り考えられるが、それぞれについての の総和を 998244353 で割った余りを求めよ。 制約 考えたこと の期待…

AtCoder ARC 176 B - Simple Math 4 (1D, 水色, 400 点)

というコーナーケースにやられた! 問題へのリンク 問題概要 整数 が与えられる。 を で割った余りの一の位の値を求めよ。 (マルチテストケース) 制約 考えたこと まず最初に考えたのは「全体を で割った世界」で考えれば良いということ。 このことを正当化…

AtCoder ABC 350 C - Sort (3Q, 灰色, 300 点)

の計算量で良いなら簡単。 「どこに値 の要素があるのか」を管理するというテクニックをここで習得しよう! 問題へのリンク 問題概要 の並び替えである順列 が与えられる。これをソートしたい。以下の操作を 回まで実施できる。 を選んで、 と を swap する …

AtCoder ABC 350 B - Dentist Aoki (6Q, 灰色, 200 点)

「集計処理」の基本問題! 問題へのリンク 問題概要 (意訳) 個の LED が最初はすべて光っている。 回の処理を行う。 回目の処理では 番目の LED の状態を flip する (光っていたら消して、消えていたら光らせる)。 最終的に何個の LED が光っているかを求め…

AtCoder ARC 176 C - Max Permutation (3D, 黄色, 700 点)

これは面白かった。 問題へのリンク 問題概要 の順列であって、以下の 個の条件を満たすものの個数を 998244353 で割った余りを求めよ。 について、 である 制約 考えたこと グラフの問題として考えることにした。つまり、0-indexed で表現すると 頂点数 、…

AtCoder ARC 176 A - 01 Matrix Again (1D, 水色, 400 点)

大敗してしまったので自戒を込めて。 問題へのリンク 問題概要 整数 が与えられる。 のグリッドであって、以下の条件を満たすものを構築せよ。 各マスの値は 0 または 1 である 個のマス の値はいずれも 1 である 行和はすべて である 列和はすべて である …

AtCoder ABC 350 A - Past ABCs (7Q, 灰色, 100 点)

構文解析の初歩ですね。C++ なら、scanf() 関数を使うと楽ですね。 問題へのリンク 問題概要 "ABC197" のような長さ 6 の文字列 が与えられる。 何回目の ABC であるかを判定し、それが 316 回を除く、1〜349 回のいずれかであるかどうかを判定せよ。 解法 C…

AtCoder ABC 350 G - Mediator (3D, 黄色, 600 点)

本当に色んな解法がある問題っぽい!! 問題へのリンク 問題概要 頂点 の 頂点からなる無向グラフがあり、最初は辺がない。以下の 2 種類のオンラインクエリに答えよ。 クエリタイプ 1:頂点 間に辺を結ぶ クエリタイプ 2:頂点 の双方に隣接する頂点がある…

EDPC (Educational DP Contest) V - Subtree (2D)

全方位木 DP の練習問題!! が素数とは限らないので「左右から累積和」が必要なタイプの全方位木 DP。 問題へのリンク 問題概要 正の整数 と、頂点数 の木 が与えられる。この木の各頂点を「黒色」または「白色」に塗る。 各頂点 について、以下の条件をみ…

AtCoder ABC 227 A - Last Card (7Q, 灰色, 100 点)

これは難しいですね。何も考えずに for 文で求めるのが比較的楽でしょうか。 問題へのリンク 問題概要 と番号のついた 人に、 枚のカードを配っていく。 人 から始めて、人 の順に 1 枚ずつカードを配るとき、最後のカードは誰に配られるでしょうか? 解法 1…

AtCoder ABC 226 A - Round decimals (7Q, 灰色, 100 点)

色んな方法がありそう! 問題へのリンク 問題概要 0 以上 100 未満の小数第三位までで表すことのできる実数 が、小数第三位まで入力されます。 を小数第一位で四捨五入した結果として得られる整数を出力してください。 考えたこと C++ で解く場合、入力は ci…

AtCoder ABC 225 A - Distinct Strings (7Q, 灰色, 100 点)

これ結構難しいと思う! 数学 IA の「場合の数」をやると、よく出て来るやつですね。 問題へのリンク 問題概要 英小文字のみからなる長さ 3 の文字列 が与えられます。 の各文字を並び替えて得られる文字列は、何種類ありますか? 解法 「3 個のものを並び替…

AtCoder ABC 224 A - Tires (8Q, 灰色, 100 点)

文字列を上手に使う練習 問題へのリンク 問題概要 末尾が "er" か "ist" であるような文字列 (2 文字以上) が与えられます。 どちらであるかを判定してください。 解法 末尾が "er" であるかどうかを判定することにしよう。文字列 S の長さを N とするとき、…

AtCoder ABC 223 A - Exact Price (8Q, 灰色, 100 点)

えぐいコーナーケースに注意! でもサンプルにあるね。 問題へのリンク 問題概要 財布に 円玉が 1 枚以上入っています。 財布に入っている合計金額がちょうど 円であるようなことが、あり得るかどうかを判定してください。 制約 考えたこと 基本的には「 が …

AtCoder ABC 222 A - Four Digits (8Q, 灰色, 100 点)

色んな方法がある。C 言語では、 printf() 関数を用いるのが楽だと思われる。 問題へのリンク 問題概要 0 以上 9999 以下の整数 が与えられます。 の先頭に必要なだけ 0 をつけ、4 桁の文字列にしたものを出力してください。 解法 C 言語であれば、整数値 の…

AtCoder ABC 221 A - Seismic magnitude scales (灰色, 100 点)

for 文を用いるのが楽だと思う。 問題へのリンク 問題概要 マグニチュード の地震は、マグニチュード の地震の何倍の強さか? (1 上がると 32 倍となる) 制約 解法 を 回かけた値を求めればよい (つまり )。 これを求めるためには、関数 pow() を用いるか、f…

AtCoder ABC 220 A - Find Multiple (灰色, 100 点)

for 文を用いるのが楽だと思う。 問題へのリンク 問題概要 以上 以下の の倍数が存在するならば 1 つ求め、存在しない場合は -1 を出力せよ。 制約 考えたこと for 文を用いるのが最も楽だと思う。 について、 で割り切れるかどうかを判定していき、 割り切…

AtCoder ABC 219 A - AtCoder Quiz 2 (灰色, 100 点)

if 文を使って落ち着いて整理しよう。 問題へのリンク 問題概要 100 点満点の試験を受ける。得点に応じて以下の評価を受ける。 0 点以上 40 点未満のとき、初級 40 点以上 70 点未満のとき、中級 70 点以上 90 点未満のとき、上級 90 点以上のとき、エキスパ…

AtCoder ABC 218 A - Weather Forecast (灰色, 100 点)

まさに「文字列の index アクセス」を練習できる問題! 問題へのリンク 問題概要 7 文字の文字列 が与えられる。この文字列は 'o' と 'x' のみからなる。 この文字列の 番目の文字が 'o' であるならば "Yes"、そうでなければ "No" と答えよ。 解法 多くのプ…