2024-11-01から1ヶ月間の記事一覧
区間を伸ばしたり縮めたりしながら、それに伴う「挿入」や「削除」に対処するデータ構造を考える系の問題！ 問題へのリンク 問題概要 数列 について、連続する 個の要素の種類数の最大値を答えよ。 制約 考えたこと 数列の幅 の区間をすべて調べるには、次の…
この問題は、for 文でも解けるし、map でも解ける。ここでは map で解いてみよう。 問題へのリンク 問題概要 個の文字列 と、 個の文字列 が与えられる。 これに対して文字列を考えて、その文字列に対するスコアは ( に含まれている分の個数) - ( に含まれて…
if 文を並べてもいいし、map を使ってもよさそう。 問題へのリンク 問題概要 文字列 が与えられる。 の各文字に対して、 O → 0 D → 0 I → 1 Z → 2 S → 5 B → 8 それ以外 → そのまま という変換をして得られる文字列を答えよ。 コード (1)：if 文 if 文を使っ…
連想配列の練習問題！ 問題へのリンク 問題概要 長さ の整数列 が与えられる。この数列に対して、次の 個のクエリに答えよ。 【クエリ】 整数 が与えられるので、整数列を順に見ていったときの「 個目の値 の要素」の index を答えよ（存在しない場合は -1）…
辞書順最小と言われたら......！！ 問題へのリンク 問題概要 文字 'd', 'p' からなる長さ の文字列 が与えられる。 この文字列のある区間をとって、その区間を 180 度回転させる（reverse した上で、'd' と 'p' を入れ替える）。 こうしてできる文字列のうち…
制約が小さいので for 文だけでも解けるし、map などを使うともっと楽になる。 問題へのリンク 問題概要 個の文字列 が与えられる。 登場回数の最も多い文字列を答えよ（タイがある場合はどれを答えても良い）。 制約 考えたこと 次の連想配列を用いて解いた…
連想配列が有効活用できる問題 問題へのリンク 問題概要 個の文字列 がある。 登場回数の最も多い文字列を、辞書順に出力せよ。 制約 考えたこと 各文字列がそれぞれ何個あるのかを求めたい。そこで、次のような配列を作りたい。 nums[str]：文字列 str の登…
set の練習！ 問題へのリンク 問題概要 二次元平面上に高橋君がいる。高橋君は原点から移動を 回行った。 回の移動は長さ の文字列で表される。各文字は L（左へ移動）、R（右へ移動）、U（上へ移動）、D（下へ移動）のいずれかである。 高橋君が同じ座標に…
連想配列（辞書）の練習問題！ 問題へのリンク 問題概要 文字列 が与えられる。 各 に対して、 となる が存在しない場合は をそのまま出力せよ となる が存在する場合は、その個数を としたとき、 に "(k)" を付して出力せよ 制約 考えたこと 問題文で言われ…
ちょっと整理が大変な複雑な問題。 問題へのリンク 問題概要 ルーレットによって 0 から 36 までのいずれかの整数が出される。 人 はどの整数が出されるかを賭けた。人 は 個の整数 にかけた。 実際に出た整数は であった。 に賭けていた人のうち、賭けた整…
連想配列で集計するといい感じに解ける！ 問題へのリンク 問題概要 枚の靴下があって、靴下 の色は という整数値で表される。 色の等しい靴下をペアにするとき、最大で何ペア作れるか？ 制約 考えたこと 次のように考えたい。 色ごとに靴下が何個あるかを整…
すごく数学的な問題 問題へのリンク 問題概要 縦、横、高さの総和が であるような直方体の体積の最大値を求めよ。 制約 考えたこと 縦、横、高さの長さを としよう。このとき、次の問題になる。 のとき、 の最大値を求めよ この手の問題では、 のとき最大に…
面白かった！ 交差数に関する問題に帰着される。 問題へのリンク 問題概要 座標平面上に、4 頂点の座標が であるような長方形があり、その長方形の周上または内部に、 とラベルのついた 個の点がある（どの 2 点も相異なる）。 について、同じラベル の 2 点…
いかにも stack が登場しそうな問題！ 問題へのリンク 問題概要 下の図のように、高さが の仕切りが等間隔に並んでいて、その間と両端の カ所のスペースを表す番号を とする。これらは幅が等しい。 今、スペース 0 に水を入れていく。1 個分のスペースについ…
evima さんの別解で解いた。 問題へのリンク 問題概要 頂点数 の単純な木が与えられる。この木に辺を 1 本追加して得られるグラフのうち、次の条件を満たすものの個数を求めよ。 単純グラフである サイクルをちょうど 1 つ含み、そのサイクルに含まれる頂点…
これ面白かった！ 問題へのリンク 問題概要 数列 が与えられる。この数列の連続する部分数列について「その総和を で割った余り」を考える。 連続する部分数列をすべて考えたときの、「その総和を で割った余り」の総和を求めよ。 制約 考えたこと この問題…
こういう探索系はみんな苦手とするイメージだったけど、結構 Difficulty 低いのね。 問題へのリンク 問題概要 グリッドで、各マスは「空き」または「壁」である。 ある空きマスを出発し、上下左右に隣接するマスへの移動を 回行う方法であって、障害物のある…
map の練習問題！ 問題へのリンク 問題概要 長さ の数列 が与えられる。 各 について、 かつ を満たす最大の整数 を求めよ（存在しない場合は -1）。 制約 考えたこと 基本的には次の情報を管理できる配列が欲しい。 last[v]：その時点で、 を満たす最大の …
演算子「%」を上手に使う系の数学問題。 問題へのリンク 問題概要 種類のゴミがある。ゴミ は、 で割って 余る日に捨てることができる。 次の 個のクエリに答えよ。 【クエリ】 ゴミ を、 日目以降に捨てたい。最短で捨てることのできる日を答えよ。 制約 考…
これ意外と難しいと思う！ 問題へのリンク 問題概要 4 個の整数 (1, 2, 3, 4 のいずれか) が与えられる。これら整数に対して、 「2 個同じ整数があったら 2 個まとめて消す」 という操作を最大で何回できるか？ 考えたこと 整理が大変だけど、色んな解法があ…
弦が交わるかどうかを判定するという、スタックの典型問題！ 問題へのリンク 問題概要 次の図のように、円周上に 個の点 があり、 本の弦がある（図は のとき）。 弦に交差があるかどうかを判定せよ。 制約 考えたこと この問題は stack で解けることで有名…
スタックの応用問題！ ヒストグラムの最大長方形を求めるアルゴリズムと似たようなスタックの使い方をする！ 問題へのリンク 問題概要 長さ の数列 が与えられる。これらの値は互いに相異なる。 各 に対して、次の条件を満たす整数 の個数を求めよ。 なる任…
問題を言い換えるのが少し難しい 問題へのリンク 問題概要 頂点数 の木が与えられる（頂点番号 ）。 この木に対して「葉を 1 つ選んで削除する」という操作を繰り返す。頂点 1 を削除するまでの操作回数の最小値を求めよ。 制約 考えたこと 0-indexed で考え…
サンプルを見れば上限が分かる系の問題！ 問題へのリンク 問題概要 各桁の値が 1 である数をレプユニット数という。 レプユニット数 3 個の和として考えられる数のうち、 番目に小さい数を求めよ。 制約 考えたこと まず、問題文の条件を満たす数をトリレプ…
昔の ABC A 問題はこういうのよくあった！ 問題へのリンク 問題概要 3 文字の文字列 が与えられる。これを並び替えることで "ABC" に一致させることができるかどうかを判定せよ。 考えたこと 並び替えて "ABC" に一致する文字列は "ABC" "ACB" "BAC" "BCA" "…
「前回の値」を保持しながらシミュレーションする系 問題へのリンク 問題概要 ボタンを押すと、1 個の飴がもらえるが、前回飴をもらってから 秒間はもらえない。 高橋君は 回ボタンを押した。それぞれ 秒後に押した（これらは単調増加）。 何回飴をもらえた…
文字列を for 文で調べる系の問題 問題へのリンク 問題概要 文字 #, . からなる長さ の文字列 が与えられる。次の条件を満たす整数 の個数を求めよ。 = # = . = # 考えたこと 次のように考えると実装しやすい。 各 に対して、文字列 の 文字目から 3 文字文…
ちょっとした算数・数学の問題！ 問題へのリンク 問題概要 考えたこと A, B, C, D, E をそれぞれ 0, 1, 2, 3, 4 と対応させよう（0 始まりにするのがコツ）。このとき、対角線の長さは、対角線の両端に対応する数値の差で表すことができる。 たとえば、線分 …
これ結構難しくて、嵌まる人は嵌まってしまうと思う！！ 問題へのリンク 問題概要 ダンジョンには、ポーション と、敵 がいる。 今、ダンジョンで 個のイベントが起こる。イベント は 2 つの整数 で表される。 のとき：ポーション が現れる それを拾うかどう…
スタックによるシミュレーション問題！ 問題へのリンク 問題概要 整合のとれたカッコ列に対して、英小文字がいくつか挿入されてできる文字列が与えられる (たとえば、"(a(ba))c")。 このような文字列に対して、高橋君が気絶するかどうかを判定したい。次のよ…
