yukicoder contest 340 C
No.1910 High Element on Grid
https://yukicoder.me/problems/no/1910
自分の失敗方針を頂点とみなし、大小関係を決めた2頂点間に有向辺を張ることを考えた。
を満たすように、かつループができないように有向辺を張ることができれば、
トポロジカルソートすることで全ての大小関係を満たす数値を振ることができて、解ける。
しかし、ループができないような張り方を思いつくことができず。
正解方針を満たすには、左上(
)を
にしさえすればよく、
残りの上辺と左辺(~
、
~
)は自由にできる。
つまり、例えばなら、縦一列(
~
)に対する条件である
を満たすことに全力投球できる。
そこで、以外(
~
)を特定の状態にしておいて、
だけ調整することで
を満たせないか考えてみる。
これは可能で、~
を昇順にしておけば、
の調整だけで「高い項」の個数を1~Hまで任意に実現できる。
横一列も同様に実現できるのでこれで解ける。
無理やり考察典型化
「構築問題で自由度が高いところを見つけたら、そこだけ調節して条件を満たせないか考えてみる」
今回、左上をにすること、更にそれにより上辺と左辺は自由な値を取れることまで気が付いていた。
それを生かすことができなかった。もう少し生かそうと考えていれば思いつけていたような気がする。
