コンテストへのリンク
A. Yet Another Tetris Problem
「縦に二個」のブロックしかおけないので、mod 2で全要素が揃っていることが条件。
B. Yet Another Palindrome Problem
四文字以上の回文があれば、その部分列で三文字のものを得られるので、三文字の回文を見つければ良い。
三文字の回文は、「A B A」という形をしている（A=Bでも良い）ので、隣同士でない位置に、同じ数字があるか判定すればOK。
Hackされたのは、実装方法がおかしくて（隣同士に文字があったとき消去するような実装をしていた）、同じ文字が三文字続いたときにダメという判定を返していたためでした。
C. Frog Jumps
連続する「L」の個数の最大値+1。DP まとめコンテストのせいで、Frogという単語をみるとDPかと身構えてしまうけど、この問題ではDPは不要でした。
D. Pair of Topics
式変形すると、$a_i-b_i>a_j-b_j$となるので、$a_i-b_i$をソートしてbisectを使って求める。
E. Sleeping Schedule
結構読解に苦労した覚えがある。
DP[h]を、時刻hに寝たときの「良い睡眠回数」の最大値とし、これを更新していく。
F. Maximum White Subtree
全方位木DP（rerooting）を使う問題。このときも、かなり時間がかかってしまった……。
いまだに全方位木DPには慣れないし、ライブラリ化もできていないけど、どうしようかね。色々な記事をパラパラと読んではいるのだけど、今一つピンと来ていないんだよね。
0 件のコメント:
コメントを投稿