問題 Editorial 問題 あるグラフに対して頂点集合Sがk-stableであるとは、S中のそれぞれの頂点に対して、隣接する頂点の中でSに含まれる頂点の数がk個以下であるものをいう。 木graphが与えられる。i∈[0..|graph|-1]のそれぞれでi-stable setの数をmod 11290…

問題 Editorial 問題 無向重み付きグラフで以下の条件を満たすものgraphが与えられる： それぞれの頂点に対して、たかだか1つの単純閉路に含まれる それぞれの頂点v,uに対して、vからuへのsimple pathはたかだか1つ 頂点start,finishと正整数kが与えられる。…

問題 Editorial 問題 lucky numberとは、それを10進数で表記したときに4と7しか現れない正整数である。 整数nが与えられる。nを複数のlucky numberの総和で表す。lucky numberの数を最小化したい。そのような解のうち、辞書順最小のlucky numberの列を求めよ…

問題 Editorial 問題 '0'〜'9'からなる文字列digitsが与えられる。 この文字列をいくつかに分割し、それぞれを整数として読む(leading zeroは許可され、単に無視される)。ただし、列はstrictly increasingでなければならない。 このような列の中で、最後の整…

実況風 Coding Easy (250) とりあえずkiwiとgrapeのオフセットを全探索。 さて、ループ内では最小のところをどうにか高速に求めなければいけないわけだが… なんていうか、なんとなくなのだけれども、 xとyの最小の差は(±xとyのオフセット差 mod gcd(x, y)) …

