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

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

バケット

AtCoder ABC 333 E - Takahashi Quest (1Q, 緑色, 450 点)

これ結構難しくて、嵌まる人は嵌まってしまうと思う!! 問題へのリンク 問題概要 ダンジョンには、ポーション と、敵 がいる。 今、ダンジョンで 個のイベントが起こる。イベント は 2 つの整数 で表される。 のとき:ポーション が現れる それを拾うかどう…

AtCoder ABC 283 D - Scope (3Q, 茶色, 400 点)

スタックによるシミュレーション問題! 問題へのリンク 問題概要 整合のとれたカッコ列に対して、英小文字がいくつか挿入されてできる文字列が与えられる (たとえば、"(a(ba))c")。 このような文字列に対して、高橋君が気絶するかどうかを判定したい。次のよ…

AtCoder ABC 058 C - 怪文書 (ARC 071 C) (5Q, 茶色, 300 点)

集計処理の応用問題 問題へのリンク 問題概要 一般に、文字列 からいくつかの文字を抜き出して、それを並び替えることによって文字列 を作れるとき、 から を作れるという。 英小文字からなる 個の文字列 が与えられる。 のいずれからも作れる文字列 のうち…

JOI 予選 2010 C - パーティー (AOJ 0545) (4Q, 難易度 4)

グラフの基本問題! 問題へのリンク 問題概要 の人 がいる。 組の友達関係があって、 組目の友達は人 と である。 人 1 の友達と、人 1 の友達の友達に相当する人 (人 1 を除く) が何人いるかを答えよ。 制約 解法 この問題はグラフの練習問題といえる。グラ…

JOI 予選 2010 B - すごろく (AOJ 0544) (6Q, 難易度 3)

すごろくを題材にした問題。すごろくの各マスには「oo マス進む」などの指示がある。これを上手に管理しよう。 問題へのリンク 問題概要 マス からなる双六が与えられる。マス 1 がスタート、マス 以上がゴールである。 回サイコロを振って、 回目には目 だ…

AtCoder ABC 371 B - Taro (6Q, 灰色, 200 点)

バケットを活用する練習問題! 問題へのリンク 問題概要 AtCoder 王国には 家がある。どこかの家で順に 人の赤子が生まれた。 人目の赤子は家 で生まれ、性別は ('M' または 'F')であった。 各赤子が長男であるかどうかを判定せよ。 制約 考えたこと 人目…

JOI 予選 2008 C - カードゲーム (AOJ 0523) (5Q, 難易度 4)

ちょっと実装が大変なので、頑張って実装しよう! 問題へのリンク 問題概要 太郎君と花子さんが大富豪を模したゲームをする。 の書かれたカードを、 枚ずつ、太郎君と花子さんに配る。太郎君に配られたカードに書かれた 個の数値が与えられる。2 人で次のよ…

AtCoder ABC 342 A - Yay! (6Q, 灰色, 150 点)

これも色んな解法がある! 問題へのリンク 問題概要 英小文字からなる 3 文字以上 100 文字以下の文字列 が与えられる。 はある 1 文字を除いて全て同じ文字で構成されています。その異なる文字があるのは何文字目か? 制約 解法 (1):全探索 大抵の問題は、…

JOI 本選 2007 C - 最古の遺跡 (AOJ 0518) (2Q, 難易度 5)

少し数学チックな問題! 問題へのリンク 問題概要 二次元の座標平面上に 個の点がある。点 の座標は である。 これら 個の点から 4 個を選ぶ。選んだ 4 点が正方形の頂点となる場合についての、正方形の面積の最大値を答えよ。 制約 考えたこと であるような…

AtCoder ABC 228 B - Takahashi's Secret (5Q, 灰色, 200 点)

これ結構難しい気がする! グラフの問題の一種。 問題へのリンク 問題概要 人 がいる。高橋君( 人のいずれとも異なる)は、自分の秘密を、この中の人 に知られてしまった。 一般に、人 は新たに秘密を知ったときには、人 にも伝えてしまう。 高橋君の秘密は…

AtCoder ABC 263 A - Full House (6Q, 灰色, 100 点)

この手の問題は最初にソートすると考えやすいことが多い。 問題へのリンク 問題概要 5 枚のカードには数 が書かれている。これがフルハウスであるかを判定せよ。 なお、5 つの数がフルハウスであるとは、同じ数が書かれたカード 3 枚と、別の同じ数が書かれ…

AtCoder ABC 248 A - Lacked Number (6Q, 灰色, 100 点)

よくある「集計処理」の問題! 問題へのリンク 問題概要 10 個の数字 0〜9 のうちから 1 つを除外した 9 個の数字からなる文字列 が与えられる。 10 個の数字 0〜9 のうち、この文字列に含まれない数字を答えよ。 考えたこと この手の問題では、次のような配…

AtCoder ABC 044 B - 美しい文字列 (6Q, 灰色, 200 点)

集計処理系の良問! 問題へのリンク 問題概要 英小文字からなる文字列 について、どの英小文字も登場回数が偶数回であるかどうかを判定せよ。 制約 解法 (1):各文字について登場回数を見ていく まずは愚直な解法を考えよう。文字 = 'a', 'b', ..., 'z' につ…

JOI 一次予選 2020 (第 2 回) C - 最頻値 (6Q, 難易度 3)

集計処理を練習しよう! 問題へのリンク 問題概要 以上 以下の整数からなる、長さ の数列 が与えられる。 長さ の新たな数列 を次のように定義する。 各 に対して、 を、 を満たす の個数 の最大値を求めよ。 制約 解法 問題の意味を解釈するのが難しいかも…

