帰着する力を鍛える
前回帰着訓練は一気にいくつもの問題のページを作ってしまったが、Scrapboxでそれをやると後で大変だということがわかった
- 考察: 思考の結節点2020-12-18 ページをたくさん作るのではなく、全部入りの大きなページを作ってから分割していくほうが良いかな
前回はAtCoder Problemsのレコメンデーションを使った だけど帰着訓練ではACにしないため、リストのトップに残り続けて不便 結局のところ僕は青色の問題を解けば良いようなのでABCなどの青色問題を端から解いていく方が良いのでは
AGCを新しい順にやるかな
https://atcoder.jp/contests/agc049/tasks/agc049_a AGC049A
AGC047B https://atcoder.jp/contests/agc047/tasks/agc047_b
- 文字列対にそれぞれ判定しても間に合わない
- 各文字列になんらかの処理をしたらそれだけで求まる仕組みが必要
- 特殊な制約の問題
- 文字列長の総和が10^6で抑えられてる
- 一致する文字列対とは
- 短い方の長さをnとした時に、末尾n-1文字が一致して、残り1文字がどちらにも含まれてる
- あらかじめ短い順にソートしておき、n-1文字一致したら26文字の配列にフラグを立てておき、その文字が出てきた時点で解をインクリメント
- 「n-1文字一致」をどうやるか
- トライ木に入れていく？
- その方針で良いらしいが、ローリングハッシュという手もあるらしい
https://atcoder.jp/contests/agc043/tasks/agc043_b
- 一度ある状態になると抜け出せない
- 1ステップで「すべての値が0〜2」になる
- 最後が2になるのは全部0で片端が2のものだけ
- 2は隣に0がないと維持されない、一般的に割とすぐ消える
- とはいえ消えない時もあるからどうしたものか