難易度5
JOIの難易度5を埋めました。→ AOJ/AtCoder-JOI
印象に残った問題を挙げます。だいたい解けなかったやつです。
Factorial
nを素因数分解してこれを使って上手くやればいいです。または、√nより大きい素因数を持つときの答えは明らかで、それ以外のときは普通に階乗を計算していってnで割り切れたところで終わればいいみたいです。
船旅
ベルマンフォードの精神を持つと、追加される辺の両端だけ調べれば良い気がします。
碁石ならべ
各マスについて、自分が属する区間の長さと区間の左端を持って、それを更新していきます。最後まで置いたら、復元する感じです。
連鎖
愚直に消滅判定しても間に合いました。最悪N2だけど、ほとんどの場合連鎖が続かないんだと思います。
1年生
dp[i][j]:=iまで使って作れるjの個数 としてiを増やしながら更新していけばいいです。
パスタ
dp[i][j][k]:=i日目にjを選んで、i-1日目にkを選んでいたときの場合の数 として各iに対して(j, k)を3×3通り考えて更新していけばいいです。最初の2日くらいはforの外で計算しました。
たのしいカードゲーム
Bの開始位置を決めて、Aの各要素に対してマッチさせていきます。または、dp[i][j]:=Aのi番目まで考慮して、Bのj番目で終わる共通列の長さの最大（Aiは必ずしも使わなくていいが、Bjは必ず使う） としてもいいです。dp[i][j]を計算するために、共通部分列は(i-1, j), (i, j-1), (i-1, j-1)の3つを使い、共通部分文字列は(i-1, j-1)の1つだけ使うことから推測されるように、この問題では2つ使います。
問題とは関係ないですが、AtCoderでは入力が変な感じになってるので気をつけたほうがいいです。C++ではcinでもscanfでも通りますが、rubyでn, m=gets.split.map(&:to_i)という受け取り方をするとREになります。AOJのほうでは大丈夫です。
JOI国のお散歩事情
明らかに衝突しそうなところ（→←となっているところ）だけ記録しといて、i番目の人についてたとえば右向きなら、衝突候補の中ではじめてAiより大きくなる座標とAi+Tとのminをとればいいです。衝突候補からの検索はlogNでできるので合計でQlogNで間に合います。two pointersでやるとlogが消えます。
