問題(言い換え) n個の点が与えられ、i個目の座標は(x[i],y[i])である 事前に自然数mとm個の数値dを自由に決めることができる その後原点からスタートし、以下の操作をm回繰り返す i番目の操作: 上下左右どれかの方向にd[i]だけ移動する 各操作の方向は自由に…

問題 長さnの文字列sが与えられる 以下の条件を満たすn頂点の木が存在するか判定し、存在する場合は具体的に1つ構築せよ(条件) 1-basedで、 s[i]= '1' のとき) 木からある辺を1つ取り除くことでサイズiの連結成分が作れる s[i]= '0' のとき) 木からどのよう…

問題 疲れた 解法 そのまんま 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頂点の完全無向グラフがあり、そこからアリスはm本の辺を取り、残りの辺はボブに渡した 二人が持っているグラフそれぞれにおける長さ3の閉路(=triangleと呼ぶ)の個数の和を求めよ1 0 解法 各頂点を1個ずつ見ていき、その頂点に繋がっているn-1本の辺か…

問題 n人が順番に座布団を積んでいく i人目は自分の番が回ってきた時に既に積まれた座布団がa[i]枚以下である場合はちょうどb[i]枚の座布団を積む n人の並び順を工夫することによって最大で何人が座布団を積むことができるか1 0 1 解法 「うまく並べればn人…

問題 家が燃えている！ 家には品物がn個あり、i個目の品物は、運び出すのにはt[i]秒かかり、燃え始めてからd[i]秒後には完全に燃え尽きてしまい、価値はp[i]である 品物は1個ずつしか運べず、完全に燃え尽きた瞬間に品物の価値は無くなる (t[i]>=d[i]の品物…

違う意味で教育的 キレた 問題 長さ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 …

めちゃくちゃ教育的類題 creep06.hatenablog.com 問題 箱根駅伝のある中継所における「各チームの通過順位」と「前の中継所からの順位変動」が与えられる 具体的には、c[i]がこの中継所をi番目に通過したチームの前の中継所からの順位変動を表し、 c[i] = '-…

問題 https://beta.atcoder.jp/contests/k4pc/tasks/k4pc_e「n本の胡瓜があり、それぞれの重さはa[i]である これらの部分集合(空でも良い)のうち、重さの総和がw以下であるようなものの個数を求めよ 1 という問題について、答えがxになるような入力例を1つ作…

類題 creep06.hatenablog.com 問題 果物1、果物2、...、果物nの、それぞれの100%ジュースを混ぜて、ミックスジュースをvリットル作りたい 果物iの100%ジュースは1リットルパックがc[i]円で売られている ミックスジュースを作るための最小コストを求めよただ…

これは良い問題だ！✨類題 creep06.hatenablog.com 問題 n人のクラスで募金を計s円集めて寄付することにした 生徒は出席番号順に寄付金額を決めていく 生徒は皆見栄っ張りなので、出席番号が1つ前の生徒よりk円以上高い金額を寄付しないと気が済まない 不満な…

面白い問題！ 問題 英小文字のみからなる文字列sが与えられる これをいくつかの空でない部分文字列s[1], s[2], ..., s[n]へ分割したい 更に任意のs[i]について、「s[i]の文字列を並び替えて回文が得られる」という条件も満たしたい 条件が成り立つようにsを…

問題 0と1のみからなる文字列sが与えられる この文字列に対し、「"101"となっているところを"010"に書き換える」という操作を行うことができる 最大で何回操作を行えるか1 解法 操作を逆から見ると、最終状態の1は「もともと1だった」か「101に操作をして出…

問題 頂点数n、辺数mの無向グラフが与えられ、グラフの各頂点iにはコインがc[i]枚乗っている 各プレイヤーは交互に以下の操作を繰り返す 1) 頂点0以外で頂点0と連結な頂点を1つ選び、それをjとする 2) jに隣接する頂点のうち、jより頂点0に近い点を1つ選び、…

典型力と地力を上げたくてなんとなく docs.google.com を解いていってるんだけど、ビビるくらい良い問題も何個かあったからどんどん書いていきます 問題 (1,2,...,n)の順列として数列aが与えられる 以下の操作を10^5回まで行えるとき、数列を1,2,...,nに並び…

問題 家がx軸上の点0にあり、オフィスがdにある またx軸上にはn個のガソリンスタンドがあり、これらの座標はx1,x2,...,xnである 家からオフィスまで一直線に、燃料タンクの容量がfで、距離1移動するたびに燃料を1使うような車で移動する 途中でガソリンスタ…