バケット
ちょっとした考察が必要になる問題。 問題へのリンク 問題概要 整数からなる数列 が与えられる。数列の各要素に対して「何もしない」「1 を足す」「1 を引く」をしていく。 操作後に、整数値 を選ぶ。 となる の個数の最大値を求めよ。 制約 考えたこと 問題…
これ結構難しくて、嵌まる人は嵌まってしまうと思う！！ 問題へのリンク 問題概要 ダンジョンには、ポーション と、敵 がいる。 今、ダンジョンで 個のイベントが起こる。イベント は 2 つの整数 で表される。 のとき：ポーション が現れる それを拾うかどう…
スタックによるシミュレーション問題！ 問題へのリンク 問題概要 整合のとれたカッコ列に対して、英小文字がいくつか挿入されてできる文字列が与えられる (たとえば、"(a(ba))c")。 このような文字列に対して、高橋君が気絶するかどうかを判定したい。次のよ…
集計処理の応用問題 問題へのリンク 問題概要 一般に、文字列 からいくつかの文字を抜き出して、それを並び替えることによって文字列 を作れるとき、 から を作れるという。 英小文字からなる 個の文字列 が与えられる。 のいずれからも作れる文字列 のうち…
グラフの基本問題！ 問題へのリンク 問題概要 の人 がいる。 組の友達関係があって、 組目の友達は人 と である。 人 1 の友達と、人 1 の友達の友達に相当する人 (人 1 を除く) が何人いるかを答えよ。 制約 解法 この問題はグラフの練習問題といえる。グラ…
すごろくを題材にした問題。すごろくの各マスには「oo マス進む」などの指示がある。これを上手に管理しよう。 問題へのリンク 問題概要 マス からなる双六が与えられる。マス 1 がスタート、マス 以上がゴールである。 回サイコロを振って、 回目には目 だ…
バケットを活用する練習問題！ 問題へのリンク 問題概要 AtCoder 王国には 家がある。どこかの家で順に 人の赤子が生まれた。 人目の赤子は家 で生まれ、性別は （'M' または 'F'）であった。 各赤子が長男であるかどうかを判定せよ。 制約 考えたこと 人目…
ちょっと実装が大変なので、頑張って実装しよう！ 問題へのリンク 問題概要 太郎君と花子さんが大富豪を模したゲームをする。 の書かれたカードを、 枚ずつ、太郎君と花子さんに配る。太郎君に配られたカードに書かれた 個の数値が与えられる。2 人で次のよ…
これも色んな解法がある！ 問題へのリンク 問題概要 英小文字からなる 3 文字以上 100 文字以下の文字列 が与えられる。 はある 1 文字を除いて全て同じ文字で構成されています。その異なる文字があるのは何文字目か？ 制約 解法 (1)：全探索 大抵の問題は、…
少し数学チックな問題！ 問題へのリンク 問題概要 二次元の座標平面上に 個の点がある。点 の座標は である。 これら 個の点から 4 個を選ぶ。選んだ 4 点が正方形の頂点となる場合についての、正方形の面積の最大値を答えよ。 制約 考えたこと であるような…
これ結構難しい気がする！ グラフの問題の一種。 問題へのリンク 問題概要 人 がいる。高橋君（ 人のいずれとも異なる）は、自分の秘密を、この中の人 に知られてしまった。 一般に、人 は新たに秘密を知ったときには、人 にも伝えてしまう。 高橋君の秘密は…
この手の問題は最初にソートすると考えやすいことが多い。 問題へのリンク 問題概要 5 枚のカードには数 が書かれている。これがフルハウスであるかを判定せよ。 なお、5 つの数がフルハウスであるとは、同じ数が書かれたカード 3 枚と、別の同じ数が書かれ…
よくある「集計処理」の問題！ 問題へのリンク 問題概要 10 個の数字 0〜9 のうちから 1 つを除外した 9 個の数字からなる文字列 が与えられる。 10 個の数字 0〜9 のうち、この文字列に含まれない数字を答えよ。 考えたこと この手の問題では、次のような配…
集計処理系の良問！ 問題へのリンク 問題概要 英小文字からなる文字列 について、どの英小文字も登場回数が偶数回であるかどうかを判定せよ。 制約 解法 (1)：各文字について登場回数を見ていく まずは愚直な解法を考えよう。文字 = 'a', 'b', ..., 'z' につ…
集計処理を練習しよう！ 問題へのリンク 問題概要 以上 以下の整数からなる、長さ の数列 が与えられる。 長さ の新たな数列 を次のように定義する。 各 に対して、 を、 を満たす の個数 の最大値を求めよ。 制約 解法 問題の意味を解釈するのが難しいかも…
このような問題を解くためにも、「バケット」を習得しよう！ 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。 こっらの数列の双方に登場する数をすべて昇順で出力せよ。 制約 解法 (1)：1 から 100 までの数を順に調べる 制約を見よう…
集計処理の面白い問題！ 問題へのリンク 問題概要 長さ の数列 が与えられる。 に出現する整数のうち、出現回数が最小である整数を出力せよ。そのようなものが複数あるときは、そのうちの最小の整数を出力せよ。 制約 解法 このような出現頻度に関する問題で…
「検索」をしながらのシミュレーション！ 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。 回のゲームをする。最初の得点は 0 点である。 回目のゲームでは、得点が 点増加する。ただし、増加したあとの得点が、もし数列 の中に含まれ…
バケットや集計処理の基本問題！ 問題へのリンク 問題概要 を 2 個ずつ集めてできる 個の整数から、1 個の整数を除外した。 そうした 個の整数を並べてできる数列 が与えられる。 最初に除外した整数の値を答えよ。 制約 解法 このくらいの難易度の問題から…
一見面倒そうに思える問題 問題へのリンク 問題概要 直線上に 7 点 A, B, C, D, E, F, G が下図のような間隔で並んでいる。 2 点を示すアルファベット が与えられるので、それらの間の距離を求めよ。 考えたこと 一見すごく面倒そうな問題だけど、工夫次第で…
ビンゴを題材とした問題。行・列・斜めを合わせて 個のラインがあるので、各ラインの空きマス数を管理しよう。 問題へのリンク 問題概要 のグリッドがあり、上から 行目、左から 列目のマスには整数 が書かれている。 今から ターンの穴あけをする。 ターン…
面白い問題！ 問題へのリンク 問題概要 箱 とボール がある。ボール は箱 に入っていて、その重さは である。 これから、ボールの入っている箱を移すことで、どの箱にもちょうど 1 個ずつボールが入っている状態にしたい。ボールを移すコストは、そのボール…
二次元いもす法の練習問題 問題へのリンク 問題概要 二次元平面上に 枚の長方形の紙がある。 枚目の紙の左下の座標は であり、右上の座標は である。 紙に覆われている部分の面積を求めよ。 制約 考えたこと 二次元いもす法の練習。 github.com コード #incl…
二次元累積和の練習問題！ 問題へのリンク 問題概要 二次元平面上に 個の点がある。 番目の点の座標は である。 「x 座標が 以上 以下で、y 座標が 以上 以下であるような点は何個あるか？」 というタイプの 回のクエリに答えよ。 制約 解法 x, y 座標の値が…
累積和をやって、その次にやる類題として、そりゃこれを出すよね！！ って感じの問題ですね。 問題へのリンク 問題概要 回くじびきを引いた。 回目の結果は であった ( のときアタリ、 のときハズレ)。 次の 回のクエリに答えよ。 【クエリ】 が与えられるの…
古き良き、ABS にも収録した問題！ 問題へのリンク 問題概要 個の整数 が与えられる。 これらの整数の中に、相異なる整数は何種類あるかを求めよ。 制約 解法 最も簡単な方法は、集合型 set 型を用いる方法だと思われる。set は 要素の挿入 (集合に要素 を挿…
とても教育的な問題ですね。 問題へのリンク editorials 問題概要 0 以上 9 以下の整数からなる、 個の整数 が与えられる。 数列 の中に一度以上登場する整数を小さい順に出力せよ。 解法 (1)：値 0, 1, ..., 9 について個別に全探索 1 つめの解法は まず、…
「集計処理」の基本問題！ 問題へのリンク 問題概要 (意訳) 個の LED が最初はすべて光っている。 回の処理を行う。 回目の処理では 番目の LED の状態を flip する (光っていたら消して、消えていたら光らせる)。 最終的に何個の LED が光っているかを求め…
「差分更新」の良い練習問題！ 問題へのリンク 問題概要 以上 以下の整数からなる長さ の数列 が与えられる。 各 に対して、 の中で最も多く登場する値を答えよ。複数個ある場合はそのうちの最小の値を答えよ。 制約 考えたこと この問題のように、各 に対し…
すごくよく似た過去問がある。これ → ABC 122 C - GeT AC 問題へのリンク 問題概要 英小文字からなる長さ の文字列 が与えられる。この文字列に対する次の 個のクエリに答えよ。 各クエリでは、文字列の区間 が与えられる。この区間を取り出した部分文字列に…
