リストの形で埋め込んでください。Nullのところは要素数を減らして対応します。解いたCTFの古典暗号でない問題で、面白さを感じた。面白さを感じて解説を書いていたら長文になってしまった。rubyを読むのは辛かったが、解くのにそう必要な知識も多くなく「CTFの暗号問題はクソなぞなぞや謎知識を要求する問題の山」だと思っていたCTF初心者の私には良い影響を与えてくれたと思う。現代暗号面白そうなのでがんばろう。感想ひと月ほど準備期間があったが、論文やらCODEFESTIVALやらDDCCやらでなかなか準備できていなかった。役に立てる気がしていなかったが案の定役に立ってなかった。Cryptは数弱にはつらい問題だったが、どうにかなりそうなのがCryptしかなかったのでCryptに取り組んでいた。読むrubyはつらかった。オイラーフェルマーの小定理さえ知ってれば小中学生でも解けるCrypt200が解けなかったのは恥としか言えない。プログラミングはじめにAOJ2335:10歳の動的計画法を解いたが、非想定解で解説記事が書かれてなかったので書くことにした。別解の中で使ってるテクニックは他でも使おうと思えば使える気がします。問題概要2次元平面上で、次のルールで(0,0)から(N,M)まで移動するときの経路数を答えよ。想定解はJAGのページにある。この記事ではDPで解く別解について解説する。x軸方向の移動とy軸方向の移動は分けて考えることができる。x軸上の移動を考える。k回の負方向への移動を含む移動によってx=pにたどり着いたとする。このときの経路数をf(k,p)と表記する。この経路数はy軸上の移動でも同じである。x軸負方向にk回移動したのちに(N,M)にたどり着いたとしよう。答えは次の式で求まることになる。二項係数の計算はO(N+M+K)ぐらいの前計算からO(1)で求まるため、前計算の結果と、f(k,N)とf(k,M)がk<=Kについて分かっていればO(K)で答えが求まることが分かった。f(k,N)とf(k,M)をk<=Kについて求める方法を考えればよい。(N+M+K))のDPをすることでf(k,N)とf(k,M)は求まるのだが、これでは時間がかかりすぎてしまう。あっても、行うDPは別解とそう変わらないのでこのDPについても説明しておく。i回の移動を行い、そのうちk回が負方向への移動であるような経路数。して、更新は次の式で行うこのようにしてDPを行えば、としてf(k,M)とf(k,N)を求めることができる。K回以上正方向に移動を行っていれば、その後どのような順番で移動しようともルールを満たしながら移動することができる。2*K回以上の移動を行った後であれば、どのタイミングで負方向への移動を行っても構わないことになる。2*K回の移動が終わるまではDPで経路数をもとめ、2*K回以上の移動を行う経路については2*K回の移動が終わった時点のDPの結果をもとに計算すればよい。和をとる範囲について補足する。2*Kステップにk'回の負方向への移動が含まれていた場合、正方向への移動は2*K-k'回である。成立しなければならない。よって、和はk'=max(0,2K-i+k)からとる。計算量は、DPを途中まで行うのにO(K^2)、DPの結果から、dp(N,k)とdp(M,k)を計算しf(k,N)とf(k,M)を求めるのにO(K)これが0<=k<=Kについて計算されるからO(K^2)となり、f(k,N)とf(k,M)を計算する処理全体でO(K^2)となる。問題全体を通した計算量は、O(N+M+K^2)である。今回は非想定解だったけども、途中までDPをしてあとは計算頑張るという方針はどこかで使えそうだ。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。