ABC286受験結果
A~E の1500点
STLを使えば実装はもう少し早かった．
C問題
操作が複数与えられた場合は，順序を変えるとどうなるかを考えると役立つケースが多い．
今回は最適解として， Rotateを何回か \(\rightarrow\) 置き換えを何回か の形のものが存在する． よって， 最初に何回rotateするかを全探索． あとは，置き換えの必要回数は，両端から文字列の一致を調べればよい． 一応，文字列の長さの偶奇に注意．
D問題
これもTLEとWAを出してしまった． WAはテストケースを実行してれば防げたのに，急いで提出したせい．
- 問題文をきちんと読むこと，
- 計算量を見積もること．
それらを守れば防げた．
DFSで全探索したがTLEした．これは計算量を見積もればすぐに分かることだった． 実装にかけた時間を無駄にしてしまった． AC解法は，ループを使ったDP.
\(i \in N \)とする． \(y\) 円作るために， \(j \in [0,i)\) に対して， 硬貨 \(j\) を何枚使うか決めたとする． 残りの硬貨 \([i,N)\) を何枚ずつ使うかどうかを決めるときは， 今 \(y\) 円ということだけが重要で， 何枚ずつ使ったかは関係ない．
E問題
BFSでOK. (移動コスト, お土産の値段) のペアをもってBFS. ただし，移動コストは昇順，お土産は降順としたいので， お土産の値段に-1を掛けておいて， ペアの min をとりながら遷移．
TLE を出してしまったが，改良してAC. 直した部分は以下の通り．
- クエリ毎のBFSをしないで，前計算した
- 前計算も，source だけ全探索で十分
- map を使わずにvector にした
実装は，Wa-shall-Floyd の方が楽だし，負コストの辺があっても正しく動く．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
