連想配列(setやmap)
色々な解法があるが、set を使うのが楽。set のよい練習問題とも言える。 問題へのリンク 問題概要 最初何も書いていない黒板がある。次の 回の操作を行った。 回目の操作では、整数 を考える 黒板に が書かれていない場合は、新たに を黒板に書く 黒板に が…
B 問題としては難しい！ 今風にいうと、Functional Graph のシミュレーション！ 問題へのリンク 問題概要 個のボタンがある。ボタン が光っているときにそのボタンを押すと、ボタン の明かりが消え、その後ボタン が光る（ であることもある）。 最初、ボタ…
難しくはないけど、重たい！ 順序付き set の練習問題。 問題へのリンク 問題概要 制約 考えたこと 順序付き set を上手く使う問題。この問題では、次の操作を実現したくなる。ここで、集合 は、初期状態では問題文で与えられる 個の家の座標を格納すること…
二次元グリッド上のシミュレーション問題！ 問題へのリンク 問題概要 のグリッドが与えられる。各マスは '.'：通路マス '#'：壁マス '@'：アイテムマス のいずれかである。最初、マス にいる。 今、グリッド上で文字列 に示す移動をする（U, D, L, R のいず…
集合型を学ぼう！ 問題へのリンク 問題概要 個の文字列 がこの順に与えられる。 初出の文字列に対して、その添字を出力せよ。 制約 解説 0-indexed で考えます。つまり、文字列を とします（出力するときには 1 を足します）。 まずは計算量のことを考えずに…
集計処理した上で、再度大きい順にソートする問題 問題へのリンク 問題概要 個の文字列 が与えられる。 この列に一回以上出現する単語を、その出現回数の多い順に並べたとき 番目の単語を出力せよ（一意に決まらない場合は "ambiguous" と出力せよ）。 制約 …
上手に式変形しよう！ 問題へのリンク 問題概要 正の整数からなるサイズ の数列 が与えられる。次の条件を満たす組 の個数を求めよ。 制約 考えたこと 条件が不思議だ。普通は よりも の方が大きいことが多いのに、 となる条件を問うとは。 さて、この手の数…
条件を上手に言い換えよう！ 問題へのリンク 問題概要 個の整数 が与えられる。 が平方数 という条件を満たすような組 の個数を求めよ。 制約 考えたこと これは「条件の言い換え」を頑張る問題。「 が平方数」という条件を扱いやすいように言い換えよう。こ…
「区間の値の和」を見たら、累積和をとろう！！ 問題へのリンク 問題概要 数列 と整数 が与えられる。 数列の連続する区間であって、その総和が に一致するものが何個あるかを求めよ。 制約 考えたこと 0-indexed で考える。 数列 の累積和を としよう。この…
for 文の練習問題 問題へのリンク 問題概要 長さの等しい 2 つの文字列 が与えられる。 に含まれる各文字 '@' について、'a', 't', 'c', 'o', 'd', 'e', 'r' のいずれかに置き変えることで、 が一致するようにできるかを判定せよ。 制約 [tex 1 \le |S| = |T…
すごく面白い問題！ 問題へのリンク 問題概要 個の文字列 が与えられる。 これらの文字列から異なる 2 つの文字列を選ぶ方法であって、それらの文字列が互いにアナグラムとなっているものの個数を求めよ。 制約 考えたこと まずは、問題の条件をわかりやすく…
連想配列の良い練習問題！ 問題へのリンク 問題概要 正の整数からなる数列が良い数列であるとは、数列に含まれる任意の整数値 について、数列中に がちょうど 個含まれていることをいう。 与えられた数列 に対して、いくつかの要素を削除することで、よい数…
素朴な map の練習問題 問題へのリンク 問題概要 りんごさんは 個の問題案を持っており、 個目の問題案の難易度は である。 ここから、配点が であるような 問からなる問題セットを作ることは可能か？ 制約 考えたこと 連想配列 (C++ ならば map) の練習問題…
遅延評価セグメント木と、その max_right, min_left で殴った！ 問題へのリンク 問題概要 マス が一列に並んでいて、それぞれ色 で塗られている。次の 回のクエリに答えよ。 クエリタイプ 1：マス と色 が指定されるので、マス から始めて「いまいるマスと同…
座標ごとに情報を整理するのは頻出！ 問題へのリンク 問題概要 x-y 座標平面上に 人がいる。それぞれ座標 の位置にいて、左右いずれかを向いている（各人が左右どちらを向いているかは文字列 で与えられる）。 各人が、その位置から、向いている方向に向かっ…
意外と整理するのが大変だと思う。map を使って整理しようとするのも自然だが、もうちょっと簡単に解くことを考えよう。 問題へのリンク 問題概要 文字列を投稿すると得点が与えられるコンテストに、 個の文字列 がこの順に投稿され、それぞれ 点が与えられ…
SNS を題材にした set の練習問題 問題へのリンク 問題概要 人から SNS について、次の 個のクエリに答えよ（初期状態では全員が誰もフォローしていない）。 クエリタイプ 1：人 が人 をフォローする（フォロー済みの場合は何もしない） クエリタイプ 2：人 …
ちょっとした考察が必要になる問題。 問題へのリンク 問題概要 整数からなる数列 が与えられる。数列の各要素に対して「何もしない」「1 を足す」「1 を引く」をしていく。 操作後に、整数値 を選ぶ。 となる の個数の最大値を求めよ。 制約 考えたこと 問題…
区間を伸ばしたり縮めたりしながら、それに伴う「挿入」や「削除」に対処するデータ構造を考える系の問題！ 問題へのリンク 問題概要 数列 について、連続する 個の要素の種類数の最大値を答えよ。 制約 考えたこと 数列の幅 の区間をすべて調べるには、次の…
この問題は、for 文でも解けるし、map でも解ける。ここでは map で解いてみよう。 問題へのリンク 問題概要 個の文字列 と、 個の文字列 が与えられる。 これに対して文字列を考えて、その文字列に対するスコアは ( に含まれている分の個数) - ( に含まれて…
if 文を並べてもいいし、map を使ってもよさそう。 問題へのリンク 問題概要 文字列 が与えられる。 の各文字に対して、 O → 0 D → 0 I → 1 Z → 2 S → 5 B → 8 それ以外 → そのまま という変換をして得られる文字列を答えよ。 コード (1)：if 文 if 文を使っ…
連想配列の練習問題！ 問題へのリンク 問題概要 長さ の整数列 が与えられる。この数列に対して、次の 個のクエリに答えよ。 【クエリ】 整数 が与えられるので、整数列を順に見ていったときの「 個目の値 の要素」の index を答えよ（存在しない場合は -1）…
制約が小さいので for 文だけでも解けるし、map などを使うともっと楽になる。 問題へのリンク 問題概要 個の文字列 が与えられる。 登場回数の最も多い文字列を答えよ（タイがある場合はどれを答えても良い）。 制約 考えたこと 次の連想配列を用いて解いた…
連想配列が有効活用できる問題 問題へのリンク 問題概要 個の文字列 がある。 登場回数の最も多い文字列を、辞書順に出力せよ。 制約 考えたこと 各文字列がそれぞれ何個あるのかを求めたい。そこで、次のような配列を作りたい。 nums[str]：文字列 str の登…
set の練習！ 問題へのリンク 問題概要 二次元平面上に高橋君がいる。高橋君は原点から移動を 回行った。 回の移動は長さ の文字列で表される。各文字は L（左へ移動）、R（右へ移動）、U（上へ移動）、D（下へ移動）のいずれかである。 高橋君が同じ座標に…
連想配列（辞書）の練習問題！ 問題へのリンク 問題概要 文字列 が与えられる。 各 に対して、 となる が存在しない場合は をそのまま出力せよ となる が存在する場合は、その個数を としたとき、 に "(k)" を付して出力せよ 制約 考えたこと 問題文で言われ…
連想配列で集計するといい感じに解ける！ 問題へのリンク 問題概要 枚の靴下があって、靴下 の色は という整数値で表される。 色の等しい靴下をペアにするとき、最大で何ペア作れるか？ 制約 考えたこと 次のように考えたい。 色ごとに靴下が何個あるかを整…
map の練習問題！ 問題へのリンク 問題概要 長さ の数列 が与えられる。 各 について、 かつ を満たす最大の整数 を求めよ（存在しない場合は -1）。 制約 考えたこと 基本的には次の情報を管理できる配列が欲しい。 last[v]：その時点で、 を満たす最大の …
面白い。各値に対する答えを予め整理して求めておく手法は頻出！ 問題へのリンク 問題概要 個の品物がある。品物 は、重さが であり、価値が である。 いくつかの品物を、総和が 以下となるように選ぶとき、選んだ品物の価値の総和の最大値を求めよ。 制約 …
グラフの基本問題！ 問題へのリンク 問題概要 の人 がいる。 組の友達関係があって、 組目の友達は人 と である。 人 1 の友達と、人 1 の友達の友達に相当する人 (人 1 を除く) が何人いるかを答えよ。 制約 解法 この問題はグラフの練習問題といえる。グラ…
