https://twitter.com/kinaba のログ (twilog の方が便利です。)
| RT @tatanaideyo: はてなブログに投稿しました Tournamentの最小道被覆問題 (Minimum Path Cover Problem) - tatanaideyoの備忘録Ⅱ https://t.co/G3f5VoNydF #はてなブログ | |
| RT @kinaba: トーナメントグラフのハミルトンパス割と多くのソートアルゴリズムそのまんまで得られるの http://t.co/0WbKXdKAqZ とかで知った http://t.co/aLATnkt83P 推移律仮定しないでもマージソート等が"隣同士の順序は合ってる"… | |
| RT @tmaehara: んん，これを信じると，なんも考えずソートを突っ込めばよかった……？ | |
| RT @tmaehara: 何も考えず comparator 書いて std::sort に放り込んだら通った．ヤベエ． https://t.co/AzRwPw4hzy | |
| これなんか面白い問題にならんかなーと思ってたんだけどトーナメントグラフ陽に書くと入力の時点で|V|^2だしうぬぬぬぬ…とか思ってたんだけど、そのまんまで出題しているところがあったのか | |
| たしか挿入ソートとかマージソートと違ってselection sortはLocallySortedの証明に推移律必要だった気がするのでクイックソートとかも多分そうでstd::sortのよくある実装だと一般には怪しいかと思ったんだけど | |
| @Mi_Sawa おおーDCJのプロ | |
| @eomole どうかしましたか（どうもしていない場合は何か面白論文を教えて下さい） | |
| よく知ってるアルゴリズムの部分的な正当性の形式証明をして、あとは機械的にその時使った仮定を全列挙、その仮定だけは何とか満たす割と極端な構造を自動的に構成してやる、とかで面白問題の半自動生成できないもんかな。（トナメグラフのハミルトンパスの他にもこういう構図になってる例ないかな） |