アルゴリズムの構築法 のバックアップ(No.2)

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• アルゴリズムの構築法 へ行く。
  • 1 (2018-12-24 (月) 23:40:17)
  • 2 (2018-12-24 (月) 23:42:55)
  • 3 (2018-12-25 (火) 12:43:04)
  • 4 (2019-01-01 (火) 13:50:14)
  • 5 (2019-01-04 (金) 22:06:22)
  • 6 (2019-01-05 (土) 14:31:00)
  • 7 (2019-01-06 (日) 01:29:17)

アルゴリズム

概要 †

• アルゴリズムを構築するアルゴリズムとして
  1. ランダムなアルゴリズムを考える
  2. 矛盾しないかを実験する。矛盾しなければ終了する。
  3. (1)に戻る。
• を走らせているのがマズそう

数学的帰納法的思考 †

• プログラミングは全て数学的帰納法
• [0, i)の転倒数がわかってるとするじゃん？からスタートすると一瞬で正しいアルゴリズムを演繹できる

必要条件と十分条件 †

• 全くわからないタイプの問題には、しばしば、必要条件を列挙していたら実は必要十分条件だった、というタイプがある
  • 必要条件が足りない場合は、漏れているケースを実験的に探索する必要がある。
  • 必要条件や十分を列挙し、ダメなケースを実験的に探すと見えてくるパターンがある
• 例
  • https://atcoder.jp/contests/arc094/tasks/arc094_d 操作がmod 3を変えないところまではわかる。f(s, t) = sからtに行ける、という関数には、もう少し条件が必要で、これを実験的に構成するとfがわかる。このfを数え上げ化することができるのでOK

状態の追加 †

• DPが思いつかなかったのは、これじゃ無理だなーとか言いながら、「iで操作する回数」を表す状態を定義しなかったから。 https://atcoder.jp/contests/caddi2018/tasks/caddi2018_c

証明 †

証明の練習問題 †

• 証明の訓練をするしか無い
• Topcoder SRM 697 D1E
  • &ref(): File not found: "IMG_0596.JPG" at page "アルゴリズムの構築法";
  • 全てのf_iが真となるようなa_iは存在するか
  • 1<=b_i<=10
  • これに対して、http://hamayanhamayan.hatenablog.jp/entry/2016/08/19/112400 みたいな、謎貪欲解がある(chokudaiさん、kmjpさん解法)。これが正しく動くことを示せ。
• ARC 53C
  • 上がって下がってする奴
  • あの貪欲の構成は面白かった気がする
• AGC 03B

• AGC29 B
  • 辺eをマッチングに使わないのならば、辺eを取ることでマッチング数を1あげることができる
  • 次数>1を使うとすると、次数>1を使う他のマッチングe=(次数>1, v)があるが、マッチングとして使えなくなる朝展が次数>1, 次数=1, vの三点となってしまい、真に悪くなる
  • 任意の頂点uについて、u-v とマッチするよりも良いマッチングの仕方があるとしたら、 a-u v-b みたいになってるはずで、対偶？を考えると、uがどれともマッチしない場合よりも何かとマッチしたほうが良い。
    • u-v とマッチするよりも良いマッチングの仕方Xがあるとします。Xにおいてuもvも使わないなら、u-v使ったほうがよいです。Xにおいて u使わない & v-b よりも u-v, bフリー のほうが良いです。Xにおいて v使わない & a-u のときも同じです。