問題 Editorial 問題 ある文字列のサブシークエンスとは、その文字列から任意の個数の文字を消したものである(連続している必要はない)。 3つの文字列a,b,cが与えられる。この3つの文字列に共通する空でないサブシークエンスの数(同じ文字列は重複して数えな…

問題 Editorial 問題 箱を2*2*heightに積む。 それぞれの箱は独立に、0.5の確率でダイナマイトが入っていて、そうでなければ空である。 「ダイナマイトクラスター」とはダイナマイトの入った箱の集合で、連結なものである(面でのみ接しているとみなす)。 サ…

問題 Editorial 問題 digits つの数字が入る所がある。今入っている数字はdigitsで与えられる。'_'の所は空であることを表す。 '_'の数だけ独立にランダムに順番に数字が選ばれる。 1つの数字が選ばれた時、次の数字が選ばれる前に、どこに数字を入れるかを…

問題 Editorial 問題 辞書dictが与えられる。 この辞書dictに含まれる単語を使ってしりとりをする。 ただし、同じ単語を複数使っても良い。 しりとりをして文字列を作ることが出来る。例えば"abc"と"cd"と"efgh"でしりとりすると"abcdefgh"という文字列にな…

問題 Editorial 問題 数列sequenceが与えられる。 「どれかを1増加させる」「どれかを1減少させる」という操作ができる。なお、マイナスにすることもできる。 最低K個の相違なる数を含ませるようにするとき、操作回数を最小化せよ 1 1 1 解答 Editorialを見…

問題 Editorial 問題 画像が上手く表現できないので略 解答 (交差点の(x * y * (真ん中, 四隅)))でDPするだけ。 (width コメント これは一瞬で解けるべき コード #include <string> #include <algorithm> #include <cstring> #include <complex> #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i</complex></cstring></algorithm></string>…

問題 Editorial 問題 Nつに分割されたパイがある。Nは3の倍数である。そのそれぞれの部分の面積piecesが与えられる。 これを自分と相手で交互に食べ、自分が食べる面積を最大化したい。 自分は、任意の部分を1つ選び、それを食べることができる。 次に、相手…

問題 Editorial 問題 複数行コメントを削除したい。それはネストできる。 複数行コメント"MLC"は以下の構文で定義される: MLC := "/*" <Nester> "*/" Nester := ("/*"も"*/"も含まない文字列) | <Nester> <MLC> <Nester>プログラムlinesがvectorで与えられる。これは各行を表していて、文</nester></mlc></nester></nester>…

問題 Editorial 問題 "Antichess"と呼ばれるゲームをする。 このゲームの目的は自分の駒を全て取られることである。 また、取れる駒があるならそのどれかを必ず取らなければならない。 今、white(自分, 先手)はポーンが何個かだけが残っていて、black(相手, …

問題 Editorial 問題 重さweightと許容重量capacityが設定された箱がNつある。 箱は他の箱の上にいくつでも積み上げられるが、どの箱も上に乗っている箱の重量の総和が許容重量以下でなければいけない。 積み上げられる最大個数を求めよ 1 1 1 解答 Editoria…

問題 Editorial 問題 3文字のアルファベット大文字が書かれたカードが何枚かある(cards)。 隣接する3つのカードの左右を選び、それらに共通する文字が2つ以上あるならば真ん中のカードを消すことができる。 カードを消せる最大枚数を求めよ 2 解答 Editorial…

問題 Editorial 問題 0〜99のマスがあるボードで複数人のプレイヤーでゲームをする。 各プレイヤーiは最初にplayers[i]のマスに居る。 各プレイヤーは各ターン、6面のサイコロを2つふり、出た目の合計だけ進む。このとき、99のマスに止まったりそこを通過し…

問題 Editorial 問題 サイズamountの数値のmultisetであって、総和がnで、全ての要素がminInComp以上で、全ての要素の最大と最小の差がminDif以下であるようなものの場合の数を求めよ 5 1 解答 Editorialを参考にした。あまりよくわかっていない。 DP。 まず…

問題 Editorial 問題 略 解答 (ターン * 残り時間 * スコア)でゲームDPするだけ コード #include <vector> #include <cstring> #define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i)) #define mset(m,v) memset(m,v,sizeof(m)) using namespace std; typedef vector<int> </int></cstring></vector>…

問題 Editorial 問題 輪になったネックレスがある。 ネックレスの各宝石の価値gemsが与えられる。 このネックレスをn回カットしてnつに分けたい。 カット後の各部分は1つ以上の宝石が含まれていなければいけない。 カット後の各部分の価値の総和の(最大-最小…

問題 Editorial 問題 6*7の盤面での"Connect Four"の局面が与えられる。 その局面に到達することが可能かかどうか、もし到達可能なら次はどのプレイヤーか、もしくはどのプレイヤーが既に勝っているか、あるいはもう打つ手はない(引き分け)か、を返せ 解答 …

問題 Editorial 問題 width*heightの長方形の紙がある。 ここから与えられたパターンpatternを何枚か切り取りたい。 パターンは90°刻みで回転してもいいが、反転してはいけない。 最大で何枚切り取れるかを求めよ 1 1 解答 左上が紙の半分に収まる切り方を全…

問題 Editorial 問題 商品がいくつかある。 商品にはそれぞれ"pointValue"と値段がある。 ポイントをその商品のpointValueだけ使ってその商品を無料で買うことができる。 また、半額ポイントというものもあって、それを1つ使って1つの商品を半額で買える。 …

問題 Editorial 問題 まず最初にランダムな単語がwordsの中から選ばれる。 最初はその単語のそれぞれの文字は隠されている。 各ターン、プレイヤーは文字を一文字言うことができる。最初に選ばれた単語の中にその文字があるなら、その部分がわかり、もう一度…

問題 Editorial 問題 今位置0に荷物がNつある。 この荷物たちをそれぞれ指定された位置boxesに移動したい。 移動するのに2つの方法がある。 一つ目がテレポート。これは複数の荷物をまとめて、任意の位置へ移動できる。ただし1回に1つの位置にしか移動できな…

問題 Editorial 問題 □□ □という形のブロックが無限にある。ブロックは自由に(90度単位で)回転できる。 length*widthの長方形にぴったり詰め込みたい(空白の部分があってはいけない)。 その「場合の数」を答えよ。ただし、対称の形でも別に数える 1 1 返り値…

http://apps.topcoder.com/stat?c=problem_statement&pm=10782&rd=14245 解答 この中の時間を基準に考えたら、時間の分岐が木になることがわかった。分岐がタイムトラベルポイントで、葉が訪れる街。 その木を左右に分割して探索していく。 この解法はO(n^5)…

http://apps.topcoder.com/stat?c=problem_statement&pm=11484&rd=14536 問題 0〜511の数値が書かれたカードが何枚か(1 値を記録できるメモリがあって、最初は0である。 プレイヤー2人がいて、交互にカードの中から一枚選び、そのカードの数値とメモリの値を…

DPは最終的な評価のみが要素になるわけじゃない。 最小化したかったりしたいものが有ればそれがDPになる。 逆に、最終的な評価などをインデックスにできる。 最後には全部とかを舐めて、Validであるインデックスのmaxを取ったりすれば良い SRM 451 DIV1 Medi…

http://apps.topcoder.com/stat?c=problem_statement&pm=11704&rd=14729 問題 命令列が与えられる "right X", "left X" (X: nat, X 右・左にX度回転する。 "forward X", "backward X" (X: nat, 1 現在の方向に対して前・後にX進む。これらの命令を入れ替える…