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

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• アルゴリズムの構築法 へ行く。
  • 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)に戻る。
• を走らせているのがマズそう

気合 †

• AtCoder? 700点とかで考察が入り組んで更にバグると、方針が合っているかの自信をなくしてしまう。やり切る気力大事。

数学的帰納法的思考 †

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

操作前後の不変量 †

• 操作が何かを保存している場合、それが必要条件や高速になっているため重要な考察となっているケースが多い
  • ARC 94 mod 3であう
  • Code Festival 2016 Tournament 2A mod 2であう

必要条件と十分条件 †

• 全くわからないタイプの問題には、しばしば、必要条件を列挙していたら実は必要十分条件だった、というタイプがある
  • 必要条件が足りない場合は、漏れているケースを実験的に探索する必要がある。
  • 必要条件や十分を列挙し、ダメなケースを実験的に探すと見えてくるパターンがある
• 例
  • 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 のときも同じです。