ABCとE1をAC。そこそこ速かったので順位はまあまあだったが、逆に言えば、時間があったのにDやE2が解けていないということ。
D. Genius
コンテスト中の考察でほぼ正しく、後は詰めるだけ、というところまで行っていたと思う。
……が、実際にコードにするのには非常に長い時間がかかってしまった。こういう問題を解くと、大体の方針は立っても、そこから実際のコードに落とすのは容易でないことを実感する。
（問題文の読解が結構面倒なので、ここまで考察するのも結構大変だけど）i→j、と進み、jが今まで行ったことのない、これまでで最大の数字のとき、この後進めるのは、
・iより前
・jより後ろ
のいずれか、である。
なので、DP[i][j]で、「一つ前がiで現在jにいるときのスコアの最大値」とすれば、メモリ二乗、時間三乗のDPで解ける。
メモリ制限もあるので、これを一次元にまとめたい。（そうすれば時間も二次元に落ちそう）
このとき、jを主役にして、
・DP[j]で「初めてjに到達して、直前にいたのがiのときの最大スコア」とするのでは遷移が上手く書けない。（私が書けなかっただけで、ちゃんとやれば多分書けるはず……）
そうではなく、
・DP[i]で、「最大でjまで到達したことがあるものの中で、現在iにいるものの最大スコア」とすると、一次元のDPテーブルを使い回せ、遷移式も簡単に書ける。
時間がかかっていたのは、前者の方針に固執してしまったせいもある。けど、その辺は、コードを書きながら遷移式を考えるので良い気がするんだけど。もっと先に考察すべきだったのかなぁ。
0 件のコメント:
コメントを投稿