精進メモ 2021/03/29~

解説ではないです。エスパーしたものもあります。

みんなのプロコン2019 E - Odd Subrectangles

問題
提出コード
こういうのを理論的に解くことができない、どうすればいいのでしょう…
全探索をベースにまず考えていき、まずはどこかで計算をまとめる方法を考えます。しかし、このような問題の場合はDPがしづらい(情報として、今までに使用することを決めた行 + 列の集合がどうしても必要になります)のと、偶奇の個数等を用いて他のまとめて数え上げるような方法が通用しません。
そこで、自分はまず実験をしました。すると、として、
の場合は数字が1種類、は2種類…というように、行数のパターンしか答えがでてこないことに気づきます。
経験から、何か使えそうなアルゴリズム・テクニックとして、行列(のランク)を選ぶと、見事に行列のランクが、答えの出現パターンと一致していることがわかりました。その後も詰めていくと、

が答えになっていることがわかるので、答えを出力するとACします。
解説ブログも簡単に漁ってみましたが、行と列の入れ替えは基本変形っぽいな、という部分に気づいていましたがそこから先の部分も似たようなことをしているのに気づきませんでしたね…
線形代数の知識があまりにも不足している気がします。

ARC116 E - Spread of Information

問題
提出コード
定数個あるものを設置して、かかる時間を最小化する問題なので、その時点で二分探索っぽいなぁと思いました。冷静に見てみると、たしかに単調性がありそうなので、時刻までに条件を達成するために必要な連絡先の個数が個いかか？という判定を行い、で二分探索をします。
判定部分は、入力が木なので木DPを疑います。
任意の頂点からちょうど距離以内に、連絡先が置かれていなければならないので、条件がきつそうな葉の部分から、ということからも、DPがよさそうだとわかります。
そこから適当に実装…をしてコンテスト中に通しきれませんでした。かなり迷走(一回DPから離れた)したのもありましたが、もっと丁寧に詰めるべきでした。葉から数えていき、今一番遠い(かつまだ距離以内に連絡先がない)頂点との距離がになったタイミングで基本的に連絡先を設置します。が、その頂点に設置したことで、もう考慮する必要がなくなった頂点を数え漏らし、連絡先の配置が最適になっていませんでした。
連絡先を設置した頂点から、あとどれくらい離れても以内に届くか、という情報もDPに持たせることで無事ACです。

第6回 ドワンゴからの挑戦状 予選 D - Arrangement

問題
提出コード
ある一定の段階まで作成した後、問題の条件を満たすことができなくなるのは2パターンあります。

• 残り2頂点(とします)になった際、の右隣にが許されず、の右隣にが許されない(条件を辺と見たときグラフがループする)パターン

• 残り頂点のとき、ある頂点が存在して、以外の個の頂点の右隣にが許されないにも関わらず、次にを選ばなかったパターン

前者の方は、残りが3頂点(の場合は最初から)になった時点で、まだ選ばれていない頂点を辞書順に全通り試せば良いです。見つかった時点で答えを出力します。このパターンは、が以上の場合、必ず1通りは問題の条件に合うものが作成できるので、のパターンだけ答えがになる可能性があります。
後者については、入次数をセグ木でもっておき、入次数の最大値が(残っている頂点数)-1になるかどうかで判定・その頂点の特定ができます。その場合にのみ、優先的に特定した頂点を選ぶ、という処理をいれてあげればよいです。
これら以外のパターンは、貪欲に小さい方から置ける頂点を探し、見つかった時点で置けばよいです。たかだか2回の探索で終わります。
あとは、この操作を繰り返し、答えを出力すればよいです。