2021-10-01から1ヶ月間の記事一覧

AtCoder Beginner Contest 224 B

https://atcoder.jp/contests/abc224/tasks/abc224_b問題文通りに書けば十分間に合いますが、 が成り立つと、 なので、 が成り立ちます。 これは、要するに長方形を2分割して、それぞれの領域で不等式成り立てば、元の長方形でも成り立つことを意味します。…

AtCoder Beginner Contest 222 E

https://atcoder.jp/contests/abc222/tasks/abc222_e最短経路が辺を通る回数をとすると、母関数を考えて、 このの係数を求めればよいです。と置いて、 として、と置けば、 なので、を計算しての係数を求めればよいです。同じの重複度をと書くと、 これを最初…

競プロ典型90問 002https://atcoder.jp/contests/typical90/tasks/typical90_bこれは、wikipedia:カタラン数ですね。格子状の経路の数え方に対応していて、右に一つ移動すると'('、上に一つ移動すると')'です。 単純に1歩ずつ進むだけでOKです。 def F(N): d…

競プロ典型90問 001

https://atcoder.jp/contests/typical90/tasks/typical90_a話題になっていた問題です。 少し考えれば、スコア以上が成り立つかは簡単に求められるので、二分探索するだけですね。これで十分速いです。以下は、PyPy2のコードです。 # coding: utf-8 # Yokan P…

AtCoder Beginner Contest 221 D

https://atcoder.jp/contests/abc221/tasks/abc221_d分割統治法で、区間の集まりを[(first, last, num)]で表して、それをマージする、というコードを書いたら意外と長いコードになってしまって、max1462msec。 解説を見ると、ああって感じで、書いてみたら実…