D - Yet Another Sorting Problem
解説は見たものの、さっとは理解できなかったため、参考にして実験してAC。
グラフの問題だと思ったし、連結成分に注目するのかな？ とは疑ったものの、確信が持てず捨ててしまった。
連結成分ごとにサイクルになる、ということに気付いてなかったのは問題。気付けば当たり前だけど、ここが考察の第一歩だったと思う。
その後の考察はどうすれば良かったか難しい……。
確かに、「左側/右側だけのサイクル」は「左右両方の側に要素があるサイクル」よりコストがかかるのは分かる。
具体的には、後者は、連結成分のノード数-1回操作すれば良いが、前者はノード数+1回操作しなくてはいけない。
ただ、サイクルごとに完結するのではないのが難しい。
「左側だけのサイクル」と「右側だけのサイクル」が両方あった場合、前者の操作途中で後者の処理をすることにより、後者をノード数-1で済ませられる……というのが本質だった。
逆に、「左側だけのサイクル」が複数あっても、それぞれの操作が干渉しないため、操作回数を減らすことはできない。
なので、max(「左側だけのサイクル」の個数, 「右側だけのサイクル」の個数)だけ、操作回数が増えるものがある、ということになる。
コンテスト中は、「左側だけの連結成分」と「右側だけの連結成分」（コンテスト中は連結成分がサイクルになると気付いてなかったのでこう書いています）が干渉することがある、ということは、連結成分ごとに見る方針は間違っているのでは？ と思ってしまい、考察を進めることができなかった。
解法を見ても、試行錯誤するしかないかなぁ、という気もするので何を反省すべきか難しい。
思いつけてない何かがあったというわけではなく、どれが正しい方針か分からなかったという感じだし。
愚直solverを書いていたら多少違ったかもしれないけれど、決定打にはならなそうだし、どう実装すれば良いかもちょっと迷ってしまう。さっと書けるなら書いていたと思うので。
うーん。
書くなら、順列同士で、一回の操作で行けるもの同士にedgeをつけて、ソートされたものからBFSする感じか。これでN+Mが9あたりまでは判定できるなら、実装する価値はあったかも。
（EやFはACしたら追記）
0 件のコメント:
コメントを投稿