titiaのノート: Educational Codeforces Round 80 (Rated for Div. 2)

2020年2月6日木曜日

　時間ギリギリでDまでの四完。なんか遠回りばかりしてしまった。順位はあまり良くなかったけど、妙な解法でもACできたことで満足感はあった。

A. Deadline

　繰り上げを無視して式を整理すると、

・$x+\frac{d}{x+1}\leqq n$

　のようになるので、コンテスト中は、左辺を微分してxの最大値を求め、その付近を探索しました。

　実際は、移項すれば二次式になるので平方完成でOK。この時点でちょっとおかしかった。

　実験（もしくは式変形）してみると、B=99…99　という形のときに条件が成り立つことが分かる。

　まず、"non-descending order", "non-ascending order"の意味が分からずタイムロス。いや、日本語では「広義単調増加」って言うから分からなかった気がしたけど、「単調非減少」も普通に使いますよね。これくらいの英語は読み取れないと……。

　その上で、コンテスト中は、A, Bの要素を左から決めていき、

・DP[i][j]=（Aの最後の値（つまり最大値）がi, Bの最後の値（つまり最小値）がjのときの場合の数）

　として、このDPをm回更新していきました。

　更新の際、新たなDP[i][j]は、前のDP[k][l]のk<=i, l>=jを満たす全ての要素を足したものになる（絵を描くと分かります）ので、累積和を使って更新することができます。

　……と、これは制約を見ると自然な解法に思えますが、もっと簡単に解けますね。

　A+reversed(B)を考えると、これが単調非減少であればOK。その場合の数は、重複組み合わせを用いて、Combi(n-1+m*2,m*2)と簡単に表せます。　

・最小値・最大値（や平均値・中央値）を考える問題は二分探索を使うと良いことが多い。

→今回は、判定の際にmが小さいことを利用できる。「答えがX以上にできるか」という判定問題を考えたとき、各行の数字はX以上か、X未満か、の二通りなので、判定に利用するbit列は$2^8$通りしかなくなる。それを全部試しても$2^{16}$通り。

　……なんだけど、コンテスト中は、後半の判定を別のやり方でしようとしていた。$2^8$通りの二乗回探索すると間に合わない気がして、各bit列に対して「それと or をとったときに全てのbitが1になるようなbit列」を列挙しておこう、と思った。

　これを前計算しておく方針なら悪くなかった思うんだけど、実際は、各列に対して素数を割り振り、「bitが立っている列に対応する素数の積」によりコード化。その値に対して約数を列挙し、（列に対応する全ての素数の積）/（約数の一つ）となる値が存在するかどうかで判定した。

　無駄に面倒なことをしていて（計算時間も遅くなっているはず）、よくこれでACできたなぁ、と今思うと感心する。

　今やったら自力ACできました。けんちょんさんのブログの解法（BITを使っている方）と同じ方法でした。

　シミュレーションを行うのは時間的に厳しいので、最小値、最大値がどこで変化するかを考えると、自分が選ばれていないときの位置変化は「±0か+1」なので、単調非減少。

　それをふまえると、各数字は変な位置変化はしないので、

・最初

・最後

・自分が選ばれたときの前後

　だけを考えれば良いと分かった。

　あとは、自分が選ばれたとき何番目の位置にいるかが分かればOK。これは、平衡二分探索木/C++のsetを使えばできそうな気もしたけど、私は持ってない。じゃあ、

・平衡二分探索木はしばしばBITで代用できる

　ので、できないか、と考えた。結局、

・各数字の位置を管理するリスト

を作り、

・BITで各位置までの出現個数を管理

して、選ばれた数字を一番最初（先頭の数字のさらに一つ手前）へ移動するよう更新していけば、BITにより選ばれた数字が何番目の位置かを調べることができた。