Eまで五完で終了。Kotlin Heroes以外ではほとんど書いてはいないけど、Kotlinはそこそこ書けるつもり。なのに、前半の問題で解くスピードがかなり遅いのは、書き慣れていないということなのかなぁ。
このコンテストで50位以内に入ることは目標の一つなのだけど、今回は掠りもしなかった。
F. Kotlinforces
制約が本質の問題。
$t_i$が1か2ということに気付かないと始まらないが、コンテスト中はそこまでに結構時間がかかってしまった。
$t_i$が1のやつは端から詰めれば良いので、$t_i$が2のやつについて考える。
$t_i$が2のやつは、
・偶数番目の端から詰める
・奇数番目の端から詰める
の二通り考えなくてはいけない。どちらかが最適となる。
これは、二次元DPでDP[i][j]で、偶数番目が残りi個、奇数番目は残りj個、とやればできるが、これだとTLE。（コンテスト中、ここまで考えた）
だが、よく考えると高速化できる。
それまで何文字使ったかは分かるので、偶数番目が残りi個のとき、奇数番目が何個使ったかは、「奇数番目の個数 - 偶数番目に今まで使った個数」で求めることができるのだ。
これで一次元のDPになり、計算量は二乗になる。
そして、DPした後、DPの復元を行うことで答えが求められる。
DPの復元パートもあるし、そこそこ実装が面倒で、コンテスト後ACするまでには結構時間がかかってしまったけど、もっと楽に書く方法はあるんだろうか。
0 件のコメント:
コメントを投稿