バケット
これ結構難しくて、嵌まる人は嵌まってしまうと思う!! 問題へのリンク 問題概要 ダンジョンには、ポーション と、敵 がいる。 今、ダンジョンで 個のイベントが起こる。イベント は 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 問題へのリンク 問題概要 英小文字からなる長さ の文字列 が与えられる。この文字列に対する次の 個のクエリに答えよ。 各クエリでは、文字列の区間 が与えられる。この区間を取り出した部分文字列に…
区間の交差を求めるのは頻出の典型処理だし、実務でも使えるテクニックなので、このまま覚えてしまって良いと思う! 問題へのリンク 問題概要 数直線において、 から までの部分をすべて赤色で塗り から までの部分をすべて青色で塗った このとき、赤色と青…