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