po

難易度5

f:id:poyopoyoyon:20170824182709p:plain

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でも通りますが、rubyn, m=gets.split.map(&:to_i)という受け取り方をするとREになります。AOJのほうでは大丈夫です。

JOI国のお散歩事情

明らかに衝突しそうなところ(→←となっているところ)だけ記録しといて、i番目の人についてたとえば右向きなら、衝突候補の中ではじめてAiより大きくなる座標とAi+Tとのminをとればいいです。衝突候補からの検索はlogNでできるので合計でQlogNで間に合います。two pointersでやるとlogが消えます。