https://twitter.com/kinaba のログ (twilog の方が便利です。)
| @eomole くわしく | |
| １日１問おもしろむずかしい問題を思いつくまで寝ない運動を日課にしよう（さっき一個考えたのでノルマを果たした気分になっており明日以降の自分に対し多大な迷惑） | |
| @eomole ふむー。なるほどです。易化という印象はわかる気がするのだけど、実際に解いたチーム数見ると6～2完までは割と例年と大差ない範囲な感じもするんですよね。おもしろいところです | |
| 日曜日の準備している時間がなさそうなので3ページくらいで終わるスライドとアドリブになりそうでございます | |
| Fは一文字へ落とす部分のDPはボトルネックではないので、GLRなりアーリー法なりなんでもいいので構文解析アルゴリズムを全部分文字列全開始記号に対して計n^3ぶん回すので国内予選なら待てる時間で終わりそう。どちらもn回で十分なように微改造もできます。区間DP（CYK）が楽だけども | |
| 近くにきたので松戸ジュンク堂によってみんとす | |
| RT @rng_58: そういえば、コンテストに使えないレベルの典型 DP が大量にたまっているのですが、夏休みに 5 時間 26 問くらいの典型 DP コンテストやったら参加する人いますか | |
| やりたい https://t.co/qfrfW88qcx | |
| 問題文を数学的に書いたらでてくる漸化式をそのままメモ化実装するだけ(例:fib) ≪≪≪ 問題のパラメタを1ずつ減らした部分問題の解から解が計算できる(例:LCS) ＜ 問題のパラメタを1から全部まで減らした部分問題の解すべて見ると解が計算できる(例:LISのO(n^2)解法) | |
| ＜ 添字の大小とリストのprefix関係以外の順序の上での部分問題を考える (例:DAG上のDP, 約数関係上のDP, 区間DP) ＜ パラメタ全履歴減らす必要はなくて直近k個だけ覚えておけばよい等利用して効率化(例:W×Hの何故か一方だけ異様に小さい問題)["典型"のボーダー] | |
| ＜ 多段DP（DP表を使ってもう一発DP、DPの1ステップがDP）≪≪ 問題で求められてるより余分な情報を求めると速い部分問題関係がでる（途中のΣを計算してオーダ落とすヤツとか）≪ http://codeforces.com/blog/entry/8219 こういう凸性とか単調性とか利用したカコイイてくにっく | |
| みたいなイメージ | |
| （同じです） |