Bまで二完。Cが解けなかったのはまずい。
No.1973 Divisor Sequence
解説AC。
素因数ごとにDPし、累積和による高速化をすれば良い。
コンテスト中は、素因数ごとに分けずに同じDPの遷移が成立すると思い込み、答えが合わず悩んでしまった。
たとえば、36の約数は、
・1 2 3 4 6 9 12 18 36
であり、12*3=36なので、12の次の数は3以下全て……となりそうだが、12*2=24は36の約数ではない！
なのでこれは成り立たず、素因数ごとに分けて考えなくてはいけなかった。
No.1974 2x2 Flipper
解説AC。
市松模様に塗ってどうこうするのかな、と考えていたが間違い。もっとシンプルに偶奇に着目すれば良かった。
2*2マスをflipしても各行・列における黒マス（白マスも）の個数の偶奇は変わらない。十分正のチェックは、端の行・列に押し込めばできる。
No.1975 Zigzag Sequence
自力AC。（C、Dより簡単かも？）
A[i]がジグザグの中央になるときの答えを足し合わせれば良い。（小さい場合と大きい場合、両方を足す）
左側がA[j]（j<i, A[j]<A[i]）となるときの部分列を考える。これは、jよりさらに左側全ては、選んでも選ばなくても良い。なので、BITを使って、pow(2, i)をA[i]に足していけば処理できる。これを左右からやる。
0 件のコメント:
コメントを投稿