E. Matrix Transformation
解説は理解したが、貪欲でAC。
公式解説の方法は、「ある操作の後に別の操作がある」という条件がいくつも現れるので、グラフにし、トポロジカルソートしてループがないか探すというもの。
しかし、貪欲に、行と列の操作を交互に31回行って一致すればYes、としてACしているコードがあった。
確かに、上記のような条件は、min(行の数, 列の数)しか現れないので、n×m≤1000 という制約があるため、これで良い。
コンテスト中は貪欲方針を書いて、二回しか回さずにWAを出していた。貪欲でいけるかも？ と考えるのは良いけど、正当性も全く思いついていないのでダメですね。
また、bitずつやらなくても実装できるところを、bitずつやって定数倍が遅い実装になっていたのもまずい。
0 件のコメント:
コメントを投稿