No.2518 Adjacent Larger
自力AC。全く条件が分からなかったが、ランダムテストを書いて実験して……を繰り返したらACできた。
与えられたAに対して、1が連続する部分を圧縮したものをBとしてたとき、
・B中に2が連続するところがあったらダメ。
・B中に、[2, 1, 2]もしくは[0, 1, 1]という部分があったらダメ。
でした。
公式解説を読むと、なるほど確かに、という感じ。
実際に元の数列を求めようとは考えたのだけど、2（や0）のところから考えれば良いとは思いつかなかった。
No.2519 Coins in Array
自力AC。f(x, y)は実験して予想した。
ただ、0になるときずっと(1, 2)をし続ければ良いというのは気付かなかった。f(奇数, 奇数)が偶数になり、f(偶数, 偶数)=0になるので、高々3ターンで0ができ、それを使って他のものを0にしていった。そのためやや面倒な実装になってしまった。
No.2520 L1 Explosion
自力ACだけど、タグを見たし、実装問題だからね。時間をかければ解ける。
ただ、最初座標変換せずとも解けるか（斜めにimos法をすれば）と勘違いしてしまった。（少なくとも単純な二次元の）imos法は長方形にしか使えないので、x'=x+y, y'=x-yのように座標変換しないと使えなかった。
実装してこのことに気付いたのはちょっと間抜けだった。
No.2521 Don't be Same
自力AC。
頭の中で色々試したら（1, 2）, (3, 4), (5, 6)のときだけ負けに思え、実装したらACできた。こういう問題は大体いつも実験しているので、実験せずに分かったのは嬉しい。
No.2522 Fall in love, Girls!
タグは見たけど自力AC。
bitDPというタグを見て制約をちゃんと見たら種類数が20というのがあったので、あとは実装問題でした。
ただ、後半に
「1, 2, .... , nと番号のついたn個の玉と1, 2, ... , kと番号のついたk個の箱があります。番号順に玉を取り出し、順番に箱につめていきます。ただし、まず1の箱をつかい、次に2の箱を使い、……と、箱も番号順に使います。一個も玉の入っていない箱があっても構いません。玉の詰め方は何通りでしょう？」
というような問題が現れ、kが小さいからDPで解いてしまった。これ、ただの二項係数ですね。気付かなかったのは恥ずかしい。
No.2523 Trick Flower
タグを見て自力AC。
SCCしてDPする問題。
そこまで分かれば実装するだけかと思ったら、トポロジカルソートの順番を逆順にしてしまいWAが出て、しばらくどこが間違っているか分からず困った。
SCCした後木DPをするのだから、SCCした後のグラフをちゃんとイメージしなくてはいけなかった。
No.2524 Stripes
解説AC。
二乗のDPの式を立てるのは簡単。それを形式的ベキ級数で解釈すると、分割統治してFFTを使いながら行列計算することにより高速化できる。
行列に多項式を入れて計算すると高速化できる、というのは初めて見たと思う。それぞれの解法を知っていれば何をしているか理解するのは難しくないが、自力で解くのは結構厳しい気もする。
0 件のコメント:
コメントを投稿