問題 0〜9,?によって構成されるN文字の文字列が与えられる。 ニコニコ文字列を2525...5のように「25」が連続した文字列とすると、上記の文字列からニコニコ文字列を取り出す方法がX通り以上だったことがわかっている。 このとき、元の文字列として考えられる…

http://d.hatena.ne.jp/phyllo_algo/20150215/1423985061Codeforces 514のD問題をかなり微妙な解法で通ってしまっていたけど、テストケースが35個ぐらいでそんなに悪意のあるケースがないためたまたま通ってしまっているようにも思われる。 http://kmjp.hate…

問題 無限に頂点がある根付きn分木が与えられる。 ある親頂点について、子頂点はn個あるが、それぞれ左からd[i]の重みになっている。 今、「根から頂点jまでの距離=根から頂点までの最短ルートの重みの和」とする。 距離xが与えられるので、距離がx以下であ…

問題 N台のロボットが1列に並べてあり、各ロボットはM種類の精密機械で構成されている。 各精密機械は何個か積まれており、ロボットiのj番目の精密機械はk個(a[i][j]=k)という情報が与えられる。 今、特殊な兵器によって、1回につき、すべてのロボットについ…

問題 a,b,cの3文字からなる、n個の文字列が与えられる。 次に、a,b,cの3文字からなる、m個の文字列が一つずつ与えられたとき、n個の文字列で以下の条件を満たす文字列がある場合YES、なければNOを返す。 ・同じ長さの文字列である ・ちょうど1つの文字が異な…

問題 K個のドーナツをN個の箱に詰めたい。箱は1つのドーナツをいれることができる。 箱のサイズが小さい箱があれば、大きい箱の中に入れる、ような入れ子にできるが、サイズの差分だけの緩衝剤を入れる必要がある。 必要な緩衝剤の合計の最小値を求める。 ま…

問題 N個の数字が与えられ、N-1個の数字の間には＋または-がはいり、その計算結果がN番目の数字になるような計算を考える。 前方から＋または-で計算して、負の数または20を超える途中計算になるような計算が許されない場合、何通りの計算方法があるか？を答…

問題 n段の階段を、各段で1〜3段のどれかを選んで上っていくことができる。 階段を上るパターンを考えるとき、1日10通りの方法で上ることができる場合、何年かかるか？ 考え方 dp[i]:=i段まで上ったときのパターン数 とすると、このパターン数はdp[i+1]とdp[…

http://judge.u-aizu.ac.jp/onlinejudge/topic.jsp?cid=DPL とりあえず、典型DPと呼ばれるであろう問題を一通り解く。 考えが違っていた部分をメモ。 Combinatorial A. Coin Changing Problem dp[i][j]と置くとき、i-1からi方向しか考えない場合が多かったけ…

問題 牛がN頭ならんでおり、各牛は1〜Kまでの番号が付けられている。 各牛の並びが与えられるので、先頭から適当に牛を選んでその番号を使って作ることができるの部分列をK+1進数の数字とみなした場合、作ることができない数字のケタ数を返す。N K 考え方 あ…

しばらくDPの問題を解きまくってDP脳になるために練習問題を解いていきたい。 @tatanaideyoさんに教えてもらった。一通り解いていきたい。 AOJ DP library http://judge.u-aizu.ac.jp/onlinejudge/topic.jsp?cid=DPL kyuridenamidaさんのまとめ http://d.hat…

問題 女子N人、男子M人いて、ここから女子P人、男子Q人だけ選ばれてチョコを渡すことが許される。 前もって、ある女子からある男子へプレゼンを渡したときの幸福度の情報が与えられる。 選ばれた男女の幸福度の合計値の最大値を答える。N,M P 考え方 女子に…

問題 無限に長い一直線上に箱が並んでおり、-100のところに赤玉がR個、0のところに緑玉がG個、100のところに青玉がB個ある。 1回の操作で、一つの玉を左右どちらかに移すことができるが、同じ箱に違う色の玉をいれる状態を作ってはいけない。 すべての箱に玉…

問題 N*Nの正方形のタコ焼き器が与えられ、各マスごとにおいしさが決められている。 店員がQ人いて、P[i]マス以下の長方形のマスを使って焼くことができる。 店員ごとに焼きあがるタコ焼きのおいしさの合計値の最大値を答える。N Q,P 考え方 任意の長方形の…

問題 整数N,Kが与えられる。 次の条件を満たす文字列が作れる場合、そのような文字列の一つを返す。なければ空文字を返す。 ・文字長はN ・各文字はAまたはBのどちらか ・i 考え方 memo[i][j][k]:=文字長iで、Bをj個含み、(i,j)のペア数がk個になっている文…

問題 N人いて、a番の人よりb番の人の方が順位が高い、という情報がM個与えられる。 1番の人の考えられる最高順位は？ 考え方 ハッシュに1を入れておいて、aの情報にハッシュに入っている番号が該当すれば、bをハッシュに追加。 これで、ハッシュは1よりも順…

問題 N人とK席があり、各人は順番に以下のルールによって席に座る。 ・i番目の人はp[i]の確率で「空いていれば座る」、(1-p[i])の確率で「両隣に人がいなければ座る」 ・どちらも満たせない場合は、座らない 空いている席数の期待値を求める。 考え方 空いて…