午前 基礎アルゴリズム#
検索#
概要#
DFS BFS 反復深化 双方向検索 A*
例題：k 短路問題#
todo
分治#
例題：平面最近点対#
todo
貪欲法#
例題#
1.[AHOI2018 中学生グループ] グループ分け#
ソート後、前から順に各数 $i$ がどこに置かれるべきか、どう置くかを考える。
2. 削除数問題#
逆に考える。順に答えの第 $i$ 位にどの数字を入れられるかを決定する。
3.[NOIP2012 上級グループ] 王様ゲーム#
前方に $S$ 人が並んでいると仮定し、次の 2 人をどう並べるかを考え、全員に拡張する。
午後 模擬試験#
T1 美しい列#
問題文#
長さ $n$ の列 $a$ と正整数 $k$ が与えられる。
小 A は、長さ $m$ の列 $a$ が美しいと考え、すべての隣接する 2 数の和が $k$ の倍数であるとき、すなわちすべての $i\in [1,m)$ について $k\ |\ (a_i+a_{i+1})$ が成り立つときに美しいと考える。
小 A は長さ $n$ の列 $a$ を持っており、残りの列が美しくなるようにできるだけ少ない数を削除したい。
最小で削除する必要がある数の個数を計算する必要がある。
考察ポイント#
逆に考えて、どれだけ残せるか。結論から出発し、結論の性質を導き出す。
進行#
まず、各入力の数を k で割った余りを考えると、結果に影響を与えないことが容易に思いつく。
次に結果の性質を考える。最初の数が $x$ であれば、2 番目の数は必ず $k-x$ でなければならず、3 番目の数は $x$ でなければならない。これを繰り返す。
したがって、余りを取った配列をスキャンし、各数（数そのもの）$i$ を考慮し、この数の前の数は $k-i$ でなければならない。結果の長さを求めるために、スキャンした数の前に、$k-x$ で終わる、結果の性質を満たす（統計的に言えば $i$ がその後に置ける）部分列の長さを保存するために、map$f [x]$（値域が大きすぎる）を使用する。したがって、$i$ に対して、その前の数は $k - i$ であるため、$f [i] = f [k - i] + 1$ とし、同時に答え ans を更新できるかどうかを確認する。
コードは以下の通り
T2 簡単な数学の問題#
問題文#
小 B は数学が大好きで、ある日、小 B の友達が彼に 2 つの数 $n,p$ を教え、$1≤i,j≤n$ かつ $i \mod j≤p$ を満たす対 $(i,j)$ がいくつあるかを尋ねた。
小 B はすぐに理解し、あなたにこの問題が解けるか尋ねた。
考察ポイント#
long long を使わずに、数論のブロック分け（todo）。
進行#
todo
T3 奇妙なスタック#
問題文#
小 C は奇妙なスタックを持っており、$n$ 個の要素が入っていて、各要素には 3 つの属性 $a_i,b_i,c_i$ がある。
小 C は毎回スタックの一番上の最初の要素と 3 番目の要素から 1 つを選んで取り出す。最初の取り出しを除いて、小 C は毎回取り出す要素の $a_i$ と $b_i$ のうち少なくとも 1 つが前回取り出した要素と同じであることを保証する。
小 C は、どのように要素を取り出せば取り出した要素の $c_i$ の合計を最大にできるかを知りたい。
考察ポイント#
todo
進行#
TODO
T4 魔法の文字列#
問題文#
小 B は長さ $n$ の文字列 $S$ を持っている。
小 B は、この文字列 $S$ のある部分列が「魔法」であると考え、その部分列に出現した文字の出現回数がすべて同じであるときに限る。
小 B は、文字列 $S$ にいくつの「魔法」の部分列があるかを知りたい。
この問題の文字列の部分列は、その文字列の連続した部分を定義する。
考察ポイント#
todo
進行#
todo
その他#
2 つの資料、一つの宿題