https://twitter.com/kinaba のログ (twilog の方が便利です。)
| @kis 山手線から中央線快速に行こうと階段を降りる→終電終わってる→各停に乗ろう→山手線ホームの向かい側→なんかホームで待ってたら電車来た！という流れっぽい | |
| @kis 実際応用的に有用な気はしますよね。パーソナライズしてなんかよくわからないけど赤っぽい方に行けば大丈夫、みたいな情報をエンコードできたら。都心の交通網の規模ではどのくらいの分解能の情報量を埋め込めるか？とか情報科学的に面白そう | |
| 交通ネットワークはグラフ構造だが終電に関してのみある程度の仮定のもとtreeやdagを成すということを巧みに活用した競プロの問題作れたら面白そう | |
| @finalfusion 代々木は紀伊国屋新宿南店に行くのに新宿で降りるより意外と近かったりするという用途の専用駅という認識ですのでその発想はありませんでした！ | |
| UTPC13のL、C++で適当に書いた解が0.3秒でJavaで適当に書いた解が経路が存在する場合で0.4秒存在しない場合で1.2秒、C++で少し真面目に書いた「通したくない」解が、経路がある場合で4.5秒ない場合で13秒、という状態でTLE2秒で出して突破されて悔しい思いをした | |
| 速くしようと思えばとりあえず書いたオーダだけあってるアルゴリズムから10倍くらい速くすることはいつでも出来るんで、本気で実行時間だけで区別するとか無理な気がする（区別可能な問題だけに絞るのは出題範囲が狭くなりすぎると思う）ので「定数倍さえ頑張れば合ってる」が明示されるべきで (続 | |
| 続) つまり競プロの問題は想定解法のオーダはこれこれである（ただし無論他のオーダの解法であっても所定の入力を制限時間以内に解けるのであれば全く正解として問題はない）という形でオーダを陽に書く形にすれば良いように思っています。入力サイズとか書くのは要するにそういうことなのだし。 | |
| UTPCの問題D http://www.kmonos.net/wlog/sub/utpc13-D.pdf と問題L http://www.kmonos.net/wlog/sub/utpc13-L.pdf の解説スライドうｐした | |
| CFL Reachability、基本的にWarfhall-Floyd×CYK法でO(N^3G^3)終わり、みたいにさらっと流されるイメージがある（偏見かもしれない）けど埋める順ちゃんと考える必要があるし最短路版にすればそれが強調されて面白くなった気がする、みたいな出題意図 | |
| RT @simezi_tan: さあ今から嘘解法UTPCがはじまります！！全問焼きなましで解く！！！！！ | |
| そういえばなんで想定解で集合をビット演算にエンコードするといった下らない作業がが要求されてるんだset<int>で通せよこの野郎、といったことは長らく思っていた | |
| UTPCのD問題の感想みてると、「証明できてないと通せない貪欲問題」作りたい野望の実践的近似としての「意外と細かい注意が必要で多くの人が実装ミスで1WAくらい食らうが、そこで証明が済んでない人は方針ミスか実装ミスか確信が持てず諦めたり証明したりしてしまう問題」は行ける気がしてきた | |
| 続) https://t.co/5xjQprii7N とか http://snuke.hatenablog.com/entry/2014/03/03/025412 とか見てそういうことを考えてたのですがしかしそういうWAはコンテスタントの精神を削るので平和さに欠けるという問題がある |