はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおける細かな話題まとめ

最大長方形

Meldable Heap

二部グラフ判定(二部グラフを頂点倍化Union-Findで判定する話も)

立方体の和集合の体積の総和を求める

全通りの組合せを考えて答える(特有のパターンがある?)

bitsetによる64倍高速化

辞書順最小を最大化する

回文

N頂点N辺のグラフ

一端を固定して、もう片方を伸ばしていくと状態変化がそんなに無いので分割統治っぽくでき、高速に処理できる

自動ベクトル化

入力がランダムの場合のテク

約数を使って再帰していく問題

無向グラフの辺最小被覆パス

  • 辺を全て被覆できるパスの数の最小値
  • ARC088 Christmas Tree
  • 「奇数次数の頂点数/2」が最小値(奇数次数がパスの端点となれば偶奇が合うため)

特殊なソートで最適解を得るテク

  • 特殊な比較関数を使ったソートを用いることで最適解(のための順番)が得られるテク
  • 隣接する二項間について、スワップすべきかを考えると比較関数を作ることができる
  • AC 天使とふすま 解説

小ネタ、小テク

  • 特殊な座圧によるクエリ対応
  • modを取ると数は半分以下になる
  • 最大値、最小値の区間をstackで持ちながら[0,i]の範囲での最適解を得ていくテクがある
  • 特殊な制約により計算量が抑えられる系
    • 「K≦10^5でs1+s2+...+sK≦10^5」で任意のペアについてクエリを処理するとき、サイズが小さい方で全探索するようにクエリを実行するとメモ化などで間に合う これ
    • どんなに意地悪してもTLEさせられないという面白いやつ
  • クエリの要素数によって場合分けを行うことでならしで間に合わせることができたりする これ
  • 条件を少しずつ変えて全探索は差分を計算することで全てを計算し直さずに全探索できる これ
  • より制約の緩い問題を解くことに帰着する
    • 「f(x) := コストがxの時の組合せ」を解くとするときに
    • 「g(x) := コストがx以下の時の組合せ」を解くのが優しい場合は、それを解いてf(x) = g(x) - g(x-1)を答えとする
    • この問題
  • 数列の中に順列が含まれていて、順列がどんな形でも関係ない場合に、特定の順列のパターンは全てのパターン÷順列のパターンで求められる
    • この問題
    • この問題では順列が含まれるのではなく、複数個同じ数が含まれない数列を含む
    • 特定の数列を含む数え上げは難しいので、同じ数が含まれない長さMの数列を含む数列を数え上げて、同じ数が含まれない長さMの数列のパターンで割って求めている
  • 「ある盤面が列または行のスワップ操作だけで全部白にできますか?」→全ての2x2のsubrectangleについて黒マスの個数が偶数