JOIG
ちゃんと証明しようとすると、結構大変！ 問題へのリンク 問題概要 人の生徒がいて、生徒 の身長は である。 これらの生徒を 2 人ずつ 組に分けて、どの組も身長差が 以下となるようにしたい。 そのようなことが可能かどうかを判定せよ。 制約 考えたこと こ…
「実は各点から左右に見て最も近い点だけ見れば良い」という点気考察をする！ 問題へのリンク 問題概要 数直線上に 個の絵がある。 番目の絵のある位置の座標は であり、'J', 'O', 'I', 'G' のいずれかの文字 が書かれている。 これらの絵に対して、以下の …
セグメント木を用いた DP 高速化！ 問題へのリンク editorials 問題概要 'R' と 'G' と 'B' のみからなる長さ の文字列 が与えられる。以下の操作を繰り返し行うことで、"RGB" を繰り返す文字列となるようにしたい。 (操作) 連続する 個以下の文字を消す 目…
JOI ではお馴染みの「 個の区間を扱う問題」。ただし実装がしんどかった。僕は区間を set で管理する方法で実装した。 問題へのリンク editorials 問題概要 制約 考えたこと いかにも貪欲法の香りが漂っている問題ですね。この手の問題では、 個の区間を終端…
for 文の練習問題！ 問題へのリンク 問題概要 o と x からなる長さ の文字列 が与えられる。 の中に o が 3 つ連続している箇所があれば "Yes" を出力し、そうでなければ "No" を出力せよ。 制約 考えたこと for 文を用いて判定しよう。具体的には、各 i に…
いかにも JOI にありがちな添字の持ち方をする DP！ 問題へのリンク 問題概要 英小文字と英大文字からなる長さ の文字列 と、長さ の文字列 が与えられる。また 0 以上 3 以下の整数 が与えられる。 次の条件を満たす文字列 の長さの最小値を求めよ。 は、英…
色んな解法が考えられそうな問題で、ドツボにハマりやすくて危険な問題だったと思う。落ち着いて整理してシンプルに考える力が問われる。実は、二分探索などは必要ない問題である。 問題へのリンク editorial 問題概要 人の選手 がいる。選手 の出身国は で…
UnionFind を使って、差分更新を頑張る！ UnionFind はオンラインの処理を簡単に実現できることが強みで、それを問いかける教育的問題ですね。他にも「左右からの結果を前処理する」という典型テクも使います！ 問題へのリンク 問題概要 のグリッドがあって…
データを上手に持って、差分更新する系の問題 問題へのリンク 問題概要 のグリッドがあって、各マスは文字 '#' か '.' のいずれかが書かれている。先手は '#' の個数が得点となり、後手は '.' の個数が得点となる。双方得点を最大化したい。 先手は行を 1 つ…
直線がいくつかの区間に分かれているとき、点がどの区間に属するかを求めたいとなったら、lower_bound()！！！ 問題へのリンク 問題概要 数直線上に 個の鐘がある。 番目の鐘は座標 の地点に配置されている。 地点 の人の聞く鐘の音の強さは、各鐘 に対する …
いわゆる「愚直シミュレーション」と呼ばれる分野の問題ですね。問題文で指示されたことを、とにかく愚直に忠実に実装できるかが問われています。地味な印象を受けるかもですが、大切なスキルです！ 問題へのリンク 問題概要 黒板に、はじめ 個の整数値 が書…
文字列の練習！ 問題へのリンク 問題概要 英大文字のみからなる、長さ の文字列 が与えられる。 の末尾の文字が 'G' 以外のとき： の末尾に文字 'G' を挿入して得られる文字列を の末尾の文字が 'G' であるとき： の末尾の文字 'G' を削除して得られる文字列…
面白かった！ ジャッジページ 問題文 問題概要 人の走者がいる。 人の中から 人を選んで、100m 走る × 3 の 300m リレーを行う。 人目の 100m 走のタイムは 秒、バトンパスタイムは 秒で与えられる。リレーの走者として、 の 人を選んでこの順に走るときの総…
「競プロ典型 90 問 001 - Yokan Party」とよく似た問題！ 問題へのリンク editorial 前提知識 基本的な二分探索 問題概要 枚の絵が一直線上に順に並んでいます。 枚目の絵は座標 の位置にあり、その価値は です。 今これらの絵から 枚の絵を選びます。この…
落ち着いて整理して考えましょう。問題自体は「累積和」が使える良い問題ですね！ 問題へのリンク editorial 問題概要 個の電球を一列に並べていて、オンオフ状態が であるような状態を作りたいとします。ただし は 番目の電球をオンにしたいことを表し、 は…
文字列の処理を練習する問題ですね 問題へのリンク 問題概要 文字の文字列 が与えられます。 は英文字のみからなります。 の 文字目以降について、 大文字ならば小文字に 小文字ならば大文字に なるように変換してくだだい。 制約 考えたこと この問題では、…
入出力の練習をしましょう。 問題へのリンク editorial 問題概要 3 人の生徒がそれぞれ 個、 個、 個の金平糖をもらいました。 これからそれぞれの生徒たちに何個かの金平糖を追加で渡すことで、3 人の生徒がもらった金平糖の個数が等しくなるようにしたいと…
