主食は米

主に競プロ備忘録

KEYENCE Programming Contest 2019 D - Double Landscape

反省

解法は解説見ればわかるのでなんで反省点のみ.

  • {a}, {b} をsortして右下から入れていこうとしていた

-> 明らかに煩雑. 典型要素として perm を考えるときには挿入/数字が入る場所から決めていく
-> 上の数字から入れていくのを

  • a_i = b_j = x なる i, j があるならば (i, j) は一意に定まる

-> これは実験でわかった.

  • 上から入れていく

-> これは考察できていたけどふわっとしていた.
x が入ることができるマスは y (<x) も入ることができる単調性があることを考えるとこれしかなさそう
ただし, y が一意に定まる a_i = b_j = y なる i, jが存在しないケースに限る(これのせいで混乱した)

まとめ

順列は数字の入る場所から考えていく
ただし単調性があるような順番に入れていくのが良い.
今回のような入ることのできる場所を掛けていくような場合には,
入れる候補が今まで入れた場所を含んでいるという性質が重要.