Dまで五完でした。Eは解説と同じことを考えていたのに、なぜかそれではまずいと思い込んでしまった。
No.1369 交換門松列・竹
二点の交換しかできないので、たくさん門松列になっていないものはそもそもダメ。少なくとも一つはダメなところを交換に使わなくてはいけないから、「ダメなところとそれ以外のどこか」を交換する全探索すれば良い。交換後に門松列列になっているかどうかは、元々門松列になっていて交換に絡まないところはチェックしなくて良いので、「ダメだったところ」と「交換した箇所の周囲」だけチェックすればOK。
この「たくさん」とか「周囲」というのが具体的にどれだけか考えるのがややこしくてWAを出したけれど、安全を取って大き目に取ればACできました。
最初から大き目に取るべきでした。
No.1370 置換門松列
公式解説と同じことを考えていたけれど、同じことをやっても（Phase 1のチェックをしていても）A[i]=A[i+2]となるケースを除けない気がしてしまった。
トポロジカルソート順に決めたとき、別の数に同じ数字が割り当てられる可能性がある気がしてしまったせいだと思うんだけど、そんなことは起こり得ない。
検証したら気付いたと思うので、変に悩まず、図を描いたり実装したりすべきでした。
0 件のコメント:
コメントを投稿