けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

JOIG

JOIG 春合宿 2023 day2-2 White Light (2D, 難易度 8)

セグメント木を用いた DP 高速化! 問題へのリンク editorials 問題概要 'R' と 'G' と 'B' のみからなる長さ の文字列 が与えられる。以下の操作を繰り返し行うことで、"RGB" を繰り返す文字列となるようにしたい。 (操作) 連続する 個以下の文字を消す 目…

JOIG 春合宿 2023 day2-1 Smartphone (難易度 8)

JOI ではお馴染みの「 個の区間を扱う問題」。ただし実装がしんどかった。僕は区間を set で管理する方法で実装した。 問題へのリンク editorials 問題概要 制約 考えたこと いかにも貪欲法の香りが漂っている問題ですね。この手の問題では、 個の区間を終端…

JOIG 2024 A - 三連続 (難易度 2)

for 文の練習問題! 問題へのリンク 問題概要 o と x からなる長さ の文字列 が与えられる。 の中に o が 3 つ連続している箇所があれば "Yes" を出力し、そうでなければ "No" を出力せよ。 制約 考えたこと for 文を用いて判定しよう。具体的には、各 i に…

JOIG 2024 E - 名前 (難易度 9)

いかにも JOI にありがちな添字の持ち方をする DP! 問題へのリンク 問題概要 英小文字と英大文字からなる長さ の文字列 と、長さ の文字列 が与えられる。また 0 以上 3 以下の整数 が与えられる。 次の条件を満たす文字列 の長さの最小値を求めよ。 は、英…

JOIG 2024 C - 座席 2 (難易度 6)

色んな解法が考えられそうな問題で、ドツボにハマりやすくて危険な問題だったと思う。落ち着いて整理してシンプルに考える力が問われる。実は、二分探索などは必要ない問題である。 問題へのリンク editorial 問題概要 人の選手 がいる。選手 の出身国は で…

JOIG 2023 E - 運河 (難易度 7)

UnionFind を使って、差分更新を頑張る! UnionFind はオンラインの処理を簡単に実現できることが強みで、それを問いかける教育的問題ですね。他にも「左右からの結果を前処理する」という典型テクも使います! 問題へのリンク 問題概要 のグリッドがあって…

JOIG 2023 D - コイン集め 2 (難易度 6)

データを上手に持って、差分更新する系の問題 問題へのリンク 問題概要 のグリッドがあって、各マスは文字 '#' か '.' のいずれかが書かれている。先手は '#' の個数が得点となり、後手は '.' の個数が得点となる。双方得点を最大化したい。 先手は行を 1 つ…

JOIG 2023 C - 鐘 (AOJ 0759, 難易度 4)

直線がいくつかの区間に分かれているとき、点がどの区間に属するかを求めたいとなったら、lower_bound()!!! 問題へのリンク 問題概要 数直線上に 個の鐘がある。 番目の鐘は座標 の地点に配置されている。 地点 の人の聞く鐘の音の強さは、各鐘 に対する …

JOIG 2023 B - 絶対階差数列 (AOJ 0758) (6Q, 難易度 2)

いわゆる「愚直シミュレーション」と呼ばれる分野の問題ですね。問題文で指示されたことを、とにかく愚直に忠実に実装できるかが問われています。地味な印象を受けるかもですが、大切なスキルです! 問題へのリンク 問題概要 黒板に、はじめ 個の整数値 が書…

JOIG 2023 A - 末尾の文字 (AOJ 0757) (9Q, 難易度 1)

文字列の練習! 問題へのリンク 問題概要 英大文字のみからなる、長さ の文字列 が与えられる。 の末尾の文字が 'G' 以外のとき: の末尾に文字 'G' を挿入して得られる文字列を の末尾の文字が 'G' であるとき: の末尾の文字 'G' を削除して得られる文字列…

JOIG 春合宿 2022 day1-1 Relay (難易度 6)

面白かった! ジャッジページ 問題文 問題概要 人の走者がいる。 人の中から 人を選んで、100m 走る × 3 の 300m リレーを行う。 人目の 100m 走のタイムは 秒、バトンパスタイムは 秒で与えられる。リレーの走者として、 の 人を選んでこの順に走るときの総…

JOIG 2021 D - 展覧会 2 (AOJ 0704, 難易度 6)

「競プロ典型 90 問 001 - Yokan Party」とよく似た問題! 問題へのリンク editorial 前提知識 基本的な二分探索 問題概要 枚の絵が一直線上に順に並んでいます。 枚目の絵は座標 の位置にあり、その価値は です。 今これらの絵から 枚の絵を選びます。この…

JOIG 2021 C - イルミネーション 2 (AOJ 0703, 難易度 4)

落ち着いて整理して考えましょう。問題自体は「累積和」が使える良い問題ですね! 問題へのリンク editorial 問題概要 個の電球を一列に並べていて、オンオフ状態が であるような状態を作りたいとします。ただし は 番目の電球をオンにしたいことを表し、 は…

JOIG 2021 B - 巻物 (AOJ 0702, 難易度 2)

文字列の処理を練習する問題ですね 問題へのリンク 問題概要 文字の文字列 が与えられます。 は英文字のみからなります。 の 文字目以降について、 大文字ならば小文字に 小文字ならば大文字に なるように変換してくだだい。 制約 考えたこと この問題では、…

JOIG 2021 A - 金平糖 (AOJ 0701, 難易度 1)

入出力の練習をしましょう。 問題へのリンク editorial 問題概要 3 人の生徒がそれぞれ 個、 個、 個の金平糖をもらいました。 これからそれぞれの生徒たちに何個かの金平糖を追加で渡すことで、3 人の生徒がもらった金平糖の個数が等しくなるようにしたいと…