ARC056/

README

ARC056 過去問感想

Last Change: 2020-04-11 20:28:36.

A問題（@2020-02-03）

制約的に難しくない？と思ったけど、よく見たら単純な算数。

なんとなくこどふぉのdiv2A問題っぽい雰囲気。

B問題（@2020-04-11）

復習が必要な問題。

誤った解法に陥ってしまった。

当初考えたものは「注目中のノードIDよりも小さいノードIDにしか移動できない、なぜならそのような移動を考えると、すでに注目中のノードは埋まっているはずだから」 というもの。 しかし、少し考えれば id=3 に向かうに当たって 5 -> 6 -> 3 のような経路は全く問題ないことがわかる。 つまり、自分が考えた条件は厳しすぎる、ということになる。

正しくは「ノード x に向かうときは、 x より大きいIDを持つノードのみからなるパスであればOK」ということになる。

Union Findを使った解法

BFSとUFをミックスしたようなやり方ではどうしてもWAが取れなかった。

代わりに、ノード番号の大きい順に、エッジ同士を連結させてよいかを判定させながら考える方法だと通った。 何が違うんだろう。。？

とにかくこの問題の教訓としては、 最短路や最長路などが問われるのではなく、単に到達可能性を問われた場合は、連結性に着目しUnion Findを考えるなどすべき。

ハマりにハマったミス

以下のようなコードを書いてしまい、ハマりにハマってしまった。

		if uf.Same(s, nextID) && nextID > i {
			uf.Unite(nextID, i)
			answers = append(answers, i)
			break
		}

このようなコードだと、注目中のノード i しか併合されなくなるが、 i よりも大きいIDのノードであれば i とつないでよく、結果的にそれらの小グループも一緒に s に併合してやる必要がある。

Union Findはグループ同士の併合を冪等的に行えるというのが強みであり、そこをちゃんと理解しきれていなかったように思える。 今後もやらかしそうなミスだったので、注意したい。

ダイクストラ法に似た解法

解説スライドでも説明されているもの。正直良くわからない。

mmxsrupさんのブログが一番わかり易いかも。。？

公式解説によると、ダイクストラ風でやるみたい。 いつもは距離の最小値を入れているが、今回は、その頂点に到達するために、通る頂点の最小値をいれ、最小値の最大が求まるようにすればいいみたい。 思いつかない。

• おそらく、そのノードのDP値がスタートのノード番号より小さく、かつ i-1 以上であればOKと判定できるのだと思う（違うかも）。
• とはいえ「大きいところから決めていく」という部分は変わらないっぽい。

やってみた

• DPで 「各ノードについて「そこに到達するまでに経由するノードの最小ID」を最大化したパスの最小ID」を計算する。
• 答えは dp[i] == i を満たすものを出力すれば良いことになる。

ダイクストラは最小化するように動き、今回は最大化を目指すこととなるため、基本的には不等号が逆転するようになる。 ただ、直感的ではないので更新の部分はかなり理解しづらいことをする必要がある。