ABC107-C で学んだこと
- リストのコピーはコストが少なくともコピーする要素分かかる。
- リストのコピーを作るのは、リストをいじる必要がある場合かつ、コピー&いじる操作を含めて時間内に処理が終わる程度のデータ数に対してのみ。それ以外はいのす法みたいに最後にまとめて処理する。
ACとなった回答がこれ。
TLEとなった回答がこれ。
ほぼ同じだけど、TLEのほうでは元のリストの部分コピーを生成して、それに対して比較を行っている。リストを書き換えたりしない問題なので、コピーを作る意味がない。コピー操作にはやはりコピーする分だけ時間がかかるため、これがTLEの原因。コピーを省くと100ms程度で終わるようになった。