JOI 一次予選 2021 (第 1 回) C - 共通要素 (6Q, 難易度 2)

このような問題を解くためにも、「バケット」を習得しよう! 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。 こっらの数列の双方に登場する数をすべて昇順で出力せよ。 制約 解法 (1):1 から 100 までの数を順に調べる 制約を見よう…

JOI 一次予選 2022 (第 2 回) D - 希少な数 (6Q, 難易度 2)

集計処理の面白い問題! 問題へのリンク 問題概要 長さ の数列 が与えられる。 に出現する整数のうち、出現回数が最小である整数を出力せよ。そのようなものが複数あるときは、そのうちの最小の整数を出力せよ。 制約 解法 このような出現頻度に関する問題で…

JOI 一次予選 2023 (第 2 回) D - 点数 (6Q, 難易度 2)

「検索」をしながらのシミュレーション! 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。 回のゲームをする。最初の得点は 0 点である。 回目のゲームでは、得点が 点増加する。ただし、増加したあとの得点が、もし数列 の中に含まれ…

JOI 一次予選 2023 (第 1 回) D - 二人三脚 (6Q, 難易度 2)

バケットや集計処理の基本問題! 問題へのリンク 問題概要 を 2 個ずつ集めてできる 個の整数から、1 個の整数を除外した。 そうした 個の整数を並べてできる数列 が与えられる。 最初に除外した整数の値を答えよ。 制約 解法 このくらいの難易度の問題から…

AtCoder ABC 305 B - ABCDEFG (6Q, 灰色, 200 点)

一見面倒そうに思える問題 問題へのリンク 問題概要 直線上に 7 点 A, B, C, D, E, F, G が下図のような間隔で並んでいる。 2 点を示すアルファベット が与えられるので、それらの間の距離を求めよ。 考えたこと 一見すごく面倒そうな問題だけど、工夫次第で…

AtCoder ABC 355 C - Bingo 2 (3Q, 灰色, 300 点)

ビンゴを題材とした問題。行・列・斜めを合わせて 個のラインがあるので、各ラインの空きマス数を管理しよう。 問題へのリンク 問題概要 のグリッドがあり、上から 行目、左から 列目のマスには整数 が書かれている。 今から ターンの穴あけをする。 ターン…

AtCoder ABC 360 C - Move It (4Q, 灰色, 250 点)

面白い問題! 問題へのリンク 問題概要 箱 とボール がある。ボール は箱 に入っていて、その重さは である。 これから、ボールの入っている箱を移すことで、どの箱にもちょうど 1 個ずつボールが入っている状態にしたい。ボールを移すコストは、そのボール…

鉄則本 B09 - Papers (2Q, ★4)

二次元いもす法の練習問題 問題へのリンク 問題概要 二次元平面上に 枚の長方形の紙がある。 枚目の紙の左下の座標は であり、右上の座標は である。 紙に覆われている部分の面積を求めよ。 制約 考えたこと 二次元いもす法の練習。 github.com コード #incl…

鉄則本 B08 - Counting Points (2Q, ★4)

二次元累積和の練習問題! 問題へのリンク 問題概要 二次元平面上に 個の点がある。 番目の点の座標は である。 「x 座標が 以上 以下で、y 座標が 以上 以下であるような点は何個あるか?」 というタイプの 回のクエリに答えよ。 制約 解法 x, y 座標の値が…

鉄則本 B06 - Lottery (4Q, ★2)

累積和をやって、その次にやる類題として、そりゃこれを出すよね!! って感じの問題ですね。 問題へのリンク 問題概要 回くじびきを引いた。 回目の結果は であった ( のときアタリ、 のときハズレ)。 次の 回のクエリに答えよ。 【クエリ】 が与えられるの…

AtCoder ABC 085 B - Kagami Mochi (6Q, 灰色, 200 点)

古き良き、ABS にも収録した問題! 問題へのリンク 問題概要 個の整数 が与えられる。 これらの整数の中に、相異なる整数は何種類あるかを求めよ。 制約 解法 最も簡単な方法は、集合型 set 型を用いる方法だと思われる。set は 要素の挿入 (集合に要素 を挿…

JOI 一次予選 2024 (第 1 回) D - 現れている数字 (6Q, 難易度 2)

とても教育的な問題ですね。 問題へのリンク editorials 問題概要 0 以上 9 以下の整数からなる、 個の整数 が与えられる。 数列 の中に一度以上登場する整数を小さい順に出力せよ。 解法 (1):値 0, 1, ..., 9 について個別に全探索 1 つめの解法は まず、…

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

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

AtCoder ABC 329 D - Election Quick Report (4Q, 灰色, 350 点)

「差分更新」の良い練習問題! 問題へのリンク 問題概要 以上 以下の整数からなる長さ の数列 が与えられる。 各 に対して、 の中で最も多く登場する値を答えよ。複数個ある場合はそのうちの最小の値を答えよ。 制約 考えたこと この問題のように、各 に対し…

AtCoder ABC 328 C - Consecutive (4Q, 灰色, 300 点)

すごくよく似た過去問がある。これ → ABC 122 C - GeT AC 問題へのリンク 問題概要 英小文字からなる長さ の文字列 が与えられる。この文字列に対する次の 個のクエリに答えよ。 各クエリでは、文字列の区間 が与えられる。この区間を取り出した部分文字列に…

AtCoder ABC 261 A - Intersection (6Q, 灰色, 100 点)

区間の交差を求めるのは頻出の典型処理だし、実務でも使えるテクニックなので、このまま覚えてしまって良いと思う! 問題へのリンク 問題概要 数直線において、 から までの部分をすべて赤色で塗り から までの部分をすべて青色で塗った このとき、赤色と青…