No.3476 {2^n-1}-gon
円の中心を含まないものを引く。
円の中心を含まないものは、最も左の点を固定し、そこから半周以内にM個全てが収まっているようなもの。
全体の個数も、引くものも二項係数で求められる。
これ、概ね最初に考えた解法だったのだが、なんでNは2ベキ-1なんだろう？ とか、引く数はこれで良いのだろうか？ などと考えてしまい混乱。もっと落ち着いて自然に考えていれば解けたはず。
No.3474 Concat Decimal
自力AC。これは普通に解けた。
全ての(i, j)でなく、i<jなるペアのみなのがちょっと引っ掛けっぽいですね。
No.3473 AtCoder < CMS
解法ツイートを見てAC。自力では分からなかった。
2^M-1を含む場合を考えると、各bitごとに、0/1を割り振るもののうち、全て0を除いた場合の数と一致する。（ここが分からなかった！）
あとは、2^M-1を何個含むか考えれば良い。
式変形をすると二項定理が使える形になるので、それで計算すれば解ける。
難しいが、解けないのはダメ。
No.3477 Yet Another LIS Triangle
自力AC。
これは簡単でした。
No.3478 XOR-Folding Primes
自力AC。
2,k,k+2という素数の三数がたくさなあり、その間を行き来するしかない。
素数を列挙した後、行き先を考えてDP→行列累乗で解ける。
Mまでにkが含まれるがk+2が含まれない場合、2→kみたいな行き方がありうると思ってしばらく悩んでしまった。このときは、P_iがk+2になるので、ありえないのですね。
0 件のコメント:
コメントを投稿