問題 疲れた 解法 そのまんま class RollingDiceDivTwo { public: int minimumFaces(vector<string> r) { int n = r[0].size(), mx[55] = {}; each(i,r) { sort(all(i)); rep(j,n) chmax(mx[j], i[j]-'0'); } return accumulate(mx, mx+n, 0); } };</string>

問題 会社がn社あり、i番目の収入はr[i]である 2個以上の会社を併合してできた会社の収入はそれらの会社の元の収入の平均になる 最後に1社だけ残るまでうまく併合していったときにできる会社の収入の最大値を求めよ 解法 収入の昇順にソートし、先頭の2社を…

問題 gcdがgでlcmがlとなるような2つの自然数(a,b)の組み合わせのうちa+bの最小値を求めよ ただしそういう組み合わせが存在しない場合は-1を返す1 解法 gcd=gということはaもbもgの倍数であることは確定する a=gx, b=gy (xとyは互いに素)とおくと gl = ab = …

問題 n個のマスがあり、いくつかのマスにチェッカーが置かれてある 各チェッカーに対しては ・1マス右に動かす (右のマスにチェッカーが置かれていない場合のみ) ・3マス右に動かす (右2マスにチェッカーが置かれていてかつ3マス先にはチェッカーが置かれて…

問題 星がn個あり、i個目の星の重さはw[i]である 「両端以外の任意の星を1つ選んで消し、その左右にある星の重みの積をスコアに加える」という操作を可能な限り繰り返す 最終的なスコアの最大値を求めよ3 1 解法 dp[l][r]: 区間[l,r]における問題の答え とし…

コーナーケース系のやつ 問題 チェーンがn個あり、i番目はs[i]である 各チェーンは '0' 〜 '9' の数字と '.' のみからなる3文字の文字列である このチェーンを任意の順番で1列に繋ぎ、数字のみからなる連続な部分列を取り出し、数字の和をスコアとする スコ…

問題 n曲からp曲選んで、以下の条件を全て満たすようなプレイリストを作りたい ① n曲全てを最低1個ずつ含む ② 同じ曲2つの間には異なる曲がm曲以上は挟まっている 何通りのプレイリストが作れるか1 0 n 解法 dp[i][j]: i曲あり、n曲のうちj曲を使ったプレイ…

問題 GogoくんがJohnにケーキが乗った皿とケーキカッターt(どちらも長方形)を渡した 皿は最初全マスにケーキが詰まっていて、皿にカッターを乗せて押すと、t[i][j]='.'のマスからはケーキが取り除かれ、t[i][j]='X'のマスは何も起こらない ただし ① カッター…

問題 王様の名前がn個与えられ、i番目の名前はs[i]である これを昇順にソートせよ ただし王様の名前は「(名前) (番号)」という構成になっていて、番号はアルファベット順ではなく数字順に並べる必要がある (例えば "Louis IX" と "Louis VIII" では文字列自…

問題 長さn(:偶数)で 'o' と 'x' のみからなる文字列sが与えられ、これの各文字を赤か青で塗る 赤で塗った文字列と青で塗った文字列が同じになるような塗り方が何通りあるか求めよ2 解法 半分全列挙前半の赤い部分をx、青い部分をyとする まずxとyの最長共通…

問題 うなぎがn匹あり、i匹目の長さはl[i]である c回までうなぎを切って長さ10のうなぎをなるべく多く作りたい 最大で何本作れるか1 1 1 解法 長さ10のうなぎは基本的には単純に1回切るごとに1本作れる 各うなぎからは最大でc[i]/10個まで作れる ただし長さc…

問題 h行w列で各要素が '0' か '1' か '?' のみからなる行列が2つ与えられる(それぞれhs, wsとする) これらの行列の '?' を0か1に書き換えて同じ行列にするとき、辞書順最小のものを求めよ1 2つの行列を一致させる方法が少なくとも1つは存在することが保証さ…