2024-02-13から1日間の記事一覧
AtCoder
JOI
JOIG
JOI難易度2
for文
for文:隣接する前後の要素を見る
全探索:線形探索法
0と1の問題
文字列
Yes/No判定問題
易しいYes/No判定問題
for文:存在するかを求める
for 文の練習問題! 問題へのリンク 問題概要 o と x からなる長さ の文字列 が与えられる。 の中に o が 3 つ連続している箇所があれば "Yes" を出力し、そうでなければ "No" を出力せよ。 制約 考えたこと for 文を用いて判定しよう。具体的には、各 i に…
AtCoder
JOI
JOIG
JOI難易度9
DP
BFS
LCS型DP
LCS
DP状態:state
スライドbitDP
DP状態:ビット
文字列
部分列
最小回数・最小個数を求める
制約条件:隣接する要素について
最適化問題
いかにも JOI にありがちな添字の持ち方をする DP! 問題へのリンク 問題概要 英小文字と英大文字からなる長さ の文字列 と、長さ の文字列 が与えられる。また 0 以上 3 以下の整数 が与えられる。 次の条件を満たす文字列 の長さの最小値を求めよ。 は、英…
AtCoder
JOI
JOIG
JOI難易度6
ソート
全部混ぜて解く
色に関する問題
一直線上のN点の問題
各kに対して
まずソートして考える
ランレングス圧縮
「次の要素」へのポインタを求める
テク:区間ごとに分割する
差分更新
for文:連続する区間を求める
色んな解法が考えられそうな問題で、ドツボにハマりやすくて危険な問題だったと思う。落ち着いて整理してシンプルに考える力が問われる。実は、二分探索などは必要ない問題である。 問題へのリンク editorial 問題概要 人の選手 がいる。選手 の出身国は で…