ABC427 B - Sum of Digits Sequence

positional_notation ってスニペットがパッと出てこなかった

ABC427 C - Bipartize

• 2部グラフ
  • 互いに隣接しない頂点からなる集合を独立集合といい、頂点集合を n 個の独立集合に分割可能なグラフのことを n 部グラフ (n-partite graph) という。 (2部グラフ - Wikipedia)
    • （独立集合は今回のF問題でも出てくる）

ABC427 D - The Simple Game

ゲームDPはどのように実装するのが実装しやすいのだろうか（模索してみてもいいかも）

ABC427 E - Wind Cleaning

• コンテスト中の解法

  • 高橋くんを外に出してからちょっと動かす解法を考えた。

    これだと、周囲が囲まれていると不可能。しかし、実際には可能。

    例えば以下のケースではうまくいかない

    ####
    #.T#
    ####
    

• グリッドエディタで、矩形選択して切り取りやコピーができると嬉しい

ABC427 F - Not Adjacent

コンテスト中にやったこと

• まずは全列挙可能か検討した
• 全列挙で何通りかについて、最初はフィボナッチ数列なことに気づかなかった。実験コードを書いて、実行して値を見てフィボナッチ数列になっていることに気づいた
• 全列挙パートが難しかった
  • itertools が使えない（使うと遅い）タイプの全探索は苦手
    • ABC424 D - 2x2 Erasing 2
    • ABC382 D - Keep Distance （工夫すれば itertools も使える）
    • (もう一問くらい合った気がする)
  • DFS を書こうとしたが、うまく書けず。数え上げの DP を列挙に転用できることに気づいて DP 風に実装した

知見

• not adjacent な部分列の個数はフィボナッチ数になる
• $N\leq 60$ とかでも指数時間のオーダーになることもある
  • 今回の計算量は $O(N \varphi^{N/2})$
• 数え上げの DP はそのまま列挙 DP に転用できる
• 和の分布を求める方法
  • 値の範囲が小さい場合は、 FFT を使った畳み込みでよい
  • 値の範囲が大きく、和の分布の特定の値のカウントだけを知りたい場合は、HashMap や二分探索をするとよい