atcoder.jp 問題概要 文字列TのABC数をT[i]=A, T[j] = B, T[k] = Cとできるi,j,k(i < j < k)の個数と定め,?にはA,B,Cのいずれかの文字で置換出来、そのような文字列全てのABC数の和を求めよ。 制約 3 <= |S| <= 1e5 Sは'A','B','C','?'で構成される 方針・所…

atcoder.jp 問題概要 N人の男性、N人の女性がいる。それぞれ1~Nの番号が振られ、男性iと女性jの相性がいい1(a_i,j = 1)か悪い(a_i,j = 0)かはわかっている。N組の相性が良いペアを作る方法は何通りか？1e9 + 7で割った余りを求めよ。 方針・所感 N <= 21なの…

atcoder.jp 問題概要 長さH+1の平行な縦棒がW本与えられる。この縦棒の1,2,...Hの高さに横線を引いてあみだくじを構成する。この時、横棒は 互いに端点を共有しない それぞれの横棒の２つの端点は同じ高さになければならない 横棒は隣り合う縦線を繋がなけれ…

atcoder.jp 問題概要 非負整数KとN個の非負整数列Aについて、0 <= X <= Kを満たす整数Xに対するf(X) =(X^A_1) + (X^A_2) + ...の最大値を求めよ。 方針・所感 問題を見てちょちょっとサンプルをいじってみた時は各ビットについてXは0,1の少ない方の値をとる…

atcoder.jp 問題概要 ちょうどN本のマッチ棒を使って作れる整数の中で最大のものを求めよ。 方針・所感 この問題のポイントは「『ちょうど』N本のマッチ棒を作る」という言葉にどれほど敏感になれたかにあるようです。(私は貪欲法でやって最後の方を全探索し…