atcoder.jp 問題概要 N行N列のグリッドを色1~Cで塗り分け、(i,j)を最初c_i,jで塗っている。(i+j)%3 = (x + y)%3ならば(i,j)の色は同じ、そうでなければ異なるように塗り替える。X→Yの色に変えた時、そのマスに対して感じる違和感をD_x,yとする。この違和感の…

atcoder.jp 問題概要 N種類のケーキはそれぞれ綺麗さx、美味しさy、人気度zのパラメタを持つ。りんごさんはこのケーキをM個違う種類から選ぶことにした。この時、|xの和|+|yの和|+|zの和|の最大値を求めよ。 制約 1 <= N <= 1000 -1e10 <= x,y,z<= 1e10 方針…

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個の箱が左右一列に並んでいて、左からi番目の箱にはAi個のお菓子が入っている。連続した箱[l,r]からM人の子供に平等に配れるようにMの倍数個取り出したい時、l,rの選び方の総数を求めよ。 制約 1 <= N <= 1e5 1 <= M , Ai<= 1e9 方針…

atcoder.jp 問題概要 東西に伸びるN個の都市1,2,...Nについて、M本の列車が存在して、列車iは都市Li~Riの区間を走っている。この時、都市piからqiまでの間に完全に含まれる列車の本数が何本かという問いがQ個与えられるので質問それぞれに対して答えを求めよ…

atcoder.jp 問題概要 1,2,3の形をしたキャンドルがついたケーキがそれぞれX,Y,Z種類ある。それぞれのケーキには美味しさが割り振られている。1,2,3のついたキャンドルをそれぞれ一つずつ買う選び方で、3つのケーキの美味しさの合計を大きい順にK番目まで出力…

atcoder.jp 問題概要 縦 H 行横 W 列に区切られたマス目があり、上から i 番目、左から j 列目のマスをマス (i,j) と呼びます。 マス (i,j) には aij 枚のコインが置かれています。 あなたは以下の操作を何度でも行うことができます。 操作: まだ選んだこと…

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 問題概要 整数 N が与えられます。N! (=1×2×...×N) の約数のうち、七五数 は何個あるでしょうか？ ここで、七五数とは約数をちょうど 75 個持つ正の整数です。 方針・所感 約数の個数は「素因数分解して、それぞれの指数に1を足して、全部掛け合…

atcoder.jp 問題概要 とある世界では、今日はクリスマスです。 高羽氏のパーティで、彼は多次元バーガーを作ることにしました。レベル L バーガー (L は 0以上の整数) とは次のようなものです。 レベル 0 バーガーとは、パティ 1 枚である。 レベル L バーガ…

atcoder.jp 問題概要 N個の寿司について、それぞれパラメタ(ネタti, 美味しさdi)が設定されていて、ここからK個選んでscore = (美味しさdiの和+(ネタの種類x)^2)が最大となる時のscoreを求めよ。 方針・所感 並び替え可能で食べる優先順位が明らかに高いもの…

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

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