Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

いかにして解くか(競プロ編)

パズルのような問題を解くということには考え方の法則がある。

いかにして問題をとくか

いかにして問題をとくか

競技プログラミングの勉強をしていて、こういう方針が立っていれば解けたというタイミングがある。そのうち、エッセンスだけを抽出していく。

  • 保存量に着目する(和とか)
  • 問題やクエリを分割する
    • 分割統治法
  • 問題を前、真ん中、後ろのみっつに分ける
    • 真ん中を捨てる
    • 真ん中が問題の要求する条件を満たす
    • 分割する点を決めると前後が貪欲に決まる。二分探索出来る etc.
  • 隣合う要素に着目する
  • 少しずらしてみて、同値なものに着目する
    • 少しずらしたものは実は同じ結果になるから総数に貢献しない
    • 頭が成り立つなら少しずらしたものも成り立つから芋づる式にいくつか成り立つ
  • どういう条件が数え上げの総数について1貢献するか考える
  • 最終図に至る分岐を考える
    • DPでは特にありがち。ある瞬間に至る際の最終手について場合分けを行う
  • 最終図から逆順に辿る
  • もっとも厳しい場合について考える
  • 問題の要求する条件が具体的にどういう場合なのか想像する
  • 問題の性質を利用してXとYを独立に考える
    • マンハッタン距離
    • 組み合わせ
  • 何かを固定して考える
    • iを固定する
    • 最終図に必ずあるであろう区間を仮定して固定する。二分探索
  • クエリを先読みする
    • ソートしたり
  • グラフの問題に帰着する
    • 二部マッチング
    • 最大流