考察:ソート
はじめての「〜が 以下になる瞬間」を捉えるというシミュレーション問題。 問題へのリンク 問題概要 高橋君は 種類の薬を処方された。薬 は、 日目まで、毎日 錠ずつ飲むこととなる。 1 日に飲む錠剤の個数がはじめて 錠以下になる日を求めよ。 制約 考えた…
lower_bound() 系の教育的問題 問題へのリンク 問題概要 一直線上に 個の点がある。点 の座標は である。 この直線上で幅 の区間を配置する。左端の座標を とするとき、 を満たす の個数をスコアとする。最大スコアを求めよ。 制約 考えたこと まず重要な考…
伝説の誤差問題!! 誤差について学べる、とても教育的な問題。 問題へのリンク 問題概要 人がコイントスをしました。各人には と番号がついています。 人目は、 回表が出て、 回裏が出ました。 人目のコイントスの成功率は と定義されます。 人 の番号を、…
いろんな方法が考えられそう! 問題へのリンク 問題概要 個の整数 が与えられる。 を満たすすべての の組に対する の総和を求めよ。 制約 考えたこと 絶対値のままだと厄介。ちょっと工夫する。まず、数列 の並びを入れ替えたとしても答えが変わらないことに…
ちゃんと証明しないと、なかなか安心して提出できない系 問題へのリンク 問題概要 整数列 が与えられる。次の操作を繰り返し行って、 の最大値と最小値の差が 1 以下となるようにしたい。実現のための操作の最小回数を求めよ。 を選んで、 に 1 を足し、 か…
連想配列が有効活用できる問題 問題へのリンク 問題概要 個の文字列 がある。 登場回数の最も多い文字列を、辞書順に出力せよ。 制約 考えたこと 各文字列がそれぞれ何個あるのかを求めたい。そこで、次のような配列を作りたい。 nums[str]:文字列 str の登…
ソートする問題。 問題へのリンク 問題概要 個のコマを数直線上に配置して、それぞれ移動させる。 それによって、 個の地点 をすべて訪れるようにしたい。総移動距離の最小値を求めよ。 制約 考えたこと とりあえず、各コマについて、「行って、引き返して」…
今の 300 点に比べると少し易しめで、でも 300 点っぽくていい感じだなと。 問題へのリンク 問題概要 個の整数 が与えられる。ここから 個の整数を選ぶ。 「選ばれた数の最大値と最小値の差」の最小値を求めよ。 制約 < 考えたこと すごく 300 点問題っぽく…
これでひとまず ABC 100 以降の CD 問題は全部書けた 問題へのリンク 問題概要 個のお店があって、各店 では 1 本 円のエナジードリンクを 本まで買うことができる。 全部で 本のドリンクを買いたい。最小で何円で実現できるか? 制約 考えたこと 基本的に安…
ペア の大きい順にソートする嘘貪欲にハマってしまった方が多そうだった 問題へのリンク 問題概要 青木君と高橋君が選挙を行う。 個の町があり、 番目の町では 青木派が 人いる 高橋派が 人いる ということがわかっている。高橋君はいくつかの町で選挙活動を…
バケットを使ってもいいし、set や map を使ってもいいかもしれない 問題へのリンク 問題概要 が 3 回ずつ表れる長さ の数列 が与えられる。 を「数列 において 2 回目にその値が登場する index」が小さい順にソートせよ。 制約 考察:まず問題を掴む 最初の…
ペアのソート。ソートの比較関数を作る系。 問題へのリンク 問題概要 人のプレイヤー によるリーグ戦の戦績表が下のように与えられる。 7 -oxoxox x-xxxox oo-xoox xoo-ooo ooxx-ox xxxxx-x oooxoo- プレイヤーを勝ち星数が多い順に並び替えよ。ただし、タイ…
1 つ 1 つの要素は難しくないが、実装がとにかく重たい!落ち着いて整理して考えたい問題。 問題へのリンク 問題概要 プレイヤー が、配点が である 個の問題からなるコンテストに挑んでいる。なお、 は 以上 以下の の倍数である。 プレイヤー には最初から…
色んな解法が考えられそうな問題で、ドツボにハマりやすくて危険な問題だったと思う。落ち着いて整理してシンプルに考える力が問われる。実は、二分探索などは必要ない問題である。 問題へのリンク editorial 問題概要 人の選手 がいる。選手 の出身国は で…
いろんな方法がありそう。こういうのを工夫して解き切る腕力はいつだって大事になる。 問題へのリンク 問題概要 個のペア値 が与えられる。 ある について かつ を満たすとき、ペア値 を削除する操作を繰り返す。 最後に残るカードの集合を求めよ。 制約 考…
文字列を辞書順にソートする方法を確認しておこう! 問題へのリンク 問題概要 人のユーザーがいて、 人目の名前は 、レーティングは である。 レーティングの総和を で割った余りを としたとき、各ユーザーの名前のうち、辞書順で小さい順に 番目のものを求…
この回、B と C が異常難易度だったために、D が実際の難易度よりもだいぶ Diff が上がってそうだ! 問題へのリンク 問題概要 台のソリがあり、それぞれトナカイを 匹必要とする。次の 回のクエリに答えよ。 【クエリ】 トナカイが 匹いるときに、最大で何台…
鉄則本 B11 とほぼ同じ問題! 問題へのリンク 問題概要 身長が であるような 人がいる。以下の 回のクエリに答えよ。 【クエリ】 整数 key が与えられるので、身長が key 以上の人が何人いるかを答えよ。 制約 考えたこと 0-indexed で考えます。 最初に、 …
ソートの練習! 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。なお、これら 個の値はすべて互いに相異なる。 これらをすべて混ぜた 個の値を小さい順に並べたとき、数列 の要素が 2 個以上連続する箇所があるかどうかを判定せよ。 制…
面白かった! 問題へのリンク 問題概要 正の整数からなる長さ の数列 が与えられる。 の値を求めよ。 制約 考えたこと まず、 という制約が怪しい!!! きっと、 として な計算量になるに違いないと思えた。 とりあえず、数列を元のまま考えるのではなく、…
めっちゃ面白い問題!! 実はよく似た類題として次の問題がある! atcoder.jp 問題へのリンク 問題概要 長さが の数列 が与えられる。この数列から 個の要素を削除する。 残った数からなる数列中の、最大値と最小値の差の最小値を求めよ。 制約 考えたこと …
この時代の一次予選は、まだちょっと難しかった 問題へのリンク 問題概要 3 個の整数 が与えられる。これらの整数のうち、2 番目に大きい値を求めよ。 制約 解法 (1) 最も楽だと思われる方法は、3 個の整数のうちの「最大値」と「最小値」を求めてあげる方法…
この手の問題は最初にソートすると考えやすいことが多い。 問題へのリンク 問題概要 5 枚のカードには数 が書かれている。これがフルハウスであるかを判定せよ。 なお、5 つの数がフルハウスであるとは、同じ数が書かれたカード 3 枚と、別の同じ数が書かれ…
ソートの練習問題 問題へのリンク 問題概要 20 個の整数が与えられる。 前半 10 個の整数のうち、大きい順に 3 個の整数の総和 後半 10 個の整数のうち、大きい順に 3 個の整数の総和 をそれぞれ求めよ。 解法 前半ができれば後半も同様なので、前半を考えま…
ちゃんと証明しようとすると、結構大変! 問題へのリンク 問題概要 人の生徒がいて、生徒 の身長は である。 これらの生徒を 2 人ずつ 組に分けて、どの組も身長差が 以下となるようにしたい。 そのようなことが可能かどうかを判定せよ。 制約 考えたこと こ…
シミュレーションするか、ソートするかによって解ける典型問題! 問題へのリンク 問題概要 人の髪の長さは最初 であった。 各人の髪の長さは 1 日に 1 ずつ伸びる。 初めて髪の長さが 以上の人が 人以上となるのは何日後かを求めよ。 制約 解法 (1):シミュ…
for 文の練習! 問題へのリンク 問題概要 個の整数 のうち、最大値と最小値を除外した 個の整数の総和を求めよ。 制約 個の整数はすべて互いに相異なる 解法 まず 個の整数を「配列」として受け取りましょう (C++ では vector<int> 型など)。 その後、配列に対し</int>…
昔の ABC A 問題はこういうのよくあった! 問題へのリンク 問題概要 3 文字の文字列 が与えられる。これを並び替えることで "ABC" に一致させることができるかどうかを判定せよ。 考えたこと 並び替えて "ABC" に一致する文字列は "ABC" "ACB" "BAC" "BCA" "…
座標ごとに情報を整理するのは頻出! 問題へのリンク 問題概要 x-y 座標平面上に 人がいる。それぞれ座標 の位置にいて、左右いずれかを向いている(各人が左右どちらを向いているかは文字列 で与えられる)。 各人が、その位置から、向いている方向に向かっ…
ソートが使えるなら、それが楽だと思う 問題へのリンク 問題概要 6 桁の正の整数 が与えられる。 が次の条件を満たすかどうかを判定せよ。 1 をちょうど 1 個含む 2 をちょうど 2 個含む 3 をちょうど 3 個含む 解法 (1):1, 2, 3 の個数を数える方法 for 文…