問題概要 匹のうさぎがいる. 人の観客から, うさぎがうさぎよりも先にゴールしたという情報を得た. これら全ての情報に合致する着順が何通りあるかを求めよ. 制約 考察 bitDPをする. dp[何匹見たか][状態]としたとき, 各うさぎがすでにゴールしたかをbitの状…

問題概要 レベルLのバーガーを以下のように定義する. レベル0のバーガーは, 'P'. レベルLのバーガー(L>=1)は, 'B' + (レベルL-1のバーガー) + 'P' + (レベルL-1のバーガー) + 'B'. このとき, レベルNのバーガーの下からX層までに'P'は何個あるか求めよ. 制約…

問題概要 N!の約数のうち, 約数をちょうど75個持つものの個数を求めよ. 制約 1 <= N <= 100 考察 約数が75個ある整数を素因数分解したときどうなるか考えてみると, a2 * b4 * c4 a2 * b24 a4 * b14 a74 の4通り. とりあえずN!の素因数がそれぞれ何個ずつある…

問題概要 操作後に同一の文字が隣り合わないように, 両端以外からお互いに1文字ずつ取り除いていく. このような操作を行うことが出来なくなった方が負けとなる. 先手と後手のどっちが勝つかを出力せよ. 制約 の中に同一の文字が隣り合う箇所はない 考察 操作…

問題概要 東西に一列に並ぶN個の島と、それをつなぐN-1個の橋がある。 a_iとb_iの間を行き来できないようにしろ、という要望がM個寄せられた。 取り除かなければならない橋の本数の最小値を求めよ。 制約 2 <= N <= 105 1 <= M <= 105 1 <= a_i < b_i <= N …

問題概要 文字列sの中に、過半数が同じ文字となる2文字以上の部分文字列t(アンバランスな部分文字列)は存在するか判定せよ。tが存在するならその区間を、しないなら-1 -1を出力せよ。 制約 2<=|s|<=105 sは小文字のアルファベットのみからなる。 考察 tは2文…