問題 円錐状の帽子を2つ組み合わせて魔女の帽子を作りたい 上側用の帽子がn個、下側用の帽子がm個ある 上側用の帽子iと下側用の帽子jは以下の条件を満たすときのみ組み合わせて魔女の帽子にできる 1) 上側の帽子の頂点は下側の帽子の頂点より上にある 2) 下…

問題 木がn本あり、i本目の高さはa[i]である コストxの魔法を使うと各木の高さを0〜xだけ増やすか減らすことができる aを競技単調増加にするために使う必要のある魔法の最小コストを求めよ2 1 解法 二分探索 使う魔法のコストを決めたとき、各木の高さは単調…

問題 2本の塔があり、距離はwである これらの塔の高さは1本目が[1,x]、2本目が[1,y]の範囲から等確率で決まる 2本の塔それぞれの頂上同士をまっすぐなロープで繋ぐ ロープの長さの期待値を求めよ1 1 解法 1本目の塔の高さをkに固定する 更に2本目の高さがmに…

問題 長方形が2つ、それぞれ左下と右上の点の座標が与えられる これらの長方形の共通範囲が 長方形 or 線 or 点 or 存在しない のどれであるか判定せよ0 解法 初期値0の2次元配列で2つの長方形が占める領域をそれぞれ全部+1すると、重なってる部分は2になる …

問題 「xのkleofas tail」とは、1個目の要素がxで、i(>2)個目の要素が i-1個目の要素=yが偶数のとき) y/2 yが奇数のとき) y-1 であるような長さ無限の数列である a 0 0 解法 kからスタートして逆操作をしていく kが偶数のときはk*2かk+1へ、奇数のときはk*2…

ちょっと面白かった 540台はなかなか解き応えのある問題が多い 問題 以下の条件を満たす文字列を作れ 1) 長さnで、アルファベット26文字の最初のn文字を1文字ずつ使っている 2) 転倒数がk以上 3) 辞書順でs以上 4) これらの条件を満たす中で辞書順最小 解法 …

問題 長さkの板が無限にある これらを切ったりくっつけたりして長さLの板をn枚作りたい 長さkの板を必要最小限の枚数だけ使うとき、最低何回板を切る必要があるか求めよ1 解法 貪欲 長さkの板を切って余った板を寄せ集めてちょうど長さLにできる場合はコスト…

自力で解けなかった 問題 n人の候補者がいる選挙が行われ、i人目の得票率は四捨五入するとp[i]パーセントだったらしい しかしこの情報が嘘である可能性がある この得票率になるような投票人数と投票の仕方が存在する場合は投票人数の最小値を、存在しない場…

問題 L xor L+1 xor L+2 xor ... xor r を求めよ1 解法 実験すると↓のコードのような法則があることがわかる class EllysXors { public: ll x(ll n) { if (n%4==0) return n; if (n%4==1) return 1; if (n%4==2) return n+1; return 0; } ll getXor(ll l, ll…

問題 x*yのグリッド上の3点a,b,cの選び方で、(ab間の距離)+(bc間の距離)+(ca間の距離)がmn以上mx以下になるようなものは何通りあるか ただしa,b,cは全てx座標もy座標も異なる必要がある3 1 解法 (ab間の距離)+(bc間の距離)+(ca間の距離) ってのは、abcを内側…

問題 n匹のアリがいて、i匹目の座標は (x[i], y[i]) である i匹目のアリはd[i]方向に毎秒1だけ進み、2匹以上のアリがどこかでぶつかるとそれらは全て消える いつまでも消えないアリは何匹いるか求めよ1 |x[i], y[i]| 解法 座標を2倍すればぶつかる場所が必ず…

問題 長さn+1で各要素が自然数であるような数列aと長さnの文字列opがあった opの各文字は '+' か '-' である op[i] = '+' のとき) b[i] = a[i]+a[i+1] op[i] = '-' のとき) b[i] = a[i]-a[i+1] という風にして作った長さnの数列bとopが与えられる 元の数列a…

問題 石を無限に持っていて、9001個以上の石を箱に詰めたい n個の箱があり、i番目の箱にはx[i]個以上y[i]個以下の石を詰めることができる 詰める石の個数が何通りあり得るか求めよ1 1 解法 2^15通り全列挙して使う箱の組み合わせを全部試す 使うと決めた箱た…

問題 自然数a, b, xが与えられる 任意の(p,q)に対して pa+qb = rx+sy を満たす(r,s)が存在するような(x,y)の組の個数を求めよ (ただしp, q, r, sは非負整数でyは自然数) 答えが無限に存在する場合は-1を返せ1 a ≠ b 解法 aもbもxの倍数の場合、yの値によらず…

問題 疲れた 解法 そのまんま 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つは存在することが保証さ…

問題 n頂点の木を自由に作る 次数がiの頂点1つにつきスコアにa[i]が加算される(1 スコアの最大値を求めよ2 0 解法 木だから次数1の頂点が2個は絶対に出来る 残りn-2個の頂点の次数は、各次数が1以上n-1以下 かつ 次数の総和が2n-4であれば任意の組み合わせが…

違う意味で教育的 キレた 問題 長さnの数列a = {A, A+1, A+2, ..., A+N}がある LittleElephantくんはこの各要素について何個かの桁を消す 消す桁は0個でも良いが完全に消すことはない また結果できる数が同じでも消す桁が違えば別の消し方として区別する (例…

問題 ボールをn個持っており、ボールiの色は左から順にs[i]である(s[i]は'R' か 'G' か 'B') これを左から順に空のテーブルに一列に置いていく ボールiを置くとき、 ボールの列の端に置く場合) 元のボールの列に含まれるボールの色の種類数をスコアに加える …

類題(前提知識) creep06.hatenablog.com 問題 長さnの順列a,bがあるとき、 magic(a,b) = max(a[1],b[1]) + max(a[2],b[2]) + ... + max(a[n],b[n]) と定義する magic(a,b)の値がk以上になるようなa,bの組み合わせの数を求めよ1 1 解法 How to deal with two …