Dは解けるべきだったし、今見るとFも難しくないですね。
コンテストへのリンク
No.987 N×Mマス計算（基本）
これは計算するだけ。
No.988 N×Mマス計算（総和）
足し算の場合は、縦の和*（横の個数）+横の和*（縦の個数）
掛け算の場合は、縦の和*横の和
No.989 N×Mマス計算（K以上）
各列に対して、ソートして二分探索
No.990 N×Mマス計算（Kの倍数）
一時間半かけてもこの問題を解けなかったようなのですが……反省。
足し算の場合、mod Kで分類すればOK。
本番では、「余りがqの個数と余りがK-qの個数の積」で計算していたので、余りが0同士の場合にWAを出していました。今見るとマヌケですね。
掛け算の場合。
約数を調べるのは良いのだけど、「Kの約数」だけを調べれば良いのを忘れていた。
たとえば、K＝2*(奇数)の場合に、A=2*3, 4*3, 8*3...みたいなのを全部別に考えてしまうコードを書いてしまいTLE。
こっちはちょっと気付きにくいけど、時間はあったんだし、ACしたかった。
No.992 最長増加部分列の数え上げ
コンテスト中は読まなかったと思うけど、LISについてちゃんと理解できているなら解けなくてはいけない問題でした。
解説を読んだ後にACしたけど、解説とは若干違う方法で解きました。
公式解説はLISの長さを主役に、ここの解説では、A_iの値を主役にしています。
後者と似た方針で、iの順番を変えなくても解くことができます。
まず、座標圧縮（今回は最小の数を1にしています）して、A_iの値を2*N^5以下にした後、DP[0]=(0, 1), DP[A_i]=(-1, 0)（初期化値は小さい値なら何でも良い）というDPテーブルを作ります。
DP[A_i]は、最後の値がA_iになるような、LISの長さと個数です。
その上で、
i番目の要素がA_iのとき、DP[A_i][0]が「DP[0][0]～DP[A_{i-1}][0]の最大値」より大きければ、既にA_iが出現しており、かつ、DP[A_i]の長さは更新されないので、長さはそのまま、個数を「DP[0]～DP[A_{i-1}]で第一要素が最大値を取っているようなものの、第二要素の和」だけ増やします。
そうでなければ、DP[A_i]の長さはそれまでの最大値の和+1で、個数はそれらの個数です。
文章で書くと分かりにくいですが、これはSegment treeで実装できます。（ちゃんと考えていないけれど、多分BITでもできるはず）
0 件のコメント:
コメントを投稿