https://twitter.com/kinaba のログ (twilog の方が便利です。)
| 問題Gの c＜original_shortest_path という制約の不等号が逆だと多項式時間で解けるものかどうか気になってるんだけど、どうなんだろ。「長さc未満の経路に乗り得る辺のみを残したグラフの最小カット」が自明な上限だけど、これより小さいことがある #icpcjp | |
| @hos_lyric 作例を簡単にするために多重辺も許すとして、「A→B に辺が3つ（長さ1,2,2）あって、B→C にも辺が3つ（長さ1,2,2）あって、AからCへの最短路を4にせよ」 だと、最適解は1を2カ所潰すですが、カットだと3本切ってしまいそうな気がして | |
| 長さ制限した場合の辺独立経路の最大数は確かNP困難なんだけど、長さ制限するとメンガーの定理は成り立たないらしいので、つまりこれは最小の辺除去数を求めるのがNP困難であることは必ずしも意味しない、という辺りまでは調べたような気がする（覚えてない | |
| 俺言語うんぬんのが沢山favられてる理由が割と本気でわからない。なんでだろう | |
| @kmaebashi 私の場合も近いと言えば近いかもしれません。Lispの本を偶然本屋で立ち読みして、「ああ文法ってこれでいいんだなるほど＆＆これなら俺でも構文解析(という単語は知りませんでしたが)できる！！」 と思ってその晩にインタプリタ作り始めたのが最初でした | |
| 少なくとも、字句解析のしかた→構文解析のしかた→評価器の作りかた、じゃなくて、逆順に説明するというのは面白そうだし必然的にモジュラリティが上がるので良いコードにもなりやすくなると思うけど、そういうテキストって何があるだろか。 |