問題 D - XXOR 解法 2進数での各桁におけるは、各の中で桁が0である個数と1である個数の多い方をにかけることで求めることができる。 ここでネックとなるのが以下という条件だが、これは桁DPを考えれば良い。 つまり、上位の桁から、未満が確定している場合…

問題 AtCoder Beginner Contest 113 - AtCoder 解法 条件を満たす横線の引き方は他の高さの引き方に影響されないため、各高さ毎に、各縦棒にたどり着けるのは何通りかをDPで求めれば良い。 DPの遷移としては、区間ごとに横線があるような引き方が何通りある…

問題 No.1011 Infinite Stairs - yukicoder 解法 コンテスト中はPython/Ruby/PHP/Golang(Go)で上限のある重複組み合わせ - Qiitaを参考にして解いたのだが、解説ではDP+累積和で解いていたので、そちらの解法が上手くイメージができなかったこともあり、解き…

問題 No.1008 Bench Craftsman - yukicoder 解法 基本は解説の通りであるが、自分なりの説明を行う。 まず、ベンチの耐久度を固定すると、人が番目の区画に与える負荷は、である。 この負荷は正の場合、人毎に等差数列になるため、imos法を用いることで、番…

問題 E - Simple String Queries 解法 クエリの回数分、文字目から文字目まで調べるのでは間に合わない。 そこで、各アルファベット毎に、以上で初めて登場する位置を探索し、その位置が以下だった場合、種類を増やすことにする。 始めて登場する位置は、各…