PAST003D 出力1をコピーすれば， \(0, \cdots, 9\) に対応するchar たちが分かる． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { vector<string> t = { ".###..#..###.###.#.#.###.###.###.###.###.", ".#.#.#</string>…

PAST003F 回文は，外から決めるか内から決めるかのどちらかが基本． 今回は外から決めることにするが，どちらでも可能． \(a_{i}\) と \(a_{n-1-i}\) に共通の文字があればそれを使う， なければ回文が作れない これを \(i\) について貪欲に決めていく． 今…

PAST003G 問題文に金移動とあり将棋の金のような動きだが，移動方法はあまり重要ではなく，基本はBFS. ただし，そのままやると無限に広がるグリッドなので無限ループに入ってしまう． そこで，グリッドの範囲を狭くすることを考える． 遠くに行き過ぎるメリ…

PAST003H 座標 \(i\) にいるとき，次に取るべき行動は， 今までの行動とは無関係に選べる． つまり，時刻だけが重要で今までの選択は無関係なので， 状態をまとめることができ，これはDPで実現可能． 実装ジャンプ中にゴールするときだけ注意． 問題文にも書…

PAST003I 転置のクエリだけが時間がかかるので，そこを何とかする． 転置は2回繰り返すともとに戻るので，回数だけ記録しておく． また，行と列は独立に操作可能． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int…

PAST003J LISに近い問題． 実験してみると，子供 \(i \in N\) が食べた最大の寿司を \(v_{i}\) とおくと， \(v\) は常に降順． よって，誰が食べるのかは binary search で求まる． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/1…

PAST003K データ構造の問題． 愚直に移動を実装していてはTLE. コンテナ毎について， 下に何があるか，上に何があるか を記録しておく． 切れ目とつなぎ目だけ更新すれば良いので \(O(Q)\) 実装今回の問題では，上に何があるかは記録しなくてもよい，また，…