https://twitter.com/kinaba のログ (twilog の方が便利です。)
| ICPCお疲れ様でした | |
| RT @icpc2016tsukuba: 本日の国内予選で出題された全ての問題について、審判長の近山隆先生による「講評(速報版）」が出ています。問題の狙いや解答の方針などがかかれていますので、是非ご覧ください。https://t.co/xWjOJVhnyg | |
| 問題DはDP二段構えの人が講評も含めて多かったみたいだけど、区間ごとに最大何個落とせるか求める区間DPすると、全消しできるかの情報も自動的に含まれる（区間長と個数が==なら全消し）ので一発で終わって楽だと思った。 | |
| RT @tmaehara: ICPCお疲れさまでした。皆様の参加記をとても楽しみにしていますので、どうぞよろしくお願いします。 | |
| RT @yosupot: 文脈自由文法の構築は区間DP(CYK法)で出来るけど、これは逆で、区間DPで構文木を作れるようなものを考えたらそれが文脈自由文法なんじゃないかという理解が降ってきた(文脈”自由”文法の自由は区間DPの分割統治に対応する) | |
| https://t.co/IhQFS9MIPC これは本当それで、なので区間DPで解ける問題はそれに対応する文脈自由文法を考えることができて、文法の形によってはCYKより高速な構文解析ができる特殊な形なので、CYKの代わりにそれでやればよい的な発想でDPの計算量落とせたりする | |
| 一見O(n^3)の区間DPに見えるが実はSLR(0)文法なので線形で解けるという問題と、一見O(n^3)の区間DPに見えるが実はGLR法で構文解析したときのスタックのパターンすごい少ないことが解析できるのでO(n log n)みたいな問題は作った | |
| RT @sugim48: 英国民投票のニュースを聞いてすぐに B 問題を作り上げる ICPC 実行委員会、完全にプロ | |
| @kmizu 元の話の流れを損なわない注意はかなり慎重に払って訳されてたので、その点に関しての心配は無用と思います。私なんぞは「意味分からないのでもうこの文全部消しましょう」みたいな適当なコメント投げちゃってたのですが、粘り強く原文を活かす工夫を探っておられ偉いなあと思ってました |